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

in der TNT-Notation) verläuft keineswegs gerade; es ist eine Grenze mit vielen gefährlichen Kurven (man denke an Abb. 18 !), eine Grenze, von der die Mathematiker im Verlauf von Jahrhunderten hier und da Teilstücke festgelegt haben. Man stelle sich vor, was für eine Sensation es wäre, eine typographische Methode zu besitzen, die jede Formel garantiert auf der richtigen Seite dieser Grenze plaziert!
Die Regeln des Wohlgeformtseins
    Es ist nützlich, eine Tabelle der Regeln für die Bildung wohlgeformter Formeln zu haben; wir geben sie nachstehend. Es gibt einige Vorstadien: die Definition von Zahlzeichen, Variablen und Termen. Diese drei Klassen von Ketten sind Bestandteile von wohlgeformten Formeln, aber selber nicht wohlgeformt. Die kleinsten wohlgeformten Formeln sind die Atome; sodann gibt es Möglichkeiten, Atome zusammenzusetzen. Viele dieser Regeln sind rekursive Verlängerungsregeln, indem sie als Eingabe ein Element einer gegebenen Klasse annehmen und ein längeres Element der gleichen Klasse erzeugen. In dieser Tabelle gebrauche ich „ x “ und ,, y “ für wohlgeformte Formeln, und „s“, „t“ und „u“ für andere Arten von TNT-Ketten. Natürlich ist keines dieser fünf Symbole selber ein Symbol von TNT.
    Z AHLZEICHEN
    0 ist ein Zahlzeichen.
    Ein Zahlzeichen, dem ein S vorausgeht, ist ebenfalls ein Zahlzeichen.
    Beispiele: 0   S0   SS0   SSS0   SSSS0   SSSSS0
    V ARIABLEN
    a ist eine Variable. Wenn wir nicht streng sein wollen, sind es auch b , c , d und e . Eine Variable, der ein oder mehrere Striche folgen, ist ebenfalls eine Variable.
    Beispiele: a    b '   c ''   d '''   e ''''
    T ERME
    Alle Zahlzeichen und Variablen sind Terme.
    Ein Term, vor dem S steht, ist ebenfalls ein Term. Wenn s und t Terme sind, dann auch (s + t) und (s · t).
    Beispiele: 0   b    SSa '   ( S0 · ( SS0 + c ))   S ( Sa · ( Sb·Sc ))
    T ERME können in zwei Kategorien aufgeteilt werden:
1)
D EFINITE Terme. Diese enthalten keine Variablen.
Beispiele: 0    ( S0 + S0 )   SS (( SS0·SS0 )+( S0·S0 ))
2)
I NDEFINITE Terme. Diese enthalten Variablen.
Beispiele: b   Sa    ( b + S0 )   ((( S0 + S0 )+ S0 )+ e )
    Die oben genannten Regeln sagen uns, wie man Teile wohlgeformter Formeln, die restlichen Regeln, wie man vollständige wohlgeformte Formeln erzeugen kann.
    A TOME
    Wenn s und t Terme sind, dann ist s = t ein Atom.
    Beispiele: S0 = 0    ( SS0 + SS0 )= SSSS0    S ( b + c )=(( c·d ) · e )
    Wenn ein Atom eine Variable u enthält, dann ist u in ihm frei. So gibt es im letzten Beispiel vier freie Variablen
    V ERNEINUNGEN
    Eine wohlgeformte Formel, der eine Tilde vorangestellt wird, ist wohlgeformt.
    Beispiele: ~ S0 = 0    ~ ∃b :( b + b )= S0    ~< 0 = 0 ⊃ S0 = 0 >   ~ b = S0
    Der Quantifizierungsstatus  einer Variablen (der uns sagt, ob sie frei oder quantifiziert ist) ändert sich bei Verneinung nicht.
    Z USAMMENSETZUNGEN
    Sind x und y wohlgeformte Formeln, und vorausgesetzt, daß keine Variable in der einen frei, in der anderen quantifiziert ist, dann sind alle folgenden Ausdrücke wohlgeformte Formeln:
    , ,
    Beispiele: < 0 = 0 ∧~ 0 = 0 >   < b = b ∨~ ∃c : c = b >   < S0 = 0 ⊃ ∀c :~ ∃b :( b + b )= c >
    Der Quantifizierungsstatus einer Variablen ändert sich hier nicht.
    Q UANTIFIZIERUNGEN
    Wenn u eine Variable ist und x eine wohlgeformte Formel, in der u frei ist, dann sind die folgenden Ketten wohlgeformte Formeln:
    ∃ u:x und ∀ u:x.
    Beispiele: ∀b :< b = b ∨~ ∃c : c = b >   ∀c :~ ∃b :( b + b )= c    ~ ∃c : Sc = d
    O FFENE F ORMELN enthalten mindestens eine freie Variable.
    Beispiele: ~ c = c    b = b    < ∀b : b = b ∧~ c = c >
    G ESCHLOSSENE F ORMELN (A USSAGEN ) enthalten keine freien Variablen.
    Beispiele: S0 = 0    ∀d : d = 0    ∃c :< ∀b : b = b ∧~ c = c >
    Damit ist die Tabelle der Erzeugungsregeln für die wohlgeformten Formeln von TNT vollständig.
Noch ein paar Übersetzungsübungen
    Und jetzt ein paar praktische Übungen für den Leser, um zu prüfen, ob er die Notationen in TNT versteht. Er versuche, die vier ersten der folgenden N-Aussagen in TNT-Formeln zu übersetzen, und die letzte in eine offene wohlgeformte Formel.
    Alle natürlichen Zahlen sind gleich 4.
    Es gibt keine natürliche Zahl, die gleich ihrem eigenen Quadrat ist.
    Verschiedene natürliche Zahlen haben verschiedene Nachfolger.
    Wenn 1 gleich 0 ist, dann ist jede Zahl ungerade.
    b ist eine Potenz von