Ultraprodukty

$% \usepackage{amsmath} % \usepackage{amsfonts} % \usepackage{amssymb} % create the definition symbol \def\bydef{\stackrel{\text{def}}{=}} \newcommand{\qed}{\mbox{ } \Box} \newcommand{\set}[1]{\{#1\}} \newcommand{\eps}{\varepsilon} \newcommand{\NN}{\mathbb N} \newcommand{\Nat}{\mathbb N} \newcommand{\RR}{\mathbb R} \newcommand{\Aa}{\mathcal A} \newcommand{\Bb}{\mathcal B} \newcommand{\Cc}{\mathcal C} \newcommand{\Dd}{\mathcal D} \newcommand{\Ll}{\mathcal L} \newcommand{\str}[1]{\mathbb {#1}} \renewcommand{\implies}{\rightarrow} \newcommand{\lor}{\vee} \newcommand{\land}{\wedge} \renewcommand{\phi}{\varphi} \renewcommand{\subset}{\subseteq} \newcommand{\models}{\vDash} \DeclareMathOperator{\dom}{Dom} \DeclareMathOperator{\ifp}{ifp} \DeclareMathOperator{\lfp}{lfp} \DeclareMathOperator{\gfp}{gfp} \DeclareMathOperator{\tcl}{tcl} \DeclareMathOperator{\ln}{ln} $

Przytoczę tutaj konstrukcję, która pozwala w dość namacalny sposób opisać model niestandardowy arytmetyki. Konstrukcja ta nazywa się ultraproduktem, i jest jedną z metod dowodzenia twierdzenia o zwartości, w następującym wariancie (który jest równoważny zwykłej wersji tw. o zwartości – zob. tutaj).

Powiemy, że nieskończony ciąg modeli $\mathcal M_1,\mathcal M_2,\ldots$ jest elementarnie zbieżny do pewnego modelu $\mathcal M^*$, jeżeli dla dowolnego zdania $\phi$, zachodzi $\mathcal M^*\models\phi$ wtedy i tylko wtedy, gdy zachodzi $\mathcal M_n\models \phi$ dla dostatecznie dużych $n$.

Twierdzenie o zwartości (wariant II). Z każdego nieskończonego ciągu modeli $\mathcal M_1,\mathcal M_2,\ldots$ można wybrać podciąg, który jest elementarnie zbieżny do pewnego modelu $\mathcal M^*$.

W dowodzie przyda się następująca definicja.

Półmiarą na $\mathbb N$ nazywamy funkcję

$$\mu:P(\mathbb N)\to \set{0,1},$$

spełniającą następujące warunki:

  1. $\mu(\emptyset)=0,$
  2. $\mu(\mathbb N)=1,$
  3. $\mu(X\cup Y)=\mu(X)+\mu(Y)-\mu(X\cap Y),$

(Określenie półmiara jest na potrzeby tej notatki, normalnie taki obiekt się utożsamia z ultrafiltrem – zobacz poniżej).

Z tych warunków wynikają inne, np.

  • Jeżeli $X\subseteq Z$ to $\mu(X)\le \mu(Z)$ – na mocy (3), zastosowanego do $X$ oraz $Y=Z-X$.
  • Jeżeli $\mu(X)=\mu(Y)=0$, to $\mu(X\cup Y)=0$,
  • dualnie, jeżeli $\mu(X)=\mu(Y)=1$, to $\mu(X\cap Y)=1$

Przykładowa półmiara to $\mu_5$ zdefiniowana tak, że $\mu_5(X)=1$ wtedy i tylko wtedy, gdy $5\in X$.

Powiemy, że półmiara jest ciągła, jeżeli $\mu(X)=0$ dla każdego zbioru zbioru $X$ o jednym elemencie (równoważnie, dla każdego skończonego $X$). Miara $\mu_5$ nie jest ciągła.

Fakt. Istnieją półmiary ciągłe.

Dowód. Konstrukcja korzysta z aksjomatu wyboru, albo – wygodniej – z lematu Kuratowskiego-Zorna (można udowodnić, że nie da się skonstruować ciągłej półmiary w ZFC nie korzystając z aksjomatu wyboru).

Celem jest skonstruowanie rodziny zbiorów $U\subseteq P(\mathbb N)$ dla której półmiarą ciągłą jest funkcja $\mu_U$ taka, że $\mu_U(X)=1$ wtw gdy $X\in U$. Jasne jest, że rodzina $U$ musi spełniać kilka własności:

  1. $\mathbb N\in U$, $\emptyset\not\in U$,
  2. Jeżeli $X\in U$ i  $X\subset Y$, to $Y\in U$,
  3. Jeżeli $X\in U$ i $Y\in U$, to $X\cap Y\in U$.
  4. Dla każdego $X\subset\mathbb N$, dokładnie jeden ze zbiorów $X,\mathbb N-X$ należy do $U$.

Rodzinę spełniającą warunki 1-3 nazywa się filtrem. Jeżeli dodatkowo spełnia warunek 4, to nazywa się ultrafiltrem. Łatwo sprawdzić, że jeżeli $U$ jest ultrafiltrem, to $\mu_U$ jest półmiarą, czyli półmiary odpowiadają ultrafiltrom, poprzez insijekcję $U\mapsto \mu_U$. Przykładowym filtrem jest rodzina wszystkich zbiorów ko-skończonych (których dopełnienie w $\mathbb N$ jest skończone). Ten filtr nie jest ultrafiltrem, bo nie należy do niego ani zbiór liczb parzystych, ani jego dopełnienie.

Lemat. Istnieje ultrafiltr $U$ taki, że $X\in U$ dla każdego ko-skończonego $X$.

Dowód. Idea: zaczynamy od $U$ składającego się ze zbiorów ko-skończonych. W każdym kroku rozpatrujemy nierozważany jeszcze zbiór $X\not\in U$ i dodajemy albo $X$ albo $\mathbb N-X$ do $U$, by rozważana rodzina wciąż zawierała się w jakimś filtrze. Tak postępujemy aż przejrzymy wszystkie elementy $P(X)$.

Tę konstrukcję można sformalizować albo przez indukcję pozaskończoną, albo (co na jedno wychodzi), korzystając z lematu Kuratowskiego-Zorna. Rozważamy zbiór filtrów, uporządkowany przez inkluzję. Pokazuje się:

  1. Suma łańcucha filtrów jest filtrem. Sprawdzamy najciekawszy warunek (3): jeżeli $C$ jest łańcuchem filtrów oraz $X,Y\in \bigcup C$, to $X\in U_1,Y\in U_2$ dla pewnych $U_1,U_2\in C$. Skoro $C$ jest łańcuchem, to $U_1\subset U_2$ – wtedy $X,Y\in U_2$ – lub $U_2\subset U_1$ – wtedy $X,Y\in U_1$. W obu przypadkach, skoro $U_1,U_2$ to ultrafiltry, to $X\cap Y\in U_1\cup U_2\subset \bigcup C$.
  2. Maksymalny (ze względu na inkluzję) filtr jest ultrafiltrem. Tu należy pokazać, że jeżeli $U$ nie jest ultrafiltrem oraz $X\subset\mathbb N$ jest taki, że $X,\mathbb N-X\not\in U$, to istnieje filtr zawierający $U\cup\set X$ lub $U\cup \set {\mathbb N-X}$.

Mając punkty 1, 2, rozważamy rodzinę wszystkich filtrów które zawierają filtr zbiorów ko-skończonych. Na mocy punktu 1, każdy łańcuch ma kres górny, więc lematu Zorna mówi, że istnieje element maksymalny, a punkt 2 mówi, że ten element jest ultrafiltrem. Wtedy $\mu_U$ jest miarą, która jest ciągła, ponieważ $\mu_U(X)=0$ dla wszystkich zbiorów skończonych $X$. $\qed$

Z powyższego lematu wynika natychmiast, że istnieje półmiara ciągła $\mu$ – wystarczy wziąć $\mu=\mu_U$. Ustalmy do końca dowodu twierdzenia o zwartości półmiarę ciągłą $\mu$. Jeżeli $\phi$ jest zdaniem o zmiennej wolnej $n$ przebiegającej liczby naturalne, to powiem, że własność $\phi$ zachodzi prawie wszędzie (względem $n$), jeżeli $\mu(\set{n:\phi(n)})=1$. Na przykład własność $n>7$ zachodzi prawie wszędzie, i dokładnie jedna z własności “$n$ jest parzyste”, “$n$ jest nieparzyste” zachodzi prawie wszędzie.

Niech $\mathcal M_1,\mathcal M_2,\ldots$ będą strukturami relacyjnymi. Konstruujemy strukturę $\mathcal M’$ następująco:

  1. Nośnikiem $\mathcal M’$ jest zbiór $$M’=\prod_{n\in\mathbb N} M_n,$$ gdzie $M_n$ jest nośnikiem $\mathcal M_n$. Innymi słowy, nośnikiem $\mathcal M’$ są ciągi $\mathbb m=(\mathbb m[1],\mathbb m[2],\ldots)$,takie, że $\mathbb m[n]\in M_n$ dla $n=1,2,\ldots$.
  2. Jeżeli $R$ jest symbolem relacyjnym arności $k$ oraz $\mathbb m_1,\ldots,\mathbb m_k$ są elementami $M’$, to deklarujemy, że zachodzi $\mathcal M’\models R(\mathbb m_1,\ldots,\mathbb m_k)$ wtedy i tylko wtedy, gdy $\mathcal M_n\models R(\mathbb m_1[n],\ldots,\mathbb m_k[n])$ zachodzi prawie wszędzie (względem $n$).
  3. Zazwyczaj, symbol $=$ nie jest uważany za element sygnatury. Możemy jednak z nim postąpić tak jak w punkcie 2, definiując binarną relację $\sim$ na $M’$: $\mathbb m_1\sim\mathbb m_2$ wtedy i tylko wtedy, gdy $\mathcal M_n\models\mathbb m_1[n]=\mathbb m_2[n]$ zachodzi prawie wszędzie.

Przykład 1: Dla $n=1,2,\ldots$, niech $\mathcal M_n$ będzie modelem standardowym liczb naturalnych $\mathcal N$, traktowanym jako struktura relacyjna przez zastąpienie symboli funkcyjnych $s,+,\cdot$ symbolami relacyjnymi $R_s,R_+,R_\times$ dla ich wykresów (arności $2,3,3$, odpowiednio). Wówczas $\mathcal M’$ jest strukturą, której elementami są ciągi $n_1,n_2,\ldots$ liczb naturalnych. Jeżeli $e$ jest wyrażeniem arytmetycznym o zmiennej wolnej $n$, to niech $c_e$ oznacza ciąg $e[n=1],e[n=2],\ldots$. Przykładowo, dla wyrażenia $n^2$, ciąg $c_{n^2}$ jest równy ${1,4,9,16,\ldots}$, a ciąg $c_{45}$ to ciąg stale równy $45$. Wówczas zachodzi $$c_0\le c_1\le c_2\le\ldots \le c_{\lceil\log n\rceil}\le c_{n}\le c_{n^2}\le c_{2^n}\le\ldots.$$ Zauważmy, że nierówność $10\le n^2$ nie zachodzi dla każdego $n$, ale zachodzi prawie wszędzie (z ciągłości miary). Także, zachodzi $c_4+c_6=c_{10}$ (to jest skrót notacyjny dla $R_+(c_4,c_6,c_{10})$). Wreszcie, zachodzi $c_0\sim (1,0,0,0,\ldots)$.$\qed$

Fakt 1. Relacja $\sim$ jest kongruencją na $\mathcal M’$, tzn. jeżeli $\mathbb m_1\sim \mathbb m’_1,\ldots,\mathbb m_k\sim \mathbb m_k’$, to

$\mathcal M’\models R(\mathbb m_1,\ldots,\mathbb m_k)$ wtedy i tylko wtedy, gdy $\mathcal M’\models R(\mathbb m’_1,\ldots,\mathbb m’_k)$

Dowód. Pokażemy tezę w przypadku $\mathbb m_1\sim\mathbb m’_1$ oraz $\mathbb m_i=\mathbb m’_i$ dla $i=2,3,\ldots,k$. Ogólny przypadek przebiega podobnie (a też wynika z symetrii i przez indukcję). Przypuśćmy, że $\mathcal M’\models R(\mathbb m_1,\ldots,\mathbb m_k)$.  Niech

\begin{align*}X&=\set{n: \mathcal M_n\models R(\mathbb m_1[n],\ldots,\mathbb m_k[n])}\\ Y&=\set{n: \mathbb m_1[n]=\mathbb m\_1[n]}.\end{align*}

Wówczas $\mu(X)=1$ oraz $\mu(Y)=1$, zatem, $\mu(X\cap Y)=1$. Zauważmy, że zbiór $$\set{n: \mathcal M_n\models R(\mathbb m’_1[n],\ldots,\mathbb m_k[n])},$$ zawiera zbiór $X\cap Y$, więc jest $\mu$-miary $1$.$\qed$

Definiujemy ultraprodukt struktur $\mathcal M_1,\mathcal M_2,\ldots$ jako strukturę ilorazową $\mathcal M^*=\mathcal M’/\sim$. W tej strukturze, nośnikiem jest zbiór klas abstrakcji relacji $\sim$, oraz $R([\mathbb m_1]_\sim,\ldots,[\mathbb m_k]_\sim)$ zachodzi w $\mathcal M^*$ wtw gdy $R(\mathbb m_1,\ldots,\mathbb m_k)$ zachodzi w $\mathcal M’$. To, że to nie zależy od wyboru reprezentantów wynika z Faktu 1. Od tej pory, element $[\mathbb m]_\sim$ struktury $\mathcal M^*$ będziemy oznaczać po prostu przez $\mathbb m$.

Fakt 2 (twierdzenie Łosia). 

Niech $\phi(x_1,\ldots,x_k)$ będzie formułą pierwszego rzędu oraz $\mathbb m_1,\ldots, \mathbb m_k\in\mathcal M^*$. Wówczas $\mathcal M^*\models \phi(\mathbb m_1,\ldots,\mathbb m_k)$ wtedy i tylko gdy $\mathcal M_n\models \phi(\mathbb m_1[n],\ldots,\mathbb m_k[n])$ $\mu$-prawie wszędzie (względem $n$).

Dowód. Indukcja po rozmiarze formuły $\phi$. W kroku bazowym rozważamy formuły atomowe, czyli postaci $x_1=x_2$ lub $R(x_1,\ldots,x_k)$, gdzie $R$ jest symbolem relacyjnym. W pierwszym przypadku, teza wynika z definicji nośnika $M^*$ jako $M’/\sim$. W drugim przypadku, wynika z Faktu 1. W kroku indukcyjnym, rozważamy trzy przypadki: gdy $\phi$ jest postaci $\neg\psi$, postaci $\psi_1\lor\psi_2$, i postaci $\exists x.\psi$. W pierwszym przypadku, korzystamy z własności że $\mu(X)=1$ wtw $\mu(\mathbb N-X)=0$. W drugim przypadku, korzystamy z własności, że $\mu(X\cap Y)=1$ wtw gdy $\mu(X)=1$ oraz $\mu(Y)=1$. Trzeci przypadek jest prosty.$\qed$

Wniosek. Jeżeli dla $n=1,2,3,\ldots$, w strukturze $\mathcal M_n$, relacja $R_f$ jest wykresem funkcji $k$-argumentowej, to w strukturze $\mathcal M^*$, relacja $R_f$ też jest wykresem funkcji $k$-argumentowej – bo tę własność się zapisuje formułą $$\forall x_1\ldots\forall x_k\exists! y.R(x_1,\ldots,x_k,y)$$ (gdzie $\exists !y.\psi(y)$ to oczywiście skrót notacyjny na $\exists y(\psi(y)\land \forall y’\psi(y’)\implies y=y’)$.

Dlatego, możemy bez problemu rozważać ultraprodukty struktur wyposażonych w symbole funkcyjne.$\qed$

Przykład 2. Kontynuujemy przykład 1. Struktura $\mathcal M^*$ jest modelem arytmetyki Peano, ponieważ każdy aksjomat $\phi$ jest spełniony we wszystkich strukturach $\mathcal M_1,\mathcal M_2,\ldots$ (bo one są równe $\mathcal N$) więc także w $\mathcal M^*$. W tym modelu, stałą $0$ jest oczywiście klasa abstrakcji funkcji $c_0$, oraz $s^k(0)=c_k$ dla $k\in\mathbb N$. Ten model jednak jest niestandardowy (nieizomorficzny z $\mathcal N$), bo np. element $c_n$ jest większy od $0,s(0),s(s(0)),\ldots$. Jednakże struktura $\mathcal M^*$ jest elementarnie równoważna (spełnia te same zdania logiki pierwszego rzędu) modelowi standardowemu $\mathcal N$, co wynika natychmiast z twierdzenia Łosia. (Na marginesie  – istnieją modele $\mathcal N’$ aksjomatyki Peano które nie są elementarnie równoważne $\mathcal N$. Innymi słowy, istnieje twierdzenie $\phi$ które zachodzi w $\mathcal N$, ale nie zachodzi w pewnym modelu $\mathcal N’$. Tego twierdzenia, siłą rzeczy, nie da się udowodnić z aksjomatów Peano, ale da się udowodnić w ZFC. Ciekawym przykładem takiego twierdzenia jest twierdzenie Goodsteina. Przykładem takiego twierdzenia, które jest często stosowane w informatyce teoretycznej, jest twierdzenie Kruskala o drzewach.) $\qed$

Przykład 3. (Niestandardowy modele liczb rzeczywistych). Rozważmy ultraprodukt $\mathcal R^*$ ciągu $\mathcal M_1,\mathcal M_2,\ldots$, gdzie $\mathcal M_n=(\mathbb R,+,\cdot,0,1,\le)$ jest uporządkowanym ciałem liczb rzeczywistych. Struktura $\mathcal R^*$ nazywa się niestandardowym modelem liczb rzeczywistych, lub też liczb hiper-rzeczywistych. Jej elementy są wyznaczone przez ciągi $r_1,r_2,\ldots$ liczb rzeczywistych; jest to ciało na mocy twierdzenia Łosia. Każdy liczba rzeczywista $r\in \mathbb R$ wyznacza element $f(r)\in\mathcal R^*$, który jest klasą abstrakcji ciągu stałego $r,r,r,\ldots$. Funkcja $f:\mathbb R\to \mathcal R^*$ jest różnowartościowa, i łatwo sprawdzić, że jest homomorfizmem ciał uporządkowanych, tj. zachowuje $+,\cdot,\le$ itd. Będziemy więc utożsamiać $\mathcal R$ z podstrukturą struktury $\mathcal R^*$. Elementy $\mathcal R^*-\mathcal R$ nazywane są liczbami niestandardowymi, a elementy $\mathcal R$ – standardowymi. Przykładowa liczba niestandardowa to klasa $\mathbb \epsilon$ abstrakcji ciągu $1,1/2,1/3,\ldots$. Jasne jest, że $\mathbb \epsilon<x$ dla dowolnej liczby rzeczywistej $x\in\mathcal R\subset\mathcal R^*$. Także, $\epsilon^2<\epsilon$.

Za to klasa abstrakcji ciągu $0,1,0,1,\ldots$ jest albo równa klasie abstrakcji ciągu $0,0,0,\ldots$, albo ciągu $1,1,1,\ldots$, w zależności od tego, czy zbiór liczb parzystych jest $\mu$-miary $1$.

Ciało $\mathcal R^*$ pozwala uprawiać analizę niestandardową, tak jak to chciał robić Leibnitz. Mówimy, że liczba niestandardowa $\eps$ jest infinitezymalna jeżeli $-x<\eps<x$ dla dowolnej (standardowej) liczby rzeczywistej $x>0$, i że jest ograniczona, jeżeli $-x<\eps<x$ dla pewnej liczby rzeczywistej $x$. Dla każdej ograniczonej liczby niestandardowej $x$ istnieje dokładnie jedna liczba standardowa, oznaczana $\textrm{st}(x)$, o tej własności, że różnica $x-\textrm{st}(x)$ jest infinitezmalna (tę liczbę możemy znaleźć metodą bisekcji: z twierdzenia Łosia, dla dowolych $x,r$, zachodzi dokładniej jedna z możliwości $x>r$, $x=r$, $x<r$. Zawężamy binsearchem nasze poszukiwania liczby $r=\textrm{st}(x)$ do coraz mniejszych przedziałów $[p,q]$ o końcach rzeczywistych, za każdym razem dwukrotnie mniejszej długości. Końce tych przedziałów zbiegają (z twierdzenia Cauchy’ego) do jakiejś liczby rzeczywistej $r=\textrm{st}(x)$). Funkcja $\textrm{st}:\mathcal R^*\to\mathcal R$ jest homomorfizmem ciał.

Każda funkcja $f:\mathbb R\to\mathbb R$ wyznacza funkcję $f^\ast:\mathcal R^*\to\mathcal R^*$, poprzez aplikację $f$ po współrzędnych: $$f^\ast([r_1,r_2,\ldots]_\sim)=[f(r_1),f(r_2),\ldots]_\sim$$

(łatwo widzieć, że to nie zależy od wyboru reprezentanta klasy abstrakcji ciągu (r_1,r_2,\ldots)). W duchu analizy niestandardowej, możemy powiedzieć, że funkcja $f:\mathbb R\to\mathbb R$ jest ciągła, jeżeli dla dowolnej liczby $x\in\mathcal R$, różnica

$$f^\ast(x+\epsilon)-f^*(x)$$

jest infinitezymalna gdy $\epsilon\in\mathcal R^*$ jest infinitezymalna.$\qed$

Dowód (twierdzenia o zwartości). Niech $\mathcal M_1,\mathcal M_2,\ldots$ będzie ciągiem modeli, i niech $\mathcal M^*$ oznacza ich ultraprodukt (względem jakiejś ustalonej półmiary ciągłej $\mu$). Twierdzimy, że ciąg modeli $\mathcal M_1,\mathcal M_2,\ldots$ posiada podciąg $\mathcal M_{n_1},\mathcal M_{n_2},\ldots$ który jest zbieżny elementarnie do ultraproduktu $\mathcal M^*$. Przypomnijmy, że na mocy Twierdzenia Łosia, $\mathcal M^*\models \phi$ wtw gdy $\mathcal M_n\models \phi$ dla $\mu$-prawie wszystkich $n$.

Niech $\phi_1,\phi_2,\ldots$ będą wszystkimi zdaniami, które zachodzą w $\mathcal M^*$. Konstruujemy ciąg $n_1,n_2,\ldots$ przez indukcję. Niech $n_1=1$ oraz dla $i>1$ niech $n_i>n_{i-1}$ będzie takie, że $\mathcal M_{n_i}\models \phi_j$ dla $j<i$. Istnieje takie $n_i$, ponieważ $\mathcal M^\ast\models \phi$, gdzie $\phi=\phi_1\land\cdots\land \phi_{i-1}$, więc $\mathcal M_n\models \phi$ dla $\mu$-prawie wszystkich $n$. Z ciągłości $n$, istnieje nieskończenie wiele $n$ takich, że $\mathcal M_n\models \phi$, więc istnieje też najmniejsze takie $n$, że $n>n_{i-1}$.

Z konstrukcji wynika, że dla każdego $m$, $\mathcal M_{n_k}\models \phi_m$ dla $k>m$. A zatem ciąg $\mathcal M_{n_1},\mathcal M_{n_2},\ldots$ jest elementarnie zbieżny do struktury $\mathcal M^*$. To kończy dowód twierdzenia o zwartości.$\qed$

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>