Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/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
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 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 Menge an
Aussagenvariablen
und
eine Teilmenge der zugehörigen
Sprache der Aussagenlogik.
Es sei
.
Dann ist
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.
In einem
Peano-Halbring
gilt für jedes
die Eigenschaft: Entweder ist
oder es gibt ein
mit
.
In einem
Peano-Halbring
erfüllt
das Wohlordnungsprinzip für erststufige Ausdrücke. D.h. für jeden Ausdruck
in der freien Variablen
gilt
Es sei ein
Peano-Halbring
und
.
Dann gibt es zu jedem
eindeutig bestimmte
mit
und mit
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.
Die Menge der Programmnummern von
Registerprogrammen,
die angesetzt auf anhalten, ist
-
aufzählbar.
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
(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