Endliche Menge/Elementare Äquivalenz/Isomorphie/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wir möchten zeigen, dass bei endlichen Mengen die elementare Äquivalenz den Isomorphietyp bereits festlegt. Wir besprechen zunächst einige typische Beispiele, die als Orientierung für den komplexen Beweis dienen sollen.


Beispiel  

Es sei ein Symbolalphabet, das ausschließlich aus (abzählbar unendlich vielen) Variablen bestehe. Zwei endliche -Mengen und sind genau dann elementar äquivalent, wenn sie die gleiche Anzahl an Elementen haben, denn die Elementanzahl kann man durch einen erststufigen Ausdruck aus ausdrücken. In diesem Fall gibt es eine Bijektion zwischen und und diese ist ein -Isomorphismus.



Beispiel  

Das Symbolalphabet bestehe (neben Variablen) aus einem einstelligen Funktionssymbol . Die Ausdrucksmenge bestehe aus einem Satz, der inhaltlich besagt, dass eine erfüllende Menge genau Elemente besitzen muss, und einen Satz, der besagt, dass die Funktion bijektiv ist. Ein Modell für ist also eine -elementige Menge zusammen mit einer fixierten Permutation

auf dieser Menge. Eine Teilmenge der Form (wir schreiben statt )

mit und mit für alle , , nennt man Zykel zu der Länge . Die Menge ist die disjunkte Vereinigung von Zykeln unterschiedlicher Länge. Zwei Elemente sind genau dann elementar äquivalent, wenn sie beide in einem gleichlangen (aber nicht unbedingt im gleichen) Zykel liegen: Einerseits lässt sich die Zykellänge erststufig formalisieren, etwa durch

wobei die Potenzen ausgeschrieben werden müssen. Andererseits kann man einfach Automorphismen angeben, indem man aus jedem Zykel ein Element auswählt und dieses auf ein beliebiges Element eines Zykels gleicher Länge schickt, wobei jeder Zykel genau einmal getroffen wird. Durch

erhält man einen wohldefinierten Automorphismus. Insbesondere kann man einen Automorphismus konstruieren, der auf abbildet. Wenn man auf (elementar äquivalent zu ) abbilden möchte, so ist dadurch schon bestimmt, wohin man die Elemente aus dem Zyklel zu abbilden muss. Es muss nämlich , , u.s.w. gelten.



Beispiel  

Wir betrachten das Symbolalphabet , das neben Variablen aus einer Konstanten und einem zweistelligen Funktionssymbol besteht. Wir betrachten die Gruppe mit der natürlichen -Struktur. Die elementaren Äquivalenzklassen sind durch die Ordnung der Elemente gegeben. Die Klassen sind

Bei einen -Automorphismus auf müssen die einelementigen Klassen auf sich selbst abgebildet werden, bei den anderen hat man gewisse Freiheiten. Allerdings gibt es Abhängigkeiten zwischen den Wahlmöglichkeiten auf den größeren Klassen. Wenn man auf abbilden möchte, so muss man zunächst auf abbilden. Wenn man diese partielle Abbildung

fortsetzen möchte, so muss man beispielsweise wegen auf oder auf abbilden, die Werte oder sind ausgeschlossen.



Beispiel  

Es sei ein Symbolalphabet und eine -Struktur mit der Eigenschaft, dass jede Äquivalenzklasse zur elementaren Äquivalenz einelementig sei. Wenn eine weitere, zu elementar äquivalente -Struktur ist, so hat auch diese einelementige Äquivalenzklassen. Die einzige Möglichkeit für einen -Isomorphismus ist dann, ein Element auf das einzige Element abzubilden, das den entsprechenden charakteristischen Ausdruck erfüllt. Es muss dann allerdings begründet werden, dass es sich wirklich um einen Homomorphismus handelt.


Aus den Überlegungen der letzten Vorlesung erhalten wir das folgende Resultat. Im Beweis arbeiten wir mit folgender Definition.


Definition  

Es sei ein erststufiges Symbolalphabet umd eine -Struktur. Eine Teilmenge heißt funktional abgeschlossen (oder eine -Unterstruktur), wenn für jede Konstante das Element zu gehört und für jedes -stellige Funktionssymbol und beliebige Elemente auch zu gehört.

Unter einem formal-zusammengesetzten Funktionssymbol (oder Funktionssymbolbaum) versteht man die Elemente der folgenden rekursiv festgelegten Menge (innerhalb der Menge von Stammbäumen).

  1. Jedes Funktionssymbol (einschließlich der Konstanten) gehört dazu.
  2. Wenn ein -stelliges Funktionssymbol ist und formal-zusammengesetzte Funktionssymbole sind, so ist auch der Stammbaum (nicht die Symbolkette) ein formal-zusammengesetztes Funktionssymbol.

Ein formal-zusammengesetztes Funktionssymbol besitzt eine natürliche Stelligkeit. Bei einer Interpretation mit Grundmenge wird ein formal-zusammengesetztes Funktionssymbol als Hintereinanderschaltung der beteiligten Abbildungen interpretiert, wofür wir wieder schreiben. Eine funktional abgeschlossene Menge ist auch unter jeder formal-zusammengesetzten Funktion abgeschlossen, siehe Aufgabe und zu einer Startmenge besteht die kleinste funktional abgeschlossene Teilmenge, die enthält, genau aus den Werten der formal-zusammengesetzten Funktionen mit Argumenten aus (man nennt dies die funktionale Hülle von ). Wenn man mit einem Element startet, und nur ein einstelliges Funktionssymbol zur Verfügung hat, so besteht die funktionale Hülle einfach aus .



Satz  

Es sei ein Symbolalphabet und es seien und -Strukturen, wobei endlich sei.

Dann sind und genau dann elementar äquivalent, wenn sie zueinander isomorph sind.

Beweis  

Dass eine Isomorphie elementare Äquivalenz impliziert, wurde in Fakt bewiesen. Für die Umkehrung seien also die beiden Strukturen elementar äquivalent, und habe Elemente. Dann gilt in die Aussage

und die entsprechende Aussage für gilt nicht. Aufgrund der elementaren Äquivalenz gilt diese Aussage (bzw. die entsprechende Aussage) auch (nicht) in . D.h. ist ebenfalls endlich mit Elementen.

Wir konstruieren nun sukzessive Teilmengen , wobei die funktional abgeschlossen sind, und Abbildungen

mit und derart, dass die für jedes Isomorphismen zwischen und sind.

Wir wählen beliebig und setzen als die kleinste, funktional abgeschlossene Teilmenge in an, die enthält. Nach Fakt gibt es einen Ausdruck in einer freien Variablen, der die elementare Äquivalenzklasse beschreibt. Wir wählen ein Element aus der entsprechenden Äquivalenzklasse in (und diese ist nicht leer wegen der elementaren Äquivalenz zwischen und ) und setzen

Für jedes formal-zusammengesetzte Funktionssymbol definieren wir (hierbei wird überall bzw. eingesetzt)

Diese Abbildung ist wohldefiniert. Ist nämlich

so gilt in

da dies für gilt und daher auch für alle dazu elementar äquivalenten Elemente, und da für die dazu nicht elementar äquivalenten Elemente der Vordersatz nicht gilt. Diese Aussage gilt dann auch bei Interpretation über . Daher ist

Wir müssen zeigen, dass ein Homomorphismus vorliegt. Die Verträglichkeit mit den Funktionssymbolen folgt unmittelbar aus der Definition der Abbildung. Ferner wird jedes Element zu einem Element aus der entsprechenden Äquivalenzklasse abgebildet. Nach (dem Beweis zu) Fakt und wegen der elementaren Äquivalenz berücksichtigt daher die Relationen. Dies gilt in beide Richtungen, d.h. eine Relation trifft auf ein Tupel genau dann zu, wenn dies auf das Bildtupel zutrifft. Die Abbildung ist injektiv: Zu zwei Elementen gibt es zusammengesetzte Funktionssymbole und mit und Bei gilt

da dies bei Interpretation von durch gilt, und diese Aussage gilt auch in . Die Abbildung ist surjektiv auf das Bild, also liegt wegen der Äquivalenz bei den Relationen insgesamt ein Isomorphismus vor.

Es seien nun und schon konstruiert und . Wir wählen und setzen als die funktionale Hülle von an. Wir betrachten die Menge aller Tupel , wobei ein Ausdruck in den freien Variablen und ist und wobei mit der Eigenschaft, dass

gilt. Dabei sei eine fixierte Interpretation auf und entsprechend eine Interpretation auf . Es gilt dann insbesondere

Daher gilt nach Fakt (angewendet auf den Isomorphismus mit ) auch

und insbesondere gibt es ein (zunächst von abhängiges) mit

Dann gibt es auch ein , das man für alle nehmen kann. Für jedes einzelne ist nämlich die erfüllende Elementmenge nicht leer, und wenn der Durchschnitt über alle leer wäre, dann schon für eine endliche Teilmenge und dann auch für die endliche Konjunktion darüber. Sei ein solches Element. Wir setzen nun

und definieren

für jedes -stellige formal zusammengesetzte Funktionssymbol . Die Wohldefiniertheit von , die Verträglichkeit mit den Funktionssymbolen und mit den Relationssymbolen (in beide Richtungen) sowie die Bijektivität und damit die Isomorphieeigenschaft folgt wie oben.

Da endlich ist, erhalten wir, wenn wir diesen Konstruktionsschritt iterieren, insgesamt eine injektive Abbildung

Da und gleich viele Elemente besitzen, ist diese auch surjektiv und insgesamt erhalten wir einen Isomorphismus.


Das im Beweis beschriebene Verfahren zur Konstruktion eines Isomorphismus ist grundsätzlich konstruktiv.