Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Liste der Hauptsätze
Es gibt unendlich viele Primzahlen.
Die diophantische Gleichung
besitzt für keineine ganzzahlige nichttriviale Lösung.
Es seieine Ausdrucksmenge in derSprache der Aussagenlogikzu einer Aussagenvariablenmenge .
Dann gelten folgende Regeln für die Ableitungsbeziehung(dabei seien Aussagen).
- Konjunktionsregel: genau dann, wenn und .
- Kettenschlussregel: Wenn und , dann auch .
- Modus ponens: Wenn und , dann ist auch .
- Wenn , so auch .
- Wenn und , dann auch .
- Widerspruchsregel: Wenn und , dann auch .
- Fallunterscheidungsregel: Wenn und , dann auch .
Es sei eine Menge an Aussagenvariablenundeinemaximal widerspruchsfreieTeilmenge der zugehörigen Sprache der Aussagenlogik. Dann gelten folgende Aussagen.
- Für jedesist entweder oder.
- Aus folgt .
- Es ist genau dann, wenn und .
- Es ist genau dann, wenn oder .
Es seieine Ausdrucksmenge in der Sprache der Aussagenlogikzu einer Aussagenvariablenmenge . Es sei widerspruchsfrei,abgeschlossen unter Ableitungen und für jede Aussagenvariable gelte oder .
Dann ist maximal widerspruchsfrei.
Es sei einegeordnete Mengemit der Eigenschaft, dass jedetotal geordneteTeilmengeeine obere Schrankein besitzt.
Dann gibt es in maximale Elemente.
Es sei eine Menge an Aussagenvariablenundeinemaximal widerspruchsfreieTeilmenge der zugehörigen Sprache der Aussagenlogik.
Dann ist erfüllbar.
Es sei eineabzählbareMenge an AussagenvariablenundeinewiderspruchsfreieTeilmenge der zugehörigen Sprache der Aussagenlogik.
Dann kann man durch sukzessive Hinzunahme von entweder oder und durch Abschluss unter der Ableitungsbeziehungzu einer maximal widerspruchsfreien Teilmengeergänzen.
Es sei einSymbolalphabeterster Stufe undeine Teilmenge. Es sei ein-Term und ein -Ausdruck.Es seien zwei-Interpretationen und in einer gemeinsamen Grundmenge gegeben, die auf identisch seien. Dann gelten folgende Aussagen.
- Es ist.
- Es ist genau dann, wenn (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus und auf den in frei vorkommenden Variablen identisch sind).
Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben und es seien paarweise verschiedene Variablen und fixierte-Terme.Es sei eine-Interpretation gegeben. Dann gelten folgende Aussagen.
- Für jeden -Term gilt
- Für jeden -Ausdruck gilt
DieExistenzeinführung im Antezedensist eine korrekte Regel.
Es sei ein Symbolalphabet erster Stufe, ein -Ausdruck und eine Variable.
Dann ist genau dann, wenn ist.
Es sei einDedekind-Peano-Modellder natürlichen Zahlen und es sei eine Menge mit einem fixierten Elementund einer Abbildung.
Dann gibt es genau eine Abbildung
die die beiden Eigenschaften
erfüllt.
Es seien und Dedekind-Peano-Modellefür die natürlichen Zahlen.
Dann gibt es eine eindeutig bestimmte bijektive Abbildung
mitund
für alle.
Insbesondere sind je zwei Dedekind-Peano-Modelle isomorph.
Es sei einSymbolalphabetund seieine syntaktische Tautologie.
Dann ist auch eine semantische Tautologie.
Es sei einSymbolalphabet, eine Menge an-Ausdrückenund ein weiterer -Ausdruck.
Dann folgt aus der Ableitungsbeziehung die Folgerungsbeziehung.
Es sei eine Menge an-Ausdrücken(über einem Symbolalphabet),diemaximal widerspruchsfreiist undBeispiele enthält.
Dann ist die inKonstruktion 14.7gegebene Interpretation ein Modell für .
Insbesondere ist erfüllbar.
Es sei einSymbolalphabet, eine Menge an-Ausdrückenund ein weiterer -Ausdruck.
Dann gilt genau dann, wenn gilt.
Es sei einSymbolalphabetundein -Ausdruck.
Dann ist genau dann eine ableitbare Tautologie,wenn allgemeingültigist.
Es sei einSymbolalphabet, eine Menge an-Ausdrücken und ein weiterer -Ausdruck.
Dann gilt genau dann, wenn es eine endliche Teilmengegibt mit .
Es sei einSymbolalphabetund eine Menge an-Ausdrücken. Es sei jede endliche Teilmengeerfüllbar.
Dann ist erfüllbar.
Es seien und isomorphe-Strukturenüber einemSymbolalphabet.
Dann sind und elementar äquivalent.
Genauer: Zu einem Isomorphismus
und einer Variablenbelegung auf und der zugehörigen Variablenbelegung auf mit den zugehörigen Interpretationen und gilt für jeden-Ausdruck die Äquivalenz
Es sei ein Symbolalphabet und es seien und -Strukturen,wobei endlich sei.
Dann sind und genau dann elementar äquivalent,wenn sie zueinander isomorph sind.
Die Menge
ist nicht -entscheidbar.
Die Menge
ist nicht -entscheidbar.
Es seieine Teilmenge der natürlichen Zahlen.
Dann ist genau dann-entscheidbar,wenn sowohl als auch das Komplement -aufzählbarist.
Es sei einRegisterprogrammmit den Programmzeilen und Registern mit den zugehörigen arithmetischen Ausdrücken in den freien Variablen . Es sei.
Dann ist eine arithmetische Repräsentierung der Programmabbildung .
Zu jeder endlichen Folge aus
gibt es natürliche Zahlen derart, dassfürist.
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 Ausdruckder arithmetischen Sprachebestimmen kann, ob er(in der Standardinterpretation )wahr oder falsch ist.
Es sei ein Symbolalphabetund die zugehörige Sprache erster Stufe.
Eine aufzählbar axiomatisierbare Theorieist-aufzählbar.
Es sei ein Symbolalphabetund die zugehörige Sprache erster Stufe.
Jede aufzählbare (oder aufzählbar axiomatisierbare),widerspruchsfreieundvollständige Theorieist 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 Spracheauflistet.
Die (erststufige)Peano-Arithmetik
istunvollständig.
Die natürliche Arithmetik, also die Menge der in wahren Ausdrücke ,
erlaubt Repräsentierungen.
Es seieine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube.
Dann gibt es zu jedem einen Satzmit
Es sei eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge (also die Menge der zugehörigen Gödelnummern)sei schwach repräsentierbarin .
Dann gibt es einen arithmetischen Satzderart, dass weder noch seine Negation aus ableitbar ist.
Die Ableitungsmenge ist also nicht vollständig.
Es seieine arithmetische Ausdrucksmenge, die widerspruchsfreiundaufzählbarsei 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 widerspruchsfreiundentscheidbarseiund die Peano-Arithmetikumfasse.
Dann ist die Widerspruchsfreiheit nicht aus ableitbar, d.h. es ist