Mojżesz Presburger – niszczyciel kwantyfikatorów
Legitymacja studencka Mojżesza Presburgera (obecnie w zbiorach archiwum UW, domena publiczna) Mojżesz Presburger przyszedł na świat 27 grudnia 1904 roku w Warszawie, najprawdopodobniej w domu przy ulicy Muranowskiej 6. Jego ojciec, Abram Chaim Presburger, osierocił go w wieku dwóch lat i od tamtej pory był wychowywany jedynie przez matkę Jochwetę, z domu Aszenmil. Przyszły adept szkoły lwowsko-warszawskiej początkowo uczył się w domu. Otrzymał tam, jak sam napisał, wiedzę elementarną wystarczającą, aby w wieku lat dziewięciu wstąpić do ośmioklasowej Szkoły Handlowej w Warszawie, z oddziałami gimnazjalnymi na ulicy Prostej w Warszawie.
Mojżesz Presburger: kariera w dwudziestoleciu
Latem 1920 roku, trzy lata przed uzyskaniem przez Mojżesza Presburgera dyplomu otwierającego drogę na studia wyższe, do Warszawy zbliżały się oddziały Armii Czerwonej. Jako piętnastolatek Presburger nie mógł odbywać regularnej służby wojskowej, postanowił więc zgłosić się na ochotnika do Polskiego Białego Krzyża. Organizacja ta założona została przez Helenę Paderewską w proteście przeciwko brakowi zgody na powstanie polskiej filii Czerwonego Krzyża podczas I wojny światowej. Zajmowała się, poza pomocą rannym i potrzebującym, również działalnością kulturalną i krzewieniem postaw patriotycznych. Presburger służył w niej w czasie najbardziej newralgicznych walk wojny polsko-bolszewickiej, od lipca do października 1920 r.
Dyplom maturalny nasz bohater uzyskał 8 maja 1923 roku i powziął zamiar podjęcia studiów na Uniwersytecie Warszawskim. Co ciekawe, zgodnie ze świadectwem, jakie pozostawił, to wcale nie matematyka i filozofia, lecz fizyka i religia były jego najmocniejszymi stronami.
23 września 1923 roku Mojżesz Presburger złożył podanie o przyjęcie na studia. Interesującym go kierunkiem była matematyka, wykładana w ramach Wydziału Filozoficznego Uniwersytetu Warszawskiego. Podczas studiów uczęszczał na zajęcia takich gigantów polskiej matematyki jak: Wacław Sierpiński (prowadzący wykłady z analizy matematycznej), Samuel Dickstein (wyższa algebra), Jan Łukasiewicz (seminarium z logiki matematycznej), Stanisław Leśniewski (aksjomatyka) oraz Alfred Tarski (nauczanie algebry w szkołach). W roku 1930 ukończył studia i otrzymał tytuł magistra z wynikiem bardzo dobrym. Podstawą do uzyskania dyplomu była praca „Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt”, czyli „O zupełności pewnego systemu liczb całkowitych, w którym jedynym działaniem jest dodawanie”. Miał zresztą możliwość ogłoszenia wyników swoich badań na I Kongresie Matematyków Słowiańskich, który odbył się w Warszawie we wrześniu 1929 roku. Jego praca okazała się jedną z najbardziej rewolucyjnych w historii tej dziedziny i do tej pory należy do najważniejszych osiągnięć w logice matematycznej. Okazało się jednak, że nie była wystarczająco dobra dla Alfreda Tarskiego. Ten wybitny naukowiec autorytatywnie orzekł, że nie może ona być podstawą do rozpoczęcia studiów doktorskich.
Nakaz egzekucji komorniczej długu Mojżesza Presburgera wobec Uniwersytetu Warszawskiego (obecnie w zbiorach archiwum UW, domena publiczna) Presburger nie starał się o kontynuację kariery uniwersyteckiej, tylko rozpoczął pracę w towarzystwach ubezpieczeniowych (Zakładzie Ubezpieczeń Społecznych, Przyszłości i Europie), gdzie działał najprawdopodobniej aż do początku II wojny światowej. O jego dalszym życiu wiadomo niewiele. W 1931 roku wziął ślub z Rebeką Krejnes. Dwa lata później napisał, razem z Antonim Wanatowskim, pracę pod frapującym tytułem „O kalkulacji emerytalnej ubezpieczeń społecznych”. Niejasna jest sprawa nieuregulowanej należności za studia w kwocie 70 zł, którą mu zasądzono w 1939 roku. Mgłą tajemnicy jest również owiana śmierć Presburgera: najprawdopodobniej zginął w roku 1943 w jednym z obozów koncentracyjnych.
Arytmetyka Presburgera
Artykuł „Zagadnienia zupełności i rozstrzygalności pewnego systemu liczb całkowitych (...)”, który mógł otworzyć mu drzwi do kariery naukowej, nie był podobno wystarczająco dobry. Dlaczego? Zgodnie z zachowaną relacją ten jeden z częściej cytowanych artykułów poświęconych logice matematycznej nie zyskał profesorskiej aprobaty, ponieważ był… zbyt prosty i za krótki.
Pomimo tego braku przychylności Presburger był traktowany przez kadrę akademicką jako partner do dyskusji naukowych. Współpracował między innymi przy edytowaniu prac Kazimierza Ajdukiewicza i, wspomnianego już, Łukasiewicza.
Arytmetyka liczb całkowitych Presburgera jest teorią pierwszego rzędu z identycznością, sformalizowaną w języku − w którym występuje symbol dodawania: + oraz dwie stałe: zero 0 i jedność 1 − i scharakteryzowaną w następującymi aksjomatami specyficznymi: 1. a + (b + c) = (a + b) + c 2. a + 0 = a 3. Ǝb (a + b = c) 4. a + b = b + a 5. na = nb → a = b dla dowolnego naturalnego n większego bądź równego 1 6. Ǝb [nb = a/nb + 1 = a / …. /nb + (n − 1) 1 = a] dla dowolnego naturalnego n większego lub równego 1 7. na + 1 nie równa się 0 dla każdego naturalnego n > 1
W zapisie aksjomatów 5.−7. symbol „na” jest skrótem termu a+a+….a+a, w którym a występuje n razy.
Aksjomaty 1.−4. są aksjomatami grupy abelowej. Aksjomat 6 stwierdza, że albo a dzieli się przez n, albo w wyniku dzielenia a przez n otrzymujemy resztę równą 1 bądź 2… bądź resztę n – 1. Schemat 7. postuluje, żeby każdy element grupy miał rząd nieskończoności, tzn. by grupa była beztorsyjna.
Stosując metodę eliminacji kwantyfikatorów, Presburger udowodnił, że jego teoria jest zupełna i rozstrzygalna. Stąd wniosek, że zbiór twierdzeń teorii jest identyczny z zawartością (inaczej: teorią) dziedziny (Z + 1, 0), w której Z jest zbiorem liczb całkowitych.
Presburger dodaje również, że arytmetyka liczb całkowitych z dodawaniem +, zerem 0, jednością 1 oraz relacją większości > jest zupełna. Presburger nie podaje aksjomatów tej drugiej teorii. Jego wynik znaczy więc dokładnie to, że zawartość dziedziny (Z, +, 0, 1, >) jest rozstrzygalna. Uzupełnienie jest istotne, ponieważ dziś wiadomo już, że relacja większość > nie jest w (Z, +, 1, 0) definiowalna. Dodajmy też, że obie teorie nie są skończenie aksjomatyzowalne.
O tym, jak znaczący był wkład Presburgera w logikę matematyczną, świadczą dwa fakty. David Hilbert i Edward Bernays włączyli wyniki jego pracy do epokowego dzieła „Grundlagen der Mathematik”. Między innymi dlatego, że ta metoda eliminacji aksjomatów dobrze sprawdzała się zastosowana do dowodu niesprzeczności. Co więcej, koncepcje zawarte w pracy Presburgera używane są w tak skumulowanej dziedzinie rozważań logiczno-matematycznych, jaką jest teoria złożoności obliczeniowej. Istnieje jeszcze jeden ciekawy fakt na temat jego geniuszu. Amerykański matematyk Anil Nerode w dyskusjach poświęconych Presburgerowi długo nie dowierzał swoim rozmówcom, gdy ci mówili, że ten nigdy nie otrzymał stopnia doktora.
Bibliografia
- Mikołaj Bojańczyk, Mojżesz Presburger, [w:] Strona internetowa Mikołaja Bojańczyka, [dostęp: 17 czerwca 2012], <[http://www.mimuw.edu.pl/~bojan/]>.
- Jan Zygmunt, Mojzesz Presburger: Life and work, „History and Philosophy of Logic”, vol. 12 (1991), s. 211−223.
Redakcja: Michał Przeperski
Korekta: Bożena Pierga
