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 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 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$ przez

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

Łatwo można sprawdzić, że $\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}$ naastępująco:

$([\eta_1]_{\equiv},[\eta_2]_{\equiv},\ldots,[\eta_n]_{\equiv})\in R^{\mathbb M}$ wtedy i tylko wtedy gdy ($\eta_1,\ldots,\eta_n\in N$ oraz) $\{i\in I: (\eta_1(i),\eta_2(i),\ldots,\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',\ldots,\eta_n,\eta_n'\in N$ są takie, że $\eta_k\equiv\eta_k'$ (dla $k=1,\ldots,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 łatwo wnioskujemy, ż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},\ldots,[\eta_n]_{\equiv}\in M$. Połóżmy $\eta(i)=f^{{\mathbb M}_i}(\eta_1(i),\ldots,\eta_n(i))$ dla $i\in I$ (tak więc $\eta\in N$). Określamy $f^{\mathbb M}([\eta_1]_{\equiv},\ldots,[\eta_n]_{\equiv})=[\eta]_{\equiv}$.

Tak jak wcześniej, zauważamy, że jeśli $\eta_1,\eta_1',\eta_2,\eta_2',\ldots,\eta_n,\eta_n'\in N$ są takie, że $\eta_k\equiv\eta_k'$ (dla $k=1,\ldots,n$), to $\{i\in I:f^{{\mathbb M}_i}(\eta_1(i),\ldots,\eta_n(i))=f^{{\mathbb M}_i}(\eta_1'(i),\ldots,\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,\ldots,x_n)$ jest formułą języka ${\mathcal L}(\tau)$ której zmienne wolne zawarte są wśród $x_1,\ldots,x_n$. Niech $\eta_1,\ldots,\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,\ldots,[\eta_n]_\equiv]$ wtedy i tylko wtedy gdy $\{i\in I:{\mathbb M}_i\models \varphi[\eta_1(i),\ldots,\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,\ldots,z_n]$ wtedy i tylko wtedy gdy ${\mathbb M}^I/F\models\varphi[g(z_1),\ldots,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 Peano (PA) czy też modeli analizy niestandardowej. W tym ostatnim kontekscie warto zacytować następujący wynik:
• Twierdzenie Rabina-Keslera: Niech τ 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 τ 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 Shelaha:

• 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.

Zobacz też

• analiza niestandardowa
• filtr (matematyka)
• struktura matematyczna