Ultraprodukt

Ultraprodukt – sposób budowania nowych modeli z danej rodziny modeli. Ultraprodukty są używane i badane w teorii modeli, teorii mnogości i algebrze. Szczególnym przypadkiem ultraproduktów są ultrapotęgi (w których używa się tylko jednego modelu wyjściowego).

Uwagi historyczne

Niektórzy matematycy twierdzą, że już dowód Kurta Gödla twierdzenia o zupełności rachunku kwantyfikatorów (logiki pierwszego rzędu) z 1930 roku można zinterpretować jako konstrukcję ultrapotęgi. Również konstrukcje rozważane przez Edwina Hewitta w 1948 w związku z ciałami rzeczywiście domkniętymi są uznawane za prekursorów ultraproduktów.

Pierwsza systematyczna i ogólna prezentacja ultraproduktów jako narzędzia w teorii modeli była dana przez polskiego matematyka Jerzego Łosia w roku 1955.

Definicja

Niech $\tau$ będzie alfabetem języka pierwszego rzędu, czyli zbiorem symboli funkcyjnych i predykatów (symboli relacyjnych). Interpretację symbolu relacyjnego $R\in \tau$ w modelu $\mathbb {M}$ będziemy oznaczać przez $R^{\mathbb {M} }$ (tak więc $R^{\mathbb {M} }$ jest relacją $n$-arną na uniwersum $M$ modelu $\mathbb {M} ,$ gdzie $n$ jest arnością symbolu relacyjnego $R$). Podobnie, jeśli $f\in \tau$ jest $n$-argumentowym symbolem funkcyjnym, to jego interpretacja w modelu $\mathbb {M}$ będzie oznaczana przez $f^{\mathbb {M} }$ (tak więc, $f^{\mathbb {M} }$ jest funkcją z $M^{n}$ w $M$). Poniżej, każde użycie słowa model oznacza model języka pierwszego rzędu ${\mathcal {L}}(\tau )$ wyznaczonego przez alfabet $\tau .$

Załóżmy, że $I$ jest zbiorem nieskończonym oraz $F$ jest filtrem podzbiorów $I.$ Przypuśćmy też, że dla każdego $i\in I$ ustaliliśmy model $\mathbb {M} _{i}$ z uniwersum $M_{i}.$

Definiujemy produkt zredukowany

$\prod \limits _{i\in I}\mathbb {M} _{i}/F$

rodziny modeli $\{\mathbb {M} _{i}:i\in I\}$ w sposób następujący.

(a) Na produkcie kartezjańskim

$N=\prod \limits _{i\in I}M_{i}$

określamy relację dwuczłonową $\equiv$ warunkiem

$\eta \equiv \nu$ wtedy i tylko wtedy, gdy ($\eta ,\nu \in N$ oraz) $\{i\in I:\eta (i)=\nu (i)\}\in F$

Relacja $\equiv$ jest relacją równoważności. Niech $M=N/\equiv$ będzie zbiorem klas abstrakcji relacji $\equiv .$

(b) Jeśli $R\in \tau$ jest $n$-arnym symbolem relacyjnym, to określamy jego interpretację $R^{\mathbb {M} }$ następująco:

$([\eta _{1}]_{\equiv },[\eta _{2}]_{\equiv },\dots ,[\eta _{n}]_{\equiv })\in R^{\mathbb {M} }$ wtedy i tylko wtedy, gdy ($\eta _{1},\dots ,\eta _{n}\in N$ oraz) $\{i\in I:(\eta _{1}(i),\eta _{2}(i),\dots ,\eta _{n}(i))\in R^{\mathbb {M} _{i}}\}\in F.$

Należy zauważyć, że jeśli $\eta _{1},\eta _{1}',\eta _{2},\eta _{2}',\dots ,\eta _{n},\eta _{n}'\in N$ są takie, że $\eta _{k}\equiv \eta _{k}'$ (dla $k=1,\dots ,n$), to

$\{i\in I:\eta _{1}(i)=\eta _{1}'(i)\ \wedge \ \eta _{2}(i)=\eta _{2}'(i)\ \wedge \ \ldots \ \wedge \ \eta _{n}(i)=\eta _{n}'(i)\}\in F.$

Stąd wynika, że powyższa definicja relacji $R^{\mathbb {M} }$ jest poprawna, tzn. nie zależy od wyboru reprezentantów klas abstrakcji.

(c) Jeśli $f\in \tau$ jest $n$-arnym symbolem funkcyjnym, to określamy jego interpretację $f^{\mathbb {M} }$ następująco:

przypuśćmy, że $[\eta _{1}]_{\equiv },[\eta _{2}]_{\equiv },\dots ,[\eta _{n}]_{\equiv }\in M.$ Połóżmy $\eta (i)=f^{\mathbb {M} _{i}}(\eta _{1}(i),\dots ,\eta _{n}(i))$ dla $i\in I$ (tak więc $\eta \in N$). Określamy

$f^{\mathbb {M} }([\eta _{1}]_{\equiv },\dots ,[\eta _{n}]_{\equiv })=[\eta ]_{\equiv }.$

Tak jak wcześniej, zauważamy, że jeśli $\eta _{1},\eta _{1}',\eta _{2},\eta _{2}',\dots ,\eta _{n},\eta _{n}'\in N$ są takie, że $\eta _{k}\equiv \eta _{k}'$ (dla $k=1,\dots ,n$), to

$\{i\in I:f^{\mathbb {M} _{i}}(\eta _{1}(i),\dots ,\eta _{n}(i))=f^{\mathbb {M} _{i}}(\eta _{1}'(i),\dots ,\eta _{n}'(i))\}\in F,$

a więc powyższa definicja funkcji $f^{\mathbb {M} }$ jest poprawna, tzn. nie zależy od wyboru reprezentantów klas abstrakcji.

Produkt zredukowany

$\prod \limits _{i\in I}\mathbb {M} _{i}/F$

to model z uniwersum $M=N/\equiv$ w którym interpretacje symboli z alfabetu $\tau$ dane są przez opis w (b) i (c).

Jeśli $F$ jest ultrafiltrem (tzn. maksymalnym filtrem właściwym), to model

$\prod \limits _{i\in I}\mathbb {M} _{i}/F$

jest nazywany ultraproduktem rodziny modeli $\{\mathbb {M} _{i}:i\in I\}.$

Jeśli $F$ jest ultrafiltrem oraz $\mathbb {M} _{i}=\mathbb {M}$ dla wszystkich $i\in I$ (czyli wszystkie modele są identyczne), to model

$\prod \limits _{i\in I}\mathbb {M} _{i}/F=\prod \limits _{i\in I}\mathbb {M} /F$

jest nazywany ultrapotęgą modelu $\mathbb {M}$. W przypadku ultrapotęg modeli, często używamy notacji $\mathbb {M} ^{I}/F$ zamiast

$\prod \limits _{i\in I}\mathbb {M} /F.$

Przykładowe wyniki i zastosowania

• Twierdzenie Łosia:

Przypuśćmy, że $\tau$ jest alfabetem języka pierwszego rzędu, $F$ jest ultrafiltrem na zbiorze $I,$ $\mathbb {M} _{i}$ jest modelem języka ${\mathcal {L}}(\tau )$ (dla $i\in I$) oraz $\varphi (x_{1},\dots ,x_{n})$ jest formułą języka ${\mathcal {L}}(\tau )$ której zmienne wolne zawarte są wśród $x_{1},\dots ,x_{n}.$ Niech $\eta _{1},\dots ,\eta _{n}\in \prod \limits _{i\in I}M_{i}.$ Wówczas

$\prod \limits _{i\in I}\mathbb {M} _{i}/F\models \varphi [[\eta _{1}]_{\equiv },\dots ,[\eta _{n}]_{\equiv }]$ wtedy i tylko wtedy, gdy $\{i\in I:\mathbb {M} _{i}\models \varphi [\eta _{1}(i),\dots ,\eta _{n}(i)]\}\in F.$

• Założmy, że $\tau ,F,I$ są jak powyżej, $\mathbb {M}$ jest modelem języka ${\mathcal {L}}(\tau ).$ Dla $z\in M$ niech $\eta _{z}\in M^{I}$ będzie funkcją stałą daną przez $\eta _{z}(i)=z$ (dla $i\in I$) oraz niech $g(z)=[\eta _{z}]_{\equiv }\in M^{I}/\equiv .$ Wówczas funkcja $g$ jest zanurzeniem elementarnym modelu $\mathbb {M}$ w jego ultrapotęgę $\mathbb {M} ^{I}/F,$ tzn. $g:M\longrightarrow M^{I}/\equiv$ jest funkcją różnowartościową oraz

$\mathbb {M} \models \varphi [z_{1},\dots ,z_{n}]$ wtedy i tylko wtedy, gdy $\mathbb {M} ^{I}/F\models \varphi [g(z_{1}),\dots ,g(z_{n})].$

W szczególności, ultrapotęga $\mathbb {M} ^{I}/F$ jest elementarnie równoważna z $\mathbb {M}$ (tzn. te same zdania są spełnione w jednym modelu co i w drugim).

• Z twierdzenia Łosia łatwo wnioskujemy, że:
  • każdy ultraprodukt grup jest grupą,
  • ultraprodukt ciał jest ciałem, ultraprodukt ciał uporządkowanych jest ciałem uporządkowanym,
  • ultraprodukt algebr Boole’a jest algebrą Boole’a,
  • ultraprodukt porządków częściowych jest porządkiem częściowym, ultraprodukt porządków liniowych jest porządkiem liniowym.
• Ultraprodukt nieskończonych dobrych porządków jest dobrym porządkiem wtedy i tylko wtedy, gdy użyty ultrafiltr jest σ-zupełny. (Przypomnijmy, że istnienie niegłównych σ-zupełnych ultrafiltrów na zbiorze nieskończonym jest równoważne z istnieniem liczby mierzalnej.)
• Ultrapotęgi uniwersum teorii mnogości V przy użyciu zupełnych ultrafiltrów są używane w badaniach dużych liczb kardynalnych. Ultrapotęgi są też używane do konstrukcji niestandardowych modeli arytmetyki Peana (PA) czy też modeli analizy niestandardowej. W tym ostatnim kontekście warto zacytować następujący wynik:
• Twierdzenie Rabina-Keslera: Niech $\tau$ będzie przeliczalnym alfabetem. Załóżmy, że κ jest liczbą kardynalną, na której nie istnieją ultrafiltry σ-zupełne. Wówczas

każdy model z uniwersum mocy κ ma właściwe elementarne rozszerzenie do modelu z uniwersum mocy κ wtedy i tylko wtedy, gdy $\kappa ^{\aleph _{0}}=\kappa .$

Charakteryzacja elementarnie równoważnych modeli

Niech $\tau$ będzie przeliczalnym alfabetem. Poniżej, każde użycie słowa model oznacza model języka pierwszego rzędu ${\mathcal {L}}(\tau )$ wyznaczonego przez alfabet $\tau$.

• Twierdzenie Keislera o ultrapotęgach: Załóżmy GCH. Niech $\mathbb {M} _{0},$ $\mathbb {M} _{1}$ będą modelami o uniwersach mocy co najwyżej $\kappa ^{+}.$ Wówczas

$\mathbb {M} _{0}$ jest elementarnie równoważny z $\mathbb {M} _{1}$ wtedy i tylko wtedy, gdy

istnieją ultrafiltry $F,G$ na $\kappa$ takie że ultrapotęgi $(\mathbb {M} _{0})^{\kappa }/F$ i $(\mathbb {M} _{1})^{\kappa }/G$ są izomorficzne.

• Twierdzenia Szelacha:
  • Niech $\mathbb {M} _{0},$ $\mathbb {M} _{1}$ będą modelami o uniwersach mocy co najwyżej $\kappa .$ Wówczas

$\mathbb {M} _{0}$ jest elementarnie równoważny z $\mathbb {M} _{1}$ wtedy i tylko wtedy, gdy

istnieją ultrafiltry $F,G$ na $2^{\kappa }$ takie że ultrapotęgi $(\mathbb {M} _{0})^{2^{\kappa }}/F$ i $(\mathbb {M} _{1})^{2^{\kappa }}/G$ są izomorficzne.

W szczególności, dwa modele są elementarnie równoważne wtedy i tylko wtedy, gdy mają izomorficzne ultrapotęgi.

• • Twierdzenia Keislera nie można udowodnić tylko w systemie ZFC, bez założenia GCH, bo następujące zdanie jest niesprzeczne z ZFC:

Istnieją elementarnie równoważne przeliczalne grafy $G_{0},G_{1}$ takie, że żadne ich ultrapotęgi $(G_{0})^{\omega }/F_{0},$ $(G_{1})^{\omega }/F_{1}$ nie są izomorficzne.

Warto zauważyć, że dowód powyższego twierdzenia (w którym Shelah skonstruował odpowiednie pojęcie forsingu) okazał się być bardzo stymulujący dla późniejszego rozwoju teorii forsingu i teorii forsingów proper.