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

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

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

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

???: Arithmetische Repräsentierung von Registerbefehlen

Die Programmzeilen eines Registerprogramms mit ${}m$ Registern bzw. die zugehörige Programmabbildung lassen sich folgendermaßen mit den Variablen ${}z,r_{1},\ldots ,r_{m},z',r'_{1},\ldots ,r'_{m}$ arithmetisch repräsentieren (dabei sei ${}\ell$ die aktuelle Programmzeile).

${}B_{\ell }=i+$ wird arithmetisiert durch
$A_{\ell }:=((z=\ell )\rightarrow (z'=z+1)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{i-1}'=r_{i-1})\wedge (r_{i}'=r_{i}+1)\wedge (r_{i+1}'=r_{i+1})\wedge \ldots \wedge (r_{m}'=r_{m})).$

${}B_{\ell }=i-$ wird arithmetisiert durch
$A_{\ell }:=((z=\ell )\rightarrow (z'=z+1)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{i-1}'=r_{i-1})\wedge ((r_{i}=0)\rightarrow r'_{i}=r_{i})\wedge (\neg (r_{i}=0)\rightarrow r_{i}'+1=r_{i})\wedge (r_{i+1}'=r_{i+1})\wedge \ldots \wedge (r_{m}'=r_{m})).$

${}B_{\ell }=C(i,j)$ wird arithmetisiert durch
$A_{\ell }:=((z=\ell )\rightarrow ((r_{i}=0\rightarrow (z'=j))\wedge (\neg (r_{i}=0)\rightarrow (z'=z+1)))\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m})).$

${}B_{\ell }=B_{h}=H$ wird arithmetisiert durch
$A_{h}:=((z=h)\rightarrow (z'=h)\wedge (r_{1}'=r_{1})\wedge \ldots \wedge (r_{m}'=r_{m})).$

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

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