Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Liste der Hauptsätze/Zufallsabfrage

???: Satz von Euklid (Primzahlen)

Es gibt unendlich viele Primzahlen.

???: Satz von Wiles (Großer Fermat)

Die diophantische Gleichung

{}x^{n}+x^{n}=z^{n}\,

besitzt für kein ${}n\geq 3$ eine ganzzahlige nichttriviale Lösung.

???: Regeln für Ableitungsbeziehung der Aussagenlogik

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ .

Dann gelten folgende Regeln für die Ableitungsbeziehung (dabei seien $\alpha ,\beta ,\gamma ,\alpha _{i}$ Aussagen).

Konjunktionsregel: ${}\Gamma \vdash \alpha \wedge \beta$ genau dann, wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \beta$ .

Kettenschlussregel: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \beta \rightarrow \gamma$ , dann auch ${}\Gamma \vdash \alpha \rightarrow \gamma$ .

Modus ponens: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \alpha \rightarrow \beta$ , dann ist auch ${}\Gamma \vdash \beta$ .

Wenn ${}\Gamma \vdash \alpha$ , so auch ${}\Gamma \vdash \beta \rightarrow \alpha$ .

Wenn ${}\Gamma \vdash \alpha _{1},\ldots ,\Gamma \vdash \alpha _{n}$ und ${}\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$ , dann auch ${}\Gamma \vdash \beta$ .

Widerspruchsregel: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$ , dann auch ${}\Gamma \vdash \beta$ .

Fallunterscheidungsregel: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \neg \alpha \rightarrow \beta$ , dann auch ${}\Gamma \vdash \beta$ .

???: Strukturelle Eigenschaften maximal widerspruchsfreier Mengen (Aussagenlogik)

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Dann gelten folgende Aussagen.

Für jedes ${}\alpha \in L^{V}$ ist entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ .

Aus ${}\Gamma \vdash \alpha$ folgt ${}\alpha \in \Gamma$ .

Es ist ${}\alpha \wedge \beta \in \Gamma$ genau dann, wenn ${}\alpha \in \Gamma$ und ${}\beta \in \Gamma$ .

Es ist ${}\alpha \rightarrow \beta \in \Gamma$ genau dann, wenn ${}\alpha \not \in \Gamma$ oder ${}\beta \in \Gamma$ .

???: Test mit Aussagenvariablen für maximal widerspruchsfrei

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ . Es sei ${}\Gamma$ widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable ${}p\in V$ gelte ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$ .

Dann ist ${}\Gamma$ maximal widerspruchsfrei.

???: Auffüllung widerspruchsfreier Mengen (Aussagenlogik, abzählbarer Fall)

Es sei ${}V$ eine abzählbare Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann kann man ${}\Gamma$ durch sukzessive Hinzunahme von entweder ${}p_{n}$ oder ${}\neg p_{n}$ und durch Abschluss unter der Ableitungsbeziehung zu einer maximal widerspruchsfreien Teilmenge ${}\Gamma '\supseteq \Gamma$ ergänzen.

???: Das Lemma von Zorn

Es sei ${}(I,\preccurlyeq )$ eine geordnete Menge mit der Eigenschaft, dass jede total geordnete Teilmenge ${}J\subseteq I$ eine obere Schranke in ${}I$ besitzt.

Dann gibt es in ${}I$ maximale Elemente.

???: Erfüllbarkeit maximal widerspruchsfreier Ausdrucksmengen (Aussagenlogik)

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann ist ${}\Gamma$ erfüllbar.

???: Vollständigkeitssatz der Aussagenlogik

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei ${}\alpha \in L^{V}$ .

Dann ist

$\Gamma \vdash \alpha {\text{ genau dann, wenn }}\Gamma \vDash \alpha .$

???: Koinzidenzlemma

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}U\subseteq S$ eine Teilmenge. Es sei ${}t$ ein ${}U$ - Term und ${}\alpha$ ein ${}U$ - Ausdruck. Es seien zwei ${}S$ - Interpretationen ${}I_{1}$ und ${}I_{2}$ in einer gemeinsamen Grundmenge ${}M$ gegeben, die auf ${}U$ identisch seien. Dann gelten folgende Aussagen.

Es ist ${}I_{1}(t)=I_{2}(t)$ .

Es ist ${}I_{1}\vDash \alpha$ genau dann, wenn ${}I_{2}\vDash \alpha$ (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus ${}U$ und auf den in ${}\alpha$ frei vorkommenden Variablen identisch sind).

???: Substitutionslemma

Es sei ein Symbolalphabet ${}S$ einer Sprache erster Stufe gegeben und es seien ${}x_{1},\ldots ,x_{k}$ paarweise verschiedene Variablen und ${}t_{1},\ldots ,t_{k}$ fixierte ${}S$ - Terme. Es sei eine ${}S$ - Interpretation ${}I$ gegeben. Dann gelten folgende Aussagen.

Für jeden ${}S$ - Term ${}s$ gilt
${}I{\left(s{\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}\right)}={\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}(s)\,.$

Für jeden ${}S$ - Ausdruck ${}\alpha$ gilt
$I\vDash \alpha {\frac {t_{1},\ldots ,t_{k}}{x_{1},\ldots ,x_{k}}}{\text{ genau dann, wenn }}{\left(I{\frac {I(t_{1}),\ldots ,I(t_{k})}{x_{1},\ldots ,x_{k}}}\right)}\vDash \alpha .$

???: Korrektheit der Existenzeinführung im Antezedens

Die Existenzeinführung im Antezedens ist eine korrekte Regel.

???: Allquantor und Tautologien

Es sei ${}S$ ein Symbolalphabet erster Stufe, ${}\alpha$ ein ${}S$ - Ausdruck und ${}x$ eine Variable.

Dann ist ${}\vdash \alpha$ genau dann, wenn ${}\vdash \forall x\alpha$ ist.

???: Induktive Definition von Abbildungen

Es sei ${}(N,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und es sei ${}M$ eine Menge mit einem fixierten Element ${}s\in M$ und einer Abbildung ${}F\colon M\rightarrow M$ .

Dann gibt es genau eine Abbildung

$\varphi \colon N\longrightarrow M,\,n\longmapsto \varphi (n),$

die die beiden Eigenschaften

\varphi (0)=s{\text{ und }}\varphi (n^{\prime })=F(\varphi (n)){\text{ für alle }}n\in \mathbb {N}

erfüllt.

???: Beziehung zwischen Dedekind-Peano-Modellen

Es seien ${}N_{1}$ und ${}N_{2}$ Dedekind-Peano-Modelle für die natürlichen Zahlen.

Dann gibt es eine eindeutig bestimmte bijektive Abbildung

$\varphi \colon N_{1}\longrightarrow N_{2}$

mit ${}\varphi (0_{1})=0_{2}$ und

{}\varphi (n')=(\varphi (n))'\,

für alle ${}n\in N_{1}$ .

Insbesondere sind je zwei Dedekind-Peano-Modelle isomorph.

???: Vorgängereigenschaft in Peano-Halbringen

In einem Peano-Halbring ${}M$

gilt für jedes ${}x\in M$ die Eigenschaft: Entweder ist ${}x=0$ oder es gibt ein ${}u\in M$ mit ${}x=u+1$ .

???: Wohlordnungsprinzip für erststufige Aussagen

In einem Peano-Halbring ${}M$ erfüllt ${}\geq$

das Wohlordnungsprinzip für erststufige Ausdrücke. D.h. für jeden Ausdruck ${}\alpha \in L^{\{0,1,+,\cdot \}}$ in der freien Variablen ${}x$ gilt

$\exists x\alpha \rightarrow \exists y{\left(\alpha {\frac {y}{x}}\wedge \forall x{\left(\alpha \rightarrow x\geq y\right)}\right)}.$

???: Division mit Rest (Peano-Halbring)

Es sei ${}M$ ein Peano-Halbring und ${}d\geq 1$ .

Dann gibt es zu jedem ${}m\in M$ eindeutig bestimmte ${}q,r\in M$ mit ${}r<d$ und mit

${}m=qd+r\,.$

???: Korrektheitssatz für Tautologien

Es sei ${}S$ ein Symbolalphabet und sei ${}\alpha \in L^{S}$ eine syntaktische Tautologie.

Dann ist ${}\alpha$ auch eine semantische Tautologie.

???: Korrektheitssatz (Ableitung)

Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$ - Ausdrücken und ${}\alpha$ ein weiterer ${}S$ -Ausdruck.

Dann folgt aus der Ableitungsbeziehung ${}\Gamma \vdash \alpha$ die Folgerungsbeziehung ${}\Gamma \vDash \alpha$ .

???: Satz von Henkin

Es sei ${}\Gamma$ eine Menge an ${}S$ - Ausdrücken (über einem Symbolalphabet ${}S$ ), die maximal widerspruchsfrei ist und Beispiele enthält.

Dann ist die in Konstruktion 14.7 gegebene Interpretation ein Modell für ${}\Gamma$ .

Insbesondere ist ${}\Gamma$ erfüllbar.

???: Vollständigkeitssatz

Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$ - Ausdrücken und ${}\alpha$ ein weiterer ${}S$ -Ausdruck.

Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn ${}\Gamma \vdash \alpha$ gilt.

???: Vollständigkeitssatz für Tautologien

Es sei ${}S$ ein Symbolalphabet und ${}\alpha \in L^{S}$ ein ${}S$ -Ausdruck.

Dann ist ${}\alpha$ genau dann eine ableitbare Tautologie, wenn ${}\alpha$ allgemeingültig ist.

???: Endlichkeitssatz

Es sei ${}S$ ein Symbolalphabet, ${}\Gamma$ eine Menge an ${}S$ - Ausdrücken und ${}\alpha$ ein weiterer ${}S$ -Ausdruck.

Dann gilt ${}\Gamma \vDash \alpha$ genau dann, wenn es eine endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ gibt mit ${}\Gamma _{e}\vDash \alpha$ .

???: Endlichkeitssatz für Erfüllbarkeit

Es sei ${}S$ ein Symbolalphabet und ${}\Gamma$ eine Menge an ${}S$ - Ausdrücken. Es sei jede endliche Teilmenge ${}\Gamma _{e}\subseteq \Gamma$ erfüllbar.

Dann ist ${}\Gamma$ erfüllbar.

???: Isomorphielemma

Es seien ${}M$ und ${}N$ isomorphe ${}S$ - Strukturen über einem Symbolalphabet ${}S$ .

Dann sind ${}M$ und ${}N$ elementar äquivalent.

Genauer: Zu einem Isomorphismus

\varphi \colon M\longrightarrow N

und einer Variablenbelegung ${}\lambda$ auf ${}M$ und der zugehörigen Variablenbelegung ${}\varphi \circ \lambda$ auf ${}N$ mit den zugehörigen Interpretationen ${}I$ und ${}J$ gilt für jeden ${}S$ - Ausdruck ${}\alpha$ die Äquivalenz

I\vDash \alpha {\text{ genau dann, wenn }}J\vDash \alpha .

???: Isomorphiesatz im endlichen Fall

Es sei ${}S$ ein Symbolalphabet und es seien ${}M$ und ${}N$ ${}S$ - Strukturen, wobei ${}M$ endlich sei.

Dann sind ${}M$ und ${}N$ genau dann elementar äquivalent, wenn sie zueinander isomorph sind.

???: Unentscheidbarkeit des Halteproblems (Selbsteingabe)

Die Menge

${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(n){\text{ hält an}}\right\}}$

ist nicht ${}R$ - entscheidbar.

???: Unentscheidbarkeit des Halteproblems

Die Menge

${\left\{n\in \mathbb {N} \mid n{\text{ ist die Nummer eines Registerprogramms }}P{\text{ und }}P(0){\text{ hält an}}\right\}}$

ist nicht ${}R$ - entscheidbar.

???: Entscheidbarkeit und Aufzählbarkeit

Es sei ${}T\subseteq \mathbb {N}$ eine Teilmenge der natürlichen Zahlen.

Dann ist ${}T$ genau dann ${}R$ - entscheidbar, wenn sowohl ${}T$ als auch das Komplement ${}\mathbb {N} \setminus T$ ${}R$ - aufzählbar ist.

???:

Die Menge der Programmnummern von Registerprogrammen, die angesetzt auf ${}0$ anhalten, ist ${}R$ - aufzählbar.

???: Programmabbildung und Repräsentierung

Es sei ${}P$ ein Registerprogramm mit den Programmzeilen ${}B_{1},\ldots ,B_{h}$ und ${}m$ Registern mit den zugehörigen arithmetischen Ausdrücken ${}A_{1},\ldots ,A_{h}$ in den freien Variablen ${}z,r_{1},\ldots ,r_{m},z',r'_{1},\ldots ,r'_{m}$ . Es sei ${}A_{P}=A_{1}\wedge \ldots \wedge A_{h}\wedge A_{h+1}$ .

Dann ist ${}A_{P}$ eine arithmetische Repräsentierung der Programmabbildung ${}\varphi _{P}$ .

???: Lemma über die

{}\beta

-Funktion

Zu jeder endlichen Folge ${}(a_{0},\ldots ,a_{s})$ aus ${}\mathbb {N}$

gibt es natürliche Zahlen ${}p,n$ derart, dass ${}\beta (p,n,i)=a_{i}$ für ${}i\leq s$ ist.

???: Repräsentierbarkeit des Halteproblems

Für ein Programm ${}P$ für eine Registermaschine

gibt es einen arithmetischen Ausdruck ${}\psi _{P}$ , der genau dann (bei der Standardinterpretation in den natürlichen Zahlen) gilt, wenn das Programm anhält.

Genauer gesagt: Wenn das Programm ${}h$ Programmzeilen besitzt und ${}m$ Register verwendet, so gibt es einen arithmetischen Ausdruck ${}\psi _{P}$ in ${}2m$ freien Variablen

derart, dass

\mathbb {N} \vDash \psi _{P}(e_{1},\ldots ,e_{m},a_{1},\ldots ,a_{m})

genau dann gilt, wenn das Programm bei Eingabe von

{}(1,e_{1},\ldots ,e_{m})

nach endlich vielen Schritten bei der Konfiguration

{}(h,a_{1},\ldots ,a_{m})

anlangt

(und insbesondere anhält).

???: Die Unentscheidbarkeit der Arithmetik

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

D.h. es gibt kein ${}R$ -Entscheidungsverfahren, mit dem man von einem beliebigen vorgegebenen Ausdruck ${}\alpha \in L_{0}^{\rm {Ar}}$ der arithmetischen Sprache bestimmen kann, ob er (in der Standardinterpretation ${}\mathbb {N}$ ) wahr oder falsch ist.

???: Aufzählbar und aufzählbar axiomatisierbar

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe.

Eine aufzählbar axiomatisierbare Theorie ${}T\subseteq L_{0}^{S}$ ist ${}R$ - aufzählbar.

???: Aufzählbar, vollständig, entscheidbar

Es sei ${}S$ ein Symbolalphabet und ${}L^{S}$ die zugehörige Sprache erster Stufe.

Jede aufzählbare (oder aufzählbar axiomatisierbare), widerspruchsfreie und vollständige Theorie ${}T\subseteq L_{0}^{S}$ ist entscheidbar.

???: Die Unaufzählbarkeit der Arithmetik

Die Menge der wahren arithmetischen Ausdrücke ist nicht ${}R$ - aufzählbar.

D.h. es gibt kein ${}R$ -Verfahren, das alle in ${}\mathbb {N}$ wahren Sätze der arithmetischen Sprache auflistet.

???: Unvollständigkeit der Peano-Arithmetik

Die (erststufige) Peano-Arithmetik

ist unvollständig.

???: Natürliche Arithmetik und Repräsentierungen

Die natürliche Arithmetik, also die Menge der in ${}\mathbb {N}$ wahren Ausdrücke ${}\mathbb {N} ^{\vDash }$ ,

erlaubt Repräsentierungen.

???: Fixpunktsatz

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube.

Dann gibt es zu jedem ${}\alpha \in L_{1}^{\rm {Ar}}$ einen Satz ${}q\in L_{0}^{\rm {Ar}}$ mit

$\Gamma \vdash q\longleftrightarrow \alpha (GN(q)).$

???: Unvollständigkeitslemma

Es sei ${}\Gamma$ eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge ${}\Gamma ^{\vdash }$ (also die Menge der zugehörigen Gödelnummern) sei schwach repräsentierbar in ${}\Gamma$ .

Dann gibt es einen arithmetischen Satz ${}q\in L_{0}^{\rm {Ar}}$ derart, dass weder ${}q$ noch seine Negation ${}\neg q$ aus ${}\Gamma$ ableitbar ist.

Die Ableitungsmenge ${}\Gamma ^{\vdash }$ ist also nicht vollständig.

???: Erster Gödelscher Unvollständigkeitssatz

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube.

Dann ist ${}\Gamma ^{\vdash }$ unvollständig.

Es gibt also einen arithmetischen Satz, für den weder ${}\Gamma \vdash q$ noch ${}\Gamma \vdash \neg q$ gilt.

???: Zweiter Gödelscher Unvollständigkeitssatz

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse.

Dann ist die Widerspruchsfreiheit ${}WF(\Gamma )$ nicht aus ${}\Gamma$ ableitbar, d.h. es ist

$\Gamma \not \vdash WF(\Gamma ).$