Satz von Fraïssé

Wir gehen von einer endlichen Symbolmenge ${\displaystyle S}$ und der zugehörigen Sprache ${\displaystyle L_{I}^{S}}$ der Prädikatenlogik erster Stufe aus. Zur angestrebten Charakterisierung benötigen wir folgende algebraische Begriffsbildungen.

Sind ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ ${\displaystyle S}$-Strukturen, so heißt eine Abbildung ${\displaystyle h}$ ein partieller Isomorphismus von ${\displaystyle {\mathcal {A}}}$ nach ${\displaystyle {\mathcal {B}}}$, wenn folgendes gilt:

• ${\displaystyle h}$ ist eine Abbildung mit Definitionsbereich ${\displaystyle \mathrm {def} (h)\subset {\mathcal {A}}}$ und Bildmenge ${\displaystyle \mathrm {bild} (h)\subset {\mathcal {B}}}$.
• ${\displaystyle h\colon \mathrm {def} (h)\rightarrow {\mathcal {B}}}$ ist injektiv.
• Ist ${\displaystyle c\in S}$ ein Konstantensymbol, so gilt:
  • Ist ${\displaystyle c^{\mathcal {A}}\in \mathrm {def} (h)}$, so ist ${\displaystyle h(c^{\mathcal {A}})=c^{\mathcal {B}}}$.
  • Ist ${\displaystyle c^{\mathcal {B}}\in \mathrm {bild} (h)}$, so ist ${\displaystyle c^{\mathcal {A}}\in \mathrm {def} (h)}$ und ${\displaystyle h(c^{\mathcal {A}})=c^{\mathcal {B}}}$.
• Ist ${\displaystyle f\in S}$ ein ${\displaystyle n}$-stelliges Funktionssymbol und sind ${\displaystyle a_{1},\ldots ,a_{n},a\in \mathrm {def} (h)}$, so gilt

${\displaystyle f^{\mathcal {A}}(a_{1},\ldots ,a_{n})=a\quad \Leftrightarrow \quad f^{\mathcal {B}}(h(a_{1}),\ldots ,h(a_{n}))=h(a)}$.

• Ist ${\displaystyle R\in S}$ ein ${\displaystyle n}$-stelliges Relationssymbol und sind ${\displaystyle a_{1},\ldots ,a_{n}\in \mathrm {def} (h)}$, so gilt

${\displaystyle R^{\mathcal {A}}(a_{1},\ldots ,a_{n})\quad \Leftrightarrow \quad R^{\mathcal {B}}(h(a_{1}),\ldots ,h(a_{n}))}$.

Dabei sind ${\displaystyle c^{\mathcal {A}},f^{\mathcal {A}},R^{\mathcal {A}}}$ die Interpretationen der Symbole ${\displaystyle c,f,R}$ im Modell ${\displaystyle {\mathcal {A}}}$. Man verwendet bei einem partiellen Isomorphismus auch die für Abbildungen übliche Schreibweise ${\displaystyle h\colon {\mathcal {A}}\rightarrow {\mathcal {B}}}$ und meint damit nur, dass der Definitionsbereich gemäß obiger Definition in ${\displaystyle {\mathcal {A}}}$ enthalten ist.

Ist ${\displaystyle h\colon {\mathcal {A}}\rightarrow {\mathcal {B}}}$ ein partieller Isomorphismus, so offenbar auch ${\displaystyle h^{-1}}$, wobei ${\displaystyle \mathrm {def} (h^{-1})=\mathrm {bild} (h)}$ und ${\displaystyle \mathrm {bild} (h^{-1})=\mathrm {def} (h)}$. Ist weiter ${\displaystyle A\subset {\mathcal {A}}}$ eine Teilmenge, so ist auch die Einschränkung ${\displaystyle h|_{A}}$ ein partieller Isomorphismus und es ist ${\displaystyle \mathrm {def} (h|_{A})=\mathrm {def} (h)\cap A}$.

Zwei ${\displaystyle S}$-Strukturen ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ heißen endlich isomorph, wenn es eine Folge ${\displaystyle (I_{n})_{n\in \mathbb {N} }}$ von nicht-leeren Mengen partieller Isomorphismen ${\displaystyle {\mathcal {A}}\rightarrow {\mathcal {B}}}$ gibt, so dass folgende Fortsetzungseigenschaften erfüllt sind:

• Zu jedem ${\displaystyle h\in I_{n+1}}$ und ${\displaystyle a\in {\mathcal {A}}}$ gibt es ein ${\displaystyle g\in I_{n}}$ mit ${\displaystyle a\in \mathrm {def} (g)}$ und ${\displaystyle g|_{\mathrm {def} (h)}\,=\,h}$.
• Zu jedem ${\displaystyle h\in I_{n+1}}$ und ${\displaystyle b\in {\mathcal {B}}}$ gibt es ein ${\displaystyle g\in I_{n}}$ mit ${\displaystyle b\in \mathrm {bild} (g)}$ und ${\displaystyle g|_{\mathrm {def} (h)}\,=\,h}$.

Ein partieller Isomorphismus ${\displaystyle h\in I_{n}}$ lässt sich also ${\displaystyle n}$-mal auf beliebige Elemente zu einem partiellen Isomorphismus fortsetzen, und zwar der Reihe nach zu partiellen Isomorphismen aus ${\displaystyle I_{n-1},I_{n-2},\ldots ,I_{0}}$; und für ${\displaystyle h^{-1}}$ gilt das ebenfalls.

Sind ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ zwei isomorphe Strukturen und ist ${\displaystyle h\colon {\mathcal {A}}\rightarrow {\mathcal {B}}}$ ein Isomorphismus, so sind ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ auch endlich isomorph, denn obige Definition ist mit ${\displaystyle I_{n}=\{h\}}$ für alle ${\displaystyle n\in \mathbb {N} }$ erfüllt. Die Umkehrung gilt nicht; weiter unten wird bewiesen, dass die geordnete Mengen ${\displaystyle (\mathbb {R} ,<)}$ und ${\displaystyle (\mathbb {Q} ,<)}$, die Symbolmenge ist hier ${\displaystyle S=\{<\}}$, endlich isomorph sind, sie können aber schon aus Mächtigkeitsgründen nicht isomorph sein.

Mit dem Begriff der endlichen Isomorphie, der sich wohl der Symbole bedient, aber keinen weiteren Bezug zur Prädikatenlogik erster Stufe nimmt, kann man die elementare Äquivalenz zweier Strukturen in der Prädikatenlogik erster Stufe charakterisieren:

Satz von Fraïssé: Für eine endliche Symbolmenge ${\displaystyle S}$ und für zwei ${\displaystyle S}$-Strukturen ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ sind äquivalent:

• ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ sind elementar äquivalent.
• ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$ sind endlich isomorph.

Zur Verdeutlichung der Begriffe wollen wir den Satz von Fraïssé beispielhaft auf die Theorie der dichten, linearen Ordnungen ohne Extrema anwenden. Eine geordnete Menge ${\displaystyle (X,<)}$ heißt linear geordnet, falls sich je zwei Elemente vergleichen lassen. Sie heißt dicht, falls zwischen je zwei Elementen ein drittes liegt. Ein Extremum einer Ordnung ist ein Element, das größer bzw. kleiner als jedes andere ist. Die Theorie der dichten linearen Ordnungen ohne Extrema wird daher durch die folgenden Sätze der Sprache ${\displaystyle L_{I}^{\{<\}}}$ definiert:

${\displaystyle \forall x\,(\neg x<x)}$

${\displaystyle \forall x\,y\,z\,((x<y\land y<z)\rightarrow x<z)}$

${\displaystyle \forall x\,y\,((x<y\lor y<x\lor x=y)}$

${\displaystyle \forall x\,\exists y\,(y<x)}$

${\displaystyle \forall x\,\exists y\,(x<y)}$

${\displaystyle \forall x\,y\,z\,(x<y\rightarrow \exists z\,(x<z\land z<y))}$.

Die ersten beiden Sätze drücken Irreflexivität und Transitivität aus. Zusammen folgt daraus die Antisymmetrie:

${\displaystyle \forall x\,y\,(\neg (x<y\land y<x))}$

Der dritte Satz besagt, dass die Elemente linear geordnet sind. Die nächsten beiden Sätze fordern, dass es keine Extrema gibt und der letzte gibt offenbar die Definition der Dichtheit wieder. Es sei ${\displaystyle \varphi _{d}}$ die Konjunktion dieser sechs Sätze, wobei der Index d an die Dichtheitseigenschaft der Ordnung erinnern soll. Aus der dritten und sechsten Aussage folgt sofort, dass dichte Ordnungen unendlich viele Elemente enthalten.

Jeder partielle Isomorphismus ${\displaystyle h\colon {\mathcal {A}}\rightarrow {\mathcal {B}}}$ mit endlichem Definitionsbereich lässt sich zu einem weiteren partiellen Isomorphismus auf ein beliebiges Element fortsetzen. Ist etwa ${\displaystyle \mathrm {def} (h)=\{a_{1},\ldots ,a_{n}\}}$ und ist ${\displaystyle a\in {\mathcal {A}}}$ ein weiteres Element, so kann man wegen der Dichtheit von ${\displaystyle {\mathcal {B}}}$ ein Element ${\displaystyle b\in {\mathcal {B}}}$ finden, das zu ${\displaystyle h(a_{1}),\ldots ,h(a_{n})}$ in denselben Größenbeziehungen steht wie ${\displaystyle a}$ zu ${\displaystyle a_{1},\ldots ,a_{n}}$. Die Festlegung

${\displaystyle g(a_{i}):=h(a_{i}),\,i\in \{1,\ldots ,n\},\quad g(a)=b}$

definiert dann einen partiellen Isomorphismus ${\displaystyle g\colon {\mathcal {A}}\rightarrow {\mathcal {B}}}$, der ${\displaystyle h}$ auf das Element ${\displaystyle a}$ fortsetzt. Dasselbe gilt für ${\displaystyle h^{-1}}$, da auch ${\displaystyle {\mathcal {A}}}$ dicht ist. Setzt man daher

${\displaystyle I_{n}:=\{h\colon {\mathcal {A}}\rightarrow {\mathcal {B}}\mid h{\mbox{ partieller Isomorphismus mit endlichem Definitionsbereich}}\}}$,

so definiert ${\displaystyle (I_{n})_{n\in \mathbb {N} }}$ eine endliche Isomorphie zwischen ${\displaystyle {\mathcal {A}}}$ und ${\displaystyle {\mathcal {B}}}$. Je zwei ${\displaystyle \{<\}}$-Strukturen, die ${\displaystyle \varphi _{d}}$ erfüllen, sind also endlich isomorph. Damit ist auch die oben behauptete endliche Isomorphie zwischen ${\displaystyle (\mathbb {R} ,<)}$ und ${\displaystyle (\mathbb {Q} ,<)}$ bewiesen.

Aus dem Satz von Fraïssé folgt nun:

• Je zwei Modelle der Klasse der dichten Ordnungen sind elementar äquivalent.

Eine typische Anwendung dieser Aussage ist:

• Für jeden ${\displaystyle \{<\}}$-Satz ${\displaystyle \psi }$ gilt ${\displaystyle \varphi _{d}\vDash \psi }$ oder ${\displaystyle \varphi _{d}\vDash \neg \psi }$.

Zum Beweis sei ${\displaystyle \varphi _{d}\nvDash \psi }$, wir müssen ${\displaystyle \varphi _{d}\vDash \neg \psi }$ zeigen. Wir tun dies indirekt, indem wir annehmen, dass es ein Modell ${\displaystyle {\mathcal {A}}}$ gibt, das ${\displaystyle \varphi _{d}}$ erfüllt, aber nicht ${\displaystyle \neg \psi }$. Dann ist ${\displaystyle {\mathcal {A}}}$ eine dichte Ordnung, da es ja ${\displaystyle \varphi _{d}}$ erfüllt, die nicht ${\displaystyle \neg \psi }$ erfüllt und daher ein Modell für ${\displaystyle \psi \,}$ sein muss. Da aber alle dichten Ordnungen nach obigem elementar äquivalent sind und daher dieselben Sätze erfüllen, folgt ${\displaystyle \psi \,}$ für jedes Modell, das ${\displaystyle \varphi _{d}}$ erfüllt, das heißt, es gilt ${\displaystyle \varphi _{d}\vDash \psi }$ im Widerspruch zur gemachten Voraussetzung. Es muss daher ${\displaystyle \varphi _{d}\vDash \neg \psi }$ gelten.

Ehrenfeucht-Fraïssé-Spiele: Charakterisierung der elementaren Äquivalenz mittels einer spieltheoretischen Deutung der endlichen Isomorphie.

• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg/Berlin/Oxford 1996, ISBN 3-8274-0130-5, insbesondere Kapitel XII