Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 22
- Repräsentierbarkeit in einer Theorie
Wir haben schon in der zwanzigsten Vorlesung davon gesprochen, wann eine arithmetische -stellige Relation (bzw. Funktion)in arithmetisch repräsentierbar ist, wann es also einen arithmetischen Ausdruck mit freien Variablen derart gibt, dass dieser Ausdruck für jede Belegung genau dann wahr wird, wenn die Relation auf das Belegungstupel zutrifft. Da vollständig ist, ergibt sich daraus die Äquivalenz, dass äquivalent zur Nichtgültigkeit und somit auch zur Gültigkeit der Negation ist. Bei nichtvollständigen Ausdrucksmengen bzw. Theorien wollen wir auch von Repräsentierungen sprechen, wobei wir diese zweite Eigenschaft explizit fordern müssen.
Definition
Es sei eine Menge vonarithmetischen Ausdrücken.EineRelationheißtrepräsentierbarin , wenn es einen -Ausdruck in freien Variablenderart gibt, dass für alle -Tupeldie beiden Eigenschaften
- Wenn, so ist ,
- Wenn,so ist ,
gelten.
Definition
Es sei eine Menge vonarithmetischen Ausdrücken.EineFunktion
heißtrepräsentierbarin , wenn es einen -Ausdruck in freien Variablenderart gibt, dass für alle -Tupeldie folgenden Eigenschaften
- Wenn, so ist ,
- Wenn,so ist ,
- ,
gelten.
Die dritte Eigenschaft besagt, dass die Ausdrucksmenge beweisen kann, dass es sich um eine Funktion handelt. Diese Eigenschaft folgt nicht aus den beiden ersten Eigenschaften. Der Ausdruck bedeutet die eindeutige Existenz und ist eine Abkürzung für .
Definition
Es sei eine Menge vonarithmetischen Ausdrücken.Man sagt, dass Repräsentierungen erlaubt,wenn jede-berechenbare Relationund jede-berechenbare Funktionrepräsentiert.
Korollar
Die natürliche Arithmetik, also die Menge der in wahren Ausdrücke ,
Beweis
Es seieine-entscheidbare Relationund es sei einRegisterprogrammmit den Registern das diese Relation entscheidet. Aufgrund von Lemma 21.1gibt es einen arithmetischen Ausdruck in freien Variablen, der den Programmablauf arithmetisch modelliert. Es gilt alsogenau dann, wenn , angesetzt auf (strenggenommen angesetzt auf , wenn man die vollständige Registerbelegung angibt)anhält mit der Ausgabe (d.h. ; andernfalls wird mit der Ausgabe angehalten),genau dann, wenn gilt.
Wegen der Vollständigkeit von bedeutet dies, dass
die Relationrepräsentiert.
Es sei
eine-berechenbare Abbildungund es sei einRegisterprogramm,dass berechnet. Aufgrund von Lemma 21.1gibt es einen arithmetischen Ausdruck in freien Variablen, der den Programmablauf arithmetisch modelliert. D.h. für jedes -Tupel gilt
genau dann, wenn das Programm bei jeder Eingabe anhält und angesetzt auf (in den ersten Registern, die Eingabe ist also )die Ausgabe (also )besitzt, genau dann, wenn
gilt. Von daher ist der Ausdruck(in den freien Variablen )
Da eine Funktion vorliegt und vollständig ist, gilt auch
Bemerkung
Man kann zeigen, dass auch die erststufige Peano-ArithmetikRepräsentierungen erlaubt.Dazu muss man zeigen, dass die in derDefinition ***** und inLemma 21.1konstruierten Ausdrücke, die die Wirkungsweise von Registerprogrammen beschreiben, nicht nur in gelten, sondern aus den erststufigen Peano-Axiomen ableitbar sind. Es ist noch nicht einmal selbstverständlich, dass die Addition der natürlichen Zahlen in der Peano-Arithmetik repräsentierbar ist, obwohl dafür direkt das Additionssymbol zur Verfügung steht, sieheAufgabe 22.4.
- Der Fixpunktsatz
Schon beim Halteproblem haben wir die Programmcodes durch eine natürliche Zahl effektiv repräsentiert, was uns ermöglichte, in ein Programm die eigene Programmnummer einzusetzen und so eine Selbstbezüglichkeit abzubilden, die zur Unlösbarkeit des Halteproblems führte. Ähnliches haben wir mit der Arithmetik vor, wobei die arithmetische Sprache durch die Symbole gegeben sei.
Den Ausdrücken der Sprache ordnen wir eine natürliche Zahl, ihre sogenannte Gödelnummer zu. Die Gödelnummer eines Ausdrucks bezeichnen wir mit . Wichtig ist dabei nicht die konkrete Gestalt, sondern allein ihre Effektivität in dem Sinne, dass diese Zuordnung durch eine Registermaschine ausführbar sein muss. Bei einem endlichen Alphabet ist die einfachste Möglichkeit, die Symbole mit Ziffern durchzunummerieren und die Ausdrücke durch die Hintereinanderschreibung der Ziffern in einem hinreichend großen Ziffernsystem zu realisieren. Da wir die Anzahl der Variablen nicht beschränken wollen, ist dies nicht direkt durchführbar. Im Falle von Programmen konnten wir die Register, deren Anzahl ebenfalls nicht beschränkt war, durch benennen. Es ist auch möglich, in einem Zwischenschritt die Variablen mit zu benennen und so ein endliches Alphabet zu erhalten. Eine andere Möglichkeit besteht darin, abzählbar unendlich viele Symbole mit den natürlichen Zahlen durchzunummerieren und einen Ausdruck der Form ( sei die Nummer des -ten Symbols im Ausdruck) durch das Produkt wiederzugeben, wobei die die Folge der Primzahlen sei.
Beispiel
Zu einer Ausdrucksmenge kann man die Menge
betrachten, also die Menge der Gödelnummern von Ausdrücken, die aus ableitbar sind. Dies ist eine Teilmenge der natürlichen Zahlen, daher kann man auf diese Menge den Begriff der Repräsentierbarkeit anwenden. Eine natürliche Frage ist, ob diese Menge in selbst repräsentierbar ist und welche Konsequenzen das hat.
Wir legen im Folgenden eine algorithmische Gödelisierung zu Grunde.
Satz
Es seieine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube.
Dann gibt es zu jedem einen Satzmit
Beweis
Wir betrachten die Abbildung
die durch
festgelegt ist. Bei der Berechnung von wird also zuerst geschaut, ob das erste Argument, also , die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist,unabhängig von . Falls ja, so ist alsomit. In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also , ersetzt, wobei man einen Satz erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung . In diesem Fall ist also.Diese Erläuterungen zeigen zugleich, dass berechenbarist.
Da nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen die Beziehungen(wir können annehmen, dass widerspruchsfreiist, da andernfalls das Resultat trivial ist)
und(für jede Belegung für und )
Den Fixpunkt zu einem vorgegebenenerhalten wir nun durch eine trickreiche Anwendung von . Wir setzen
Der Ausdruck besitzt die Gödelnummer . Wir behaupten nun, dass der Satz
die zu beweisende Ableitungsbeziehung erfüllt.
Der Ausdruck besitzt die einzige freie Variable , daher gilt
Aufgrund der Repräsentierungseigenschaft ist daher
Aus der Allaussage erhält man durch Spezialisierung(man ersetzt die Variable durch den Term )
Da das Antezedens der rechten Implikation aus ableitbar ist, folgt
Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu
Durch Substitutionergibt sich
und somit nach einer prädikatenlogischen Umformulierung
Da hierbei keine freie Variablen besitzt, ist auch
und das Sukzedens ist gerade , so dass auch die Rückrichtung ableitbar ist.
<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2014) | >> |
---|