Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 22/latex
\setcounter{section}{22}
\zwischenueberschrift{Repräsentierbarkeit in einer Theorie}
Wir haben schon in der zwanzigsten Vorlesung davon gesprochen, wann eine arithmetische $r$-stellige Relation $R$
\zusatzklammer {bzw. Funktion} {} {}
in $\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 $\N^\vDash$ vollständig ist, ergibt sich daraus die Äquivalenz, dass
\mathl{(n_1 , \ldots , n_r) \not\in R}{} äquivalent zur Nichtgültigkeit
\mathl{\N \not\vDash \psi (n_1 , \ldots , n_r)}{} und somit auch zur Gültigkeit der Negation
\mathl{\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.
\inputdefinition
{}
{
Es sei $\Gamma$ eine Menge von
\definitionsverweis {arithmetischen Ausdrücken}{}{.}
Eine
\definitionsverweis {Relation}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N^r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {repräsentierbar}{}
in $\Gamma$, wenn es einen $L^{\rm Ar}$-Ausdruck $\psi$ in $r$
\definitionsverweis {freien Variablen}{}{}
derart gibt, dass für alle $r$-Tupel
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_{r})
}
{ \in }{ \N^r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die beiden Eigenschaften
\aufzaehlungzwei {Wenn
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_{r})
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ist
\mathl{\Gamma \vdash \psi (n_1 , \ldots , n_{r})}{,}
} {Wenn
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_{r})
}
{ \notin }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ist
\mathl{\Gamma \vdash \neg \psi (n_1 , \ldots , n_{r})}{,}
}
gelten.
}
\inputdefinition
{}
{
Es sei $\Gamma$ eine Menge von
\definitionsverweis {arithmetischen Ausdrücken}{}{.}
Eine
\definitionsverweis {Funktion}{}{}
\maabbdisp {F} {\N^r} {\N^s
} {}
heißt
\definitionswort {repräsentierbar}{}
in $\Gamma$, wenn es einen $L^{\rm Ar}$-Ausdruck $\psi$ in
\mathl{r+s}{}
\definitionsverweis {freien Variablen}{}{}
derart gibt, dass für alle
\mathl{(r+s)}{-}Tupel
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_{r+s})
}
{ \in }{ \N^{r+s}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die folgenden Eigenschaften
\aufzaehlungdrei{Wenn
\mavergleichskette
{\vergleichskette
{ F(n_1, \ldots , n_{r})
}
{ = }{ (n_{r+1} , \ldots , n_{r+s})
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ist
\mathl{\Gamma \vdash \psi (n_1 , \ldots , n_{r+s})}{,}
}{Wenn
\mavergleichskette
{\vergleichskette
{ F(n_1, \ldots , n_{r})
}
{ \neq }{ (n_{r+1} , \ldots , n_{r+s})
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
so ist
\mathl{\Gamma \vdash \neg \psi (n_1 , \ldots , n_{r+s})}{,}
}{
\mathl{\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
\mathl{\exists z { \left( \alpha(z) \wedge \forall y { \left( \alpha(y) \rightarrow y = z \right) } \right) }}{.}
\inputdefinition
{}
{
Es sei $\Gamma$ eine Menge von \definitionsverweis {arithmetischen Ausdrücken}{}{.} Man sagt, dass $\Gamma$ \definitionswort {Repräsentierungen erlaubt}{,} wenn $\Gamma$ jede $R$-\definitionsverweis {berechenbare Relation}{}{} und jede $R$-\definitionsverweis {berechenbare Funktion}{}{} \definitionsverweis {repräsentiert}{}{.}
}
\inputfaktbeweis
{Natürliche Arithmetik/Erlaubt Repräsentierungen/Fakt}
{Korollar}
{}
{
\faktsituation {}
\faktvoraussetzung {Die natürliche Arithmetik, also die Menge der in $\N$ wahren Ausdrücke $\N^\vDash$,}
\faktfolgerung {\definitionsverweis {erlaubt Repräsentierungen}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\N^r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
$R$-\definitionsverweis {entscheidbare Relation}{}{}
und es sei $P$ ein
\definitionsverweis {Registerprogramm}{}{}
mit den Registern
\mathl{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
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_r)
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn $P$, angesetzt auf
\mathl{(n_1 , \ldots , n_r)}{}
\zusatzklammer {strenggenommen angesetzt auf \mathlk{(1, n_1 , \ldots , n_r, 0 , \ldots , 0 )}{,} wenn man die vollständige Registerbelegung angibt} {} {}
anhält mit der Ausgabe $0$
\zusatzklammer {d.h. \mathlk{(h, 0 , n'_2 , \ldots , n'_m )}{;} andernfalls wird mit der Ausgabe $1$ angehalten} {} {,}
genau dann, wenn
\mathl{\N \vDash \psi_P (n_1 , \ldots , n_r,0 , \ldots , 0 ,0 , n'_2 , \ldots , n'_m)}{} gilt.
Wegen der Vollständigkeit von $\N$ bedeutet dies, dass
\mavergleichskettedisp
{\vergleichskette
{ \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
\definitionsverweis {repräsentiert}{}{.}}
{}
\teilbeweis {}{}{}
{Es sei
\maabbdisp {F} {\N^r} {\N^s
} {}
eine
$R$-\definitionsverweis {berechenbare Abbildung}{}{}
und es sei $P$ ein
\definitionsverweis {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
\mathl{(r+s)}{-}Tupel
\mathl{n_1 , \ldots , n_{r+s}}{} gilt
\mavergleichskettedisp
{\vergleichskette
{ 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
\mathl{(n_1 , \ldots , n_r)}{}
\zusatzklammer {in den ersten $r$ Registern, die Eingabe ist also \mathlk{(1, n_1 , \ldots , n_r, 0 , \ldots , 0)}{}} {} {}
die Ausgabe
\mathl{(n_{r+1} , \ldots , n_{r+s})}{}
\zusatzklammer {also \mathlk{(h, n_{r+1} , \ldots , n_{r+s}, \ell_{m+s+1} , \ldots , \ell_{2m} )}{}} {} {}
besitzt, genau dann, wenn
\mathdisp {\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
\zusatzklammer {in den freien Variablen \mathlk{x_1 , \ldots , x_r,x_{r+1} , \ldots , x_{r+s}}{}} {} {}
\mavergleichskettedisp
{\vergleichskette
{\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 $\N^\vDash$ vollständig ist, gilt auch
\mathdisp {\N \vDash \exists ! x_{r+1} \ldots \exists ! x_{r+s} \Theta (n_{1} , \ldots , n_{r} , x_{r+1} , \ldots , x_{r+s} )} { . }
}
{}
\inputbemerkung
{}
{
Man kann zeigen, dass auch die erststufige \definitionsverweis {Peano-Arithmetik}{}{} \definitionsverweis {Repräsentierungen erlaubt}{}{.} Dazu muss man zeigen, dass die in der Definition ***** und in Lemma 21.1 konstruierten Ausdrücke, die die Wirkungsweise von Registerprogrammen beschreiben, nicht nur in $\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.4.
}
\zwischenueberschrift{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
\mathl{0,1,+,\cdot}{} gegeben sei.
Den Ausdrücken der Sprache ordnen wir eine natürliche Zahl, ihre sogenannte \stichwort {Gödelnummer} {} zu. Die Gödelnummer eines Ausdrucks $\alpha$ bezeichnen wir mit
\mathl{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
\mathl{R \prime \prime \ldots \prime}{} benennen. Es ist auch möglich, in einem Zwischenschritt die Variablen
\mathl{x_1,x_2,x_3 \ldots}{} mit
\mathl{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
\mathl{s_{i_1}s_{i_2} \ldots s_{i_n}}{} (\mathlk{i_j}{} sei die Nummer des $j$-ten Symbols im Ausdruck) durch das Produkt
\mathl{p_1^{i_1} p_2^{i_2} \cdots p_n^{i_n}}{} wiederzugeben, wobei die
\mathl{p_1, p_2, p_3, \ldots}{} die Folge der Primzahlen sei.
\inputbeispiel{}
{
Zu einer Ausdrucksmenge $\Gamma$ kann man die Menge
\mathdisp {{ \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.
\inputfaktbeweis
{Arithmetische Satzmenge/Repräsentierungen/Fixpunktsatz/Fakt}
{Satz}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{ L^{\rm Ar}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube.}
\faktfolgerung {Dann gibt es zu jedem
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L^{\rm Ar}_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Satz
\mavergleichskette
{\vergleichskette
{q
}
{ \in }{L^{\rm Ar}_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathdisp {\Gamma \vdash q \longleftrightarrow \alpha ( GN(q))} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{Wir betrachten die Abbildung
\maabbeledisp {F} {\N \times \N} {\N
} {(m,n)} {F(m,n)
} {,}
die durch
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ F(m,n)
}
{ \defeq} {\begin{cases} GN( \alpha(n)),\, \text { falls } m \text{ die } GN \text{ eines } \alpha \in L^{\rm Ar}_1 \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
\mavergleichskette
{\vergleichskette
{ F(m,n)
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
unabhängig von $n$. Falls ja, so ist also
\mavergleichskette
{\vergleichskette
{m
}
{ = }{GN(\alpha)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^{\rm Ar}_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
In diesem Ausdruck wird dann die einzige freie Variable durch das zweite Argument der Abbildung, also $n$, ersetzt, wobei man einen Satz
\mathl{\alpha(n)}{} erhält. Dessen Gödelnummer ist nach Definition der Wert der Abbildung
\mathl{F(m,n)}{.} In diesem Fall ist also
\mavergleichskette
{\vergleichskette
{ F(m,n)
}
{ = }{ GN(\alpha(n))
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese Erläuterungen zeigen zugleich, dass $F$
\definitionsverweis {berechenbar}{}{}
ist.}
{}\teilbeweis {}{}{}
{Da $\Gamma$ nach Voraussetzung Repräsentierungen erlaubt, gibt es einen Ausdruck
\mathl{\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
\mathl{m,n,k}{} die Beziehungen
\zusatzklammer {wir können annehmen, dass $\Gamma$
\definitionsverweis {widerspruchsfrei}{}{}
ist, da andernfalls das Resultat trivial ist} {} {}
\mathdisp {F(m,n)=k \text{ genau dann, wenn } \Gamma \vdash \varphi(m,n,k)} { , }
\mathdisp {F(m,n) \not = k \text{ genau dann, wenn } \Gamma \vdash \neg \varphi(m,n,k)} { }
und
\zusatzklammer {für jede Belegung $m,n$ für $x$ und $y$} {} {}
\mathdisp {\Gamma \vdash \exists ! z \varphi (m,n,z)} { . }
}
{}
\teilbeweis {}{}{}
{Den Fixpunkt zu einem vorgegebenen
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L^{\rm Ar}_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erhalten wir nun durch eine trickreiche Anwendung von $\varphi$. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{s
}
{ \defeq} {\forall z { \left( \varphi(x,x,z) \rightarrow \alpha(z) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Der Ausdruck $s$ besitzt die Gödelnummer
\mathl{GN(s)}{.} Wir behaupten nun, dass der Satz
\mavergleichskettedisp
{\vergleichskette
{q
}
{ \defeq} { s \frac{ GN(s)}{x}
}
{ =} {\forall z { \left( \varphi (GN(s),GN(s),z) \rightarrow \alpha(z) \right) }
}
{ } {
}
{ } {
}
}
{}{}{}
die zu beweisende Ableitungsbeziehung
\mathl{\Gamma \vdash q \leftrightarrow \alpha ( GN(q))}{} erfüllt.}
{}
\teilbeweis {}{}{}
{Der Ausdruck $s$ besitzt die einzige freie Variable $x$, daher gilt
\mavergleichskettedisp
{\vergleichskette
{ F(GN(s),GN(s))
}
{ =} { GN { \left( s \frac{GN(s)}{x} \right) }
}
{ =} { GN(q)
}
{ } {
}
{ } {
}
}
{}{}{.}
Aufgrund der Repräsentierungseigenschaft ist daher
\mathdisp {\Gamma \vdash \varphi (GN(s),GN(s),GN(q))} { . }
Aus der Allaussage $q$ erhält man durch
\definitionsverweis {Spezialisierung}{}{}
\zusatzklammer {man ersetzt die Variable $z$ durch den Term \mathlk{GN(q)}{}} {} {}
\mathdisp {\vdash q \rightarrow { \left( \varphi(GN(s), GN(s), GN(q)) \rightarrow \alpha (GN(q)) \right) }} { . }
Da das Antezedens der rechten Implikation aus $\Gamma$ ableitbar ist, folgt
\mathdisp {\Gamma \vdash q \rightarrow \alpha(GN(q))} { . }
}
{\leerzeichen{}Dies besagt also die Ableitbarkeit der Hinrichtung.}
\teilbeweis {}{}{}
{Die aufgrund der Repräsentierbarkeit oben angeführte eindeutige Existenzaussage führt zu
\mathdisp {\Gamma \vdash \forall z { \left( \varphi(GN(s), GN(s),z) \rightarrow (z = GN(q)) \right) }} { . }
Durch
\definitionsverweis {Substitution}{}{}
ergibt sich
\mathdisp {\vdash ( z = GN(q)) \rightarrow ( \alpha (GN(q)) \rightarrow \alpha (z) )} { }
und somit nach einer prädikatenlogischen Umformulierung
\mathdisp {\Gamma \vdash \forall z { \left( \varphi(GN(s), GN(s),z) \wedge \alpha (GN(q)) \rightarrow \alpha (z) \right) }} { . }
Da hierbei
\mathl{\alpha(GN(q))}{} keine freie Variablen besitzt, ist auch
\mathdisp {\Gamma \vdash \alpha (GN(q)) \rightarrow { \left( \forall z (\varphi(GN(s), GN(s),z) \rightarrow \alpha (z)) \right) }} { , }
und das Sukzedens ist gerade $q$, so dass auch die Rückrichtung ableitbar ist.}
{}