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^[1] można zinterpretować jako konstrukcję ultrapotęgi^[2]. Również konstrukcje rozważane przez Edwina Hewitta w 1948^[3] 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^[4].

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^[5]. W tym ostatnim kontekście warto zacytować następujący wynik:
Twierdzenie Rabina-Keslera^[6]^[7]: 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^[8]: 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^[9]^[10]:
- 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.

Przypisy

↑ Gödel, K.: Die Vollständigkeit der Axiome des logischen Funktionenkalküls. „Monatshefte f. Math”, 37 (1930), s. 349–360.
↑ Bell, J.L.; Slomson, A.B.: Models and ultraproducts: An introduction. North-Holland Publishing Co., Amsterdam-London, 1969, s. 259.
↑ Hewitt, E.: Rings of real-valued continuous functions. I. Transactions of the American Mathematical Society 64 (1948), s. 45–99.
↑ Łoś, J.: Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres. „Mathematical interpretation of formal systems”, North-Holland Publishing Co., Amsterdam, 1955, s. 98–113.
↑ Robinson, A.: Non-standard analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1996. ISBN 0-691-04490-2.
↑ Rabin, M.O.: Arithmetical extensions with prescribed cardinality. „Indag. Math.” 21 (1959), s. 439–446.
↑ Keisler, H.J.: Limit ultrapowers. Transactions of the American Mathematical Society 107 (1963), s. 382–408.
↑ Keisler, H.J.: Ultraproducts and elementary classes. „Indag. Math.” 23 (1961), s. 477–495.
↑ Shelah, Every two elementarily equivalent models have isomorphic ultrapowers -- Israel J Math 10 (1971) 224-233.
↑ Shelah, S.: Vive la différence. I. Nonisomorphism of ultrapowers of countable models. [w:] Set theory of the continuum (Berkeley, CA, 1989), Math. Sci. Res. Inst. Publ., 26. Springer, New York, 1992, s. 357–405.

[1] Gödel, K.: Die Vollständigkeit der Axiome des logischen Funktionenkalküls. „Monatshefte f. Math”, 37 (1930), s. 349–360.

[2] Bell, J.L.; Slomson, A.B.: Models and ultraproducts: An introduction. North-Holland Publishing Co., Amsterdam-London, 1969, s. 259.

[3] Hewitt, E.: Rings of real-valued continuous functions. I. Transactions of the American Mathematical Society 64 (1948), s. 45–99.

[4] Łoś, J.: Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres. „Mathematical interpretation of formal systems”, North-Holland Publishing Co., Amsterdam, 1955, s. 98–113.

[5] Robinson, A.: Non-standard analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1996. ISBN 0-691-04490-2.

[6] Rabin, M.O.: Arithmetical extensions with prescribed cardinality. „Indag. Math.” 21 (1959), s. 439–446.

[7] Keisler, H.J.: Limit ultrapowers. Transactions of the American Mathematical Society 107 (1963), s. 382–408.

[8] Keisler, H.J.: Ultraproducts and elementary classes. „Indag. Math.” 23 (1961), s. 477–495.

[9] Shelah, Every two elementarily equivalent models have isomorphic ultrapowers -- Israel J Math 10 (1971) 224-233.

[10] Shelah, S.: Vive la différence. I. Nonisomorphism of ultrapowers of countable models. [w:] Set theory of the continuum (Berkeley, CA, 1989), Math. Sci. Res. Inst. Publ., 26. Springer, New York, 1992, s. 357–405.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]