An unsolvable problem of elementary number theory. (Q5923142)

Betrachten wir eine Klasse von Aussagen der elementaren Zahlentheorie, die eine freie Variable \(n\) (\(n\) positiv und ganz) oder auch mehrere derartige Variable \(x_1, x_2, \dots, x_m\) enthalten, z. B. die Aussage: Es gibt positive ganze Zahlen \(x, y, z\), so daß \(x^n + y^n = z^n\). Zu jeder derartigen Klasse von Aussagen gehört eine zahlentheoretische Funktion \(f\), so daß \(f (n)\) bzw. \(f(x_1, x_2, \dots, x_m)\) den Wert 2 oder 1 hat, je nachdem ob für \(n\) bzw. \(x_1, x_2, \dots, x_m\) die betreffende Aussage richtig oder falsch ist. Die Kenntnis eines Verfahrens, das uns für jedes \(n\) die Entscheidung über die Richtigkeit der Aussage ermöglichen würde, böte uns die Möglichkeit, den Wert von \(f(n)\) für jedes gegebene \(n\) zu berechnen. Das Umgekehrte ist natürlich ebenfalls der Fall. Funktionen der angegebenen Art, die die Eigenschaft der Berechenbarkeit besitzen, wollen wir rekursiv nennen. \textit{Church} gibt nun eine Funktion an, von der er beweist, daß sie nicht rekursiv ist. Die Bildung dieser Funktion steht in engem Zusammenhang mit dem \textit{Church}schen System der Logik (\textit{A. Church}, Proc. nat. Acad. Sci. USA 21 (1935), 275-281; F. d. M. \(61_{\text{I}}\), 55) und dem dort gebrauchten Begriff der Konversion. Zwei Formeln \(\mathfrak A\) und \(\mathfrak B\) des \textit{Church}schen Systems heißen durch Konversion ineinander überführbar, im (metamathematischen) Zeichen \(\mathfrak A\) conv \(\mathfrak B\), wenn \(\mathfrak B\) sich aus \(\mathfrak A\) nach den \textit{Church}schen Regeln zur Ableitung neuer Formehl gewinnen läßt. Nun läßt sich jeder Formel des \textit{Church}schen Systems nach dem Verfahren von \textit{Gödel} (\textit{K. Gödel}, Mh. Math. Phys. 38 (1931), 173-198; F. d. M. \(57_{\text{I}}\), 54) eine positive ganze Zahl als Repräsentant zuordnen. \(\mathfrak A\) conv \(\mathfrak B\) entspricht dann eine zahlentheoretische Aussage und eine zahlentheoretische Funktion der oben genannten Art mit zwei Argumenten. Von dieser Funktion zeigt der Verf. nun, daß die Annahme der Rekursivität auf einen Widerspruch führt. Das würde also bedeuten, daß es schon Probleme der elementaren Zahlenlehre gibt, die nicht entscheidbar sind. -- Um den Beweis führen zu können, muß der Verf. selbstverständlich den Begriff der Rekursivität formal genau bestimmen. Es fragt sich nun, ob sich dieser Begriff ein für allemal in einem formalen System genau festlegen läßt und ob nicht jedes derartige System einer unendlichen Erweiterung fähig ist. Oder um die Frage zunächst einfacher zu formulieren: Gibt es zahlentheoretische Funktionen, die zwar die Eigenschaft der Berechenbarkeit besitzen, aber nicht ``rekursiv'' im \textit{Church}schen Sinne sind? Diese Frage ist sicher nicht einfach zu entscheiden, denn tatsächlich ist die \textit{Church}sche Definition der Rekursivität die allgemeinste, die wir kennen. (Über andere Definitionen der Rekursivität siehe z. B. \textit{D. Hilbert}, \textit{P. Bernays}, Grundlagen der Mathematik I (1934; F. d. M. \(60_{\text{I}}\), 17-19), Kap. 7.) Jedenfalls gibt uns die vorliegende Arbeit eine gewisse Erklärung dafür, weshalb so viele verhältnismäßig einfach zu formulierende Probleme der elementaren Zahlentheorie so große Schwierigkeiten bieten und bisher der Inangriffnahme trotzten.