Satz von Łoś

Der Satz von Łoś, benannt nach dem polnischen Mathematiker Jerzy Łoś, ist ein Satz aus der Modelltheorie aus dem Jahre 1955, der einen alternativen Zugang zum Kompaktheitssatz ermöglicht. Die Existenz von Modellen gewisser mathematischer Strukturen wird auf die Existenz von Ultrafiltern zurückgeführt.

Begriffsbildungen

Boolesche Ausdehnung

Es sei $S$ eine vorgegebene Signatur, das heißt eine Menge von nicht-logischen Symbolen, wie zum Beispiel $S=\{0,1,+,\cdot \}$ zur Beschreibungen von Ringen oder Körpern. Weiter sei $(M_{i})_{i\in I}$ eine nicht-leere Familie von $S$-Strukturen und $\prod _{i\in I}M_{i}$ deren kartesisches Produkt, das wir im Folgenden abkürzend mit $M$ bezeichnen wollen.

Sei weiter $\varphi =\varphi (x_{1},\ldots ,x_{n})$ eine Formel der Sprache $L_{I}^{S}$ der Prädikatenlogik erster Stufe, deren freie Variable unter den $x_{1},\ldots ,x_{n}$ zu finden sind. Für jedes Tupel $(a_{1}(i),\ldots ,a_{n}(i))\in M_{i}^{n}$ ist dann $\varphi (a_{1}(i),\ldots ,a_{n}(i))$ eine Aussage, die auf $M_{i}$ zutreffen kann oder nicht, das heißt, für die $M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))$ oder nicht. $M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))$ liest man als $M_{i}$ ist Modell von $\varphi (a_{1}(i),\ldots ,a_{n}(i))$. Durch diese nicht ganz saubere aber übliche Schreibweise $\varphi (a_{1}(i),\ldots ,a_{n}(i))$ soll angedeutet werden, dass die Elemente $a_{1}(i),\ldots ,a_{n}(i)\in M_{i}$ an die Stelle der freien Variablen mit dem gleichen Index treten und damit eine Aussage im Modell $M_{i}$ bilden.

Wir betrachten zu $\varphi =\varphi (x_{1},\ldots ,x_{n})$ nun ein Tupel $(a_{1},\ldots a_{n}):I\rightarrow M^{n}$ und interessieren uns für die Menge aller Indizes, für die $M_{i}$ ein Modell von $\varphi (a_{1}(i),\ldots ,a_{n}(i))$ ist. Wir definieren daher

$\|\varphi (a_{1},\ldots ,a_{n})\|\,:=\,\{i\in I;\,M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))\}$

und nennen diese Menge die Boolesche Ausdehnung von $\varphi (a_{1},\ldots ,a_{n})$.

Reduzierte Produkte

Zusätzlich zur oben beschriebenen Situation betrachten wir nun einen Filter $F$ auf der Indexmenge $I$ und definieren

$a\cong _{F}b\quad \Leftrightarrow \quad \{i\in I;\,a(i)=b(i)\}\in F$

für $a,b\in M$. Diese Menge ist nichts anderes als die Boolesche Ausdehnung $\|(x_{1}=x_{2})(a,b)\|$ der Formel $(x_{1}=x_{2})$ angewandt auf das Zweiertupel $(a,b):I\rightarrow M^{2}$.

Die Eigenschaften eines Filters zeigen, dass dadurch eine Äquivalenzrelation auf dem kartesischen Produkt der $M_{i}$ definiert ist. Die Faktormenge nach dieser Äquivalenzrelation heißt das reduzierte Produkt zum Filter $F$ und wird mit $M/F$ bezeichnet.

Durch die folgenden Festlegungen, deren Wohldefiniertheit zu zeigen ist, wird das reduzierte Produkt ebenfalls zu einer $S$-Struktur:

• $c^{M/F}:=(c^{M_{i}})_{i\in I}/F$ für jedes Konstantensymbol $c\in S$.

• $f^{M/F}(a_{1}/F,\ldots ,a_{n}/F):=(f^{M_{i}}(a_{1}(i),\ldots ,a_{n}(i)))_{i\in I}/F$ für jedes n-stellige Funktionssymbol $f\in S$.

• $R^{M/F}(a_{1}/F,\ldots ,a_{n}/F)$ genau dann, wenn $\{i\in I;R^{M_{i}}(a_{1}(i),\ldots ,a_{n}(i))\}\in F$ für jedes n-stellige Relationssymbol $R\in S$.

Ist speziell $F$ ein Ultrafilter, das heißt maximal unter allen Filtern auf $I$, so nennt man $M/F$ das Ultraprodukt der $M_{i}$ zum Ultrafilter $F$.

Formulierung des Satzes

Der Satz von Łoś stellt ein Kriterium für die Gültigkeit von Formeln in Ultraprodukten bereit:

Es sei $(M_{i})_{i\in I}$ eine nicht-leere Familie von $S$-Strukturen und $U$ ein Ultrafilter auf $I$. Dann gilt

$\prod _{i\in I}M_{i}/U\vDash \varphi (a_{1}/U,\ldots ,a_{n}/U)$ genau dann, wenn $\|\varphi (a_{1},\ldots ,a_{n})\|\in U$

für alle Formeln $\varphi =\varphi (x_{1},\ldots ,x_{n})$ aus $L_{I}^{S}$ und alle Tupel $(a_{1},\ldots ,a_{n}):I\rightarrow (\prod _{i\in I}M_{i})^{n}$.

Anwendungen

An zwei Beispielen sollen typische Anwendungen des Satzes von Łoś vorgestellt werden.

Kompaktheitssatz

Zum Kompaktheitssatz ist zu zeigen, dass eine Menge $\Phi$ von Sätzen aus $L_{I}^{S}$ bereits dann ein Modell hat, wenn für jede endliche Teilmenge von $\Phi$ ein Modell gefunden werden kann. Um den Satz von Łoś in Anwendung zu bringen, betrachtet man als Indexmenge $I$ die Menge alle endlichen Teilmengen von $\Phi$ und zu jedem $i\in I$ ein nach Voraussetzung existierendes Modell $M_{i}$ von $i$. Die Obermengen der endlichen Durchschnitte der Mengen $\{j\in I;i\subset j\}$ bilden einen Filter, der in einem Ultrafilter $U$ enthalten ist. Aus dem Satz von Łoś folgt nun leicht, dass $\prod _{i\in I}M_{i}/U$ ein Modell für $\Phi$ ist.

Dieser Beweis hat gegenüber Gödels Beweis den Vorteil, dass auf die Verwendung des syntaktischen Ableitbarkeitsbegriffs (siehe Prädikatenlogik erster Stufe) und den Vollständigkeitssatz verzichtet werden kann. Dieses Vorgehen wird im unten angegebenen Lehrbuch von Philipp Rothmaler konsequent ausgeführt.

Ringtheorie

• Es sei $\varphi$ ein Satz der Sprache $L_{I}^{S}$ mit $S=\{0,1,+,\cdot \}$, der in allen Ringen der Charakteristik 0 gelte. Dann gilt der Satz bereits in Ringen hinreichend hoher Charakteristik.

Nimmt man im Sinne eines Widerspruchsbeweises an, dass es Ringe $M_{i}$, $i\in \mathbb {N}$, beliebig hoher Charakteristik $m_{i}$ gibt, für die der Satz $\varphi$ nicht gilt, ohne Einschränkung $m_{1}<m_{2}<m_{3}<\ldots$, so betrachte man einen Ultrafilter $U$ auf $\mathbb {N}$, der den Fréchet-Filter umfasst. Sätze der Form $1+\ldots +1=0$ sind wegen der aufsteigenden Charakteristiken in fast allen $M_{i}$ falsch und nach dem Satz von Łoś daher auch im Ultraprodukt $\prod M_{i}/U$, das heißt letzteres ist ein Ring der Charakteristik 0. Nach Voraussetzung gilt daher $\varphi$ im Ultraprodukt und mit einer erneuten Anwendung des Satzes von Łoś ist die Menge aller Indizes, für die der Satz in $M_{i}$ richtig ist, im Ultrafilter enthalten, das heißt, er muss entgegen der Annahme von einigen, sogar von unendlich vielen, der $M_{i}$ erfüllt werden. Dieser Widerspruch beendet den Beweis.