Satz von Fraïssé

Der Satz von Fraïssé, benannt nach Roland Fraïssé, ist ein Satz aus der mathematischen Logik. Ist S eine endliche Symbolmenge, so charakterisiert er die elementare Äquivalenz zweier S-Strukturen auf rein algebraische Weise, ohne Bezug auf die Prädikatenlogik erster Stufe zu nehmen.

Endliche Isomorphie

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

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

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

$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 $R\in S$ ein n-stelliges Relationssymbol und sind $a_1,\ldots, a_n \in \mathrm{def}(h)$, so gilt

$R^{\mathcal{A}}(a_1,\ldots, a_n) \quad \Leftrightarrow \quad R^{\mathcal{B}}(h(a_1),\ldots, h(a_n))$.

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

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

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

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

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

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

Formulierung des Satzes

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 S und für zwei S-Strukturen $\mathcal{A}$ und $\mathcal{B}$ sind äquivalent:

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

Anwendung

Zur Verdeutlichung der Begriffe wollen wir den Satz von Fraïssé beispielhaft auf die Theorie der dichten Ordnungen anwenden. Eine geordnete Menge (X, < ) mit mindestens zwei Elementen heißt dicht, falls es keine kleinsten und größten Elemente gibt und falls zwischen je zwei verschiedenen Elementen ein drittes liegt. Die Theorie der dichten Ordnungen wird daher durch die folgenden Sätze der Sprache $L_I^{\{<\}}$ definiert:

$\forall x\,(\neg x<x)$

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

$\exists x\, y\,(x<y)$

$\forall x\,\exist y\,(y<x)$

$\forall x\,\exist y\,(x<y)$

$\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, der dritte besagt, dass die Ordnungsrelation nicht leer ist, und die letzten drei geben offenbar die Definition der Dichheit wieder. Es sei φ_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 $h:\mathcal{A}\rightarrow\mathcal{B}$ mit endlichem Definitionsbereich lässt sich zu einem weiteren partiellen Isomorphismus auf ein beliebiges Element fortsetzen. Ist etwa $\mathrm{def}(h) = \{a_1,\ldots, a_n\}$ und ist $a\in \mathcal{A}$ ein weiteres Element, so kann man wegen der Dichtheit von $\mathcal{B}$ ein Element $b\in\mathcal{B}$ finden, das zu $h(a_1),\ldots, h(a_n)$ in den selben Größenbeziehungen steht wie a zu $a_1,\ldots, a_n$. Die Festlegung

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

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

$I_n := \{ h:\mathcal{A}\rightarrow\mathcal{B};\, h \mbox{ partieller Isomorphismus mit endlichem Definitionsbereich}\}$,

so definiert $(I_n)_{n\in \N}$ eine endliche Isomorphie zwischen $\mathcal{A}$ und $\mathcal{B}$. Je zwei { < }-Strukturen, die φ_d erfüllen, sind also endlich isomorph. Damit ist auch die oben behauptete endliche Isomorphie zwischen $(\R,<)$ und $(\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 { < }-Satz ψ gilt $\varphi_d \vDash \psi$ oder $\varphi_d \vDash \neg\psi$.

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

Siehe auch

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

Literatur

• 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