Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 16

Aus Wikiversity
Zur Navigation springen Zur Suche springen



-Homomorphismen und elementare Äquivalenz

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 16.3. 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 Satz 12.3 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 16.6.


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 Lemma 16.6 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.



Elementare Äquivalenz für Elemente

Inwiefern kann man die einzelnen Elemente in einer gegebenen -Struktur mit der durch gegebenen Sprache einzeln adressieren bzw. voneinander unterscheiden? Zur Präzisierung dieser Fragestellung dient das Konzept der elementaren Äquivalenz für Elemente.


Definition  

Es sei ein erststufiges Symbolalphabet und eine -Struktur. Wir nennen zwei Elemente elementar äquivalent, wenn für jeden Ausdruck in der einen freien Variablen und jede Variablenbelegung auf die Beziehung

gilt.

Die elementare Äquivalenz drücken wir durch aus. Dabei handelt es sich offenbar um eine Äquivalenzrelation auf der Menge . Wenn

ein -Isomorphismus (also ein Automorphismus) ist, der auf abbildet, so müssen die beiden Elemente elementar äquivalent sein, wie aus Satz 16.7 für eine beliebige Interpretation mit und folgt.


Beispiel  

Es sei ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol besteht und es sei eine -Struktur, wobei als die Permutation mit

interpretiert werde. Hier sind die Äquivalenzklassen zur elementaren Äquivalenz gleich der sogenannten Zykelzerlegung, nämlich gleich , und . Die Ordnung der Elemente kann man in der Sprache zu ausdrücken und erhält dadurch trennende Ausdrücke, beispielsweise ist ein Ausdruck in der einen freien Variablen , der genau dann wahr wird, wenn durch belegt wird. Der Ausdruck

ist ein Ausdruck, der genau dann wahr wird, wenn durch oder belegt wird, u.s.w. Dass oder zueinander elementar äquivalent sind, sieht man am einfachsten, wenn man den Automorphismus betrachtet, der durch die Transposition gegeben ist. Dieser ist nämlich ein -Automorphismus und daher können wir des Isomorphiesatz anwenden.



Beispiel  

Wenn man in der Definition 16.8 auch Ausdrücke in mehreren freien Variablen zulassen würde, so wären Elemente nur mit sich selbst äquivalent. Betrachten wir dazu den Ausdruck , den wir nennen, und zwei Elemente aus . In der Interpretation sei durch belegt. Dann gilt , denn dies bedeutet , aber , denn dies bedeuet .


Für eine Konstante in , die in als das Element interpretiert wird, ist die zugehörige Äquivalenzklasse einelementig: Sie wird durch den Ausdruck in der einen freien Variablen charakterisiert, der offenbar nur bei der Belegung von durch wahr wird. Wir fragen uns, ob es für jede Äquivalenzklasse zur elementaren Äquivalenz einen solchen charakterisierenden Ausdruck (oder trennenden Ausdruck) in einer freien Variablen gibt.



Lemma  

Es sei ein Symbolalphabet erster Stufe und eine -Struktur mit der Eigenschaft, dass es in nur endlich viele Klassen zur elementaren Äquivalenz gibt.

Dann gibt es zu jeder Äquivalenzklasse einen -Ausdruck in einer freien Variablen , der die Klasse beschreibt, für den also

gilt.

Beweis  

Es seien die Äquivalenzklassen der elementaren Äquivalenzrelation und sei ein fest gewählter Repräsentant. Wir zeigen, dass es für einen solchen trennenden Ausdruck gibt. Zu jedem gibt es einen Ausdruck in der freien Variablen mit , aber , da ja und nicht elementar äquivalent sind. Wir können annehmen, dass die relevante Variable in jedem dieser Ausdrücke die gleiche ist. Der konjugierte Ausdruck

ist in einer Interpretation (zur -Struktur ) genau dann wahr, wenn die Variable durch ein Element aus belegt wird.



Beispiel  

Für das Symbolalphabet und die natürlichen Zahlen mit der kanonischen Interpretation sind sämtliche Klassen zur elementaren Äquivalenz einelementig und können auch durch Ausdrücke charakterisiert werden, und zwar wird die Zahl durch den Ausdruck mit Strichen eindeutig beschrieben.



Beispiel  

Es sei das Symbolalphabet, das außer Variablen für jedes ein einstelliges Relationssymbol enthält, und es sei

Wir betrachten die Menge , wobei wir das Relationssymbol durch

interpretieren. Zwei Elemente können dann nicht elementar äquivalent sein, da sie sich nicht gegenseitig teilen können und daher beispielsweise , also , aber nicht , also , gilt. Die Äquivalenzklassen sind also einelementig. Es ist aber nicht möglich, diese Klassen durch einen Ausdruck in dieser Sprache zu charakterisieren, da die Gültigkeitsmengen zu jedem Ausdruck entweder leer sind oder unendlich viele Elemente enthalten, siehe Aufgabe 17.8.




Lemma  

Es sei ein Symbolalphabet erster Stufe und eine -Struktur. Für jede elementare Äquivalenzklasse gebe es einen -Ausdruck in einer freien Variablen , der die Klasse beschreibt, für den also

gilt.

Dann gelten folgende Aussagen.

  1. Für jedes -stellige Relationssymbol ist auf den Äquivalenzklassen wohldefiniert.
  2. Für jedes -stellige Funktionssymbol ist auf den Äquivalenzklassen wohldefiniert (und zwar in dem Sinn, dass aus die elementare Äquivalenz folgt).

Beweis  

(1). Es sei ein -stelliges Relationssymbol. Für ein -Tupel aus mit und ein weiteres dazu elementar-äquivalentes Tupel (es gelte also ) müssen wir zeigen. Es seien Ausdrücke in der einen freien (untereinander verschiedenen) Variablen , die die Äquivalenzklassen zu bzw. charakterisieren. Es gilt

wie ja die Belegung von durch zeigt. Ebenso gilt

wie die entsprechende Belegung zeigt. Dies ist jetzt ein Ausdruck in der einen freien Variablen . Wenn man statt mit durch ein anderes elementar äquivalentes Element belegt, so erhält man nach Definition der elementaren Äquivalenz

und damit

Somit hat man den ersten Existenzquantor durch einen Allquantor ersetzt. In dieser Weise fährt man mit den anderen Existenzquantoren fort und erhält schließlich

Einsetzen von für liefert also, da ja auf zutrifft,

und somit .

(2). Die Aussage für Funktionssymbole wird ähnlich bewiesen, siehe Aufgabe 17.6.


<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2014) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)