Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/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).

1. Konjunktionsregel: ${}\Gamma \vdash \alpha \wedge \beta$ genau dann, wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \beta$.
2. Kettenschlussregel: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \beta \rightarrow \gamma$, dann auch ${}\Gamma \vdash \alpha \rightarrow \gamma$.
3. Modus ponens: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \alpha \rightarrow \beta$, dann ist auch ${}\Gamma \vdash \beta$.
4. Wenn ${}\Gamma \vdash \alpha$, so auch ${}\Gamma \vdash \beta \rightarrow \alpha$.
5. 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$.
6. Widerspruchsregel: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$, dann auch ${}\Gamma \vdash \beta$.
7. 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.

1. Für jedes ${}\alpha \in L^{V}$ ist entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$.
2. Aus ${}\Gamma \vdash \alpha$ folgt ${}\alpha \in \Gamma$.
3. Es ist ${}\alpha \wedge \beta \in \Gamma$ genau dann, wenn ${}\alpha \in \Gamma$ und ${}\beta \in \Gamma$.
4. 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.

 

???: 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.

 

???: 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.

 

???: 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.

1. Es ist ${}I_{1}(t)=I_{2}(t)$.
2. 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.

1. 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)\,.$

2. 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.

 

???: 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.

 

???: 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 ).$