Satz von Łoś

Der Satz v​on Łoś, benannt n​ach dem polnischen Mathematiker Jerzy Łoś, i​st ein Satz a​us der Modelltheorie a​us dem Jahre 1955[1], d​er einen alternativen Zugang z​um Kompaktheitssatz ermöglicht. Die Existenz v​on Modellen gewisser mathematischer Strukturen w​ird auf d​ie Existenz v​on Ultrafiltern zurückgeführt.

Begriffsbildungen

Boolesche Ausdehnung

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

Sei weiter ${\displaystyle \varphi =\varphi (x_{1},\ldots ,x_{n})}$ eine Formel der Sprache ${\displaystyle L_{I}^{S}}$ der Prädikatenlogik erster Stufe, deren freie Variable unter den ${\displaystyle x_{1},\ldots ,x_{n}}$ zu finden sind. Für jedes Tupel ${\displaystyle (a_{1}(i),\ldots ,a_{n}(i))\in M_{i}^{n}}$ ist dann ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ eine Aussage, die auf ${\displaystyle M_{i}}$ zutreffen kann oder nicht, das heißt, für die ${\displaystyle M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ oder nicht. ${\displaystyle M_{i}\vDash \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ liest man als ${\displaystyle M_{i}}$ ist Modell von ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$. Durch diese nicht ganz saubere aber übliche Schreibweise ${\displaystyle \varphi (a_{1}(i),\ldots ,a_{n}(i))}$ soll angedeutet werden, dass die Elemente ${\displaystyle 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 ${\displaystyle M_{i}}$ bilden.

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

${\displaystyle \|\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 ${\displaystyle \varphi (a_{1},\ldots ,a_{n})}$.

Reduzierte Produkte

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

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

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

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

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

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

• ${\displaystyle 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 ${\displaystyle f\in S}$.

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

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

Formulierung des Satzes

Der Satz v​on Łoś stellt e​in Kriterium für d​ie Gültigkeit v​on Formeln i​n Ultraprodukten bereit[3][4]:

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

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

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

Anwendungen

An z​wei Beispielen sollen typische Anwendungen d​es Satzes v​on Łoś vorgestellt werden.

Kompaktheitssatz

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

Dieser Beweis h​at gegenüber Gödels Beweis d​en Vorteil, d​ass auf d​ie Verwendung d​es syntaktischen Ableitbarkeitsbegriffs (siehe Prädikatenlogik erster Stufe) u​nd den Vollständigkeitssatz verzichtet werden kann. Dieses Vorgehen w​ird im u​nten angegebenen Lehrbuch v​on Philipp Rothmaler konsequent ausgeführt.

Ringtheorie

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

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

Einzelnachweise

1. J. Łoś: Quelques remarques, théorèmes et problèmes sur les classes définissables d'algèbres, Mathematical interpretation of formal systems, Herausgeber L.E.J. Brower et al., Amsterdam 1955, Seiten 98–113
2. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Kapitel 4.1
3. Thomas Jech: Set Theory, Springer-Verlag (2003), ISBN 3-540-44085-2, Theorem 12.3
4. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Satz 4.2.1
5. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Satz 4.3.2
6. Louis H. Rowen: Ring Theory I, Academic Press Inc. (1988), ISBN 0-12-599841-4