Teoria mnogości i jej metamatematyka

W dziedzinie podstaw teorii mnogości Mostowski badał zależności pomiędzy rozmaitymi formułami teoriomnogościowymi, w szczególności formami tzw. pewnika wyboru postulującego istnienie selektora dla rodzin zbiorów niepustych. W pierwszej połowie XX w. aksjomat ten budził kontrowersje ze względu na brak określenia konstruktywnych technik znajdowania selektora. (Dziś, w wieku XXI, na ogół nie jest już traktowany jako tak kontrowersyjny.) Istotnym problemem badawczym teorii mnogości, do mniej więcej roku 1970, były zależności pomiędzy różnymi formami aksjomatu wyboru. Aksjomat ten jest równoważny następującej własności zbiorów: każdy zbiór może być dobrze uporządkowany. Słabszą formą tego zdania jest „każdy zbiór może być uporządkowany liniowo”. Mostowski wykazał, że ta druga forma nie implikuje pierwszej^[4], czyli jest istotnie słabsza. Dowód Mostowskiego, opierający się na wcześniejszych propozycjach B. Russela i – szczególnie – A. Fraenkla, doprowadził do stworzenia metody nazywanej obecnie metodą Fraenkla i Mostowskiego. Metoda ta zakłada istnienie indywiduów, tj. obiektów nieposiadających elementów, ale nie będących zbiorem pustym. Dziś powszechnie przyjmowana teoria mnogości, zazwyczaj oznaczana ZFC (aksjomatyka Zermela i Fraenkla z pewnikiem wyboru), nie dopuszcza istnienia indywiduów. Wyniki uzyskane metodami Fraenkla i Mostowskiego zostały odtworzone w latach 60. i 70. XX wieku przy użyciu metody wymuszania (forcingu) wprowadzonej przez P.J. Cohena we wczesnych latach 60. Mostowski poświęcił teorii wymuszania swą książkę^[5]. Wykazał też, że struktury relacyjne postaci ${\displaystyle \langle A,E\rangle ,}$ gdzie ${\displaystyle E}$ jest relacją ufundowaną (tj. nieposiadającą ciągów nieskończonych zstępujących), są izomorficzne ze strukturami postaci ${\displaystyle \langle S,\in \rangle ,}$ gdzie ${\displaystyle S}$ jest zbiorem przechodnim. Strukturę ${\displaystyle \langle S,\in \rangle }$ nazywa się często kolapsem Mostowskiego.

Teoria modeli

Mostowski był jednym z twórców teorii modeli (zdefiniowanej jako poddziedzina podstaw matematyki przez A. Tarskiego). Mostowski wprowadził szereg ważnych technik teorii modeli. Najważniejszą z tych technik jest metoda „elementów nieodróżnialnych”, wprowadzona wspólnie z A. Ehrenfeuchtem. Autorzy pokazują, że teorie mające modele nieskończone posiadają modele z dowolnie dużymi zbiorami elementów nieodróżnialnych^[6]. Jako skutek tego wyniku teorie takie mają modele posiadające duże grupy automorfizmów. Metoda elementów nieodróżnialnych jest po dziś dzień jedną z podstawowych technik teorii modeli. Inne badania Mostowskiego w teorii modeli dotyczyły zależności zbioru zdań prawdziwych w produkcie kartezjańskim struktur ${\displaystyle {\mathcal {A}}}$ i ${\displaystyle {\mathcal {B}},}$ ${\displaystyle {\mathcal {A}}\times {\mathcal {B}}}$ od zbiorów zdań prawdziwych w ${\displaystyle {\mathcal {A}}}$ i zdań prawdziwych w ${\displaystyle {\mathcal {B}}}$^[7]. Dalsze badania teorio-modelowe Mostowskiego dotyczyły topologicznych własności przestrzeni złożonych z modeli, z topologią generowaną poprzez zbiory struktur spełniających zadaną formułę.

Kwantyfikatory uogólnione

Mostowski wprowadził pojęcie uogólnionego kwantyfikatora^[8]. Przykładem takiego kwantyfikatora jest kwantyfikator „istnieje nieskończenie wiele obiektów ${\displaystyle x,}$ takich że ${\displaystyle \varphi }$”. Innymi słowy formuła ${\displaystyle Qx\varphi }$ prawdziwa jest w strukturze ${\displaystyle {\mathcal {A}},}$ jeśli ${\displaystyle \varphi (x)}$ spełnione jest w strukturze ${\displaystyle {\mathcal {A}}}$ przez nieskończenie wiele ${\displaystyle a.}$ Kwantyfikator ten (i inne znalezione później przez innych badaczy) znalazł istotne zastosowania w badaniach podstaw informatyki. Pojęcie kwantyfikatora uogólnionego zostało następnie rozszerzone przez Pera Lindströma, co doprowadziło do zdefiniowania pojęcia abstrakcyjnej logiki. Kwantyfikatory podlegające definicji podanej przez Andrzeja Mostowskiego są często nazywane „kwantyfikatorami Mostowskiego”.

Hierarchie zbiorów liczb naturalnych

Definiowalne podzbiory zbioru liczb naturalnych i ogólniej iloczynu kartezjańskiego ${\displaystyle N^{k}}$ mogą być klasyfikowane ze względu na postać definicji. Ograniczając się do definicji w postaci normalnej (ang. prenex normal form), można klasyfikować zbiory ze względu na liczbę przemian kwantyfikatorów i pierwszy kwantyfikator w preneksie. Tak więc zbiory klasy ${\displaystyle \Sigma _{1}}$ mają definicję posiadającą preneks złożony z kwantyfikatorów egzystencjalnych, zbiory klasy ${\displaystyle \Pi _{1}}$ to uzupełnienia zbiorów klasy ${\displaystyle \Sigma _{1},}$ dalej zaś indukcyjnie – zbiory klasy ${\displaystyle \Sigma _{n+1}}$ to rzuty zbiorów klasy ${\displaystyle \Pi _{n},}$ zaś zbiory klasy ${\displaystyle \Pi _{n+1}}$ to uzupełnienia zbiorów klasy ${\displaystyle \Sigma _{n+1}.}$ Mostowski wykazał, że wszystkie te klasy są różne, że każda z tych klas posiada relację uniwersalną i wiele innych własności^[9]. Podobne wyniki i w tym samym czasie uzyskał matematyk amerykański S. Kleene.

Hierarchia opisana powyżej nazywana jest zazwyczaj hierarchią Kleene i Mostowskiego. Hierarchię tę można rozszerzyć w pozaskończoność. Uzyskuje się w ten sposób hierarchię zbiorów hiperarytmetycznych nazywaną w literaturze hierarchią Davisa i Mostowskiego.

Metamatematyka arytmetyki Peana

Rozwijając badania K. Gödla Mostowski studiował modele arytmetyki Peana. Jedną z konsekwencji twierdzenia o niezupełności aksjomatyzowalnych rozszerzeń arytmetyki Peana jest to, że zbiór numerów Gödla konsekwencji arytmetyki Peana jest klasy ${\displaystyle \Sigma _{1},}$ ale nie jest obliczalny. Mostowski studiował zbiory zdań prawdziwych w definiowalnych modelach arytmetyki Peana. Mostowski studiował, szczególnie w latach 40. XX wieku, szereg zagadnień związanych z twierdzeniem Gödla o niezupełności i poświęcił tej dziedzinie monografię^[10], która była przez wiele lat klasycznym wprowadzeniem do problematyki niezupełności.

Metamatematyka arytmetyki II rzędu

Mostowski zajmował się intensywnie badaniami tzw. teorii II rzędu, tj. dwusortowych teorii ze zmiennymi dla obiektów pierwszego rzędu, a także zmiennych dla obiektów drugiego rzędu, podklas klasy obiektów pierwszego rzędu. Pierwszą z tych teorii jest arytmetyka II rzędu, zakładająca aksjomaty Peana dla obiektów pierwszego rzędu i schemat istnienia zbiorów (ang. comprehension) dla obiektów rzędu drugiego. Mostowski studiował modele teorii tego typu. W szczególności wraz z A. Grzegorczykiem i Cz. Ryll-Nardzewskim studiował modele arytmetyki II rzędu, których liczby naturalne są uporządkowane w typ ${\displaystyle \omega }$ (tzw. ${\displaystyle \omega }$ – modele arytmetyki II rzędu)^[11]. Mostowski rozważał też mniejsze rodziny takich modeli, na przykład zachowujące pojęcie dobrego porządku (tzw. ${\displaystyle \beta }$-modele). Mostowski studiował również analogiczną konstrukcję dla teorii zbiorów i klas (zazwyczaj nazywaną teorią klas Kelleya i Morse’a), uzyskując wiele analogicznych wyników.

W 1966 otrzymał nagrodę państwową I stopnia^[12]. W 2024 Rada Warszawy nadała jednej z ulic w dzielnicy Mokotów nazwę ul. Andrzeja Mostowskiego^[13].