Gödel, Escher, Bach - ein Endloses Geflochtenes Band

ist nicht der Sukzessor irgendeiner natürlichen Zahl“ sind. Deshalb ist es gut, daß sie sich leicht ineinander umwandeln lassen.
    Die nächste Regel ist, wenn möglich, noch anschaulicher. Sie entspricht der sehr einfachen Art logischen Schließens, wenn wir von „2 ist eine Primzahl“ zu „Es gibt eine Primzahl“ übergehen. Die Benennung der Regel bedarf keiner Erklärung:
    E XISTENZREGEL : Angenommen ein Term (der Variablen enthalten kann, vorausgesetzt daß sie frei sind) tritt ein oder mehrere Male in einem S ATZ auf. Dann kann jeder einzelne Auftritt des Terms (oder können einige oder alle Auftritte) durch eine Variable ersetzt werden, die sonst in dem S ATZ nicht auftritt, und der entsprechende Existenzquantor muß vorangestellt werden.
    Wenden wir diese Regel — wie gewohnt — auf Axiom 1 an:
∀a :~ Sa = 0
Axiom 1
∃b : ∀a :~ Sa = b
Existenzregel
    Der Leser könnte jetzt versuchen, nach den bisher gegebenen Regeln Symbole herumzuschieben, um den S ATZ zu erzeugen: ~ ∀b : ∃a : Sa = b .
Regeln für Gleichheit und Sukzessor
    Wir haben Regeln für die Manipulation von Quantoren angegeben, aber bis jetzt noch keine für die Symbole „=“ und „ S “. Das holen wir nunmehr nach. Im folgenden stehen r, s und t alle für beliebige Terme.
    G LEICHHEITSREGELN :
    S YMMETRIE : Wenn r = s ein S ATZ ist, dann auch s = r.
    T RANSITIVITÄT : Wenn r = s und s = t S ÄTZE sind, dann auch r = t.
    R EGELN FÜR DEN S UKZESSOR :
    A NFÜGEN VON S: Wenn r=t ein S ATZ ist, dann auch S r= S t.
    W EGLASSEN VON S: Wenn S r= S t ein S ATZ ist, dann auch r=t.
    Wir sind nunmehr mit Regeln ausgerüstet, die uns eine phantastische Vielfalt von S ÄTZEN liefern können. Zum Beispiel ergeben die folgenden Ableitungen ziemlich grundlegende S ÄTZE :
1)
∀a : ∀b :( a + Sb )= S ( a + b )
Axiom 3
2)
∀b :( S0 + Sb )= S ( S0 + b )
Spezialisierungsregel ( S0 für a )
3)
( S0 + S0 )= S ( S0 + 0 )
Spezialisierungsregel ( 0 für b )
4)
∀a :( a + 0 )= a
Axiom 2
5)
( S0 + 0 )= S0
Spezialisierungsregel ( S0 für a )
6)
S ( S0 + 0 )= SS0
S anfügen
7)
( S0 + S0 )= SS0
Transitivität (Zeilen 3, 6)
 
* * * * *
 
1)
∀a : ∀b :( a·Sb )=(( a·b )+ a )
Axiom 5
2)
∀b :( S0·Sb )=(( S0·b )+ S0 )
Spezialisierungsregel ( S0 für a )
3)
( S0·S0 )=(( S0·0 )+ S0 )
Spezialisierungsregel ( 0 für b )
4)
∀a : ∀b :( a + Sb )= S ( a + b )
Axiom 3
5)
∀b :(( S0·0 )+ Sb )= S (( S0·0 )+ b )
Spezialisierungsregel (( S0·0 ) für a )
6)
(( S0·0 )+ S0 )= S (( S0·0 )+ 0 )
Spezialisierungsregel ( 0 für b )
7)
∀a :( a + 0 )= a
Axiom 2
8)
(( S0·0 )+ 0 )=( S0·0 )
Spezialisierungsregel (( S0·0 ) für a )
9)
∀a :( a·0 )= 0
Axiom 4
10)
( S0·0 )= 0
Spezialisierungsregel ( S0 für a )
11)
(( S0·0 )+ 0 )= 0
Transitivität (Zeilen 8, 10)
12)
S (( S0·0 )+ 0 )= S0
S anfügen
13)
(( S0·0 )+ S0 )= S0
Transitivität (Zeilen 6, 12)
14)
( S0·S0 )= S0
Transitivität (Zeilen 3, 13)
Illegale Abkürzungen
    Hier erhebt sich eine interessante Frage: „Wie können wir eine Ableitung für die Kette 0 = 0 herstellen?“ Der nächstliegende Weg scheint der zu sein, daß wir zuerst die Kette ∀a : a = a ableiten und dann von der Spezialisierungsregel Gebrauch machen. Wie stehtes nun mit der folgenden „Ableitung“ von ∀a : a = a ... Was stimmt hier nicht? Kann man es ins Lot bringen?
1)
∀a :( a + 0 )= a
Axiom 2
2)
∀a : a =( a + 0 )
Symmetrieregel
3)
∀a : a = a
Transitivität (Zeilen 2, 1)
    Ich stellte diese Mini-Aufgabe, um eine einfache Tatsache zu unterstreichen: Man sollte bei der Manipulation von Symbolen (wie z. B. „=“), mit denen man vertraut ist, nicht zu voreilig sein. Man muß den Regeln folgen und nicht seinem Wissen um die passive Bedeutung der Symbole. Natürlich ist Wissen dieser Art von unschätzbarem Wert, wenn man den Weg einer Ableitung verfolgt.
Warum Spezialisierung und Generalisierung eingeschränkt sind
    Wir wollen nunmehr herausfinden, warum sowohl bei der Spezialisierung als auch bei der Generalisierung Einschränkungen nötig sind. Es folgen zwei Ableitungen. In beiden wurde eine der Einschränkungen nicht beachtet. Man sehe sich die katastrophalen Ergebnisse an, die so entstehen:
000000000000000000000
1)
[
push
2)
a = 0
Voraussetzung
3)
∀a : a = 0
Generalisierungsregel (falsch)
4)
Sa = 0
Spezialisierungsregel
5)
]
pop
6)
< a = 0 ⊃ Sa = 0 >
Fantasieregel
7)
∀a :< a = 0 ⊃ Sa = 0 >
Generalisierungsregel
8)
< 0 = 0 ⊃ S0 = 0 >
Spezialisierungsregel
9)
0 = 0
vorhergehender S ATZ
10)
S0 = 0
Abtrennung