Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Vorlesung 17/kontrolle

Aus Wikiversity



Isomorphie und elementare Äquivalenz im endlichen Fall

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  Referenznummer erstellen

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  Referenznummer erstellen

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  Referenznummer erstellen

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  Referenznummer erstellen

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  Referenznummer erstellen

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 17.6 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  Satz 17.6 ändern

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 Satz 16.7 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 Lemma 16.11 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) Lemma 16.14 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 Satz 16.7 (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. Es 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.



Nichtstandardmodelle

Definition  Referenznummer erstellen

Es sei eine fixierte - Struktur (das Standardmodell) über einem Symbolalphabet . Dann nennt man eine weitere -Struktur , die zu elementar äquivalent, aber nicht zu - isomorph ist, ein Nichtstandardmodell von .

Bemerkung   Referenznummer erstellen

So formuliert ist diese Definition für jedes Modell anwendbar. Man verwendet sie aber eigentlich nur dann, wenn ein wohlbestimmtes „prominentes“ Modell ausgezeichnet ist. Das Standardmodell ist dann in der Regel durch den Kontext festgelegt. Im zahlentheoretischen Kontext ist das Standardmodell, die entsprechenden Nichtstandardmodelle heißen Nichtstandardmodelle der Arithmetik, die Untersuchung solcher Modelle heißt Nichtstandardarithmetik. Im analytschen Kontext sind die reellen Zahlen das Standardmodell, die entsprechenden Nichtstandardmodelle heißen Nichtstandardmodelle der reellen Zahlen; man spricht von Nichtstandardanalysis.


Es ist keineswegs selbstverständlich, dass es Nichtstandardmodelle gibt. Dies ergibt sich, und zwar ganz allgemein für jede unendliche Struktur, aus einer Reihe von Überlegungen, die an den Vollständigkeitssatz anschließen. Ein wesentlicher Punkt ist dabei, dass man zwar die Unendlichkeit eines Modells durch ein erststufiges Axiomenschema beschreiben kann, nicht aber erststufig verschiedene Mächtigkeiten unterscheiden kann. Zu beschreibt die Aussage

dass es mindestens verschiedene Elemente gibt (d.h. diese Aussage ist interpretiert in einem Modell genau dann richtig, wenn mindestens Elemente besitzt). Die Ausdrucksmenge

beschreibt daher die Unendlichkeit einer Menge. Aufgabe 15.18 zeigt, dass es Nichtstandardmodelle der Arithmetik gibt (siehe auch Korollar 15.11) und Aufgabe 15.17 zeigt (das Argument werden wir gleich wiederholen), dass es abzählbare Modelle gibt, die zu den reellen Zahlen elementar äquivalent sind. Man spricht von reell-abgeschlossenen Körpern.



Reell-abgeschlossene Körper

Beispiel  Referenznummer erstellen

Die Symbolmenge bestehe aus (und abzählbar unendlich vielen Variablen), die in den reellen Zahlen in natürlicher Weise interpretiert werden. Die Ausdrucksmenge

ist somit widerspruchsfrei. Der Beweis zu Lemma 15.3 zeigt, dass es dann eine abzählbare Symbolerweiterung und eine -Ausdrucksmenge gibt, die Beispiele enthält (es ist nicht selbstverständlich, ob selbst Beispiele enthält. Da es überabzählbar viele reelle Zahl gibt, liegt nicht jede reelle Zahl im Bild der Terminterpretation, so dass man Lemma 14.5 nicht anwenden kann), und die nach Lemma 15.4 zu einer maximal widerspruchsfreien Ausdrucksmenge ergänzt werden kann. Nach dem Satz von Henkin gibt es ein erfüllendes Modell, das aus Identifizieren von Termen entsteht. Da die Termmenge abzählbar ist, ist auch dieses Modell abzählbar. Es gibt daher ein abzählbares Nichtstandardmodell der reellen Zahlen.


Die Menge der rationalen Zahlen bilden einen abzählbaren angeordneten Körper, aber kein Nichtstandardmodell der reellen Zahlen, da ja beispielsweise die Aussage in gilt, aber nicht in . Wichtige erststufige Aussagen, die in und damit auch in jedem Nichtstandardmodell gelten, fassen wir in folgender Proposition zusammen.


Proposition  Referenznummer erstellen

Für die reellen Zahlen gelten folgende Aussagen über dem Symbolalphabet[1]

  1. Die Axiome eines[2] angeordneten Körpers.
  2. Für jedes ungerade gilt
  3. Für jedes gerade gilt
  4. Für jeden -Ausdruck in einer freien Variablen gilt
  5. Für jeden -Ausdruck in einer freien Variablen gilt

Beweis  

(1) ist in der Axiomatik der reellen Zahlen enthalten.
(2) folgt aus dem Zwischenwertsatz, der Stetigkeit von Polynomen und dem Verhalten von Polynomen von ungeradem Grad gegen .
(3) folgt aus wiederholter Anwendung von [[Reelle positive Zahl/Quadratwurzel/Eindeutige Existenz/Fakt|Kurs:Analysis (Osnabrück 2021-2023)/Reelle positive Zahl/Quadratwurzel/Eindeutige Existenz/Fakt/Faktreferenznummer (Analysis (Osnabrück 2021-2023))]] und Teil (2).
(4) ist eine Formulierung von Satz 7.5 (Analysis (Osnabrück 2021-2023)) für solche Teilmengen, die in der ersten Stufe beschrieben werden können.
(5) folgt aus dem Dedekindschen Schnittaxiom.


Diese Eigenschaften (insbesondere die beiden letzten) sind ein erststufiger Ersatz für die Vollständigkeit (ähnlich wie das Axiomenschema der Induktion in den erststufigen Peano-Axiomen ein Ersatz für die zweitstufige Induktion der Dedekind-Peano Axiome ist). Das Archimedes-Axiom, also dass es zu jeder reellen Zahl eine natürliche Zahl gibt, lässt sich nicht erststufig charakterisieren, da dies für die natürlichen Zahlen nicht möglich ist. Wir betrachten zu den Ausdruck

wobei durch die -fache Addition der mit sich selbst repräsentiert wird. Eine Aussage wie „“, was nichtarchimedisch bedeutet ( soll hier eine natürliche Zahl sein), ist nicht erststufig formulierbar.


Beispiel  Referenznummer erstellen

Die Symbolalphabet bestehe aus den Zeichen (und abzählbar unendlich vielen Variablen), die in den reellen Zahlen in natürlicher Weise interpretiert werden. Die Ausdrucksmenge

ist somit widerspruchsfrei. Wir betrachten für den Ausdruck

Es sei die Vereinigung von mit . Jede endliche Teilmenge von ist erfüllbar (nämlich in ), also ist nach Korollar 15.10 auch erfüllbar. Es gibt also eine -Struktur , in der alle erststufigen Sätze von gelten und auch alle bei geeigneter Belegung gelten, d.h. es gibt ein Element , das jenseits jeder natürlichen Zahl liegt. Insbesondere ist ein nicht-archimedisch angeordneter Körper.



Definition  Referenznummer erstellen

Ein angeordneter Körper heißt reell-abgeschlossen, wenn folgende Eigenschaften gelten.

  1. Jedes nichtnegative Element aus besitzt eine Quadratwurzel in .
  2. Jedes Polynom mit ungeradem Grad besitzt in eine Nullstelle.

Man kann zeigen, dass ein reell-abgeschlossener Körper elementar äquivalent zu den reellen Zahlen ist und insbesondere die oben angeführten Eigenschaften besitzt. Eine wichtige Eigenschaft ist ferner, dass algebraisch abgeschlossen ist (d.h. durch Hinzunahme eines Elementes mit wird der Körper algebraisch abgeschlossen). Ein (abzählbares Modell) eines reell-abgeschlossenen Körpers sind die reellen algebraischen Zahlen, also alle reellen Zahlen, die Nullstelle eines Polynoms mit rationalen Koeffizienten sind. Dies ist zugleich der kleinste reell-abgeschlossene Körper. Da die Zahlen und transzendent sind, folgt, dass diese Zahlen nicht erststufig charakterisierbar sind. Eine Besonderheit der Theorie der reell-abgeschlossenen Körper ist, dass es dafür eine Entscheidungsprozedur gibt, d.h. es gibt einen maschinell durchführbaren Algorithmus, die Quantorenelimination, der für jeden Ausdruck über der erststufigen Sprache zur Symbolmenge entscheidet, ob aus den Axiomen ableitbar ist (äquivalent, in jedem reell-abgeschlossenen Körper gilt) oder nicht. Es gibt also prinzipiell keine erststufig formulierbaren „substantiellen Probleme“ für die reellen Zahlen.



Fußnoten
  1. Um die Lesbarkeit zu erhöhen benutzen wir auch andere Variablennamen.
  2. Die Beziehung wird durch erklärt. Alternativ kann man die Symbolmenge um ergänzen.