Satz von Fraïssé

mathematischer Satz

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

Literatur

Bearbeiten
  • 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