Gibt es Arten von Arithmetik, die trotz des Satzes von Gödel entscheidbar sind?

Ja, es gibt entscheidbare Arithmetik. Aber Gödels ursprünglicher Beweis aus dem Jahr 1931 stand im Rahmen von Russells Principia Mathematica, die gewählt wurde, weil sie zu dieser Zeit der am weitesten entwickelte logische Rahmen für die Reproduktion der gesamten Mathematik war. Später vereinfachte er den Beweis und zeigte, dass die Peano-Arithmetik ausreicht.

In Anlehnung an Ihren ersten Vorschlag gibt es die Presburger Arithmetik , die 1929 eingeführt wurde, etwa ein Jahr bevor Gödel sein Ergebnis erhielt. Es hat Addition, Gleichheit und sogar Induktion, aber keine Multiplikation. Das Fehlen der Multiplikation schließt die Definition der Gödel-Nummerierung und damit die Konstruktion von Gödel-Sätzen aus. Dies ist kein Beweis der Vollständigkeit, aber es erklärt, warum es rückwirkend gilt, Presburger selbst hat einen expliziten Entscheidungsalgorithmus erstellt. Ein Algorithmus mag es sein, aber er ist nicht zu einfach. Fischer und Rabin haben 1974 bewiesen, dass die Rechenkomplexität des Entscheidungsproblems doppelt exponentiell ist. Eine interessante Tatsache über den Unterschied zwischen den beiden Arithmetiken: Glivický und Kalahat kürzlich ein Modell der Presburger Arithmetik erstellt, bei dem der Satz von Fermat Last versagt, und es gibt unendlich viele Gegenbeispiele. Es wird angenommen, dass dies für die Peano-Arithmetik nicht passieren kann, obwohl dies technisch nicht aus dem Beweis von Wiles folgt, siehe Gibt es nicht standardmäßige Gegenbeispiele zum Satz von Fermat Last?

Die beiden anderen Vorschläge sind nicht so einfach umzusetzen, weil Endlichkeit Eigenschaft eines Modells ist, nicht einer formalen Theorie. Versuche, Endlichkeit in Axiome (erster Ordnung) zu schreiben, a la Dedekind zum Beispiel, produzieren etwas, was nicht das ist, was es intuitiv bedeutet (es gibt unendliche Modelle von Theorien, die in Axiomen "beanspruchen", endlich zu sein). Wenn wir uns jedoch für ein Modell mit endlichem Definitionsbereich anstelle einer Theorie erster Ordnung entscheiden, ist das natürlich entscheidbar, weil man alle Möglichkeiten durch erschöpfende Suche prüfen kann.

Es gibt eine Art Arithmetik mit endlichen Modellen, die alle Ressourcen der Peano-Arithmetik schont, aber die klassische Logik durch die parakonsistente Logik LP ersetzt. Dies sind Priesters widersprüchliche Arithmetik . Beachten Sie eine Subtilität im Begriff der Vollständigkeit für inkonsistente Modelle: Während es ein Entscheidungsverfahren gibt, das jedem Satz wahr/falsch zuweist, wird es einige geben, denen es beide zuweist , die als wahre Widersprüche oder Diatheien bezeichnet werden. Der Grund, warum wir ein endliches Modell haben können, ist, dass wir "inkonsistente ganze Zahlen" haben können, für die n = n + 1, dies zu einem echten Widerspruch führt, aber die Theorie nicht trivialisiert, parakonsistent, dass sie ist. Tatsächlich ist das Modell für alle Zahlen kleiner als die am wenigsten inkonsistente Zahl N identisch mit der üblichen Peano-Arithmetik, und Priest argumentiert, dass wir unmöglich wissen können, was von Objekten in unserer Welt "wahr" ist, wenn N exorbitant groß ist, siehe seine Was könnte die am wenigsten widersprüchliche Zahl sein?

Dies bestätigt Wittgensteins paradoxe Meinung , dass Inkohärenz kein Problem für die Rechenmathematik (oder jedes Sprachspiel) ist, und seine Antizipation parakonsistenter Logik:

„ Irgendetwas sagt mir, dass ein Widerspruch in den Axiomen eines Systems nicht wirklich schaden kann, bis er aufgedeckt wird. Wir denken an einen versteckten Widerspruch wie an eine versteckte Krankheit, die schadet, obwohl (und vielleicht gerade weil) Das zeigt sich nicht auf naheliegende Art. Aber zwei Spielregeln, die sich in einem bestimmten Fall widersprechen, sind bis zum Erscheinen des Falles vollkommen in Ordnung, und erst dann wird es notwendig, zwischen ihnen durch eine weitere Regel zu entscheiden ... Na dann, ziehe aus einem Widerspruch keine Schlüsse, sondern mach das zur Regel. “

Ein wichtiges Beispiel ist die übliche Arithmetik reeller Zahlen – ein berühmter Satz von Tarski besagt, dass die Theorie der reellen abgeschlossenen Körper entscheidbar ist.

Aus gewisser Sicht liegt die Schwierigkeit der ganzzahligen Arithmetik gerade darin, dass es nicht genug davon gibt – die Komplexität der Zahlentheorie kommt daher, dass es so viele Gleichungen gibt, die keine Lösungen haben. Wenn man sich erlaubt, Polynome zu wurzeln (und aus den komplexen die reellen Zahlen ziehen zu können), vereinfacht sich die Theorie sehr.

Wenn Conifolds Antwort angesichts ihrer Weitläufigkeit überhaupt am Punkt vorbeigeht, müssen Sie meinen: "Warum hat Gödel die Arithmetik gewählt?" Und die Antwort muss lauten, dass der Bauablauf in jeder anderen Form zu fremd wäre.

Was philosophisch wichtig ist, ist, dass eine stärkere Logik die Dinge nicht immer entscheidbarer machen kann. Rechnen ist nebensächlich. Aber es ist so tief in uns verwurzelt, dass es keinen Sinn macht, es zu vermeiden.

Wir wissen, dass ZF nicht vollständig ist, weil wir die Arithmetik aus der Mengenlehre aufbauen können, angesichts des Standardansatzes, die ganzen Zahlen als einen Turm von Anfangssegmenten von "Omega" zu definieren. Wir müssen also nicht mit der Arithmetik beginnen , solange wir unterwegs darauf stoßen. Im Falle der Mengenlehre ist sie nicht unser Hauptanliegen.

Es scheint mir, dass wir wissen, dass das eigentliche Problem irgendwie von der Stärke der Induktion abhängt, die die Rekursion unterstützt. Induktion reduziert auf nur die unendliche Menge von Axiomen, die erster Ordnung bleiben, bringt Ihnen keinen Beweis. Sie erhalten Presburger-Arithmetik, die nicht stark genug ist, um zu scheitern, es sei denn, Sie treten aus dem System heraus und berechnen verschiedene Tatsachen der Multiplikation vorab, die man normalerweise durch vollständige Induktion über Addition ableitet.

Sie brauchen nicht unbedingt eine vollständige Induktion zweiter Ordnung, die Teil der ursprünglichen Peano-Definition ist. Wir kommen mit einem Induktionsdurchgang aus, um das Verhalten der Addition festzustellen und die Multiplikation zu definieren, aber dann brauchen wir nur die Version erster Ordnung für den zweiten Induktionsdurchgang.

Zwei Induktionsdurchgänge werden offensichtlich Ihre Fähigkeit zerstören, die Wahrheit in Ihrem System zu definieren. Wenn Sie ein starkes, konsistentes System wollen, reicht einer nicht aus und zwei sind zu viel.

Wir können uns vorstellen, dass eine nicht-arithmetische Sichtweise immer noch ein Konzept des Zählens beinhalten würde, um das Äquivalent der Induktion zu begründen, aber alternative Konzepte des Zählens scheinen Zeitverschwendung zu sein.