Satz von Trachtenbrot

Der Satz von Trachtenbrot, benannt nach Boris Trachtenbrot, ist ein Satz aus der mathematischen Logik. Er wurde 1950 bewiesen[1] und besagt, dass die in allen endlichen Modellen allgemeingültigen Sätze der Prädikatenlogik erster Stufe nicht rekursiv aufzählbar sind. Daraus ergeben sich Konsequenzen für die Prädikatenlogik zweiter Stufe.

Formulierungen des Satzes

Es sei ${\displaystyle S_{\infty }}$ die Symbolmenge mit abzählbar unendlich vielen Konstantensymbolen und für jede Stelligkeit abzählbar unendlichen vielen Funktions- und Relationssymbolen. Weiter sei ${\displaystyle \Phi _{a}}$ die Menge aller ${\displaystyle L_{I}^{S_{\infty }}}$-Sätze der Prädikatenlogik erster Stufe, die in allen endlichen ${\displaystyle S_{\infty }}$-Strukturen erfüllt sind. Dann gilt:

${\displaystyle \Phi _{a}}$ ist nicht rekursiv aufzählbar.

Kurzfassung: Die im Endlichen allgemeingültigen Sätze erster Stufe sind nicht rekursiv aufzählbar.[2]

Weiter sei ${\displaystyle \Phi _{e}}$ die Menge aller ${\displaystyle L_{I}^{S_{\infty }}}$-Sätze, zu denen es eine ${\displaystyle S_{\infty }}$-Struktur gibt, in der sie erfüllt sind. Dann gilt:

${\displaystyle \Phi _{e}}$ ist nicht entscheidbar.

Kurzfassung: Die im Endlichen erfüllbaren Sätze erster Stufe sind nicht entscheidbar.[3][4]

Bemerkung zum Beweis

Die zweite Formulierung wird auf die Unlösbarkeit des Halteproblems zurückgeführt, in dem man ausnutzt, dass sich Turing-Maschinen in endlichen Modellen beschreiben lassen. Daraus ergibt sich dann die zuerst genannte Fassung, denn die im Endlichen allgemeingültigen Sätze sind genau die Negationen der im Endlichen nicht erfüllbaren Sätze.

Unvollständigkeit der Prädikatenlogik zweiter Stufe

Als Anwendung zeigen wir, wie aus dem Satz von Trachtenbrot die Unvollständigkeit der Prädikatenlogik zweiter Stufe folgt. Es sei ${\displaystyle \Phi }$ die Menge der Sätze der Prädikatenlogik zweiter Stufe, die in allen Modellen gültig sind. Dann gilt:

${\displaystyle \Phi }$ ist nicht rekursiv aufzählbar.

Diesen Sachverhalt nennt man die Unvollständigkeit der Prädikatenlogik zweiter Stufe. Zum Beweis sei ${\displaystyle \varphi _{endl}}$ ein Satz der Prädikatenlogik zweiter Stufe, der genau in endlichen Modellen gilt, etwa

${\displaystyle \varphi _{endl}=\forall X\,((\forall x\,\exists ^{1}y\,Xxy\,\land \,\forall xyz\,(Xxz\land Xyz\rightarrow x\equiv y))\rightarrow \forall y\,\exists x\,Xxy)}$,

d. h. für alle ${\displaystyle X}$ gilt, wenn ${\displaystyle X}$ eine Funktion ist und ${\displaystyle X}$ injektiv ist, dann ist ${\displaystyle X}$ surjektiv. Wäre nun ${\displaystyle \Phi }$ rekursiv aufzählbar, so starte man ein Aufzählungsverfahren und immer dann, wenn dieses eine Aussage der Form ${\displaystyle \varphi _{endl}\rightarrow \varphi }$ mit einem ${\displaystyle L_{I}^{S_{\infty }}}$-Satz ${\displaystyle \varphi }$ der Prädikatenlogik erster Stufe erzeugt, gebe man ${\displaystyle \varphi }$ aus. Auf diese Weise werden alle im Endlichen allgemeingültigen Sätze erster Stufe aufgezählt, was dem Satz von Trachtenbrot widerspricht.[5]

Einzelnachweise

1. B. Trakhtenbrot: Die Unmöglichkeit eines Algorithmus für das Entscheidungsproblem im Endlichen (Russisch), Doklady Akademii Nauk SSSR (1950), Band 70, Seiten 569–572. Englische Übersetzung in American Mathematical Society, Translations (1963), Series 2, Band 23, Seiten 1–5.
2. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, X, Satz 5.4
3. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, X, Satz 5.3
4. H.-D. Ebbinghaus, J. Flum, W. Thomas: Finite Model Theory, Springer Verlag, ISBN 3-540-28787-6, Theorem 7.2.1
5. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, X, Satz 5.5