Satz von Gödel wobei die unabhängige Variable ist. Bekenntnis eines großen Logikers

Jedes System mathematischer Axiomen ist ab einer gewissen Komplexität entweder in sich widersprüchlich oder unvollständig.

1900 fand in Paris die Weltkonferenz der Mathematiker statt, auf der David Hilbert (1862–1943) die seiner Meinung nach wichtigsten 23 von ihm formulierten Probleme, die von theoretischen Wissenschaftlern gelöst werden sollten, in Form von Thesen vorstellte des kommenden zwanzigsten Jahrhunderts. Nummer zwei auf seiner Liste war eines dieser einfachen Probleme, die offensichtlich erscheinen, bis Sie ein wenig tiefer graben. Modern formuliert war es die Frage: Reicht die Mathematik allein aus? Hilberts zweite Aufgabe reduzierte sich darauf, strikt zu beweisen, dass das Axiomensystem – Grundaussagen der Mathematik ohne Beweis zugrunde gelegt – vollkommen und vollständig sind, also alles Existierende mathematisch beschreiben können. Es musste nachgewiesen werden, dass es möglich ist, ein solches System von Axiomen aufzustellen, dass sie erstens miteinander konsistent sind und zweitens daraus Rückschlüsse auf die Wahrheit oder Falschheit einer Aussage gezogen werden können.

Nehmen wir ein Beispiel aus der Schulgeometrie. In der standardmäßigen euklidischen Planimetrie (Geometrie auf einer Ebene) kann bedingungslos bewiesen werden, dass die Aussage „Die Winkelsumme eines Dreiecks beträgt 180°“ und die Aussage „Die Winkelsumme eines Dreiecks beträgt 137°“ wahr ist " ist falsch. Im Wesentlichen ist in der euklidischen Geometrie jede Aussage entweder falsch oder wahr, und die dritte ist nicht gegeben. Und zu Beginn des zwanzigsten Jahrhunderts glaubten Mathematiker naiv, dass die gleiche Situation in jedem logisch konsistenten System beobachtet werden sollte.

Und dann veröffentlichte 1931 irgendein bebrillter Wiener Mathematiker Kurt Gödel einen kurzen Artikel, der einfach die ganze Welt der sogenannten „mathematischen Logik“ auf den Kopf stellte. Nach langen und komplexen mathematischen und theoretischen Präambeln stellte er buchstäblich Folgendes fest. Nehmen wir eine Aussage wie: „Annahme Nr. 247 ist in diesem Axiomensystem logisch unbeweisbar“ und nennen sie „Aussage A“. Also bewies Gödel einfach die folgende erstaunliche Eigenschaft jedes Axiomensystems:

"Wenn eine Aussage A bewiesen werden kann, dann kann eine Nicht-A-Aussage bewiesen werden."

Mit anderen Worten, wenn es möglich ist, die Gültigkeit der Aussage „Annahme 247 ist nicht beweisbar“ zu beweisen, dann ist es auch möglich, die Gültigkeit der Aussage „Annahme 247 ist beweisbar“ zu beweisen. Das heißt, um zur Formulierung des zweiten Hilbert-Problems zurückzukehren, wenn das Axiomensystem vollständig ist (dh jede Aussage darin bewiesen werden kann), dann ist es inkonsistent.

Der einzige Ausweg aus dieser Situation besteht darin, ein unvollständiges System von Axiomen zu akzeptieren. Das heißt, wir müssen uns damit abfinden, dass wir im Kontext jedes logischen Systems immer noch „Typ A“-Aussagen haben werden, die offensichtlich wahr oder falsch sind, und wir können ihre Wahrheit nur außerhalb des Rahmens der Axiomatik beurteilen, die wir haben angenommen. Wenn es solche Aussagen nicht gibt, dann ist unsere Axiomatik widersprüchlich, und in ihrem Rahmen wird es zwangsläufig Formulierungen geben, die sowohl bewiesen als auch widerlegt werden können.

Die Formulierung von Gödels erstem oder schwachem Unvollständigkeitssatz lautet also: "Jedes formale System von Axiomen enthält ungelöste Annahmen." Aber Gödel hörte hier nicht auf und formulierte und bewies Gödels zweiten oder starken Unvollständigkeitssatz: „Die logische Vollständigkeit (oder Unvollständigkeit) irgendeines Systems von Axiomen kann nicht im Rahmen dieses Systems bewiesen werden. Um es zu beweisen oder zu widerlegen, sind zusätzliche Axiome (Stärkung des Systems) erforderlich.“

Es wäre sicherer zu glauben, dass Gödels Theoreme abstrakt sind und uns nichts angehen, sondern nur Bereiche erhabener mathematischer Logik, aber tatsächlich stellte sich heraus, dass sie direkt mit der Struktur des menschlichen Gehirns zusammenhängen. Der englische Mathematiker und Physiker Roger Penrose (geb. 1931) zeigte, dass Gödels Theoreme verwendet werden können, um grundlegende Unterschiede zwischen dem menschlichen Gehirn und einem Computer zu beweisen. Der Punkt seiner Argumentation ist einfach. Der Computer arbeitet streng logisch und kann nicht feststellen, ob Aussage A wahr oder falsch ist, wenn dies den Rahmen der Axiomatik sprengt, und solche Aussagen sind nach dem Satz von Gödel zwangsläufig vorhanden. Eine Person, die mit einer solchen logisch nicht beweisbaren und unwiderlegbaren Aussage A konfrontiert ist, ist immer in der Lage, ihre Wahrheit oder Falschheit zu bestimmen - basierend auf alltäglichen Erfahrungen. Zumindest darin ist das menschliche Gehirn einem durch reine Logikschaltkreise gefesselten Computer überlegen. Das menschliche Gehirn ist in der Lage, die ganze Tiefe der Wahrheit zu verstehen, die in Gödels Theoremen enthalten ist, aber ein Computer kann das niemals. Das menschliche Gehirn ist also alles andere als ein Computer. Er ist in der Lage, Entscheidungen zu treffen, und der Turing-Test wird bestanden.

Ich frage mich, ob Hilbert eine Ahnung hatte, wie weit uns seine Fragen bringen würden?

Kurt Gödel
Kurt Gödel, 1906–78

Österreichischer, dann amerikanischer Mathematiker. Geboren in Brünn (Brünn, jetzt Brünn, Tschechien). Er absolvierte die Universität Wien, wo er Lehrer an der Fakultät für Mathematik blieb (seit 1930 - Professor). 1931 veröffentlichte er einen Satz, der später seinen Namen erhielt. Als rein unpolitischer Mensch überlebte er die Ermordung seines Freundes und Abteilungsmitarbeiters durch einen NS-Studenten äußerst hart und verfiel in eine tiefe Depression, deren Rückfälle ihn bis an sein Lebensende verfolgten. In den 1930er Jahren emigrierte er in die Vereinigten Staaten, kehrte aber in seine Heimat Österreich zurück und heiratete. 1940, auf dem Höhepunkt des Krieges, musste er auf der Durchreise durch die UdSSR und Japan nach Amerika fliehen. Einige Zeit arbeitete er am Princeton Institute for Advanced Study. Leider konnte die Psyche des Wissenschaftlers es nicht ertragen und er verhungerte in einer psychiatrischen Klinik und weigerte sich zu essen, weil er überzeugt war, dass sie ihn vergiften wollten.

Kommentare: 0

    Wie entwickelt sich das Wissenschaftsmodell in den Naturwissenschaften? Alltägliche oder wissenschaftliche Erfahrungen sammeln sich an, ihre Meilensteine ​​sind in Form von Postulaten sauber formuliert und bilden die Grundlage des Modells: eine Reihe von Aussagen, die von allen akzeptiert werden, die innerhalb dieses Modells arbeiten.

    Anatoli Wassermann

    1930 bewies Kurt Gödel zwei Theoreme, die, von der mathematischen Sprache in die menschliche Sprache übersetzt, etwa Folgendes bedeuten: Jedes Axiomensystem, das reich genug ist, um zur Definition der Arithmetik verwendet zu werden, ist entweder unvollständig oder inkonsistent. Ein unvollständiges System bedeutet, dass im System eine Aussage formuliert werden kann, die mit diesem System weder bewiesen noch widerlegt werden kann. Aber Gott ist per Definition die ultimative Ursache aller Ursachen. Mathematisch bedeutet dies, dass die Einführung des Axioms über Gott unser gesamtes Axiom vervollständigt. Wenn es einen Gott gibt, dann kann jede Aussage entweder bewiesen oder widerlegt werden, indem sie sich auf die eine oder andere Weise auf Gott bezieht. Aber nach Gödel ist das gesamte Axiomensystem zwangsläufig widersprüchlich. Das heißt, wenn wir glauben, dass Gott existiert, müssen wir zu dem Schluss kommen, dass Widersprüche in der Natur möglich sind. Und da es keine Widersprüche gibt, sonst würde unsere ganze Welt an diesen Widersprüchen zerbröckeln, müssen wir zu dem Schluss kommen, dass die Existenz Gottes mit der Existenz der Natur unvereinbar ist.

    Sosinsky A. B.

    Gödels Theorem gilt neben der Entdeckung der Relativitätstheorie, der Quantenmechanik und der DNA allgemein als die größte wissenschaftliche Errungenschaft des 20. Jahrhunderts. Wieso den? Was ist sein Wesen? Welche Bedeutung hat es? Alexey Bronislavovich Sosinsky, Mathematiker, Professor an der Unabhängigen Moskauer Universität, Offizier des Ordens der Akademischen Palmen der Französischen Republik, Preisträger des RF-Regierungspreises im Bereich Bildung im Jahr 2012, enthüllt diese Fragen in seinem Vortrag im Rahmen der Polit.ru Public Lectures-Projekt. Insbesondere wurden mehrere unterschiedliche Formulierungen davon gegeben, drei Ansätze zu seinem Beweis beschrieben (von Kolmogorov, Chaitin und Gödel selbst) und seine Bedeutung für Mathematik, Physik, Informatik und Philosophie erläutert.

    Uspenski V. A.

    Die Vorlesung widmet sich der syntaktischen Version des Gödelschen Unvollständigkeitssatzes. Gödel selbst bewies die syntaktische Version unter Verwendung einer stärkeren Annahme als der Konsistenz, nämlich der sogenannten Omega-Konsistenz.

    Uspenski V. A.

    Vorlesungen der Summer School "Modern Mathematics", Dubna.

Gödels Unvollständigkeitssatz

Uspensky V.A.

Vielleicht ist Gödels Unvollständigkeitssatz wirklich einzigartig. Einzigartig insofern, als sie sich darauf beziehen, wenn sie "alles in der Welt" beweisen wollen - von der Anwesenheit von Göttern bis zur Abwesenheit von Vernunft. Mich hat schon immer eine eher "primäre Frage" interessiert - und wer von denen, die sich auf das Unvollständigkeitstheorem beziehen, könnte es nicht nur formulieren, sondern auch beweisen? Ich veröffentliche diesen Artikel, weil er eine sehr zugängliche Formulierung des Satzes von Gödel darstellt. Ich empfehle Ihnen, zuerst den Artikel von Tullio Regge Kurt Gödel und seinen berühmten Satz zu lesen

Der Schluss auf die Unmöglichkeit eines universellen Wahrheitskriteriums ist eine direkte Folge des Ergebnisses, das Tarski durch die Kombination von Gödels Unentscheidbarkeitssatz mit seiner eigenen Wahrheitstheorie erhält, wonach es auch für einen relativ engen Bereich kein universelles Wahrheitskriterium geben kann der Zahlentheorie und damit für jede arithmetische Wissenschaft. Dieses Ergebnis gilt natürlich a fortiori für den Begriff der Wahrheit in jedem nichtmathematischen Wissensgebiet, in dem Arithmetik weit verbreitet ist.

Karl Popper

Uspensky Vladimir Andreevich wurde am 27. November 1930 in Moskau geboren. Absolvent der Fakultät für Mechanik und Mathematik der Staatlichen Universität Moskau (1952). Doktor der physikalischen und mathematischen Wissenschaften (1964). Professor, Leiter der Abteilung für Mathematische Logik und Theorie der Algorithmen der Fakultät für Mechanik und Mathematik (1966). Liest Vorlesungen "Einführung in die mathematische Logik", "Berechenbare Funktionen", "Gödelscher Vollständigkeitssatz". Bereitete 25 Kandidaten und 2 Doktoren der Wissenschaften vor

1. Problemstellung

Der Unvollständigkeitssatz, dessen genaue Formulierung wir am Ende dieses Kapitels und vielleicht später (falls es den Leser interessiert) und den Beweis geben werden, besagt ungefähr Folgendes: Unter bestimmten Bedingungen gibt es in jeder Sprache wahre, aber unbeweisbare Aussagen.

Wenn wir auf diese Weise einen Satz formulieren, bedarf fast jedes Wort einer Erklärung. Daher werden wir damit beginnen, die Bedeutung der Wörter zu erklären, die wir in dieser Formulierung verwenden.

1.1. Sprache

Wir werden hier keine möglichst allgemeine Definition einer Sprache geben, sondern uns lieber auf jene sprachlichen Begriffe beschränken, die wir später brauchen werden. Es gibt zwei solche Konzepte: „das Alphabet der Sprache“ und „die Menge wahrer Aussagen der Sprache“.

1.1.1. Alphabet

Mit Alphabet meinen wir eine endliche Menge elementarer Zeichen (d. h. Dinge, die nicht in Bestandteile zerlegt werden können). Diese Zeichen werden Buchstaben des Alphabets genannt. Unter einem Wort eines Alphabets verstehen wir eine endliche Folge von Buchstaben. Zum Beispiel sind gewöhnliche Wörter im Englischen (einschließlich Eigennamen) Wörter des 54-Buchstaben-Alphabets (26 Kleinbuchstaben, 26 Großbuchstaben, ein Bindestrich und ein Apostroph). Ein weiteres Beispiel - natürliche Zahlen in Dezimalschreibweise sind Wörter eines 10-Buchstaben-Alphabets, dessen Buchstaben Zeichen sind: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Wir verwenden gewöhnliche Großbuchstaben zur Bezeichnung Alphabete. Wenn L ein Alphabet ist, dann ist L? bezeichnet die Menge aller Wörter des Alphabets L, - Wörter, die aus seinen Buchstaben gebildet werden. Wir gehen davon aus, dass jede Sprache ihr eigenes Alphabet hat, so dass alle Ausdrücke dieser Sprache (dh Namen verschiedener Objekte, Aussagen über diese Objekte usw.) Wörter dieses Alphabets sind. Beispielsweise kann jeder Satz in englischer Sprache sowie jeder in Englisch geschriebene Text als Wort des erweiterten 54-Buchstaben-Alphabets betrachtet werden, das auch Satzzeichen, Leerzeichen zwischen Wörtern, ein rotes Linienzeichen und möglicherweise einige enthält andere nützliche Charaktere. Unter der Annahme, dass die Ausdrücke der Sprache Wörter irgendeines Alphabets sind, schließen wir somit "geschichtete" Ausdrücke des Typs f(x)dx von der Betrachtung aus. Diese Einschränkung ist jedoch nicht allzu bedeutend, da jeder derartige Ausdruck unter Verwendung geeigneter Konventionen in eine lineare Form "gedehnt" werden kann. Irgendeine in L enthaltene Menge M? wird eine Wortmenge des Alphabets L genannt. Wenn wir einfach sagen, dass M eine Wortmenge ist, dann meinen wir, dass es ein Wort irgendeines Alphabets ist. Nun kann die obige Annahme über Sprache wie folgt umformuliert werden: In jeder Sprache ist jede Menge von Ausdrücken eine Wortmenge.

1.1.2. Viele wahre Behauptungen

Wir nehmen an, dass uns eine Teilmenge T der Menge L gegeben ist? (wobei L das Alphabet einer Sprache ist, die wir in Betracht ziehen), die als Menge der "wahren Aussagen" (oder einfach "Wahrheiten") bezeichnet wird. Wenn wir direkt zur Teilmenge T übergehen, lassen wir die folgenden Zwischenschritte der Argumentation aus: Erstens, welche Wörter des Alphabets L wohlgeformte Ausdrücke der Sprache sind, das heißt, sie haben eine bestimmte Bedeutung in unserer Interpretation dieser Sprache (z , 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 sind wohlgeformte Ausdrücke, während Ausdrücke wie +=x dies nicht sind); zweitens, welche Ausdrücke sind Formeln, d.h. kann von einem Parameter abhängen (z. B. x = 3, x = y, 2 = 3, 2 = 2); drittens, welche der Formeln geschlossene Formeln sind, d.h. Anweisungen, die nicht von Parametern abhängen (z. B. 2=3, 2=2); und schließlich, welche geschlossenen Formeln wahre Aussagen sind (zB 2=2).

1.1.3. Grundlegendes Sprachpaar

1.2. "Nicht beweisbar"

„Unbeweisbar“ bedeutet, keine Beweise zu haben.

1.3. Nachweisen

Obwohl der Begriff „Beweis“ vielleicht einer der wichtigsten in der Mathematik ist (die Bourbaki beginnen ihr Buch „Fundamentals of Mathematics“ mit den Worten: „Seit der Zeit der alten Griechen bedeutete „Mathematik“ zu sagen dasselbe wie "Beweis" sagen), hat er keine genaue Definition. Im Allgemeinen gehört der Beweisbegriff mit all seinen semantischen Zweigen eher der Psychologie als der Mathematik an. Aber wie dem auch sei, Evidenz ist einfach ein Argument, das wir selbst ziemlich überzeugend finden, um alle anderen zu überzeugen.

Wenn er niedergeschrieben wird, wird der Beweis zu einem Wort in irgendeinem Alphabet P, genauso wie jeder englische Text ein Wort in dem Alphabet L ist, wofür oben ein Beispiel gegeben wurde. Die Menge aller Beweise bildet eine Teilmenge (und eine ziemlich große Teilmenge) der Menge P?. Wir werden nicht versuchen, diesen sowohl "naiven" als auch "absoluten" Beweisbegriff genau zu definieren oder - was äquivalent ist - die entsprechende Teilmenge von P? zu definieren. Stattdessen betrachten wir ein formales Analogon dieses vagen Begriffs, für den wir im Folgenden noch den Begriff „Beweis“ verwenden werden. Dieses Analogon hat zwei sehr wichtige Merkmale, die es vom intuitiven Konzept unterscheiden (obwohl die intuitive Idee des Beweises diese Merkmale immer noch in gewissem Maße widerspiegelt). Zunächst einmal nehmen wir an, dass es unterschiedliche Beweiskonzepte gibt, also unterschiedliche Teilmengen von Beweisen in P? . Im Folgenden werden wir fordern, dass es für jede solche Vorstellung eines Beweises eine effiziente Methode gibt, mit anderen Worten einen Algorithmus, der notwendigerweise bestimmen würde, ob ein gegebenes Wort des Alphabets P ein Beweis ist oder nicht. Wir gehen auch davon aus, dass es einen Algorithmus gibt, mit dem immer bestimmt werden kann, welche Aussage ein gegebener Beweis beweist. (In vielen Situationen ist die zu beweisende Aussage einfach die letzte Aussage in der Folge von Schritten, die den Beweis bilden.)

Daher lautet unser endgültiger Wortlaut der Definition wie folgt:

(1) Wir haben das Alphabet L (das Alphabet der Sprache) und das Alphabet P (das Alphabet des Beweises).

(2) Wir erhalten eine Menge P, die eine Teilmenge von P ist und deren Elemente "Beweise" genannt werden. Im Folgenden gehen wir davon aus, dass wir auch einen Algorithmus haben, mit dem wir feststellen können, ob ein beliebiges Wort des Alphabets P ein Element der Menge P, also ein Beweis, ist oder nicht.

(3) Haben wir auch eine Funktion? (um herauszufinden, was genau bewiesen wurde), wessen Domäne ist? die Bedingung P???P? erfüllt und deren Wertebereich in P? liegt. Wir gehen davon aus, dass wir einen Algorithmus haben, der diese Funktion berechnet (die genaue Bedeutung der Worte "Algorithmus berechnet eine Funktion" ist die folgende: Die Werte der Funktion werden mit diesem Algorithmus erhalten - einem Satz spezieller Transformationsregeln). Wir werden sagen, dass das Element p? P ist ein Beweis des Wortes?(p) des Alphabets L.

Troika<Р, Р, ?>, das die Bedingungen (1)-(3) erfüllt, heißt ein deduktives System über dem Alphabet L.

Für den Leser, der mit der üblichen Definition von „Beweis“ in Begriffen von „Axiom“ und „Schlussregel“ vertraut ist, werden wir nun erklären, wie diese Methode als Spezialfall der in Abschnitt 1.3.2 gegebenen Definition angesehen werden kann. Das heißt, ein Beweis wird normalerweise als eine Folge solcher Sprachausdrücke definiert, von denen jeder entweder ein Axiom ist oder zuvor aus bereits existierenden Aussagen unter Verwendung einer der Inferenzregeln gewonnen wurde. Wenn wir dem Alphabet unserer Sprache ein neues Wort * hinzufügen, können wir einen solchen Beweis als Wort schreiben, das aus dem resultierenden Alphabet zusammengesetzt ist: Die Folge von Ausdrücken wird zum Wort C1*C2*...*Cn. In diesem Fall hat die Funktion, die bestimmt, was genau bewiesen wurde, ihren Wert in dem Teil dieses Wortes, der unmittelbar auf den letzten Buchstaben * in der Sequenz folgt. Der Algorithmus, dessen Existenz in Abschnitt 1.3.2 gefordert wird. Definitionen, können leicht konstruiert werden, sobald wir eine der akzeptierten Bedeutungen der Wörter „Axiom“ und „Schlussregel“ genau definiert haben.

1.4 Versuche, den Unvollständigkeitssatz richtig zu formulieren

1.4.1. Erster Versuch

„Unter bestimmten Bedingungen für das fundamentale Paar der Sprache des Alphabets L und des deduktiven Systems<Р, Р, ?>über L gibt es immer ein Wort in T, das keinen Beweis hat. Diese Option sieht immer noch vage aus. Insbesondere könnten wir leicht so viele deduktive Systeme finden, wie wir wollen, mit sehr wenigen beweisbaren Wörtern. ?) Es gibt keine Wörter überhaupt, das hätte Beweise.

1.4.2. Zweiter Versuch

Es gibt einen anderen, natürlicheren Ansatz. Angenommen, uns wird eine Sprache gegeben – in dem Sinne, dass uns ein grundlegendes Paar dieser Sprache gegeben wird. Nun werden wir nach einem solchen deduktiven System über L suchen (intuitiv suchen wir nach einer Beweistechnik), mit dem wir möglichst viele Wörter aus T beweisen könnten, im Grenzfall alle Wörter aus T. Der Satz von Gödel beschreibt die Situation, in der ein solches deduktives System (durch das jedes Wort in T beweisbar wäre) existiert nicht. Daher möchten wir folgende Aussage formulieren:

"Unter bestimmten Bedingungen in Bezug auf das Fundamentalpaar gibt es kein solches deduktives System, in dem jedes Wort aus T einen Beweis hätte."

Eine solche Aussage ist jedoch offensichtlich falsch, da man nur ein deduktives System nehmen muss, in dem P = L, P = P? und?(p) = p für alle p in P?; dann jedes Wort von L? ist trivial beweisbar. Daher müssen wir einige Einschränkungen hinsichtlich der von uns verwendeten deduktiven Systeme akzeptieren.

1.5. Konsistenz

Es wäre ganz natürlich zu fordern, dass nur „wahre Aussagen“, also nur Wörter aus T, bewiesen werden können. Wir werden sagen, dass das deduktive System<Р, Р, ?>ist konsistent in Bezug auf ein fundamentales Paar if?(P)?T. Bei allen weiteren Überlegungen werden wir uns nur für solche konsistenten deduktiven Systeme interessieren. Wenn uns eine Sprache gegeben wäre, dann wäre es äußerst verlockend, ein solch konsistentes deduktives System zu finden, in dem jede wahre Aussage einen Beweis hätte. Die uns interessierende Variante des Satzes von Gödel besagt genau, dass es unter bestimmten Bedingungen in Bezug auf das Fundamentalpaar unmöglich ist, ein solches deduktives System zu finden.

1.6. Vollständigkeit

Es wird gesagt, dass das deduktive System<Р,Р,?>bezüglich des Fundamentalpaares vollständig ist, vorausgesetzt dass ?(P)?T. Dann nimmt unsere Formulierung des Unvollständigkeitssatzes die folgende Form an:

Unter bestimmten Bedingungen bezüglich des Fundamentalpaares gibt es kein solches deduktives System<Р,Р,?>über L, die sowohl vollständig als auch relativ konsistent wäre.

Referenzliste

Für die Vorbereitung dieser Arbeit wurden Materialien von der Website http://filosof.historic.ru verwendet.

09sen

Jedes System mathematischer Axiomen ist ab einer gewissen Komplexität entweder in sich widersprüchlich oder unvollständig.

1900 fand in Paris die Weltkonferenz der Mathematiker statt David Gilbert(David Hilbert, 1862–1943) skizzierte in Form von Thesen die seiner Meinung nach 23 wichtigsten Aufgaben, die Theoretiker des kommenden 20. Jahrhunderts zu lösen hatten. Nummer zwei auf seiner Liste war eines dieser einfachen Probleme, die offensichtlich erscheinen, bis Sie ein wenig tiefer graben. Modern formuliert war es die Frage: Reicht die Mathematik allein aus? Hilberts zweite Aufgabe reduzierte sich darauf, strikt zu beweisen, dass das Axiomensystem – Grundaussagen der Mathematik ohne Beweis zugrunde gelegt – vollkommen und vollständig sind, also alles Existierende mathematisch beschreiben können. Es musste nachgewiesen werden, dass es möglich ist, ein solches System von Axiomen aufzustellen, dass sie erstens miteinander konsistent sind und zweitens daraus Rückschlüsse auf die Wahrheit oder Falschheit einer Aussage gezogen werden können.

Nehmen wir ein Beispiel aus der Schulgeometrie. In der standardmäßigen euklidischen Planimetrie (Geometrie auf einer Ebene) kann bedingungslos bewiesen werden, dass die Aussage „Die Winkelsumme eines Dreiecks beträgt 180°“ und die Aussage „Die Winkelsumme eines Dreiecks beträgt 137°“ wahr ist " ist falsch. Im Wesentlichen ist in der euklidischen Geometrie jede Aussage entweder falsch oder wahr, und die dritte ist nicht gegeben. Und zu Beginn des zwanzigsten Jahrhunderts glaubten Mathematiker naiv, dass die gleiche Situation in jedem logisch konsistenten System beobachtet werden sollte.

Und dann 1931 irgendein bebrillter Wiener Mathematiker Kurt Gödel- nahm und veröffentlichte einen kurzen Artikel, der einfach die ganze Welt der sogenannten "mathematischen Logik" umstürzte. Nach langen und komplexen mathematischen und theoretischen Präambeln stellte er buchstäblich Folgendes fest. Nehmen wir eine Aussage wie: „Annahme Nr. 247 ist in diesem Axiomensystem logisch unbeweisbar“ und nennen sie „Aussage A“. Also bewies Gödel einfach die folgende erstaunliche Eigenschaft jedes Axiomensystems:

"Wenn eine Aussage A bewiesen werden kann, dann kann eine Nicht-A-Aussage bewiesen werden."

Mit anderen Worten, wenn es möglich ist, die Gültigkeit der Aussage „Annahme 247 ist nicht beweisbar“ zu beweisen, dann ist es auch möglich, die Gültigkeit der Aussage „Annahme 247 ist beweisbar“ zu beweisen. Das heißt, um zur Formulierung des zweiten Hilbert-Problems zurückzukehren, wenn das Axiomensystem vollständig ist (dh jede Aussage darin bewiesen werden kann), dann ist es inkonsistent.

Der einzige Ausweg aus dieser Situation besteht darin, ein unvollständiges System von Axiomen zu akzeptieren. Das heißt, wir müssen uns damit abfinden, dass wir im Kontext jedes logischen Systems immer noch „Typ A“-Aussagen haben werden, die offensichtlich wahr oder falsch sind, und wir können ihre Wahrheit nur außerhalb des Rahmens der Axiomatik beurteilen, die wir haben angenommen. Wenn es solche Aussagen nicht gibt, dann ist unsere Axiomatik widersprüchlich, und in ihrem Rahmen wird es zwangsläufig Formulierungen geben, die sowohl bewiesen als auch widerlegt werden können.

Die Formulierung von Gödels erstem oder schwachem Unvollständigkeitssatz lautet also: "Jedes formale Axiomensystem enthält ungelöste Annahmen". Aber Gödel hörte hier nicht auf und formulierte und bewies Gödels zweiten oder starken Unvollständigkeitssatz: „Die logische Vollständigkeit (oder Unvollständigkeit) irgendeines Systems von Axiomen kann nicht im Rahmen dieses Systems bewiesen werden. Um es zu beweisen oder zu widerlegen, sind zusätzliche Axiome (Stärkung des Systems) erforderlich.

Es wäre sicherer zu glauben, dass Gödels Theoreme abstrakt sind und uns nichts angehen, sondern nur Bereiche erhabener mathematischer Logik, aber tatsächlich stellte sich heraus, dass sie direkt mit der Struktur des menschlichen Gehirns zusammenhängen. Das hat der englische Mathematiker und Physiker Roger Penrose (*1931) gezeigt Gödels Sätze kann verwendet werden, um die Existenz grundlegender Unterschiede zwischen dem menschlichen Gehirn und einem Computer zu beweisen. Der Punkt seiner Argumentation ist einfach. Der Computer arbeitet streng logisch und kann nicht feststellen, ob Aussage A wahr oder falsch ist, wenn dies den Rahmen der Axiomatik sprengt, und solche Aussagen sind nach dem Satz von Gödel zwangsläufig vorhanden. Eine Person, die mit einer solchen logisch nicht beweisbaren und unwiderlegbaren Aussage A konfrontiert ist, ist immer in der Lage, ihre Wahrheit oder Falschheit zu bestimmen - basierend auf alltäglichen Erfahrungen. Zumindest darin ist das menschliche Gehirn einem durch reine Logikschaltkreise gefesselten Computer überlegen. Das menschliche Gehirn ist in der Lage, die ganze Tiefe der Wahrheit zu verstehen, die in Gödels Theoremen enthalten ist, aber ein Computer kann das niemals. Das menschliche Gehirn ist also alles andere als ein Computer. Er ist in der Lage, Entscheidungen zu treffen, und der Turing-Test wird bestanden.

Gödels Unvollständigkeitssätze

Gödels Unvollständigkeitssätze

Gödels Unvollständigkeitssätze- zwei Sätze der mathematischen Logik über die grundsätzlichen Grenzen der formalen Arithmetik und damit jeder hinreichend starken Theorie erster Ordnung.

Der erste Satz besagt, dass wenn die formale Arithmetik konsistent ist, sie eine unwiderlegbare und unwiderlegbare Formel enthält.

Der zweite Satz besagt, dass, wenn die formale Arithmetik konsistent ist, eine Formel darin nicht ableitbar ist, was die Konsistenz dieser Theorie sinnvoll bestätigt.

Gödels erster Unvollständigkeitssatz

Die Behauptung von Gödels erstem Unvollständigkeitssatz kann wie folgt formuliert werden:

Wenn formale Arithmetik S konsistent ist, dann enthält sie eine geschlossene Formel G, sodass weder G noch ihre Negation ¬G ableitbar sind S .

Beim Beweis des Satzes konstruierte Gödel die Formel G explizit, manchmal wird sie als unlösbare Formel von Gödel bezeichnet. In der Standardinterpretation ist der Satz G behauptet seine eigene Nicht-Ableitbarkeit in S. Daher ist diese Formel nach dem Satz von Gödel, wenn eine Theorie S konsistent ist, tatsächlich in S nicht ableitbar und daher in der Standardinterpretation wahr. Also für natürliche Zahlen die Formel G ist wahr, aber nicht in S ableitbar.

Gödels Beweis kann auch für jede aus S gewonnene Theorie durchgeführt werden, indem man neue Axiome hinzufügt, zum Beispiel die Formel G als Axiom. Daher ist jede konsistente Theorie, die eine Erweiterung der formalen Arithmetik ist, unvollständig.

Um den ersten Unvollständigkeitssatz zu beweisen, ordnete Gödel jedem Symbol, Ausdruck und jeder Folge von Ausdrücken in der formalen Arithmetik eine bestimmte Zahl zu. Da Formeln und Sätze arithmetische Sätze und formale Ableitungen von Sätzen Folgen von Formeln sind, wurde es möglich, von Sätzen und Beweisen in Bezug auf natürliche Zahlen zu sprechen. Lassen Sie zum Beispiel die unlösbare Gödel-Formel G hat eine Nummer m, dann ist es äquivalent zu der folgenden Aussage in der Sprache der Arithmetik: "Es gibt keine solche natürliche Zahl n, was n es gibt eine Formelableitungsnummer mit Nummer m". Ein solcher Vergleich von Formeln und natürlichen Zahlen wird als Arithmetisierung der Mathematik bezeichnet und wurde von Gödel erstmals durchgeführt. Diese Idee wurde später zum Schlüssel zur Lösung vieler wichtiger Probleme der mathematischen Logik.

Beweisskizze

Lassen Sie uns ein formales System PM festlegen, in dem elementare mathematische Konzepte dargestellt werden können.

Die Ausdrücke eines formalen Systems sind von außen gesehen endliche Folgen primitiver Symbole (Variablen, logische Konstanten und Klammern oder Punkte), und es ist nicht schwierig, genau zu spezifizieren, welche Folgen primitiver Symbole Formeln sind und welche nicht. Ebenso sind Beweise formal gesehen nichts anderes als endliche Folgen von Formeln (mit fest definierten Eigenschaften). Für die mathematische Betrachtung spielt es keine Rolle, welche Objekte wir als primitive Symbole nehmen, und wir entscheiden uns, für diese Zwecke natürliche Zahlen zu verwenden. Dementsprechend ist die Formel eine endliche Folge natürlicher Zahlen, die Ableitung der Formel eine endliche Folge endlicher Folgen natürlicher Zahlen. Mathematische Begriffe (Aussagen) werden so zu Begriffen (Aussagen) über natürliche Zahlen oder deren Folgen und können daher selbst (zumindest teilweise) in der Symbolik des PM-Systems ausgedrückt werden. Es kann insbesondere gezeigt werden, dass die Begriffe "Formel", "Ableitung", "ableitbare Formel" innerhalb des PM-Systems definierbar sind, dh man kann beispielsweise die Formel zurückgewinnen F(v) in PM mit einer freien Variablen v(dessen Typ eine numerische Folge ist) so dass F(v), in einer intuitiven Interpretation, bedeutet: v- ableitbare Formel. Lassen Sie uns nun einen unentscheidbaren Satz des PM-Systems konstruieren, das heißt den Satz EIN, für die weder EIN, noch Nicht-A nicht ableitbar, wie folgt:

Eine Formel in PM mit genau einer freien Variablen, deren Typ eine natürliche Zahl ist (eine Klasse von Klassen), wird Ausdrucksklasse genannt. Lassen Sie uns die Klassenausdrücke in irgendeiner Weise in einer Reihenfolge anordnen, bezeichnen n-e durch R(n), und beachten Sie, dass das Konzept des "Klassenausdrucks" sowie die Ordnungsbeziehung R können im PM-System definiert werden. Sei α ein beliebiger Klassenausdruck; durch [α; n] bezeichnen die Formel, die aus dem Klassenausdruck α gebildet wird, indem die freie Variable durch das Symbol einer natürlichen Zahl ersetzt wird n. Ternäre Beziehung x = [j;z] stellt sich auch als in PM definierbar heraus. Jetzt definieren wir eine Klasse K natürliche Zahlen wie folgt:

n ∈ K≡ ¬Bew[ R(n);n] (*)

(wo Bew x meint: x- ableitbare Formel). Da alle in dieser Definition vorkommenden Begriffe in PM ausgedrückt werden können, gilt das gleiche für den Begriff K, die aus ihnen aufgebaut ist, das heißt, es gibt einen solchen Klassenausdruck S dass die Formel [ S;n], was intuitiv interpretiert wird, bedeutet, dass eine natürliche Zahl n gehört K. Als Klassenausdruck S identisch mit einigen bestimmten R(q) in unserer Nummerierung, das heißt

S = R(q)

gilt für eine bestimmte natürliche Zahl q. Zeigen wir nun, dass der Satz [ R(q);q] ist in PM unentscheidbar. Also, wenn der Satz [ R(q);q] als ableitbar angenommen wird, dann erweist es sich als wahr, d. h. gemäß dem oben Gesagten q wird gehören K, also nach (*), ¬Bew[ R(q);q] erfüllt, was unserer Annahme widerspricht. Wenn andererseits die Negation [ R(q);q] ableitbar war, dann ¬ n ∈ K, das heißt, Bew[ R(q);q] wird wahr sein. Folglich, [ R(q);q] zusammen mit seiner Negation ableitbar, was wiederum unmöglich ist.

Polynomische Form

Für jede konsistente Theorie T man kann einen solchen ganzzahligen Wert des Parameters K angeben, dass die Gleichung (θ + 2 z − b 5) 2 + (u + tθ − l) 2 + (j + mθ − e) 2 + (n − q 16) 2 + ((g + eq 3 + lq 5 + (2(e − zλ)(1 + g) 4 + λ b 5+λ b 5 q 4)q 4)(n 2 − n) + (q 3 − bl + l + θλ q 3 + (b 5 − 2)q 5)(n 2 − 1) − r) 2 + (p − 2ws 2 r 2 n 2) 2 + (p 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − ksn 2) 2 + η − k 2) 2 + (r + 1 + hp − h − k) 2 + (a − (wn 2 + 1)rsn 2) 2 + (2r+ 1 + φ − c) 2 + (bw + ca − 2c+ 4αγ − 5γ − d) 2 + ((a 2 − 1)c 2 + 1 − d 2) 2 + ((a 2 − 1)ich 2 c 4 + 1 − f 2) 2 + (((a + f 2 (d 2 − a)) 2 − 1)(2r + 1 + jc) 2 + 1 − (d + Öf) 2) 2 + (((z + u + j) 2 + u) 2 + j − K) 2 = 0 hat keine Lösungen in nicht negativen ganzen Zahlen, aber diese Tatsache kann theoretisch nicht bewiesen werden T . Darüber hinaus ist für jede konsistente Theorie die Menge der Werte des Parameters K, die diese Eigenschaft haben, unendlich und algorithmisch nicht aufzählbar.

Gödels zweiter Unvollständigkeitssatz

In der formalen Arithmetik S kann man eine Formel konstruieren, die in der Standardinterpretation genau dann wahr ist, wenn die Theorie S widerspruchsfrei ist. Für diese Formel gilt die Aussage des zweiten Satzes von Gödel:

Wenn formale Arithmetik S konsistent ist, dann enthält es eine nicht ableitbare Formel, die inhaltlich die Konsistenz behauptet S .

Mit anderen Worten, die Konsistenz der formalen Arithmetik kann mit dieser Theorie nicht bewiesen werden. Es gibt jedoch Beweise für die Konsistenz der formalen Arithmetik mit Mitteln, die in ihr nicht ausdrückbar sind.

Beweisskizze

Zunächst wird eine Formel erstellt Con, was sinnvoll die Unmöglichkeit ausdrückt, irgendeine Formel in der Theorie S zusammen mit ihrer Negation abzuleiten. Dann wird die Aussage des ersten Satzes von Gödel durch die Formel ausgedrückt Con ⊃ G, wo G- Gödels unlösbare Formel. Alle Argumente für den Beweis des ersten Theorems lassen sich mittels S ausdrücken und ausführen, d. h. in S ist die Formel ableitbar Con ⊃ G. Also, wenn S ableitbar ist Con, dann leiten wir darin und ab G. Allerdings gilt nach Gödels erstem Satz, wenn S konsistent ist, dann G darin ist nicht ableitbar. Wenn also S konsistent ist, dann die Formel Con.

Anmerkungen

siehe auch

Verknüpfungen

  • V. A. Uspensky Gödels Unvollständigkeitssatz. - M.: Nauka, 1982. - 110 S. - (Beliebte Vorlesungen über Mathematik).
  • Akademiemitglied Yu L. Ershov "Beweise in der Mathematik", Programm von A. Gordon vom 16. Juni 2003
  • A. B. Sosinsky Satz von Gödel // Sommerschule "Moderne Mathematik". - Dubna: 2006.
  • P. J. Cohen Zu den Grundlagen der Mengenlehre // Fortschritte in den mathematischen Wissenschaften. - 1974. - T. 29. - Nr. 5 (179). - S. 169–176.
  • M. Kordonsky Ende der Wahrheit. - ISBN 5-946448-001-04
  • V. A. Uspensky Gödels Unvollständigkeitssatz und vier Wege zu ihm // Sommerschule "Moderne Mathematik". - Dubna: 2007.
  • Zenkin A.A. Timesharing-Prinzip und Analyse einer Klasse quasi-endlicher plausibler Argumentation (am Beispiel des Unabzählbarkeitssatzes von G. Kantor) // DAN. - 1997. - T. 356. - Nr. 6. - S. 733-735.
  • Chechulin V. L. Zu einer Kurzfassung des Beweises der Gödelschen Sätze // „Grundlegende Probleme der Mathematik und Informationswissenschaften“, Materialien des XXXIV Far Eastern Mathematical School-Seminars, benannt nach Akademiker E.V. Zolotova. - Chabarowsk, Russland: 2009. - S. 60-61.

Wikimedia-Stiftung. 2010 .

Sehen Sie, was "Gödels Unvollständigkeitssätze" in anderen Wörterbüchern sind:

    Dieser Begriff hat andere Bedeutungen, siehe Satz von Gödel. Der Unvollständigkeitssatz von Gödel und der zweite Satz von Gödel [1] sind zwei Sätze der mathematischen Logik über die grundlegenden Beschränkungen der formalen Arithmetik und folglich jeglicher ... ... Wikipedia

    Gödels Unvollständigkeitssätze sind zwei Sätze der mathematischen Logik über die Unvollständigkeit formaler Systeme einer bestimmten Art. Inhalt 1 Gödels erster Unvollständigkeitssatz 2 Gödels zweiter Unvollständigkeitssatz ... Wikipedia

    Dieser Begriff hat andere Bedeutungen, siehe Satz von Gödel. Gödels Satz über die Vollständigkeit des Prädikatenkalküls ist einer der fundamentalen Sätze der mathematischen Logik: Er stellt einen eindeutigen Zusammenhang zwischen logischer Wahrheit ... ... Wikipedia her

    Gemeinsamer Name für zwei von K. Gödel aufgestellte Theoreme. Das erste G. t. über n. behauptet, dass es in jedem konsistenten formalen System, das ein Minimum an Arithmetik (Zeichen und die üblichen Regeln zu ihrer Behandlung) enthält, eine formal Unentscheidbarkeit gibt ... ... Mathematische Enzyklopädie

zum Thema: "SATZ VON GODEL"

Kurt Gödel

Kurt Gödel – der größte Spezialist für mathematische Logik – wurde am 28. April 1906 in Brunn (heute Brünn, Tschechien) geboren. Er absolvierte die Universität Wien, wo er seine Doktorarbeit verteidigte, und war 1933–1938 Assistenzprofessor. Nach dem Anschluss emigrierte er in die Vereinigten Staaten. Von 1940 bis 1963 arbeitete Gödel am Princeton Institute for Advanced Study. Gödel ist Ehrendoktor der Universitäten Yale und Harvard, Mitglied der US National Academy of Sciences und der American Philosophical Society.

1951 erhielt Kurt Gödel die höchste wissenschaftliche Auszeichnung der Vereinigten Staaten, den Einstein-Preis. In einem diesem Ereignis gewidmeten Artikel schrieb ein anderer der größten Mathematiker unserer Zeit, John von Neumann: „Der Beitrag von Kurt Gödel zur modernen Logik ist wirklich monumental. Dies ist mehr als nur ein Denkmal. Dies ist ein Meilenstein, der zwei Epochen trennt ... Man kann ohne Übertreibung sagen, dass Gödels Arbeit das Fachgebiet der Logik als Wissenschaft grundlegend verändert hat.

Tatsächlich zeigt schon eine trockene Aufzählung von Gödels Leistungen in der mathematischen Logik, dass ihr Verfasser im Wesentlichen die Grundlagen für ganze Teilgebiete dieser Wissenschaft gelegt hat: die Theorie der Modelle (1930; der sogenannte Satz von der Vollständigkeit des engen Prädikatenkalküls, der zeigt, grob gesagt, die Hinlänglichkeit der Mittel der "formalen Logik", um alle in ihrer Sprache ausgedrückten wahren Sätze zu beweisen), konstruktive Logik (1932–1933; resultiert aus der Möglichkeit, einige Klassen von Sätzen der klassischen Logik auf ihre intuitionistischen Gegenstücke zu reduzieren, die legte den Grundstein für den systematischen Einsatz von „immersing operationen“, die eine solche Reduktion verschiedener logischer Systeme aufeinander erlauben), formale Arithmetik (1932–1933; Ergebnisse zur Möglichkeit, klassische Arithmetik auf intuitionistische Arithmetik zu reduzieren, in gewissem Sinne zeigend Konsistenz der ersten in Bezug auf die zweite), die Theorie der Algorithmen und rekursiven Funktionen (1934; Definition des Begriffs einer allgemeinen rekursiven Funktion, die eine entscheidende Rolle spielte Rolle bei der Feststellung der algorithmischen Unlösbarkeit einer Reihe wichtiger mathematischer Probleme. Und in der Umsetzung logischer und mathematischer Probleme auf elektronischen Rechnern - andererseits), axiomatische Mengenlehre (1938; Beweis der relativen Konsistenz des Wahlaxioms und Cantors Kontinuumshypothese aus den Axiomen der Mengenlehre, die den Anfang markierten einer Reihe wichtiger Ergebnisse zu relativer Konsistenz und mengentheoretischen Prinzipien der Unabhängigkeit).

Gödels Unvollständigkeitssatz

Einführung

1931 erschien in einer der deutschen wissenschaftlichen Zeitschriften ein relativ kleiner Artikel mit einem ziemlich erschreckenden Titel "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme". Ihr Autor war ein 25-jähriger Mathematiker der Universität Wien, Kurt Gödel, der später am Princeton Institute for Advanced Study arbeitete. Diese Arbeit spielte eine entscheidende Rolle in der Geschichte der Logik und Mathematik. In der Entscheidung der Harvard University, Gödel die Ehrendoktorwürde zu verleihen (1952), wurde sie als eine der größten Errungenschaften der modernen Logik bezeichnet.

Zum Zeitpunkt der Veröffentlichung jedoch kein Titel von Gödels Werk. Auch sein Inhalt sagte den meisten Mathematikern nichts. Wie im Titel erwähnt, ist Principia Mathematica Alfred North Whiteheads und Bertrand Russells monumentale dreibändige Abhandlung über mathematische Logik und die Grundlagen der Mathematik; die Vertrautheit mit der Abhandlung war keineswegs eine notwendige Bedingung für eine erfolgreiche Arbeit in den meisten Zweigen der Mathematik. Das Interesse an den Themen, die in Gödels Arbeit behandelt werden, war immer das Los einer sehr kleinen Gruppe von Wissenschaftlern. Gleichzeitig waren die Argumente, die Gödel in seinen Beweisen anführte, für ihre Zeit so ungewöhnlich. Dass ein vollständiges Verständnis davon eine exklusive Kenntnis des Themas und Vertrautheit mit der Literatur erfordert, die sich diesen sehr spezifischen Problemen widmet.

Erster Unvollständigkeitssatz

Gödels erster Unvollständigkeitssatz scheint das bedeutendste Ergebnis in der mathematischen Logik zu sein. Es klingt so:

Für eine beliebige konsistente formale und berechenbare Theorie, in der grundlegende arithmetische Sätze bewiesen werden können, kann ein wahrer arithmetischer Satz konstruiert werden, dessen Wahrheit im Rahmen der Theorie nicht bewiesen werden kann. Mit anderen Worten, jede vollkommen nützliche Theorie, die ausreicht, um die Arithmetik darzustellen, kann nicht sowohl konsistent als auch vollständig sein.

Hier bedeutet das Wort "Theorie" "eine unendliche Menge" von Aussagen, von denen einige ohne Beweis als wahr angenommen werden (solche Aussagen werden Axiome genannt), während andere (Theoreme) aus den Axiomen abgeleitet werden können und daher angenommen werden ( bewiesen) wahr. Der Ausdruck „in der Theorie beweisbar“ bedeutet „abgeleitet von den Axiomen und Grundelementen der Theorie (konstante Symbole des Alphabets) unter Verwendung von Standardlogik (erster Ordnung). Eine Theorie ist konsistent (konsistent), wenn es unmöglich ist, eine widersprüchliche Aussage in ihr zu beweisen. Der Ausdruck „kann aufgebaut werden“ bedeutet, dass es eine mechanische Prozedur (Algorithmus) gibt, die eine Aussage aufbauen kann, die auf Axiomen, Primitiven und Logik erster Ordnung basiert. "Elementare Arithmetik" ist das Vorhandensein von Additions- und Multiplikationsoperationen über natürliche Zahlen. Der resultierende wahre, aber unbeweisbare Satz wird für eine gegebene Theorie oft als "Gödel-Folge" bezeichnet, aber es gibt eine unendliche Anzahl anderer Sätze in der Theorie, die die gleiche Eigenschaft haben, innerhalb der Theorie unbeweisbar zu sein.

Die Annahme, dass eine Theorie berechenbar ist, bedeutet, dass es prinzipiell möglich ist, einen Computeralgorithmus (Computerprogramm) zu implementieren, der (wenn er beliebig lange Zeiten bis unendlich berechnen darf) eine Liste aller Theoreme der Theorie berechnet. Tatsächlich reicht es aus, nur die Liste der Axiome zu berechnen, und alle Theoreme können effizient aus einer solchen Liste abgeleitet werden.

Der erste Unvollständigkeitssatz wurde in Gödels Arbeit von 1931 mit "Theorem VI" betitelt. Über formal unentscheidbare Sätze in Principia Mathematica und verwandten Systemen I. In Gödels Originalaufnahme klang es so:

„Die allgemeine Schlussfolgerung über die Existenz unentscheidbarer Sätze lautet:

Satz VI .

Für jede ω-konsistente rekursive Klasse k FORMEL es gibt rekursive ZEICHEN r so dass weder (v Gen r), noch ¬( v Gen r)gehören nicht zu Flg (k)(wobei v ist FREIE VARIABLE r ) ».

Bezeichnung Flg kommt von ihm. Folgerungsmenge- Reihe von Sequenzen, Gen kommt von ihm. Verallgemeinerung- Verallgemeinerung.

Grob gesagt Gödels Aussage G behauptet: „Wahrheit G kann nicht nachgewiesen werden." Wenn G innerhalb der Theorie bewiesen werden könnte, dann würde die Theorie einen Satz enthalten, der sich selbst widerspricht, und daher wäre die Theorie inkonsistent. Doch wenn G nicht beweisbar, dann ist sie wahr, und daher ist die Theorie unvollständig (die Aussage G darin nicht ableitbar).

Diese Erklärung ist in gewöhnlicher natürlicher Sprache und daher nicht ganz mathematisch streng. Um einen strengen Beweis zu liefern, nummerierte Gödel Aussagen mit natürlichen Zahlen. In diesem Fall gehört auch die zahlenbeschreibende Theorie zur Menge der Sätze. Fragen nach der Beweisbarkeit von Sätzen lassen sich in diesem Fall in Form von Fragen nach den Eigenschaften natürlicher Zahlen darstellen, die bei vollständiger Theorie berechenbar sein müssen. In diesem Sinne besagt Gödels Aussage, dass es keine Zahl mit einer bestimmten Eigenschaft gibt. Eine Zahl mit dieser Eigenschaft ist ein Beweis für die Widersprüchlichkeit der Theorie. Existiert eine solche Zahl, ist die Theorie entgegen der ursprünglichen Annahme widersprüchlich. Unter der Annahme, dass die Theorie konsistent ist (wie die Prämisse des Satzes nahelegt), stellt sich heraus, dass es keine solche Zahl gibt und Gödels Aussage wahr ist, aber dies kann im Rahmen der Theorie nicht bewiesen werden (daher ist die Theorie unvollständig). . Ein wichtiger konzeptioneller Hinweis ist, dass man davon ausgehen muss, dass eine Theorie widerspruchsfrei ist, um Gödels Aussage für wahr zu erklären.

Gödels zweiter Unvollständigkeitssatz

Gödels zweiter Unvollständigkeitssatz lautet wie folgt:

Für jede formal rekursiv aufzählbare (d. h. effektiv generierte) Theorie T, einschließlich grundlegender arithmetischer Wahrheitsaussagen und bestimmter formaler Beweisbarkeitsaussagen, enthält eine gegebene Theorie T genau dann eine Aussage über ihre Konsistenz, wenn die Theorie T inkonsistent ist.

Mit anderen Worten, die Konsistenz einer hinreichend reichhaltigen Theorie kann mit dieser Theorie nicht bewiesen werden. Es kann sich jedoch durchaus herausstellen, dass die Konsistenz einer bestimmten Theorie durch eine andere, mächtigere formale Theorie festgestellt werden kann. Aber dann stellt sich die Frage nach der Konsistenz dieser zweiten Theorie und so weiter.

Viele haben versucht, dieses Theorem zu verwenden, um zu beweisen, dass intelligente Aktivitäten nicht auf Berechnungen reduziert werden können. Zum Beispiel hat der berühmte Logiker John Lucas 1961 ein ähnliches Programm entwickelt. Seine Argumentation erwies sich als recht anfällig – allerdings stellte er die Aufgabe breiter. Roger Penrose verfolgt einen etwas anderen Ansatz, der im Buch komplett „von Grund auf neu“ dargestellt wird.

Diskussionen

Die Konsequenzen von Theoremen wirken sich auf die Philosophie der Mathematik aus, insbesondere auf jene Formalismen, die formale Logik verwenden, um ihre Prinzipien zu definieren. Man kann den ersten Unvollständigkeitssatz wie folgt umformulieren: es ist unmöglich, ein umfassendes System von Axiomen zu finden, die es beweisen könnten alle mathematische Wahrheiten und keine einzige Lüge". Andererseits macht diese Umformulierung unter dem Gesichtspunkt der strengen Formalität wenig Sinn, da sie davon ausgeht, dass die Begriffe „wahr“ und „falsch“ in einem absoluten und nicht in einem relativen Sinne definiert werden jedes spezifische System.

IN VERBINDUNG STEHENDE ARTIKEL