Ultraprodukt

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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[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 1955[4].

Definicja[edytuj | edytuj kod]

Niech τ 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},\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 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},\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 τ 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[edytuj | edytuj kod]

  • 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:
  • 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[5]. W tym ostatnim kontekscie warto zacytować następujący wynik:
  • Twierdzenie Rabina-Keslera[6][7]: 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[edytuj | edytuj kod]

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[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/Gizomorficzne.
  • Twierdzenia Shelaha[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}/Gizomorficzne.
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ż[edytuj | edytuj kod]

Przypisy

  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.