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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Repräsentierbarkeit der Halteeigenschaft

Ein Durchlauf eines Registerprogramms (das auf Register Bezug nimmt) bis zum Rechenschritt wird am einfachsten durch die Folge der Programmkonfigurationen , , dokumentiert, wobei jede Programmkonfiguration aus der Nummer der im Rechenschritt abzuarbeitenden Programmzeile und der Folge der Registerinhalte (zu diesem Zeitpunkt) besteht. Wenn man diese Konfigurationen einfach hintereinander schreibt, so erhält man eine Folge von Zahlen. Wenn umgekehrt eine solche Zahlenfolge gegeben ist, so kann man einfach überprüfen, ob sie den Durchlauf des Programms bis zum Schritt korrekt dokumentiert. Man muss sicherstellen, dass sich jeder Abschnitt aus dem Vorgängerabschnitt ergibt, wenn die Programmzeile angewendet wird (der Abschnitt muss also durch die Programmabbildung aus dem Vorgängerabschnitt hervorgehen).



Lemma  

Für ein Programm für eine Registermaschine

gibt es einen arithmetischen Ausdruck , der genau dann (bei der Standardinterpretation in den natürlichen Zahlen) gilt, wenn das Programm anhält.

Genauer gesagt: Wenn das Programm Programmzeilen besitzt und Register verwendet, so gibt es einen arithmetischen Ausdruck in freien Variablen

derart, dass
genau dann gilt, wenn das Programm bei Eingabe von nach endlich vielen Schritten bei der Konfiguration anlangt

(und insbesondere anhält).

Beweis  

Es sei der das Programm repräsentierende Ausdruck im Sinne von Fakt ***** in den Variablen (zur Notationsvereinfachung schreiben wir also statt und statt .). Es sei der Ausdruck (in den vier freien Variablen ), der die -Funktion arithmetisch repräsentiert. Der Ausdruck

ist also genau dann wahr in , wenn ist. Diese Beziehung verwenden wir für (bzw. ) und (bzw. ) und . Daher ist der Ausdruck (in den freien Variablen )

bei Interpretation in genau dann wahr, wenn die -Funktion für die aufeinander folgenden Zahlen (eingesetzt in die dritte Komponente der -Funktion) gleich und für die aufeinander folgenden Zahlen gleich ist. An der mit bezeichneten Stelle in steht die -fache Addition der Variablen mit sich selbst plus die -fache Addition der .

Mit diesem Ausdruck soll der Konfigurationsübergang beim -ten Rechenschritt beschrieben werden. Da man die Registerbelegung beim -ten Rechenschritt nicht von vornherein kennt, muss man den Übergang mit Allquantoren ansetzen. Der Ausdruck

besagt, dass der durch über die -Funktion kodierte Konfigurationsübergang durch das Programm bewirkt wird.

In analoger Weise ist der Ausdruck (in den freien Variablen )

(bei inhaltlicher Interpretation) genau dann wahr, wenn und für ist, und der Ausdruck (in den freien Variablen )

ist genau dann wahr, wenn und für ist.

Somit besagt der Ausdruck

dass das Programm mit der Startkonfiguration anhält und dabei die Konfiguration erreicht.



Die Unentscheidbarkeit der Arithmetik

Die Idee des folgenden Beweises beruht darauf, dass man, wie wir in der letzten Vorlesung gezeigt haben, die Arbeitsweise von Registerprogrammen mit arithmetischen Ausdrücken repräsentieren und damit die Unentscheidbarkeit des Halteproblems arithmetisch modellieren kann.



Satz  

Die Menge der wahren arithmetischen Ausdrücke (ohne freie Variablen) ist nicht -entscheidbar.

D.h. es gibt kein -Entscheidungsverfahren, mit dem man von einem beliebigen vorgegebenen Ausdruck der arithmetischen Sprache bestimmen kann, ob er (in der Standardinterpretation ) wahr oder falsch ist.

Beweis  

Nach Lemma 11.1 gibt es zu jedem Programm (mit Befehlen und Registern) einen arithmetischen Ausdruck in freien Variablen , der bei der Belegung mit genau dann wahr ist, wenn das Programm, angesetzt auf , schließlich mit der Konfiguration anhält. Der Ausdruck

besagt daher, dass das Programm bei Nulleingabe mit der Registerbelegung anhält und der Ausdruck (ohne freie Variablen)

besagt, dass das Programm überhaupt anhält. Es gilt also

genau dann, wenn bei Nulleingabe anhält. Man beachte, dass die Abbildung, die einem jeden Programm dieses zuordnet, effektiv durch eine Registermaschine durchführbar ist.

Wenn es ein Entscheidungsverfahren für arithmetische Sätze geben würde, so könnte man insbesondere auch die Richtigkeit von entscheiden. Doch dann würde es ein Entscheidungsverfahren für das Halteproblem im Widerspruch zu Satz 9.6 geben.




Folgerungen aus der Unentscheidbarkeit

Wir werden aus der Unentscheidbarkeit weitere Folgerungen über die Aufzählbarkeit und die Axiomatisierbarkeit der Arithmetik in der ersten Stufe ziehen. Dazu werden wir diese Begriffe allgemein für sogenannte Theorien einführen.


Definition  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Teilmenge heißt Theorie, wenn abgeschlossen unter der Ableitungsbeziehung ist, d.h. wenn aus für bereits folgt.

Zu jeder Ausdrucksmenge ist die Menge der aus ableitbaren Sätze eine Theorie. Häufig wählt man „kleine“ und „handhabbare“ Mengen, um übersichtliche Theorien zu erhalten. Mengen, die eine Theorie erzeugen, heißen auch Axiomensysteme für diese Theorie. Es ist im Allgemeinen schwierig zu entscheiden, ob ein bestimmter Satz aus einem Axiomensystem ableitbar ist, also zu der entsprechenden Theorie dazugehört.

Wenn eine Interpretation einer Sprache erster Stufe ist, so ist , also die Menge der in dem Modell gültigen Sätze, ebenfalls eine Theorie. Dies folgt direkt aus der Korrektheit des Ableitungskalküls. So ist eine Theorie zur Sprache , die alle bei der Standardinterpretation gültigen Sätze beinhaltet.

Die Menge aller aus den Peano-Axiomen ableitbaren Sätze bildet die Peano-Arithmetik, die wir hier nennen. Es ist .

Die Gesamtmenge ist natürlich ebenfalls abgeschlossen unter der Ableitungsbeziehung. Sie ist widersprüchlich im Sinne der folgenden Definition.


Definition  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt widersprüchlich, wenn es einen Satz mit und gibt.



Lemma

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe, wobei die Sprache zumindest eine Variable besitzen möge. Es sei eine Theorie.

Dann ist genau dann widersprüchlich, wenn ist.

Beweis

Siehe Aufgabe 11.5.


Man interessiert sich natürlich hauptsächlich für widerspruchsfreie (also nicht widersprüchliche) Theorien.


Definition  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt vollständig, wenn für jeden Satz gilt oder .

Dabei ist grundsätzlich auch erlaubt, dass sowohl als auch zu gehört, doch liegt dann bereits eine widersprüchliche Theorie vor.

Zu einer Interpretation einer Sprache erster Stufe ist die Gültigkeitsmenge eine widerspruchsfreie vollständige Theorie. Dies ergibt sich aus dem rekursiven Aufbau der Gültigkeitsbeziehung (die beinhaltet, dass wir das Tertium non datur anerkennen - sonst wäre eine mathematische Argumentation nicht möglich).


Definition  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt endlich axiomatisierbar, wenn es endlich viele Sätze mit gibt.

Das ist häufig zu viel verlangt, wie die einstufige Peano-Arithmetik zeigt (zumindest haben wir sie nicht durch ein endliches Axiomensystem eingeführt). Eine schwächere Variante wird in der folgenden Definition beschrieben.


Definition  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe. Eine Theorie heißt aufzählbar axiomatisierbar, wenn es eine -aufzählbare Satzmenge mit gibt.



Lemma  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe.

Eine aufzählbar axiomatisierbare Theorie ist -aufzählbar.

Beweis  

Es sei eine -aufzählbare Satzmenge, die axiomatisiert, und es sei , , eine -Aufzählung von . Es sei , , eine -Aufzählung der prädikatenlogischen Tautologien aus . Wenn ein Satz aus ableitbar ist, so gibt es eine endliche Auswahl aus (bzw. aus der gewählten Aufzählung) derart, dass

eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem wächst, das Gewünschte: Für jedes notiert man die Tautologien in der Form

Wenn überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes , ob alle zu gehören. Falls ja, und wenn ein Satz ist, so wird notiert. Danach geht man zum nächsten . Wenn man , erreicht hat, so geht man zu , wobei man aber wieder bei anfängt.




Satz  

Es sei ein Symbolalphabet und die zugehörige Sprache erster Stufe.

Jede aufzählbare (oder aufzählbar axiomatisierbare), widerspruchsfreie und vollständige Theorie ist entscheidbar.

Beweis  

Nach Lemma 11.9 bedeutet die aufzählbare Axiomatisierbarkeit, dass schon die Theorie selbst aufzählbar ist. Sei also aufzählbar, vollständig und widerspruchsfrei, und sei , , eine Aufzählung von . Es sei ein Satz. Wegen der Widerspruchsfreiheit und der Vollständigkeit gilt entweder oder . Daher kommt entweder oder in der Aufzählung von vor. Bei ist und bei ist .


Bemerkung  

Eine widersprüchliche Theorie ist natürlich aufzählbar, vollständig und entscheidbar, da sie jeden Satz enthält. Ohne die Voraussetzung der Widerspruchsfreiheit ist aber das Argument im Beweis zu Satz 11.10 nicht durchführbar. Wenn in einer Aufzählung einer Theorie eine widersprüchliche Aussage auftritt, so ist die Theorie natürlich widersprüchlich. Wenn aber bis zu einem bestimmten Zeitpunkt keine widersprüchliche Aussage auftritt, so lässt sich nicht entscheiden, ob dies an der Widerspruchsfreiheit der Theorie oder der Art der Aufzählung liegt. Wenn also in der Aufzählung vorkommt, so kann man daraus nicht ohne die Bedingung der Widerspruchsfreiheit auf schließen.




Satz  

Die Menge der wahren arithmetischen Ausdrücke ist nicht -aufzählbar.

D.h. es gibt kein -Verfahren, das alle in wahren Sätze der arithmetischen Sprache auflistet.

Beweis  

Dies folgt direkt aus Satz 11.10 und aus Satz 11.2.




Korollar  

Die (erststufige) Peano-Arithmetik

ist unvollständig.

Beweis  

Wegen würde die Vollständigkeit hier die Gleichheit bedeuten. Da die Peano-Arithmetik -aufzählbar ist, würde aus Satz 11.10 die Entscheidbarkeit folgen im Widerspruch zu Satz 11.2.



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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)