Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 22

Repräsentierbarkeit in einer Theorie

Wir haben schon in der zwanzigsten Vorlesung davon gesprochen, wann eine arithmetische ${}r$ -stellige Relation ${}R$ (bzw. Funktion) in ${}\mathbb {N}$ arithmetisch repräsentierbar ist, wann es also einen arithmetischen Ausdruck ${}\psi$ mit ${}r$ freien Variablen derart gibt, dass dieser Ausdruck für jede Belegung genau dann wahr wird, wenn die Relation auf das Belegungstupel zutrifft. Da ${}\mathbb {N} ^{\vDash }$ vollständig ist, ergibt sich daraus die Äquivalenz, dass ${}(n_{1},\ldots ,n_{r})\not \in R$ äquivalent zur Nichtgültigkeit ${}\mathbb {N} \not \vDash \psi (n_{1},\ldots ,n_{r})$ und somit auch zur Gültigkeit der Negation ${}\mathbb {N} \vDash \neg \psi (n_{1},\ldots ,n_{r})$ ist. Bei nichtvollständigen Ausdrucksmengen bzw. Theorien wollen wir auch von Repräsentierungen sprechen, wobei wir diese zweite Eigenschaft explizit fordern müssen.

Definition

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Relation ${}T\subseteq \mathbb {N} ^{r}$ heißt repräsentierbar in ${}\Gamma$ , wenn es einen ${}L^{\rm {Ar}}$ -Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$ -Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die beiden Eigenschaften

Wenn ${}(n_{1},\ldots ,n_{r})\in T$ , so ist ${}\Gamma \vdash \psi (n_{1},\ldots ,n_{r})$ ,
Wenn ${}(n_{1},\ldots ,n_{r})\notin T$ , so ist ${}\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r})$ ,

gelten.

Definition

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Funktion

F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}

heißt repräsentierbar in ${}\Gamma$ , wenn es einen ${}L^{\rm {Ar}}$ -Ausdruck ${}\psi$ in ${}r+s$ freien Variablen derart gibt, dass für alle ${}(r+s)$ -Tupel ${}(n_{1},\ldots ,n_{r+s})\in \mathbb {N} ^{r+s}$ die folgenden Eigenschaften

Wenn ${}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})$ , so ist ${}\Gamma \vdash \psi (n_{1},\ldots ,n_{r+s})$ ,
Wenn ${}F(n_{1},\ldots ,n_{r})\neq (n_{r+1},\ldots ,n_{r+s})$ , so ist ${}\Gamma \vdash \neg \psi (n_{1},\ldots ,n_{r+s})$ ,
${}\Gamma \vdash \exists !x_{r+1}\ldots \exists !x_{r+s}\psi (n_{1},\ldots ,n_{r},x_{r+1},\ldots ,x_{r+s})$ ,

gelten.

Die dritte Eigenschaft besagt, dass die Ausdrucksmenge beweisen kann, dass es sich um eine Funktion handelt. Diese Eigenschaft folgt nicht aus den beiden ersten Eigenschaften. Der Ausdruck ${}\exists !z\alpha$ bedeutet die eindeutige Existenz und ist eine Abkürzung für ${}\exists z{\left(\alpha (z)\wedge \forall y{\left(\alpha (y)\rightarrow y=z\right)}\right)}$ . Hierbei ersetzen wir die freie Variable von ${}\alpha$ durch ${}z$ bzw. durch ${}y$ .

Gelegentlich werden wir mit dem folgenden schwächeren Repräsentierungsbegriff für Relationen arbeiten.

Definition

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Eine Relation ${}T\subseteq \mathbb {N} ^{r}$ heißt schwach repräsentierbar in ${}\Gamma$ , wenn es einen ${}L^{\rm {Ar}}$ -Ausdruck ${}\psi$ in ${}r$ freien Variablen derart gibt, dass für alle ${}r$ -Tupel ${}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}$ die Äquivalenz

(n_{1},\ldots ,n_{r})\in T{\text{ genau dann, wenn }}\Gamma \vdash \psi (n_{1},\ldots ,n_{r})

gilt.

Im widerspruchsfreien Fall folgt aus der obigen (starken) Repräsentierung für eine Relation auch die schwache Repräsentierung.

Definition

Es sei ${}\Gamma$ eine Menge von arithmetischen Ausdrücken. Man sagt, dass ${}\Gamma$ Repräsentierungen erlaubt, wenn ${}\Gamma$ jede ${}R$ - berechenbare Relation und jede ${}R$ - berechenbare Funktion repräsentiert.

Korollar

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

erlaubt Repräsentierungen.

Beweis

Es sei ${}T\subseteq \mathbb {N} ^{r}$ eine ${}R$ - entscheidbare Relation und es sei ${}P$ ein Registerprogramm mit den Registern ${}R_{0},R_{1},\ldots ,R_{m}$ das diese Relation entscheidet. Aufgrund von Lemma 21.1 gibt es einen arithmetischen Ausdruck ${}\psi _{P}$ in ${}2m$ freien Variablen, der den Programmablauf arithmetisch modelliert. Es gilt also ${}(n_{1},\ldots ,n_{r})\in T$ genau dann, wenn ${}P$ , angesetzt auf ${}(n_{1},\ldots ,n_{r})$ (strenggenommen angesetzt auf $(1,n_{1},\ldots ,n_{r},0,\ldots ,0)$ , wenn man die vollständige Registerbelegung angibt) anhält mit der Ausgabe ${}0$ (d.h. $(h,0,n'_{2},\ldots ,n'_{m})$ ; andernfalls wird mit der Ausgabe ${}1$ angehalten), genau dann, wenn ${}\mathbb {N} \vDash \psi _{P}(n_{1},\ldots ,n_{r},0,\ldots ,0,0,n'_{2},\ldots ,n'_{m})$ gilt.

Wegen der Vollständigkeit von ${}\mathbb {N}$ bedeutet dies, dass

{}\theta _{P}=\exists y_{2}\ldots \exists y_{m}\psi _{P}(x_{1},\ldots ,x_{r},0,\ldots ,0,0,y_{2},\ldots ,y_{m})\,

die Relation repräsentiert.
Es sei

F\colon \mathbb {N} ^{r}\longrightarrow \mathbb {N} ^{s}

eine ${}R$ - berechenbare Abbildung und es sei ${}P$ ein Registerprogramm, dass ${}F$ berechnet. Aufgrund von Lemma 21.1 gibt es einen arithmetischen Ausdruck ${}\psi _{P}$ in ${}2m$ freien Variablen, der den Programmablauf arithmetisch modelliert. D.h. für jedes ${}(r+s)$ -Tupel ${}n_{1},\ldots ,n_{r+s}$ gilt

{}F(n_{1},\ldots ,n_{r})=(n_{r+1},\ldots ,n_{r+s})\,

genau dann, wenn das Programm ${}P$ bei jeder Eingabe anhält und angesetzt auf ${}(n_{1},\ldots ,n_{r})$ (in den ersten ${}r$ Registern, die Eingabe ist also $(1,n_{1},\ldots ,n_{r},0,\ldots ,0)$ ) die Ausgabe ${}(n_{r+1},\ldots ,n_{r+s})$ (also $(h,n_{r+1},\ldots ,n_{r+s},\ell _{m+s+1},\ldots ,\ell _{2m})$ ) besitzt, genau dann, wenn

\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r},0,\ldots ,0,n_{r+1},\ldots ,n_{r+s},\ell _{m+s+1},\ldots ,\ell _{2m})

gilt. Von daher ist der Ausdruck (in den freien Variablen $x_{1},\ldots ,x_{r},x_{r+1},\ldots ,x_{r+s}$ )

{}\Theta =\exists z_{m+s+1}\ldots \exists z_{2m}\Psi (x_{1},\ldots ,x_{r},0,\ldots ,0,x_{r+1},\ldots ,x_{r+s},z_{m+s+1},\ldots ,z_{2m})\,

Da eine Funktion vorliegt und ${}\mathbb {N} ^{\vDash }$ vollständig ist, gilt auch

\mathbb {N} \vDash \exists !x_{r+1}\ldots \exists !x_{r+s}\Theta (n_{1},\ldots ,n_{r},x_{r+1},\ldots ,x_{r+s}).

\Box

Bemerkung

Man kann zeigen, dass auch die erststufige Peano-Arithmetik Repräsentierungen erlaubt. Dazu muss man zeigen, dass die in der Definition 20.3 und in Lemma 21.1 konstruierten Ausdrücke, die die Wirkungsweise von Registerprogrammen beschreiben, nicht nur in ${}\mathbb {N}$ gelten, sondern aus den erststufigen Peano-Axiomen ableitbar sind. Es ist noch nicht einmal selbstverständlich, dass die Addition der natürlichen Zahlen in der Peano-Arithmetik repräsentierbar ist, obwohl dafür direkt das Additionssymbol zur Verfügung steht, siehe Aufgabe 22.15.

Der Fixpunktsatz

Schon beim Halteproblem haben wir die Programmcodes durch eine natürliche Zahl effektiv repräsentiert, was uns ermöglichte, in ein Programm die eigene Programmnummer einzusetzen und so eine Selbstbezüglichkeit abzubilden, die zur Unlösbarkeit des Halteproblems führte. Ähnliches haben wir mit der Arithmetik vor, wobei die arithmetische Sprache durch die Symbole ${}0,1,+,\cdot$ gegeben sei.

Den Ausdrücken der Sprache ordnen wir eine natürliche Zahl, ihre sogenannte Gödelnummer zu. Die Gödelnummer eines Ausdrucks ${}\alpha$ bezeichnen wir mit ${}GN(\alpha )$ . Wichtig ist dabei nicht die konkrete Gestalt, sondern allein ihre Effektivität in dem Sinne, dass diese Zuordnung durch eine Registermaschine ausführbar sein muss. Bei einem endlichen Alphabet ist die einfachste Möglichkeit, die Symbole mit Ziffern durchzunummerieren und die Ausdrücke durch die Hintereinanderschreibung der Ziffern in einem hinreichend großen Ziffernsystem zu realisieren. Da wir die Anzahl der Variablen nicht beschränken wollen, ist dies nicht direkt durchführbar. Im Falle von Programmen konnten wir die Register, deren Anzahl ebenfalls nicht beschränkt war, durch ${}R\prime \prime \ldots \prime$ benennen. Es ist auch möglich, in einem Zwischenschritt die Variablen ${}x_{1},x_{2},x_{3}\ldots$ mit ${}x,x\prime ,x\prime \prime ,\ldots$ zu benennen und so ein endliches Alphabet zu erhalten. Eine andere Möglichkeit besteht darin, abzählbar unendlich viele Symbole mit den natürlichen Zahlen durchzunummerieren und einen Ausdruck der Form ${}s_{i_{1}}s_{i_{2}}\ldots s_{i_{n}}$ ( $i_{j}$ sei die Nummer des ${}j$ -ten Symbols im Ausdruck) durch das Produkt ${}p_{1}^{i_{1}}p_{2}^{i_{2}}\cdots p_{n}^{i_{n}}$ wiederzugeben, wobei die ${}p_{1},p_{2},p_{3},\ldots$ die Folge der Primzahlen sei.

Beispiel

Zu einer Ausdrucksmenge ${}\Gamma$ kann man die Menge

{\left\{GN(\alpha )\mid \Gamma \vdash \alpha \right\}}

betrachten, also die Menge der Gödelnummern von Ausdrücken, die aus ${}\Gamma$ ableitbar sind. Dies ist eine Teilmenge der natürlichen Zahlen, daher kann man auf diese Menge den Begriff der Repräsentierbarkeit anwenden. Eine natürliche Frage ist, ob diese Menge in ${}\Gamma$ selbst repräsentierbar ist und welche Konsequenzen das hat.

Wir legen im Folgenden eine algorithmische Gödelisierung zu Grunde.

Satz

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

Beweis

Wir betrachten die Abbildung

F\colon \mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(m,n)\longmapsto F(m,n),

die durch

F(m,n):={\begin{cases}GN(\alpha (n)),\,{\text{ falls }}m{\text{ die }}GN{\text{ eines }}\alpha \in L_{1}^{\rm {Ar}}{\text{ ist}}\,,\\0{\text{ sonst}}\,,\end{cases}}\,

festgelegt ist. Bei der Berechnung von ${}F$ wird also zuerst geschaut, ob das erste Argument, also ${}m$ , die Gödelnummer eines arithmetischen Ausdrucks mit genau einer freien Variablen ist. Falls nicht, so ist ${}F(m,n)=0$ , unabhängig von ${}n$ . Falls ja, so ist also ${}m=GN(\alpha )$ mit ${}\alpha \in L_{1}^{\rm {Ar}}$ . In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also ${}n$ , ersetzt, wobei man einen Satz ${}\alpha (n)$ erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung ${}F(m,n)$ . In diesem Fall ist also ${}F(m,n)=GN(\alpha (n))$ . Diese Erläuterungen zeigen zugleich, dass ${}F$ berechenbar ist.
Da ${}\Gamma$ nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck ${}\varphi (x,y,z)$ mit drei freien Variablen, der diese Abbildung repräsentiert. D.h. es gilt für jede Belegung der Variablen mit natürlichen Zahlen ${}m,n,k$ die Beziehungen (wir können annehmen, dass ${}\Gamma$ widerspruchsfrei ist, da andernfalls das Resultat trivial ist)

F(m,n)=k{\text{ genau dann, wenn }}\Gamma \vdash \varphi (m,n,k),

F(m,n)\not =k{\text{ genau dann, wenn }}\Gamma \vdash \neg \varphi (m,n,k)

und (für jede Belegung ${}m,n$ für ${}x$ und ${}y$ )

\Gamma \vdash \exists !z\varphi (m,n,z).

Den Fixpunkt zu einem vorgegebenen ${}\alpha \in L_{1}^{\rm {Ar}}$ erhalten wir nun durch eine trickreiche Anwendung von ${}\varphi$ . Wir setzen

{}s:=\forall z{\left(\varphi (x,x,z)\rightarrow \alpha (z)\right)}\,.

Der Ausdruck ${}s$ besitzt die Gödelnummer ${}GN(s)$ . Wir behaupten nun, dass der Satz

{}q:=s{\frac {GN(s)}{x}}=\forall z{\left(\varphi (GN(s),GN(s),z)\rightarrow \alpha (z)\right)}\,

die zu beweisende Ableitungsbeziehung ${}\Gamma \vdash q\leftrightarrow \alpha (GN(q))$ erfüllt.
Der Ausdruck ${}s$ besitzt die einzige freie Variable ${}x$ , daher gilt