Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 21/latex
\setcounter{section}{21}
\epigraph { Für uns gibt es kein Ignorabimus, und meiner Meinung nach auch für die Naturwissenschaft überhaupt nicht. Statt des törichten Ignorabimus heiße im Gegenteil unsere Losung: Wir müssen wissen, wir werden wissen. } { David Hilbert }
Zuletzt haben wir gezeigt, wir man die Programmabbildung zu einem Registerprogamm arithmetisch repräsentieren kann. Die Programmabbildung enthält zwar die volle Information über das Programm, doch die Frage, wie man die Eigenschaft, ob ein Programm anhält oder nicht, arithmetisch repräsentiert, ist damit noch nicht beantwortet, sondern bedarf weiterer Überlegungen.
\zwischenueberschrift{Repräsentierbarkeit der Halteeigenschaft}
Ein Durchlauf eines Registerprogramms $P$
\zusatzklammer {das auf $m$ Register Bezug nimmt} {} {}
bis zum Rechenschritt $t$ wird am einfachsten durch die Folge der Programmkonfigurationen
\mathbed {K_s} {}
{1 \leq s \leq t} {}
{} {} {} {,}
dokumentiert, wobei jede Programmkonfiguration $K_s$ aus der Nummer der im Rechenschritt $s$ abzuarbeitenden Programmzeile und der Folge der Registerinhalte
\zusatzklammer {zu diesem Zeitpunkt} {} {}
besteht. Wenn man diese Konfigurationen einfach hintereinander schreibt, so erhält man eine Folge von
\mathl{t(m+1)}{} Zahlen. Wenn umgekehrt eine solche Zahlenfolge gegeben ist, so kann man einfach überprüfen, ob sie den Durchlauf des Programms bis zum Schritt $t$ korrekt dokumentiert. Man muss sicherstellen, dass sich jeder Abschnitt zu den Indizes
\mathl{(s+1) (m+1)+1 , \ldots , (s+1) (m+1)+m+1}{} aus dem Vorgängerabschnitt zu den Indizes
\mathl{s (m+1)+1 , \ldots , s (m+1)+m+1}{} ergibt, wenn die Programmzeile zu
\mathl{s (m+1)+1}{} angewendet wird
\zusatzklammer {der Abschnitt muss also durch die Programmabbildung aus dem Vorgängerabschnitt hervorgehen} {} {.}
\inputfaktbeweis
{Repräsentierbarkeit von Registerprogrammen/Über p-adische beta Funktion/Fakt}
{Lemma}
{}
{
\faktsituation {Für ein
\definitionsverweis {Programm}{}{}
$P$ für eine Registermaschine}
\faktfolgerung {gibt es einen
\definitionsverweis {arithmetischen Ausdruck}{}{}
$\psi_P$, der genau dann
\zusatzklammer {bei der Standardinterpretation in den natürlichen Zahlen} {} {}
gilt, wenn das Programm anhält.}
\faktzusatz {Genauer gesagt: Wenn das Programm $h$ Programmzeilen besitzt und $m$ Register verwendet, so gibt es einen arithmetischen Ausdruck $\psi_P$ in $2 m$
\definitionsverweis {freien Variablen}{}{}
derart, dass
\mathdisp {\N \vDash \psi_P(e_1 , \ldots , e_m, a_1 , \ldots , a_m )} { }
genau dann gilt, wenn das Programm bei Eingabe von
\mathl{(1,e_1 , \ldots , e_m)}{} nach endlich vielen Schritten bei der Konfiguration
\mathl{(h,a_1 , \ldots , a_m)}{} anlangt
\zusatzklammer {und insbesondere anhält} {} {.}}
\faktzusatz {}
}
{
Es sei $A_P$ der das Programm repräsentierende Ausdruck im Sinne von
Lemma 20.4
in den Variablen
\mathl{r_0 , \ldots , r_m,r_0' , \ldots , r_m'}{}
\zusatzklammer {zur Notationsvereinfachung schreiben wir also $r_0$ statt $z$ und $r_0'$ statt $z'$.} {} {.}
Es sei $\vartheta$ der Ausdruck
\zusatzklammer {in den vier freien Variablen \mathlk{p,n,i,r}{}} {} {,}
der die
$\beta$-\definitionsverweis {Funktion}{}{}
\definitionsverweis {arithmetisch repräsentiert}{}{.}
Der Ausdruck
\mathdisp {\vartheta (p, n, i, r )} { }
ist also genau dann wahr in $\N$, wenn\zusatzfussnote {Wir verwenden hier für die Termvariablen und mögliche Einsetzungen die gleichen Buchstaben} {.} {}
\mavergleichskette
{\vergleichskette
{\beta(p,n,i)
}
{ = }{r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Diese Beziehung verwenden wir für
\mavergleichskette
{\vergleichskette
{i
}
{ = }{s(m +1) + j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {bzw. \mathlk{i=(s+1)(m +1) + j}{}} {} {}
und
\mavergleichskette
{\vergleichskette
{r
}
{ = }{r_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {bzw. \mathlk{r=r'_j}{}} {} {}
und
\mavergleichskette
{\vergleichskette
{j
}
{ = }{ 0 , \ldots , m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Daher ist der Ausdruck
\zusatzklammer {in den freien Variablen \mathlk{p,n,s,r_j,r_j'}{}} {} {}
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ T(p,n,s)
}
{ \defeq} {\vartheta (p,n, s( m +1), r_0 ) \wedge \ldots \wedge \vartheta (p,n, s( m +1) + m, r_m ) \wedge \vartheta (p,n, (s+1)(m +1), r'_0 ) \wedge \ldots \wedge \vartheta (p,n, (s+1)( m +1) + m, r'_m )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
bei Interpretation in $\N$ genau dann wahr, wenn die $\beta$-Funktion
\mathl{\beta(p,n,-)}{} für die
\mathl{m +1}{} aufeinander folgenden Zahlen
\zusatzklammer {eingesetzt in die dritte Komponente der $\beta$-Funktion} {} {}
\mathl{s( m +1), s( m +1)+1 , \ldots , s( m +1) + m}{} gleich
\mathl{r_0,r_1 , \ldots , r_m}{} und für die
\mathl{m +1}{} aufeinander folgenden Zahlen
\mathl{(s+1)( m +1), (s+1)( m +1)+1 , \ldots , (s+1)( m +1) + m}{} gleich
\mathl{r'_0,r'_1 , \ldots , r'_m}{} ist. An der mit
\mathl{s(m+1)+j}{} bezeichneten Stelle in
\mathl{T(p,n,s)}{} steht die
\mathl{(m+1)}{-}fache Addition der Variablen $s$ mit sich selbst plus die $j$-fache Addition der $1$.
Mit diesem Ausdruck soll der Konfigurationsübergang beim $s$-ten Rechenschritt beschrieben werden. Da man die Registerbelegung beim $s$-ten Rechenschritt nicht von vornherein kennt, muss man den Übergang mit Allquantoren ansetzen. Der Ausdruck
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ E(p,n,s)
}
{ \defeq} {\forall r_0 \forall r_1 \ldots \forall r_m \forall r_0' \forall r'_1 \ldots \forall r'_m ( T (p, n, s) \rightarrow A_P )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besagt, dass der durch
\mathl{p,n,s}{} über die $\beta$-Funktion kodierte Konfigurationsübergang durch das Programm bewirkt wird.
In analoger Weise ist der Ausdruck
\zusatzklammer {in den $m +2$ freien Variablen \mathlk{p,n, x_1 , \ldots , x_m}{}} {} {}
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ D(p,n)(x_1 , \ldots , x_m)
}
{ \defeq} {\vartheta (p,n,0,1) \wedge \vartheta (p,n, 1 ,x_1 ) \wedge \ldots \wedge \vartheta (p,n, m ,x_m )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {bei inhaltlicher Interpretation} {} {}
genau dann wahr, wenn
\mavergleichskette
{\vergleichskette
{ \beta(p,n,0)
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \beta(p,n,j)
}
{ = }{x_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für
\mavergleichskette
{\vergleichskette
{j
}
{ = }{1 , \ldots , m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Der Ausdruck
\zusatzklammer {in den \mathlk{m +3}{} freien Variablen \mathlk{p,n,t, y_1 , \ldots , y_m}{}} {} {}
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{F(p,n,t)(y_1 , \ldots , y_m)
}
{ \defeq} { \vartheta (p,n, t(m +1) , h ) \wedge \vartheta (p,n, t(m +1) + 1 , y_1 ) \wedge \ldots \wedge \vartheta (p,n, t(m +1)+ m , y_m )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist genau dann wahr, wenn
\mavergleichskette
{\vergleichskette
{\beta(p,n,t(m + 1) )
}
{ = }{h
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \beta(p,n,t(m + 1) + j)
}
{ = }{ y_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für
\mavergleichskette
{\vergleichskette
{j
}
{ = }{ 1 , \ldots , m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
Somit besagt der Ausdruck
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ \psi_P
}
{ =} { \exists p \exists n \exists t { \left( D(p,n)(x_1 , \ldots , x_m) \wedge \forall s (1 \leq s < t \rightarrow E(p,n,s)) \wedge F(p,n,t)(y_1 , \ldots , y_m) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
dass das Programm mit der Startkonfiguration
\mathl{(1,x_1 , \ldots , x_m )}{} anhält und dabei die Konfiguration
\mathl{(h,y_1 , \ldots , y_m )}{} erreicht.
\zwischenueberschrift{Die Unentscheidbarkeit der Arithmetik}
Die Idee des folgenden Beweises beruht darauf, dass man, wie wir in der letzten Vorlesung gezeigt haben, die Arbeitsweise von Registerprogrammen mit arithmetischen Ausdrücken repräsentieren und damit die Unentscheidbarkeit des Halteproblems arithmetisch modellieren kann.
\inputfaktbeweis
{Unentscheidbarkeit der Arithmetik/Registermaschine/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {Die Menge der wahren arithmetischen Ausdrücke
\zusatzklammer {ohne freie Variablen} {} {}
ist nicht
$R$-\definitionsverweis {entscheidbar}{}{.}}
\faktzusatz {D.h. es gibt kein $R$-Entscheidungsverfahren, mit dem man von einem beliebigen vorgegebenen Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^{\rm Ar}_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der
\definitionsverweis {arithmetischen Sprache}{}{}
bestimmen kann, ob er
\zusatzklammer {in der Standardinterpretation $\N$} {} {}
wahr oder falsch ist.}
\faktzusatz {}
}
{
Nach
Lemma 21.1
gibt es zu jedem Programm $P$
\zusatzklammer {mit $h$ Befehlen und $m$ Registern} {} {}
einen arithmetischen Ausdruck $\psi_P$ in $2m$ freien Variablen
\mathl{x_1 , \ldots , x_m, y_1 , \ldots , y_m}{,} der bei der Belegung mit
\mavergleichskette
{\vergleichskette
{ e_1 , \ldots , e_m, a_1 , \ldots , a_m
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann wahr ist, wenn das Programm, angesetzt auf
\mathl{(1,e_1 , \ldots , e_m)}{,} schließlich mit der Konfiguration
\mathl{(h,a_1 , \ldots , a_m)}{} anhält. Der Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \varphi_P
}
{ =} { \psi_P(0,0 , \ldots , 0, y_1 , \ldots , y_m)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besagt daher, dass das Programm bei Nulleingabe mit der Registerbelegung
\mathl{(y_1 , \ldots , y_m)}{} anhält und der Ausdruck
\zusatzklammer {ohne freie Variablen} {} {}
\mavergleichskettedisp
{\vergleichskette
{ \theta_P
}
{ =} { \exists y_1 \exists y_2 \ldots \exists y_m \varphi_P
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
besagt, dass das Programm überhaupt anhält. Es gilt also
\mathdisp {\N \vDash \theta_P} { }
genau dann, wenn $P$ bei Nulleingabe anhält. Man beachte, dass die Abbildung, die einem jeden Programm $P$ dieses $\theta_P$ zuordnet, effektiv durch eine Registermaschine durchführbar ist.
Wenn es ein Entscheidungsverfahren für arithmetische Sätze geben würde, so könnte man insbesondere auch die Richtigkeit von
\mathl{\N \vDash \theta_P}{} entscheiden. Doch dann würde es ein Entscheidungsverfahren für das Halteproblem im Widerspruch zu
Satz 19.6
geben.
\zwischenueberschrift{Folgerungen aus der Unentscheidbarkeit}
Wir werden aus der Unentscheidbarkeit weitere Folgerungen über die Aufzählbarkeit und die Axiomatisierbarkeit der Arithmetik in der ersten Stufe ziehen. Dazu werden wir diese Begriffe allgemein für sogenannte Theorien einführen.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.} Eine Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {Theorie}{,} wenn $T$ abgeschlossen unter der
\definitionsverweis {Ableitungsbeziehung}{}{}
ist, d.h. wenn aus
\mathl{T \vdash \alpha}{} für
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bereits
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt.
}
Zu jeder Ausdrucksmenge $\Gamma$ ist die Menge $\Gamma^\vdash$ der aus $\Gamma$ ableitbaren Sätze eine Theorie. Häufig wählt man \anfuehrung{kleine}{} und \anfuehrung{handhabbare}{} Mengen, um übersichtliche Theorien zu erhalten. Mengen, die eine Theorie erzeugen, heißen auch \stichwort {Axiomensysteme} {} für diese Theorie. Es ist im Allgemeinen schwierig zu entscheiden, ob ein bestimmter Satz aus einem Axiomensystem ableitbar ist, also zu der entsprechenden Theorie gehört.
Wenn $I$ eine Interpretation einer Sprache erster Stufe ist, so ist
\mathl{I^\vDash_0}{,} also die Menge der in dem Modell gültigen Sätze, ebenfalls eine Theorie. Dies folgt direkt aus der Korrektheit des Ableitungskalküls. So ist $\N^\vDash_0$ eine Theorie zur Sprache
\mathl{L_0^{\rm Ar}}{,} die alle bei der Standardinterpretation gültigen Sätze beinhaltet.
Die Menge aller aus den erststufigen
\definitionsverweis {Peano-Axiomen}{}{}
ableitbaren Sätze bildet die \stichwort {Peano-Arithmetik} {,} die wir hier ${\rm PA}$ nennen. Es ist
\mathl{{\rm PA} \subseteq \N^\vDash_0}{.}
Die Gesamtmenge
\mathl{L^S_0}{} ist natürlich ebenfalls abgeschlossen unter der Ableitungsbeziehung. Sie ist widersprüchlich im Sinne der folgenden Definition.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.} Eine
\definitionsverweis {Theorie}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {widersprüchlich}{,} wenn es einen Satz
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \neg \alpha
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
{Theorie/Erster Stufe/Ableitbar/Widersprüchlich/Total/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{,} wobei die Sprache zumindest eine Variable besitzen möge. Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Theorie.}
\faktfolgerung {Dann ist $T$ genau dann
\definitionsverweis {widersprüchlich}{}{,}
wenn
\mavergleichskette
{\vergleichskette
{T
}
{ = }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 21.5. }
Man interessiert sich natürlich hauptsächlich für widerspruchsfreie
\zusatzklammer {also nicht widersprüchliche} {} {}
Theorien.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.} Eine
\definitionsverweis {Theorie}{}{}
$T$ heißt \definitionswort {vollständig}{,} wenn für jeden Satz
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{ \neg \alpha
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Dabei ist grundsätzlich auch erlaubt, dass sowohl $\alpha$ als auch $\neg \alpha$ zu $T$ gehört, doch liegt dann bereits eine widersprüchliche Theorie vor. Zu einer Interpretation $I$ einer Sprache erster Stufe ist die Gültigkeitsmenge
\mathl{I^\vDash_0}{} eine widerspruchsfreie vollständige Theorie. Dies ergibt sich aus dem rekursiven Aufbau der Gültigkeitsbeziehung
\zusatzklammer {die beinhaltet, dass wir das Tertium non datur anerkennen - sonst wäre eine mathematische Argumentation nicht möglich} {} {.}
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.} Eine
\definitionsverweis {Theorie}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {endlich axiomatisierbar}{,} wenn es endlich viele Sätze
\mavergleichskette
{\vergleichskette
{ \alpha_1 , \ldots , \alpha_n
}
{ \in }{L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit\zusatzfussnote {Das Ableitungssymbol schränken wir hier auf die Sätze ein, eigentlich müssten wir
\mavergleichskette
{\vergleichskette
{T
}
{ = }{\{ \alpha_1 , \ldots , \alpha_n\}^\vdash \cap L_0^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreiben} {.} {}
\mavergleichskette
{\vergleichskette
{ T
}
{ = }{ \{ \alpha_1 , \ldots , \alpha_n\}^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
Das ist häufig zu viel verlangt, wie die erststufige Peano-Arithmetik zeigt
\zusatzklammer {zumindest haben wir sie nicht durch ein endliches Axiomensystem eingeführt} {} {.}
Eine schwächere Variante wird in der folgenden Definition beschrieben.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.} Eine
\definitionsverweis {Theorie}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {aufzählbar axiomatisierbar}{,} wenn es eine
$R$-\definitionsverweis {aufzählbare}{}{}
Satzmenge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{T
}
{ = }{ \Gamma^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
\inputfaktbeweis
{Theorie/Erster Stufe/Ableitbar/Aufzählbar axiomatisierbar/Aufzählbar/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.}}
\faktfolgerung {Eine
\definitionsverweis {aufzählbar axiomatisierbare Theorie}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
$R$-\definitionsverweis {aufzählbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $\Gamma$ eine
$R$-\definitionsverweis {aufzählbare}{}{}
Satzmenge, die $T$ axiomatisiert, und es sei
\mathbed {\alpha_n} {}
{n \in \N_+} {}
{} {} {} {,}
eine $R$-Aufzählung von $\Gamma$. Es sei
\mathbed {\beta_n} {}
{n \in \N_+} {}
{} {} {} {,}
eine $R$-Aufzählung der prädikatenlogischen Tautologien aus
\mathl{L^S}{.} Wenn ein Satz $\gamma$ aus $\Gamma$ ableitbar ist, so gibt es eine endliche Auswahl
\mathl{\alpha_1 , \ldots , \alpha_n}{} aus $\Gamma$
\zusatzklammer {bzw. aus der gewählten Aufzählung} {} {}
derart, dass
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \gamma} { }
eine prädikatenlogische Tautologie ist. Daher leistet das folgende Verfahren, bei dem $n$ wächst, das Gewünschte: Für jedes $n$ notiert man die Tautologien
\mathl{\beta_1 , \ldots , \beta_n}{} in der Form
\mavergleichskettedisp
{\vergleichskette
{ \beta_i
}
{ =} { \delta_1 \wedge \ldots \wedge \delta_s \rightarrow \epsilon
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wenn $\beta_i$ überhaupt diese Form besitzt, so ist diese eindeutig bestimmt. Danach überprüft man für jedes
\mavergleichskette
{\vergleichskette
{i
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
ob alle
\mathl{\delta_1 , \ldots , \delta_s}{} zu
\mathl{\{ \alpha_1 , \ldots , \alpha_n \}}{} gehören. Falls ja, und wenn $\epsilon$ ein Satz ist, so wird $\epsilon$ notiert. Danach geht man zum nächsten $i$. Wenn man
\mavergleichskette
{\vergleichskette
{i
}
{ = }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
erreicht hat, so geht man zu
\mathl{n+1}{,} wobei man aber wieder bei
\mavergleichskette
{\vergleichskette
{i
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
anfängt.
\inputfaktbeweis
{Theorie/Erster Stufe/Ableitbar/Aufzählbar, vollständig, widerspruchsfrei/Entscheidbar/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $L^ S$ die zugehörige
\definitionsverweis {Sprache erster Stufe}{}{.}}
\faktfolgerung {Jede
\definitionsverweis {aufzählbare}{}{}
\zusatzklammer {oder
\definitionsverweis {aufzählbar axiomatisierbare}{}{}} {} {,}
\definitionsverweis {widerspruchsfreie}{}{}
und
\definitionsverweis {vollständige Theorie}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\definitionsverweis {entscheidbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Nach
Lemma 21.9
bedeutet die aufzählbare Axiomatisierbarkeit, dass schon die Theorie selbst aufzählbar ist. Es sei also $T$ aufzählbar, vollständig und widerspruchsfrei, und sei
\mathbed {\alpha_n} {}
{n \in \N_+} {}
{} {} {} {,}
eine Aufzählung von $T$. Es sei
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \in }{ L^S_0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Satz. Wegen der Widerspruchsfreiheit und der Vollständigkeit gilt entweder
\mathkor {} {\beta \in T} {oder} {\neg \beta \in T} {.}
Daher kommt entweder
\mathkor {} {\beta} {oder} {\neg \beta} {}
in der Aufzählung von $T$ vor. Bei
\mavergleichskette
{\vergleichskette
{ \alpha_n
}
{ = }{ \beta
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und bei
\mavergleichskette
{\vergleichskette
{ \alpha_n
}
{ = }{\neg \beta
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \notin }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputbemerkung
{}
{
Eine widersprüchliche Theorie ist natürlich aufzählbar, vollständig und entscheidbar, da sie jeden Satz enthält. Ohne die Voraussetzung der Widerspruchsfreiheit ist aber das Argument im Beweis zu
Satz 21.10
nicht durchführbar. Wenn in einer Aufzählung einer Theorie eine widersprüchliche Aussage auftritt, so ist die Theorie natürlich widersprüchlich. Wenn aber bis zu einem bestimmten Zeitpunkt keine widersprüchliche Aussage auftritt, so lässt sich nicht entscheiden, ob dies an der Widerspruchsfreiheit der Theorie oder der Art der Aufzählung liegt. Wenn also in der Aufzählung $\neg \beta$ vorkommt, so kann man daraus nicht ohne die Bedingung der Widerspruchsfreiheit auf
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \notin }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schließen.
}
\inputfaktbeweis
{Arithmetik/Erster Stufe/Ableitbar/Nicht aufzählbar/Nicht axiomatisierbar/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {Die Menge der wahren arithmetischen Ausdrücke ist nicht
$R$-\definitionsverweis {aufzählbar}{}{.}}
\faktzusatz {D.h. es gibt kein $R$-Verfahren, das alle in $\N$ wahren Sätze der
\definitionsverweis {arithmetischen Sprache}{}{}
auflistet.}
\faktzusatz {}
}
{
Dies folgt direkt aus Satz 21.10 und aus Satz 21.2.
\inputfaktbeweis
{Peano-Arithmetik/Erste Stufe/Unvollständig/Fakt}
{Korollar}
{}
{
\faktsituation {}
\faktvoraussetzung {Die
\zusatzklammer {erststufige} {} {}
\definitionsverweis {Peano-Arithmetik}{}{}}
\faktfolgerung {ist
\definitionsverweis {unvollständig}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wegen
\mavergleichskette
{\vergleichskette
{PA
}
{ \subseteq }{\N^\vDash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
würde die Vollständigkeit hier die Gleichheit bedeuten. Da die Peano-Arithmetik
$R$-\definitionsverweis {aufzählbar}{}{}
ist, würde
aus Satz 21.10
die
\definitionsverweis {Entscheidbarkeit}{}{}
folgen im Widerspruch zu
Satz 21.2.
Die Lücke zwischen $PA$ und $\N^\vDash_0$ kann man nicht systematisch auffüllen, da man das vorstehende Argument auf jede aufzählbar-axiomatisierbare Theorie $T$ mit
\mathl{PA \subseteq T \subseteq \N^\vDash_0}{} anwenden kann.