Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Liste der Hauptsätze/Zufallsabfrage
Es gibt unendlich viele Primzahlen.
Die diophantische Gleichung
besitzt für kein eine ganzzahlige nichttriviale Lösung.
Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu 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 Aussagenvariablen und eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Dann gelten folgende Aussagen.
- Für jedes ist entweder oder .
- Aus folgt .
- Es ist genau dann, wenn und .
- Es ist genau dann, wenn oder .
Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Es sei widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable gelte oder .
Dann ist maximal widerspruchsfrei.
Es sei eine geordnete Menge mit der Eigenschaft, dass jede total geordnete Teilmenge eine obere Schranke in besitzt.
Dann gibt es in maximale Elemente.
Es sei eine Menge an Aussagenvariablen und eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.
Dann ist erfüllbar.
Es sei eine abzählbare Menge an Aussagenvariablen und eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.
Dann kann man durch sukzessive Hinzunahme von entweder oder und durch Abschluss unter der Ableitungsbeziehung zu einer maximal widerspruchsfreien Teilmenge ergänzen.
Es sei ein Symbolalphabet erster Stufe und eine 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
Die Existenzeinführung im Antezedens ist eine korrekte Regel.
Es sei ein Symbolalphabet erster Stufe, ein - Ausdruck und eine Variable.
Dann ist genau dann, wenn ist.
Es sei ein Dedekind-Peano-Modell der natürlichen Zahlen und es sei eine Menge mit einem fixierten Element und einer Abbildung .
Dann gibt es genau eine Abbildung
die die beiden Eigenschaften
erfüllt.
Es seien und Dedekind-Peano-Modelle für die natürlichen Zahlen.
Dann gibt es eine eindeutig bestimmte bijektive Abbildung
mit und
für alle .
Insbesondere sind je zwei Dedekind-Peano-Modelle isomorph.
Es sei ein Symbolalphabet und sei eine syntaktische Tautologie.
Dann ist auch eine semantische Tautologie.
Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck.
Dann folgt aus der Ableitungsbeziehung die Folgerungsbeziehung .
Es sei eine Menge an - Ausdrücken (über einem Symbolalphabet ), die maximal widerspruchsfrei ist und Beispiele enthält.
Dann ist die in Konstruktion 14.7 gegebene Interpretation ein Modell für .
Insbesondere ist erfüllbar.
Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck.
Dann gilt genau dann, wenn gilt.
Es sei ein Symbolalphabet und ein -Ausdruck.
Dann ist genau dann eine ableitbare Tautologie, wenn allgemeingültig ist.
Es sei ein Symbolalphabet, eine Menge an - Ausdrücken und ein weiterer -Ausdruck.
Dann gilt genau dann, wenn es eine endliche Teilmenge gibt mit .
Es sei ein Symbolalphabet und eine Menge an - Ausdrücken. Es sei jede endliche Teilmenge erfüllbar.
Dann ist erfüllbar.
Es seien und isomorphe - Strukturen über einem Symbolalphabet .
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 sei eine Teilmenge der natürlichen Zahlen.
Dann ist genau dann - entscheidbar, wenn sowohl als auch das Komplement - aufzählbar ist.
Es sei ein Registerprogramm mit 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, 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.
Eine aufzählbar axiomatisierbare Theorie ist - aufzählbar.
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 (erststufige) Peano-Arithmetik
ist unvollständig.
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