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

Mathematische Logik
Modelltheorie
Fraisse, Satz von