Prädikatenlogik/Elementare Äquivalenz/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Zwei -Strukturen und über einem erststufigen Symbolalphabet heißen elementar äquivalent, wenn jeder -Satz, der in gilt, auch in gilt.

Dies bedeutet, dass in den beiden Strukturen überhaupt die gleichen Sätze gelten.

In der Mathematik spielen strukturerhaltende Abbildungen eine herausragende Rolle. Eine erststufige Version dieses Konzeptes kommt in folgender Definition zum Ausdruck.


Definition  

Es sei ein erststufiges Symbolalphabet und und seien -Strukturen. Eine Abbildung

heißt -Homomorphismus, wenn folgende Eigenschaften gelten.

  1. Für jede Konstante ist
  2. Für jedes -stellige Funktionssymbol ist

    für alle .

  3. Für jedes -stellige Relationsymbol impliziert die Gültigkeit von

    die Gültigkeit von

Die üblichen Begriffe der Mathematik, beispielsweise ein Gruppenhomomorphismus, eine Ringhomomorphismus, eine lineare Abbildung zwischen Vektorräumen, eine monotone Abbildung zwischen geordneten Mengen, fallen unter diesen abstrakten Homomorphiebegriff.


Definition  

Es sei ein erststufiges Symbolalphabet und und seien -Strukturen. Eine bijektive Abbildung

heißt -Isomorphismus, wenn sowohl als auch die Umkehrabbildung ein -Homomorphismus ist.

Zwei -Strukturen heißen -isomorph, wenn es einen -Isomorphismus zwischen ihnen gibt. Bei spricht man auch von einem Automorphismus.


Beispiel  

Es sei ein erststufiges Symbolalphabet, das nur aus einer Variablenmenge besteht, die Konstantenmenge und die Mengen der Funktionssymbole und der Relationssymbole seinen also leer. Dann ist jede (nichtleere) Menge unmittelbar eine -Struktur und jede Abbildung

ist ein -Homomorphismus. Insbesondere ist jede bijektive Abbildung

ein -Isomorphismus.


Bemerkung  

Es sei ein erststufiges Symbolalphabet und und seien -Strukturen. Eine bijektive Abbildung

die ein -Homomorphismus ist, muss kein -Isomorphismus sein, da die Umkehrabbildung im Allgemeinen kein Homomorphismus sein muss. Deshalb fordert man in der Definition eines Isomorphismus explizit die Homomorphie der Umkehrabbildung. Wenn allerdings das Symbolalphabet keine Relationssymbole enthält, so ist die Umkehrabbildung automatisch ein Homomorphismus, siehe Aufgabe. Ein Extremfall liegt, vor, wenn ein Relationssymbol in als die leere Relation interpretiert wird. Dann verhält sich bezüglich dieses Relationssymbols -homomorph, unabhängig von der Interpretation von auf .


Wir haben in Fakt gesehen, dass je zwei Modelle der (allerdings nicht erststufig formulierten) Dedekind-Peano-Axiome zueinander isomorph sind. Dabei war die einzige Konstante und die Nachfolgerabbildung die einzige (einstellige) Funktion. Auch zwei Modelle der reellen Zahlen sind isomorph, was schwieriger zu beweisen ist. Die zugehörigen Axiomensysteme legen also das intendierte Modell bis auf Isomorphie fest, und zwar ist sogar jeweils der Isomorphismus eindeutig bestimmt. Letzteres gilt beispielsweise für die komplexen Zahlen nicht. Die komplexen Zahlen können als algebraischer Abschluss von eingeführt werden. Je zwei solche algebraische Abschlüsse sind untereinander isomorph, allerdings ist die Isomorphie nicht eindeutig bestimmt. Beispielsweise ist die komplexe Konjugation ein nichttrivialer Automorphismus auf .



Lemma

Es sei ein erststufiges Symbolalphabet, und seien -Strukturen und

ein -Homomorphismus. Es sei eine Variablenbelegung in und die nach übertragene Variablenbelegung. Es seien und die zugehörigen Interpretationen.

Dann ist

für alle -Terme .

Beweis

Siehe Aufgabe.


Die folgende Aussage heißt Isomorphiesatz (oder Isomorphielemma).



Satz  

Es seien und isomorphe -Strukturen über einem Symbolalphabet .

Dann sind und elementar äquivalent.

Genauer: Zu einem Isomorphismus

und einer Variablenbelegung auf und der zugehörigen Variablenbelegung auf mit den zugehörigen Interpretationen und gilt für jeden -Ausdruck die Äquivalenz

Beweis  

Wir beweisen den Zusatz durch Induktion über den Aufbau der Ausdrücke, woraus sich dann die Hauptaussage, die unabhängig von Belegungen ist, ergibt. Es sei ein Isomorphismus

fixiert. Nach Fakt respektiert der Isomorphismus die Interpretation aller Terme. Da die Situation symmetrisch ist, müssen wir lediglich zeigen, dass aus der Gültigkeit von die Gültigkeit von folgt. Für einen Ausdruck der Form

mit Termen bedeutet

einfach

Daher ist

und somit

Für ein -stelliges Relationssymbol und Terme bedeutet

dass auf zutrifft. Dann trifft aufgrund der Homomorphie von auch auf

zu. Also ist

Wir kommen zum Induktionsschluss. Bei , und folgt die Aussage aus der Induktionsvoraussetzung, wobei man bei der Negation und der Implikation verwendet, dass eine Äquivalenz bewiesen wird.

Für eine Existenzaussage bedeutet

dass es ein derart gibt, dass

gilt. Es sei

Nach der Induktionsvoraussetzung, angewendet auf und die Interpretation , die zu in der gleichen Beziehung steht wie zu (d.h. die Variablenbelegungen sind durch miteinander verbunden) gilt

Dies impliziert


Für die meisten Axiomensysteme in der Mathematik gibt es natürlich verschiedene nicht isomorphe und im Allgemeinen auch nicht elementar äquivalente Modelle. Es gibt beispielsweise eine Vielzahl an Gruppen, die - nach Definition - alle die Gruppenaxiome erfüllen, die aber ansonsten wenig miteinander zu tun haben. Interessanter ist die Frage, ob es, wenn man ein Axiomensystem für ein bestimmtes intendiertes Modell aufstellt, es dieses bis auf Isomorphie festlegt (oder ob es nichtisomorphe Modelle gibt) oder ob es die Menge aller gültigen elementaren Aussagen vollständig festlegt, also ob alle im intendierten Modell gültigen Sätze aus dem Axiomensystem ableitbar sind.