Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Vorlesung 16
- -Homomorphismen und elementare Äquivalenz
In der Mathematik spielen strukturerhaltende Abbildungen eine herausragende Rolle. Eine erststufige Version dieses Konzeptes kommt in folgender Definition zum Ausdruck.
Es sei ein erststufiges Symbolalphabet und und seien - Strukturen. Eine Abbildung
heißt -Homomorphismus, wenn folgende Eigenschaften gelten.
- Für jede Konstante
ist
- Für jedes -stellige Funktionssymbol
ist
für alle .
- Für jedes -stellige Relationsymbol
impliziert die Gültigkeit von
die Gültigkeit von
Die üblichen Begriffe der Mathematik, beispielsweise ein Gruppenhomomorphismus, ein Ringhomomorphismus, eine lineare Abbildung zwischen Vektorräumen, eine monotone Abbildung zwischen geordneten Mengen, fallen unter diesen abstrakten Homomorphiebegriff.
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.
Es sei ein erststufiges Symbolalphabet, das nur aus einer Variablenmenge besteht, die Konstantenmenge und die Mengen der Funktionssymbole und der Relationssymbole seien also leer. Dann ist jede (nichtleere) Menge unmittelbar eine - Struktur und jede Abbildung
ist ein - Homomorphismus. Insbesondere ist jede bijektive Abbildung
ein - Isomorphismus.
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, siehe Satz 47.1 (Grundkurs Mathematik (Osnabrück 2018-2019)). 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 .
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
- Elementare Äquivalenz und Isomorphiesatz
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. Die folgende Aussage heißt Isomorphiesatz (oder Isomorphielemma).
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
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.5 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.
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. Zu zwei nicht elementaar äquivalenten Elementen nennen wir einen Ausdruck mit und einen trennenden Ausdruck.
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 den Isomorphiesatz anwenden.
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 in einer freien Variablen gibt.
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.
Es seien die Äquivalenzklassen der elementaren Äquivalenzrelation und sei ein fest gewählter Repräsentant. Wir zeigen, dass es für einen solchen charakterisierenden 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.
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.
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 16.25.
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.
- Für jedes -stellige Relationssymbol ist auf den Äquivalenzklassen wohldefiniert.
- Für jedes -stellige Funktionssymbol ist auf den Äquivalenzklassen wohldefiniert (und zwar in dem Sinn, dass aus die elementare Äquivalenz folgt).
(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 16.32.
<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2021) | >> |
---|