Satz von Fraïssé

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

Endliche Isomorphie

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

Sind und -Strukturen, so heißt eine Abbildung ein partieller Isomorphismus von nach , wenn folgendes gilt:

  • ist eine Abbildung mit Definitionsbereich und Bildmenge .
  • ist injektiv.
  • Ist ein Konstantensymbol, so gilt:
    • Ist , so ist .
    • Ist , so ist und .
  • Ist ein -stelliges Funktionssymbol und sind , so gilt
.
  • Ist ein -stelliges Relationssymbol und sind , so gilt
.

Dabei sind die Interpretationen der Symbole im Modell . Man verwendet bei einem partiellen Isomorphismus auch die für Abbildungen übliche Schreibweise und meint damit nur, dass der Definitionsbereich gemäß obiger Definition in enthalten ist.

Ist ein partieller Isomorphismus, so offenbar auch , wobei und . Ist weiter eine Teilmenge, so ist auch die Einschränkung ein partieller Isomorphismus und es ist .

Zwei -Strukturen und heißen endlich isomorph, wenn es eine Folge von nicht-leeren Mengen partieller Isomorphismen gibt, so dass folgende Fortsetzungseigenschaften erfüllt sind:

  • Zu jedem und gibt es ein mit und .
  • Zu jedem und gibt es ein mit und .

Ein partieller Isomorphismus lässt sich also -mal auf beliebige Elemente zu einem partiellen Isomorphismus fortsetzen, und zwar der Reihe nach zu partiellen Isomorphismen aus ; und für gilt das ebenfalls.

Sind und zwei isomorphe Strukturen und ist ein Isomorphismus, so sind und auch endlich isomorph, denn obige Definition ist mit für alle erfüllt. Die Umkehrung gilt nicht; weiter unten wird bewiesen, dass die geordnete Mengen und , die Symbolmenge ist hier , 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 und für zwei -Strukturen und sind äquivalent:

  • und sind elementar äquivalent.
  • und sind endlich isomorph.

Anwendung

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 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 definiert:

.

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

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 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 mit endlichem Definitionsbereich lässt sich zu einem weiteren partiellen Isomorphismus auf ein beliebiges Element fortsetzen. Ist etwa und ist ein weiteres Element, so kann man wegen der Dichtheit von ein Element finden, das zu in denselben Größenbeziehungen steht wie zu . Die Festlegung

definiert dann einen partiellen Isomorphismus , der auf das Element fortsetzt. Dasselbe gilt für , da auch dicht ist. Setzt man daher

,

so definiert eine endliche Isomorphie zwischen und . Je zwei -Strukturen, die erfüllen, sind also endlich isomorph. Damit ist auch die oben behauptete endliche Isomorphie zwischen und 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 oder .

Zum Beweis sei , wir müssen zeigen. Wir tun dies indirekt, indem wir annehmen, dass es ein Modell gibt, das erfüllt, aber nicht . Dann ist eine dichte Ordnung, da es ja erfüllt, die nicht erfüllt und daher ein Modell für sein muss. Da aber alle dichten Ordnungen nach obigem elementar äquivalent sind und daher dieselben Sätze erfüllen, folgt für jedes Modell, das erfüllt, das heißt, es gilt im Widerspruch zur gemachten Voraussetzung. Es muss daher 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