Ultraprodukt

Ultraprodukt – pojęcie stosowane w matematycznej teorii modeli; jest to pewien matematyczny sposób budowania nowych modeli z danej rodziny modeli. Ultraprodukty są szeroko 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 ${\displaystyle \tau }$ będzie alfabetem języka pierwszego rzędu, czyli zbiorem symboli funkcyjnych i predykatów (symboli relacyjnych). Interpretację symbolu relacyjnego ${\displaystyle R\in \tau }$ w modelu ${\displaystyle \mathbb {M} }$ będziemy oznaczać przez ${\displaystyle R^{\mathbb {M} }}$ (tak więc ${\displaystyle R^{\mathbb {M} }}$ jest relacją ${\displaystyle n}$-arną na uniwersum ${\displaystyle M}$ modelu ${\displaystyle \mathbb {M} ,}$ gdzie ${\displaystyle n}$ jest arnością symbolu relacyjnego ${\displaystyle R}$). Podobnie, jeśli ${\displaystyle f\in \tau }$ jest ${\displaystyle n}$-argumentowym symbolem funkcyjnym, to jego interpretacja w modelu ${\displaystyle \mathbb {M} }$ będzie oznaczana przez ${\displaystyle f^{\mathbb {M} }}$ (tak więc, ${\displaystyle f^{\mathbb {M} }}$ jest funkcją z ${\displaystyle M^{n}}$ w ${\displaystyle M}$). Poniżej, każde użycie słowa model oznacza model języka pierwszego rzędu ${\displaystyle {\mathcal {L}}(\tau )}$ wyznaczonego przez alfabet ${\displaystyle \tau .}$

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

Definiujemy produkt zredukowany

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

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

(a) Na produkcie kartezjańskim

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

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

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

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

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

${\displaystyle ([\eta _{1}]_{\equiv },[\eta _{2}]_{\equiv },\dots ,[\eta _{n}]_{\equiv })\in R^{\mathbb {M} }}$ wtedy i tylko wtedy, gdy (${\displaystyle \eta _{1},\dots ,\eta _{n}\in N}$ oraz) ${\displaystyle \{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 ${\displaystyle \eta _{1},\eta _{1}',\eta _{2},\eta _{2}',\dots ,\eta _{n},\eta _{n}'\in N}$ są takie, że ${\displaystyle \eta _{k}\equiv \eta _{k}'}$ (dla ${\displaystyle k=1,\dots ,n}$), to

${\displaystyle \{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 ${\displaystyle R^{\mathbb {M} }}$ jest poprawna, tzn. nie zależy od wyboru reprezentantów klas abstrakcji.

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

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

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

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

${\displaystyle \{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 ${\displaystyle f^{\mathbb {M} }}$ jest poprawna, tzn. nie zależy od wyboru reprezentantów klas abstrakcji.

Produkt zredukowany

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

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

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

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

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

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

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

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

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

Przykładowe wyniki i zastosowania

• Twierdzenie Łosia:

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

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

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

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

W szczególności, ultrapotęga ${\displaystyle \mathbb {M} ^{I}/F}$ jest elementarnie równoważna z ${\displaystyle \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 ${\displaystyle \sigma }$-zupełny. (Przypomnijmy, że istnienie niegłównych ${\displaystyle \sigma }$-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 ${\displaystyle \tau }$ będzie przeliczalnym alfabetem. Załóżmy, że ${\displaystyle \kappa }$ 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 ${\displaystyle \kappa ^{\aleph _{0}}=\kappa .}$

Charakteryzacja elementarnie równoważnych modeli

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

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

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

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

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

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

istnieją ultrafiltry ${\displaystyle F,G}$ na ${\displaystyle 2^{\kappa }}$ takie że ultrapotęgi ${\displaystyle (\mathbb {M} _{0})^{2^{\kappa }}/F}$ i ${\displaystyle (\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 ${\displaystyle G_{0},G_{1}}$ takie, że żadne ich ultrapotęgi ${\displaystyle (G_{0})^{\omega }/F_{0},}$ ${\displaystyle (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