Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Liste der Hauptsätze
Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck.
Dann gilt genau dann, wenn gilt.
Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck.
Dann gilt genau dann, wenn es eine endliche Teilmenge gibt mit .
Die Menge
ist nicht - entscheidbar.
Die Menge
ist nicht - entscheidbar.
Es sei eine Teilmenge der natürlichen Zahlen.
Dann ist genau dann - entscheidbar, wenn sowohl als auch das Komplement - aufzählbar ist.
Die Programmzeilen eines Registerprogramms mit Registern bzw. die zugehörige Programmabbildung lassen sich folgendermaßen mit den Variablen arithmetisch repräsentieren (dabei sei die aktuelle Programmzeile).
- wird arithmetisiert durch
- wird arithmetisiert durch
- wird arithmetisiert durch
- wird arithmetisiert durch
Zu jeder endlichen Folge aus
gibt es natürliche Zahlen derart, dass für ist.
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(und insbesondere anhält).
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.
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.
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.
Die natürliche Arithmetik, also die Menge der in wahren Ausdrücke ,
erlaubt Repräsentierungen.
Es sei eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube.
Dann gibt es zu jedem einen Satz mit
Es sei eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge (also die Menge der zugehörigen Gödelnummern) sei schwach repräsentierbar in .
Dann gibt es einen arithmetischen Satz derart, dass weder noch seine Negation aus ableitbar ist.
Die Ableitungsmenge ist also nicht vollständig.
Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube.
Dann ist unvollständig.
Es gibt also einen arithmetischen Satz, für den weder noch gilt.
Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse.
Dann ist die Widerspruchsfreiheit nicht aus ableitbar, d.h. es ist