Kategorien
Logik Paradoxe

Kleene-Rosser-Paradoxon

In der Mathematik ist das Kleene-Rosser-Paradoxon ein Paradoxon, das zeigt, dass bestimmte Systeme der formalen Logik inkonsistent sind, insbesondere die 1930 eingeführte Version von Currys kombinatorischer Logik und die ursprüngliche Lambda-Rechnung der Kirche, die 1932–1933 eingeführt wurde und beide ursprünglich als gedacht war Systeme der formalen Logik. Das Paradoxon wurde 1935 von Stephen Kleene und JB Rosser ausgestellt.

Das Paradox
Kleene und Rosser konnten zeigen, dass beide Systeme ihre nachweislich vollständigen, definierbaren zahlentheoretischen Funktionen charakterisieren und aufzählen können, wodurch sie einen Begriff konstruieren konnten, der das Richard-Paradoxon in formaler Sprache im Wesentlichen repliziert.

Später gelang es Curry, die entscheidenden Bestandteile der Kalküle zu identifizieren, die die Konstruktion dieses Paradoxons ermöglichten, und daraus ein viel einfacheres Paradoxon zu konstruieren, das heute als Curry-Paradoxon bekannt ist.

1935 veröffentlichten Kleene und Rosser einen Beweis dafür, dass bestimmte Systeme der formalen Logik inkonsistent sind, in dem Sinne, dass jede Formel, die in ihrer Notation ausgedrückt werden kann, auch nachweisbar ist. Es gibt also nur zwei Systeme in der Literatur, für die dieser Inkonsistenzbeweis gilt; Das kirchliche System von 1932-1933 und das, was ich 1934 als 8-System bezeichnete. Trotz dieser begrenzten Anwendung ist das Argument von Kleene und Rosser ein Theorem von großer Bedeutung für die Führung künftiger Forschung. Es ist ein Theorem mit demselben allgemeinen Charakter wie die berühmten Unvollständigkeitssätze von Löwenheim, Skolem und Godel, die in der jüngsten Forschung zu mathematischen Grundlagen eine so herausragende Rolle gespielt haben.

Der Beweis von Kleene und Rosser ist lang und kompliziert und enthält Komplikationen, die dazu neigen, die wesentliche Bedeutung ihres Satzes zu verschleiern. Dementsprechend besteht ein gewisses Interesse an dem Problem, dieses Paradoxon zugänglicher zu machen und es so darzustellen, dass diese wesentliche Bedeutung deutlicher hervorgehoben wird. Dies versucht das vorliegende Papier zu tun. Das Paradoxon wird hier durch eine Methode dargestellt und abgeleitet, die unter dem angegebenen Gesichtspunkt viele Vorteile gegenüber den ursprünglichen Entdeckern aufweist.

Bevor wir auf eine ausführliche Diskussion eingehen, ist es zweckmäßig, das Paradoxon vage vorab zu untersuchen und die zentrale Idee in ihrer Ableitung intuitiv zu erläutern

Eines der Ziele, auf die Mathematiker beim Aufbau formaler Systeme abzielen, ist die Vollständigkeit – womit ich nicht die Vollständigkeit im technischen Sinne meine, sondern einfach die Angemessenheit des Systems für den einen oder anderen Zweck.

Es gibt zwei Arten solcher Vollständigkeit, die besonders betroffen sind; beide sind wünschenswerte Eigenschaften formaler Systeme der mathematischen Logik. Diese kombinatorische Vollständigkeit bzw. deduktive Vollständigkeit. Sie können grob wie folgt erklärt werden. Eine Theorie ist genau dann kombinatorisch vollständig, wenn jeder Ausdruck A, der aus den Begriffen des Systems und einem unbestimmten oder variablen Hilfsmittel x gebildet wird, innerhalb des Systems als Funktion von x dargestellt werden kann (dh wir können im System eine Funktion bilden, deren Der Wert für ein beliebiges Argument entspricht dem Ergebnis des Ersetzens dieses Arguments für x in W). Eine Theorie ist deduktiv vollständig, wenn wir, wenn wir einen Satz B auf der Hypothese ableiten können, dass ein anderer Satz A gilt, ohne Hypothese einen dritten Satz (wie A ^) B ableiten können, der diese Ableitbarkeit ausdrückt. Die kombinatorische Vollständigkeit ist somit eine Eigenschaft, die sich auf die möglichen Konstruktionen von Begriffen (oder Formeln) innerhalb des Systems bezieht. Die deduktive Vollständigkeit bezieht sich auf die möglichen Ableitungen. Die deduktive Vollständigkeit ist eine bekannte Eigenschaft bestimmter Systeme. Die kombinatorische Vollständigkeit wurde erst in den letzten Jahren erreicht.

Das Wesentliche des Kleene-Rosser-Theorems ist, dass es zeigt, dass diese beiden Arten der Vollständigkeit nicht kompatibel sind – dh dass jedes System, das beide besitzt, inkonsistent ist. Das Argument ist im Wesentlichen eine Verfeinerung des Richard-Paradoxons; es zeigt in der Tat, dass das Richard-Paradoxon formal innerhalb des Systems eingerichtet werden kann.

Um dies vorläufig zu sehen, stellen wir das Richard-Paradoxon wie folgt auf. In jedem formalen System der Arithmetik ist die Anzahl definierbarer numerischer Funktionen natürlicher Zahlen aufzählbar; Lassen Sie sie daher in einer Reihenfolge aufzählen

Lassen wir die Erklärung dieses Paradoxons aus intuitiver Sicht außer Acht und betrachten wir, was bei einem System geschieht, das sowohl kombinatorisch als auch deduktiv vollständig ist. Wenn in einem solchen System eine Funktion eine numerische Funktion ist, dh wenn sie numerische Werte für alle numerischen Argumente (u) angibt, kann eine formale Aussage dieser Tatsache innerhalb des Systems demonstriert werden, da sie deduktiv vollständig ist; Durch eine rekursive Aufzählung aller Theoreme kann dann die Menge aller numerischen Funktionen effektiv in einer Folge aufgezählt werden. Da die Theorie kombinatorisch vollständig ist, können wir dann innerhalb des Systems die Funktion / definieren; Dies ist nachweislich eine numerische Funktion, und die Demonstration dieser Tatsache wird uns den Wert von n effektiv sagen, so dass der obige Widerspruch sicherlich entstehen wird.

Dies zeigt auf grobe Weise die Natur des Paradoxons. Bevor wir zu den formalen Entwicklungen übergehen, werde ich einige Bemerkungen zum vorliegenden Beweis und seiner Beziehung zu dem von Kleene und Rosser interpolieren.

Bei den Untersuchungen von Church und seinen Schülern wird die postulierte kombinatorische Vollständigkeit dadurch geschwächt, dass das A tatsächlich x enthält – so dass es keinen Apparat zur Darstellung einer Konstanten als Funktion geben muss; Es gibt auch eine Schwächung der deduktiven Vollständigkeit. Diese Komplikationen vermeiden nicht das Paradoxon, wie Kleene und Rosser gezeigt haben; Sie erhöhen jedoch die Länge und Komplexität der Ableitung erheblich. Wenn das Ziel darin besteht, den zentralen Nerv des Paradoxons freizulegen, besteht der logische Ansatz darin, den Beweis für den einfacheren Fall, den der kombinatorischen (und deduktiven) Vollständigkeit im starken Sinne, durchzuführen und dann zu zeigen, welche Änderungen erforderlich sind Führen Sie den Beweis für den komplizierteren Fall durch.