Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 12

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Repräsentierbarkeit in einer Theorie

Wir haben schon in der zehnten 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 von arithmetischen Ausdrücken. Eine Relation heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die beiden Eigenschaften

  1. Wenn , so ist ,
  2. Wenn , so ist ,

gelten.


Definition  

Es sei eine Menge von arithmetischen Ausdrücken. Eine Funktion

heißt repräsentierbar in , wenn es einen -Ausdruck in freien Variablen derart gibt, dass für alle -Tupel die folgenden Eigenschaften

  1. Wenn , so ist ,
  2. Wenn , so ist ,
  3. ,

gelten.

Die dritte Eigenschaft besagt, dass die Theorie beweisen kann, dass es sich um eine Funktion handelt. Diese Eigenschaft folgt nicht aus den beiden ersten Eigenschaften.


Definition  

Es sei eine Menge von arithmetischen Ausdrücken. Man sagt, dass Repräsentierungen erlaubt, wenn jede -berechenbare Relation und jede -berechenbare Funktion repräsentiert.



Korollar  

Die natürliche Arithmetik, also die Menge der in wahren Ausdrücke ,

erlaubt Repräsentierungen.

Beweis  

Es sei eine -entscheidbare Relation und es sei ein Registerprogramm mit den Registern das diese Relation entscheidet. Aufgrund von Lemma 11.1 gibt es einen arithmetischen Ausdruck in freien Variablen, der den Programmablauf arithmetisch modelliert. Es gilt also genau 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 Relation repräsentiert.
Es sei

eine -berechenbare Abbildung und es sei ein Registerprogramm, dass berechnet. Aufgrund von Lemma 11.1 gibt 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-Arithmetik Repräsentierungen erlaubt. Dazu muss man zeigen, dass die in der Definition ***** und in Lemma 11.1 konstruierten 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, siehe Aufgabe 12.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 sei eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube.

Dann gibt es zu jedem einen Satz mit

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 also mit . 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 berechenbar ist.
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 widerspruchsfrei ist, da andernfalls das Resultat trivial ist)

und (für jede Belegung für und )


Den Fixpunkt zu einem vorgegebenen erhalten 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

 Dies besagt also die Ableitbarkeit der Hinrichtung.

Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu

Durch Substitution ergibt 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 2011-2012) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)