Benutzer:Schreiber/Baustelle/Artikel4

aus Wikipedia, der freien Enzyklopädie

Erster Unvollständigkeitssatz

Der erste Unvollständigkeitssatz lässt sich wie folgt allgemein formulieren:

Sei T ein formales System, welches natürliche Zahlen mit Addition und Multiplikation beschreiben kann. Dann gilt eine der folgenden Möglichkeiten:
  • Es gibt wahre arithmetische Formeln, die in T nicht beweisbar sind.
  • Es gibt falsche arithmetische Formeln, die in T beweisbar sind.

Ist T ausreichend stark, lässt sich die Aussage wie folgt präzisieren:

Sei T ein formales System, in dem das System Q interpretierbar ist. Dann gilt eine der folgenden Möglichkeiten:
  • Es gibt wahre arithmetische Formeln, die in T nicht beweisbar sind.
  • T ist widersprüchlich.

Dabei ist Q (auch Robinson-Arithmetik) eine schwache Form der Arithmetik in Prädikatenlogik erster Stufe. Diese verfügt über die Konstante 0 „null“, die Nachfolgerfunktion S, welche intuitiv zu einer gegebenen Zahl eins addiert, sowie die Funktionen + für Addition und ✕ für Multiplikation. Sie hat folgende Axiome, die elementare Eigenschaften der natürlichen Zahlen und der arithmetischen Operationen formalisieren:

  • Null hat keinen Vorgänger: Sx0
  • Wenn x+1 = y+1 gilt, dann ist x=y: (Sx = Sy) → x = y
  • Jede Zahl ist gleich Null oder hat einen Vorgänger: y=0 ∨ ∃x (Sx = y)
  • Rekursive Definition von Addition und Multiplikation:
    • x + 0 = x
    • x + Sy = S(x + y)
    • x0 = 0
    • x ✕ Sy = (x ✕ y) + x

Im Folgenden wird angenommen, dass T das System Q selbst ist. Der Beweis lässt sich genauso in jedem anderen System durchführen, in dem sich die Arithmetik so interpretieren lässt, dass sich alle Funktionen aus Q so durch Ausdrücke des neuen Systems definieren lassen, dass alle Theoreme von Q in Theoreme des anderen Systems übergehen. Gödel bewies den Satz ursprünglich für das viel stärkere System der Principia Mathematica. Ebenso lässt sich der Beweis in der Zermelo-Fraenkel-Mengenlehre durchführen, die als einziges nichtlogisches Zeichen die Elementrelation hat, in der Zahlen aber als Mengen interpretiert werden können, sodass alle Theoreme von Q als Theoreme der Mengenlehre interpretierbar sind.

Der Beweis zerfällt in vier Teile:

  1. Arithmetisierung der Syntax: Jeder Formel der Theorie wird eine Zahl, die sogenannte Gödelnummer, zugewiesen, aus der sich die Formel wieder effektiv rekonstruieren lässt. Diese Nummerierung wird auf endliche Folgen von Formeln erweitert.
  2. Arithmetisierung der Beweisbarkeitsrelation: Eine Formel Beweis(x, y) wird konstruiert, sodass für jedes Paar von Zahlen n und m, Beweis(n, m) genau dann wahr ist, wenn n die Gödelnummer eines Beweises einer Formel ist, deren Gödelnummer m ist.
  3. Konstruktion des Gödelsatzes: Es wird eine Formel konstruiert, die informell besagt „Ich bin nicht beweisbar.“, der sogenannte Gödelsatz.
  4. Nachweis der Unbeweisbarkeit: Es wird gezeigt, dass der Gödelsatz weder bewiesen noch widerlegt werden kann.

Arithmetisierung der Syntax

Das Hauptproblem bei der Ausführung des oben beschriebenen Beweises scheint zunächst darin zu liegen dass bei der Konstruktion einer Aussage p, die äquivalent zu „p ist unbeweisbar“, p eine Referenz auf p enthalten muss. Gödels Lösung ist, zu zeigen, dass Aussagen auf eine solche Weise Zahlen zugewiesen werden können, dass das Beweisen einer Aussage dadurch ersetzt werden kann, dass überprüft wird, ob die der Aussage zugewiesene Zahl eine gewisse arithmetische Eigenschaft hat. Dies ermöglicht die Konstruktion einer selbstbezüglichen Formel, die unendlichen Regress vermeidet.

Der erste Schritt des Beweises besteht somit darin, Formeln und endliche Folgen von Formeln (injektiv) auf natürliche Zahlen abzubilden. Diese Zahlen heißen Gödelnummern der Formeln. Es sind verschiedene Verfahren bekannt, Gödelnummern zuzuweisen. Die folgende Gödelnummerierung orientiert sich an der von Douglas Hofstadter in Gödel, Escher, Bach benutzten. Zunächst wird jedem Symbol der Sprache der Arithmetik eine Zahl zugeordnet, ähnlich dem ASCII-Code, der jedem Buchstaben eine eindeutige Zahl zuordnet:

Nummer Symbol Bedeutung
666 0 Null
123 S Nachfolgerfunktion
111 = Gleichheit
112 + Addition
236 Multiplikation
362 ( linke Klammer
323 ) rechte Klammer
Nummer Symbol Bedeutung
262 eine Variable
163 Strich (für weitere Variablen x', x'', …)
333 Existenzquantor
626 Allquantor
161 logisches und
616 logisches oder
223 Negation

Die Gödelnummer einer Formel erhält man durch Aneinanderreihung der Gödelnummern für jedes Symbol der Formel. Die Gödelnummern der Symbole werden durch 0 getrennt, da keine Gödelnummer eines Symbols eine 0 enthält. Damit kann jede Formel eindeutig aus ihrer Gödelnummer rekonstruiert werden. Die Gödelnummer einer Formel F wird mit G(F) bezeichnet.

Mit dieser Gödelnummerierung erhält beispielsweise der Satz, der das Kommutativgesetz der Addition ausdrückt, die Nummer:

626 0 262 0 626 0 262 0 163 0 362 0 262 0 112 0 262 0 163 0 111 0 262 0 163 0 112 0 262 0 323

(die Leerzeichen dienen nur der Lesbarkeit.) Nicht alle Zahlen repräsentieren Formeln, beispielsweise steht

111 0 626 0 112 0 262

für "", was keine korrekte Formel ist.

Da jede natürliche Zahl durch wiederholte Anwendung der Nachfolgeroperation S auf 0 erhalten werden kann, hat jede natürliche Zahl eine Gödelnummer. So ist beispielsweise die Gödelnummer für 4, SSSS0, gleich:

123 0 123 0 123 0 123 0 666.

Die Zuweisung von Gödelnummern kann auf endliche Folgen von Formeln erweitert werden. Um die Gödelnummer einer endlichen Folge von Formeln zu erhalten werden die Nummern die Formeln hintereinander geschrieben und jeweils durch zwei Nullen getrennt. Da die Gödelnummer einer Formel nie zwei aufeinanderfolgende Nullen enthält, kann jede Formel der Folge eindeutig rekonstruiert werden.

Es ist wichtig, dass die formale Arithmetik einige einfache Tatsachen beweisen kann. Insbesondere muss sie beweisen können, dass jede Zahl eine Gödelnummer hat. Ebenso muss sie beweisen, dass es für die Gödelnummer einer Formel F(x) mit einer freien Variable und eine Zahl m die Gödelnummer einer Formel F(m) gibt, in der alle Vorkommen von x durch die Gödelnummer von m ersetzt wurden, und dass man diese Gödelnummer aus der ersten durch eine effektive Prozedur erhalten kann.

Die Beweisbarkeitsrelation

Das formale System besitzt Axiome und Schlussregeln, aus denen die Formeln des Systems bewiesen werden können. Ein formaler Beweis im System ist somit eine Kette von Formeln, in der jede entweder ein Axiom ist oder sich durch eine Schlussregel aus früheren Formeln gewinnen lässt.

Da das formale System rekursiv aufzählbar ist, kann man effektiv entscheiden, ob eine gegebene Zahl Gödelnummer eines Axioms ist. Im Falle des endlich axiomatisierten Systems Q genügt es sogar, zu überprüfen, ob die Zahl zur Gödelnummer einer der sieben Axiome gleich ist.

Ableitungsregeln können als binäre Relationen zwischen Gödelnummern von Folgen von Formeln repräsentiert werden. So gibt es beispielsweise eine Ableitungsregel D1, durch die man aus den Formeln S1,S2 die Formel erhält. Dann besagt die Relation R1 zu dieser Ableitungsregel, dass n genau dann in Relation zu m steht (n R1m gilt), wenn n die Gödelnummer einer Liste von Formeln ist, die S1 und S2 enthält, und wenn m die Gödelnummer einer Liste von Formeln ist, die aus den Formeln in der von n kodierten Liste besteht und zusätzlich enthält. Da jede Ableitungsregel eine einfache formale Vorschrift ist, ist es möglich, effektiv zu entscheiden, ob zwei Zahlen n und m in Relation R1 stehen.

Der zweite Schritt ist, zu zeigen, dass diese Gödelnummerierung benutzt werden kann, um den Begriff der Beweisbarkeit auszudrücken. Angenommen die Theorie hat die Axiome A1, A2, A3, … und die Ableitungsregeln: D1, D2, D3, … . R1, R2, R3, … seien die zugehörigen Relationen.

Ein Beweis einer Formel S ist eine Kette von Formeln, in denen jede entweder ein Axiom ist, oder aus früheren Aussagen durch eine Ableitungsregel entsteht, und in der die letzte Aussage S ist. Damit lässt sich die Gödelnummer eines Beweises mit der oben angegebenen Methode zur Kodierung endlicher Folge von Formeln definieren. Zudem lässt sich eine Formel Beweis(x,y) definieren, die für zwei Zahlen x and y genau dann wahr (und beweisbar) ist, wenn x die Gödelnummer eines Beweises von S ist, und y = G(S) ist.

Beweis(x,y) ist eine arithmetische Relation, ebenso wie etwa "x+y = 6", nur beträchtlich komplizierter. Gegeben eine solche Relation R(x,y), ist für alle spezifischen Zahlen n und m entweder die Formel R(m,n) oder ihre Negation R(m,n) beweisbar, aber nicht beide. Dies liegt daran, dass die Relation zwischen den Zahlen auf einfache Weise „überprüft“ werden kann. Die Konstruktion der Formel Beweis hängt entscheidend davon ab, dass die Theorie rekursiv aufzählbar ist; ohne diese Annahme wäre die Formel nicht konstruierbar.

Damit lässt sich nun eine Formel Beweisbar(y) definieren, die die metasprachliche Aussage „F ist beweisbar“ repräsentiert: F ist beweisbar, wenn es eine Zahl x gibt, die einen Beweis für F kodiert:

Beweisbar(y) = ∃ x (Beweis(x, y))

Dabei ist "Beweisbar(y)" ebenso wie "Beweis(x, y)" nur eine Abkürzung für eine bestimmte, sehr lange, arithmetische Formel; die Symbol "Beweis" und "Beweisbar" selbst gehört nicht zur Sprache des Systems.

Ein wichtiges Merkmal der Formel Beweisbar(y) ist, dass Beweisbar(G(p)) beweisbar ist, wenn p beweisbar ist. Denn wenn p beweisbar ist, dann existiert ein Beweis mit Gödelnummer n. Dann ist Beweisbar(n, G(p)) wahr und, wie oben dargelegt, beweisbar. Damit ist erst recht die schwächere Existenzaussage ∃ x Beweisbar(x, G(p)) beweisbar.

Diagonalisierung

Der nächste Schritt besteht darin, eine Aussage zu konstruieren, die ihre eigene Unbeweisbarkeit behauptet. Hierzu lässt sich das Diagonallemma anwenden. Dieses besagt, dass es in der Arithmetik und stärkeren formalen Systemen für jede Formel F(x) mit freier Variable x eine Aussage p gibt, sodass das System die Äquivalenz

pF(G(p)).

beweist. Man erhält also eine Formel mit der intuitiven Bedeutung „Ich habe die Eigenschaft F(x).“ Wenn man für F die Negation von Beweisbar(x) einsetzt, erhält man die Aussage p mit der Bedeutung „Meine Gödelnummer ist die Gödelnummer einer unbeweisbaren Formel“, also „Ich bin unbeweisbar“.

Die Formel p ist nicht direkt gleich zu ¬Beweisbar(G(p)); vielmehr besagt p, dass man, wenn man eine gewisse Berechnung ausführt, die Nummer einer unbeweisbaren Aussage erhält. Wenn man nun diese Berechnung durchführt, zeigt sich aber, dass die entstehende Zahl die Gödelnummer von p selbst ist. Diese Konstruktion ähnelt folgender natürlichsprachigen Aussage:

"ist in Anführungszeichen und gefolgt von sich selbst unbeweisbar." ist in Anführungszeichen und gefolgt von sich selbst unbeweisbar.

Dieser Satz bezieht sich nicht direkt auf sich selbst, aber man erhält die ursprüngliche Aussage, wenn man die angegebene Umformung durchführt, und damit behauptet der Satz seine eigene Unbeweisbarkeit. Der Beweis des Diagonallemmas benutzt eine ähnliche Methode.

Beweis der Unabhängigkeit des Gödelsatzes

Man nehme nun an, dass das formale System ω-konsistent, und damit konsistent, ist. Sei p die Aussage, die im vorangehenden Abschnitt konstruiert wurde.

Wenn p beweisbar wäre, dann wäre Bew(G(p)) beweisbar. Aber p ist äquivalent zur Negation von Bew(G(p)). Damit wäre das System inkonsistent, da es eine Aussage und ihre Negation beweisen würde. Also kann p nicht beweisbar sein, da die Theorie nach Voraussetzung konsistent ist.

Wenn die Negation von p beweisbar wäre, dann wäre Bew(Gp)) beweisbar. Aber keine natürliche Zahl n kann die Gödelnummer eines Beweises von p sein, da p nicht beweisbar ist. Damit ermöglicht das System einerseits die Konstruktion einer Zahl mit einer bestimmten Eigenschaften, aber beweist andererseits für jede Zahl n, dass diese die Eigenschaft nicht hat. Dies ist in einem ω-konsistenten System unmöglich. Damit ist die Negation von p nicht beweisbar.

Damit ist die Aussage p unentscheidbar: sie kann im gewählten System weder bewiesen noch widerlegt werden. Damit ist das System entweder ω-inkonsistent oder unvollständig. Diese Argumentation lässt sich auf jedes formale System, das die Voraussetzungen erfüllt, anwenden. Damit sind alle formalen Systeme, die die Voraussetzungen erfüllen, entweder ω-inkonsistent oder unvollständig.

Dabei ist zu bemerken, dass p auch dann nicht beweisbar ist, wenn das System konsistent und ω-inkonsistent ist. Die Annahme der ω-Konsistenz ist nur dazu nötig, zu zeigen, dass die Negation von p nicht beweisbar ist.

Wenn man versucht, die Unvollständigkeit zu beseitigen, indem man eine der unbeweisbaren Formeln p oder nicht p als Axiom hinzufügt, erhält man ein neues formales System. Auf dieses lässt sich der gleiche Prozess anwenden und man erhält wieder eine Aussage der Form „Ich bin im neuen System nicht beweisbar.“ und das neue System ist wieder entweder ω-inkonsistent oder unvollständig.

Verallgemeinerung von Rosser

Wie im vorangehenden Abschnitt gezeigt, erlaubt die Konstruktion des Gödelsatzes zunächst nur den Beweis der Unvollständigkeit für ω-konsistente Systeme. J. Barkley Rosser zeigte 1936, dass sich mit der gleichen Technik die Unvollständigkeit auch für ω-inkonsistente Systeme zeigen lässt.

Durch das Diagonallemma lässt sich ein Satz konstruieren, der die metasprachliche Bedeutung „Wenn es einen Beweis für mich gibt, dann gibt es einen kürzeren Beweis für meine Negation.“ hat. Dieser Satz wird auch als Rossersatz R bezeichnet:

Angenommen R ist beweisbar und es gibt einen Beweis mit Gödelnummer n. Dann gibt es eine Zahl m < n, die Gödelnummer eines Beweises der Negation von R ist. Damit beweist das formale System einen Satz und seine Negation, ist also inkonsistent.

Nun nehme man an, das System sei konsistent und der Rossersatz sei widerlegbar, wobei es einen Beweis für die Negation mit Gödelnummer n gibt. Da das System konsistent ist, ist R nicht beweisbar. Dann ist beweisbar:

Da es keinen Beweis für R gibt, gibt es auch keinen Beweis mit Gödelnummer kleiner gleich n. Damit ist die Formel wahr. Da es nur endlich viele Zahlen kleiner n gibt, ist die Formel äquivalent zu einer quantorenfreien Formel und damit auch beweisbar.
Für jede Zahl größer n findet man eine kleinere Zahl, die Nummer eines Beweises von ist. Dies folgt direkt daraus, dass n eine solche Nummer ist.

Damit lässt sich aber durch Kontraposition und Modus Ponens beweisen:

was dem Rossersatz R entspricht. Dies ist ein Widerspruch, da R nach Annahme nicht beweisbar sein kann. Also ist der Rossersatz in einem konsistenten System nicht widerlegbar.

Genaue Formulierung und Beweisskizze des zweiten Unvollständigkeitssatzes

Der zweite Unvollständigkeitssatz besagt:

Jedes hinreichend mächtige konsistente System kann die eigene Konsistenz nicht beweisen.

Eine hinreichende Bedingung für „hinreichend mächtig“ ist, dass der Beweis des ersten Unvollständigkeitssatzes im System formalisiert werden kann. Dazu muss es eine Formel Bew(x) besitzen, die die Beweisbarkeit in diesem System ausdrückt. Zudem muss diese Formel den sogenannten Bernays-Löb-Axiomen genügen. Diese fordern, dass für alle Formeln F und H folgende Bedingungen gelten:

  1. Wenn , dann

Dies ist zwar im System Q, für das sich der erste Unvollständigkeitssatz bereits zeigen lässt, noch nicht erfüllt, aber bereits in der Primitiv Rekursiven Arithmetik (PRA), und erst recht in stärkeren Theorien wie der Peano-Arithmetik und der Mengenlehre.

Mithilfe dieser Eigenschaften lässt sich nun wie folgt der erste Unvollständigkeitssatz formalisieren. Sei F die beim Beweis des ersten Satzes konstruierte Aussage mit der Bedeutung „Ich bin nicht beweisbar.“ Dann lassen sich folgende drei Aussagen ableiten:

  • (nach Axiom 3)
  • (nach der Definition von F)
  • (nach Axiom 1 und 3)

Durch Kontraposition erhält man aus diesen drei Sätzen folgenden Satz, der dem ersten Unvollständigkeitssatz entspricht:

Um einen Widerspruch zu erzeugen, nehme man nun an, dass T seine Konsistenz beweist, das heißt . Damit gilt , also . Nach Axiom 1 gilt . Andererseits erhält man aus und aber .

Dann wäre aber T inkonsistent, da es sowohl F als auch beweist. Also kann T, wenn es konsistent ist, die eigene Konsistenz nicht beweisen.

Alternativ lässt sich der zweite Unvollständigkeitssatz auch durch den Satz von Löb beweisen. Nach diesem gilt für ein System T, das die Bernays-Löb-Axiome erfüllt, die Aussage nur dann, wenn auch gilt. Wenn nun T seine eigene Konsistenz beweist, gilt und damit . Nach dem Satz von Löb gilt also , also ist T inkonsistent.

Relationship with computability

The incompleteness theorem is closely related to several results about undecidable sets in recursion theory.

Stephen Cole Kleene (1943) presented a proof of Gödel's incompleteness theorem using basic results of computability theory. One such result shows that the halting problem is unsolvable: there is no computer program that can correctly determine, given a program P as input, whether P eventually halts when run with some given input. Kleene showed that the existence of a complete effective theory of arithmetic with certain consistency properties would force the halting problem to be decidable, a contradiction. This method of proof has also been presented by Shoenfield (1967, p. 132); Charlesworth (1980); and Hopcroft and Ullman (1979).

Franzén (2005, p. 73) explains how Matiyasevich's solution to Hilbert's 10th problem can be used to obtain a proof to Gödel's first incompleteness theorem. Matiyasevich proved that there is no algorithm that, given a multivariate polynomial p(x1, x2,...,xk) with integer coefficients, determines whether there is an integer solution to the equation p = 0. Because polynomials with integer coefficients, and integers themselves, are directly expressible in the language of arithmetic, if a multivariate integer polynomial equation p = 0 does have a solution in the integers then any sufficiently strong theory of arithmetic T will prove this. Moreover, if the theory T is ω-consistent, then it will never prove that some polynomial equation has a solution when in fact there is no solution in the integers. Thus, if T were complete and ω-consistent, it would be possible to determine algorithmically whether a polynomial equation has a solution by merely enumerating proofs of T until either "p has a solution" or "p has no solution" is found, in contradiction to Matiyasevich's theorem.

James Jones gives a concrete example of Diophantine equation (containing a parameter, say K) with a property that for every consistent effectively generated theory T there exists an integer value of parameter K such that the equation has no solutions over non-negative integers, but it cannot be proved in T. Moreover, for every such theory, the set of numbers with this property is an infinite, not recursively enumerable set. In principle, (at least one) such value of K can be effectively computed from the axioms of T.[1][2][3]

Smorynski (1977, p. 842) shows how the existence of recursively inseparable sets can be used to prove the first incompleteness theorem. This proof is often extended to show that systems such as Peano arithmetic are essentially undecidable (see Kleene 1967, p. 274).

Chaitin's incompleteness theorem gives a different method of producing independent sentences, based on Kolmogorov complexity. Like the proof presented by Kleene that was mentioned above, Chaitin's theorem only applies to theories with the additional property that all their axioms are true in the standard model of the natural numbers. Gödel's incompleteness theorem is distinguished by its applicability to consistent theories that nonetheless include statements that are false in the standard model; these theories are known as ω-inconsistent.


sonst

In principle, proving a statement true or false can be shown to be equivalent to proving that the number matching the statement does or doesn't have a given property. Because the formal system is strong enough to support reasoning about numbers in general, it can support reasoning about numbers which represent formulae and statements as well. Crucially, because the system can support reasoning about properties of numbers, the results are equivalent to reasoning about provability of their equivalent statements.



The "truth" of the Gödel sentence

The proof of Gödel's incompleteness theorem just sketched is proof-theoretic (also called syntactic) in that it shows that if certain proofs exist (a proof of P(G(P)) or its negation) then they can be manipulated to produce a proof of a contradiction. This makes no appeal to whether P(G(P)) is "true", only to whether it is provable. Truth is a model-theoretic, or semantic, concept, and is not equivalent to provability except in special cases.

By analyzing the situation of the above proof in more detail, it is possible to obtain a conclusion about the truth of P(G(P)) in the standard model of natural numbers. As just seen, q(n,G(P)) is provable for each natural number n, and is thus true in the model . Therefore, within this model,

P(G(P)) =

holds. This is what the statement "P(G(P)) is true" usually refers to—the sentence is true in the intended model. It is not true in every model, however: If it were, then by Gödel's completeness theorem it would be provable, which we have just seen is not the case.

Discussion and implications

The incompleteness results affect the philosophy of mathematics, particularly versions of formalism, which use a single system formal logic to define their principles. One can paraphrase the first theorem as saying the following:

An all-encompassing axiomatic system can never be found that is able to prove all mathematical truths, but no falsehoods.

On the other hand, from a strict formalist perspective this paraphrase would be considered meaningless because it presupposes that mathematical "truth" and "falsehood" are well-defined in an absolute sense, rather than relative to each formal system.

The following rephrasing of the second theorem is even more unsettling to the foundations of mathematics:

If an axiomatic system can be proven to be consistent from within itself, then it is inconsistent.

Therefore, to establish the consistency of a system S, one needs to use some other more powerful system T, but a proof in T is not completely convincing unless T's consistency has already been established without using S.

Theories such as Peano arithmetic, for which any computably enumerable consistent extension is incomplete, are called essentially undecidable or essentially incomplete.


This fact is sometimes thought to have severe consequences for the program of logicism proposed by Gottlob Frege and Bertrand Russell, which aimed to define the natural numbers in terms of logic (Hellman 1981, p. 451–468). Some (like Bob Hale and Crispin Wright) argue that it is not a problem for logicism because the incompleteness theorems apply equally to second order logic as they do to arithmetic. They argue that only those who believe that the natural numbers are to be defined in terms of first order logic have this problem.


Minds and machines

Authors including J. R. Lucas have debated what, if anything, Gödel's incompleteness theorems imply about human intelligence. Much of the debate centers on whether the human mind is equivalent to a Turing machine, or by the Church–Turing thesis, any finite machine at all. If it is, and if the machine is consistent, then Gödel's incompleteness theorems would apply to it.

Hilary Putnam (1960) suggested that while Gödel's theorems cannot be applied to humans, since they make mistakes and are therefore inconsistent, it may be applied to the human faculty of science or mathematics in general. Assuming that it is consistent, either its consistency cannot be proved or it cannot be represented by a Turing machine.

Avi Wigderson (2010) has proposed that the concept of mathematical "knowability" should be based on computational complexity rather than logical decidability. He writes that "when knowability is interpreted by modern standards, namely via computational complexity, the Gödel phenomena are very much with us."

Paraconsistent logic

Although Gödel's theorems are usually studied in the context of classical logic, they also have a role in the study of paraconsistent logic and of inherently contradictory statements (dialetheia). Graham Priest (1984, 2006) argues that replacing the notion of formal proof in Gödel's theorem with the usual notion of informal proof can be used to show that naive mathematics is inconsistent, and uses this as evidence for dialetheism. The cause of this inconsistency is the inclusion of a truth predicate for a theory within the language of the theory (Priest 2006:47). Stewart Shapiro (2002) gives a more mixed appraisal of the applications of Gödel's theorems to dialetheism. Carl Hewitt (2008) has proposed that (inconsistent) paraconsistent logics that prove their own Gödel sentences may have applications in software engineering.

Appeals to the incompleteness theorems in other fields

Appeals and analogies are sometimes made to the incompleteness theorems in support of arguments that go beyond mathematics and logic. Several authors have commented negatively on such extensions and interpretations, including Torkel Franzén (2005); Alan Sokal and Jean Bricmont (1999); and Ophelia Benson and Jeremy Stangroom (2006). Bricmont and Stangroom (2006, p. 10), for example, quote from Rebecca Goldstein's comments on the disparity between Gödel's avowed Platonism and the anti-realist uses to which his ideas are sometimes put. Sokal and Bricmont (1999, p. 187) criticize Régis Debray's invocation of the theorem in the context of sociology; Debray has defended this use as metaphorical (ibid.).

The role of self-reference

Torkel Franzén (2005, p. 46) observes:

Gödel's proof of the first incompleteness theorem and Rosser's strengthened version have given many the impression that the theorem can only be proved by constructing self-referential statements [...] or even that only strange self-referential statements are known to be undecidable in elementary arithmetic. To counteract such impressions, we need only introduce a different kind of proof of the first incompleteness theorem.

He then proposes the proofs based on Computability, or on information theory, as described earlier in this article, as examples of proofs that should "counteract such impressions".

History

Nachdem Gödel in seiner Doktorarbeit 1929 den Gödelschen Vollständigkeitssatz bewiesen hatte, wandte er sich einem zweiten Problem für seine Habilitation zu. Sein ursprüngliches Ziel war, eine positive Lösung zu Hilberts zweitem Problem zu finden (Dawson 1997, p. 63), das nach einem finiten Konsistenzbeweis für die Arithmetik fragt.

Zach, Richard (2003), "The Practice of Finitism: Epsilon Calculus and Consistency Proofs in Hilbert's Program", Synthese (Berlin, New York: Springer-Verlag) 137 (1): 211–259, doi:10.1023/A:1026247421383, ISSN 0039-7857

Gödel war nicht der einzige, der am Problem der Konsistenz arbeitete. Ackermann hatte 1925 einen fehlerhaften Konsistenzbeweis für die Analysis veröffentlicht, in dem er Hilberts Methode der ε-Substitution anzuwenden versuchte.[4] Von Neumann korrigierte 1927 diesen Beweis für Arithmetik ohne Induktion.[5] 1928 teilte Ackermann Bernays einen neuen Beweis mit. Nachdem der Unvollständigkeitssatz zeigte, dass der Beweis fehlerhaft sein musste, zeigte von Neumann konkret, dass die verwendete Beweistechnik inkorrekt war.[6] 1931 veröffentlichte Jacques Herbrand einen weiteren Konsistenzbeweis für die Arithmetik ohne Induktion.[7]

Im Laufe seiner Arbeit entdeckte Gödel, dass, während ein Satz, der seine eigene Falschheit behauptet, zu einem Paradox führt, ein Satz, der seine eigene Unbeweisbarkeit behauptet, dies nicht tut. Gödel war sich auch des später von Tarski veröffentlichten Resultats über die Undefinierbarkeit von Wahrheit bewusst, veröffentlichte es aber nicht. Gödel announced his first incompleteness theorem to Carnap, Feigel and Waismann on August 26, 1930; all four would attend a key conference in Königsberg the following week.

Announcement

The 1930 Königsberg conference was a joint meeting of three academic societies, with many of the key logicians of the time in attendance. Carnap, Heyting, and von Neumann delivered one-hour addresses on the mathematical philosophies of logicism, intuitionism, and formalism, respectively (Dawson 1996, p. 69). The conference also included Hilbert's retirement address, as he was leaving his position at the University of Göttingen. Hilbert used the speech to argue his belief that all mathematical problems can be solved. He ended his address by saying,

"For the mathematician there is no Ignorabimus, and, in my opinion, not at all for natural science either. ... The true reason why [no one] has succeeded in finding an unsolvable problem is, in my opinion, that there is no unsolvable problem. In contrast to the foolish Ignoramibus, our credo avers: We must know. We shall know!"

This speech quickly became known as a summary of Hilbert's beliefs on mathematics (its final six words, "Wir müssen wissen. Wir werden wissen!", were used as Hilbert's epitaph in 1943). Although Gödel was likely in attendance for Hilbert's address, the two never met face to face (Dawson 1996, p. 72).

Gödel announced his first incompleteness theorem at a roundtable discussion session on the third day of the conference. The announcement drew little attention apart from that of von Neumann, who pulled Gödel aside for conversation. Later that year, working independently with knowledge of the first incompleteness theorem, von Neumann obtained a proof of the second incompleteness theorem, which he announced to Gödel in a letter dated November 20, 1930 (Dawson 1996, p. 70). Gödel had independently obtained the second incompleteness theorem and included it in his submitted manuscript, which was received by Monatshefte für Mathematik on November 17, 1930.

Gödel's paper was published in the Monatshefte in 1931 under the title Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (On Formally Undecidable Propositions in Principia Mathematica and Related Systems I). As the title implies, Gödel originally planned to publish a second part of the paper; it was never written.

Generalisierung und Akzeptanz

Gödel gave a series of lectures on his theorems at Princeton in 1933–1934 to an audience that included Church, Kleene, and Rosser. By this time, Gödel had grasped that the key property his theorems required is that the theory must be effective (at the time, the term "general recursive" was used). Rosser bewies 1936, dass sich die Voraussetzung der ω-Konsistenz durch einfache Konsistenz ersetzen lässt, wenn der Gödelsatz entsprechend geändert wird. Alonzo Church und Alan Turing bewiesen 1936 unabhängig voneinander mithilfe ihrer neu entwickelten Berechenbarkeitsmodelle und aufbauend auf Gödels Arbeit die Unentscheidbarkeit der Prädikatenlogik, aus der sich der erste Unvollständigkeitssatz ebenfalls herleiten lässt.

Gentzen veröffentlichte 1936 einen Konsistenzbeweis für die volle erststufige Arithmetik mithilfe transfiniter Induktion. Hilbert akzeptierte diesen Beweis als „finit“, obwohl er nach Gödels Resultat nicht in der Arithmetik formalisiert werden kann.

Die Bedeutung des Unvollständigkeitssatzes für Hilberts Programm war schnell erkannt. Bernays veröffentlichte im zweiten Band von Grundlagen der Mathematik (1939) den ersten detaillierten Beweis des zweiten Unvollständigkeitssatzes, mit weiteren Resultaten von Ackermann über die Methode der ε-Substitution und Gentzens Konsistenzbeweis.

Kritik

Im September 1931 schrieb Ernst Zermelo Gödel, dass er eine wesentliche Lücke in Gödels Argument gefunden habe.[8]. Gödel antwortete im Oktober mit einem zehnseitigen Brief, aber Zermelo veröffentlichte seine Kritik. Gödel entschied decided that to pursue the matter further was pointless, and Carnap agreed (Dawson:77). Zermelo konzentrierte sich in der Folge auf viel stärkere Logiken als Logik erster Stufe, mit denen er hoffte

Paul Finsler benutzte 1926 eine Version des Richard-Paradoxons, um eine Aussage zu konstruieren, die in einem informellen System, das er entwickelt hatte, unbeweisbar ist. Gödel kannte diese Arbeit nicht, als er den Unvollständigkeitssatz bewies (Collected Works Vol. IV., p. 9). Finsler schrieb Gödel 1931 über seine Arbeit, die er als ersten Beweis des Unvollständigkeitssatzes ansah. Finslers Methoden beruhten nicht auf einer Formalisierung der Beweisbarkeit. Gödel hielt Finslers Arbeit für fehlerhaft. Finsler argumentierte weiterhin für seine Philosophie der Mathematik, die Formalisierung scheute.

Wittgenstein and Gödel

Ludwig Wittgenstein schrieb einige Passagen über den Unvollständigkeitssatz, die 1953 posthum in seinen Philosophische Untersuchungen veröffentlicht wurden. Gödel was a member of the Vienna Circle during the period in which Wittgenstein's early ideal language philosophy and Tractatus Logico-Philosophicus dominated the circle's thinking. Writings in Gödel's Nachlass express the belief that Wittgenstein deliberately misread his ideas.

Multiple commentators have read Wittgenstein as misunderstanding Gödel (Rodych 2003), although Juliet Floyd and Hilary Putnam (2000), as well as Graham Priest (2004),[9] have provided textual readings arguing that most commentary misunderstands Wittgenstein. On their release, Bernays, Dummett, and Kreisel wrote separate reviews on Wittgenstein's remarks, all of which were extremely negative (Berto 2009:208). The unanimity of this criticism caused Wittgenstein's remarks on the incompleteness theorems to have little impact on the logic community. In 1972, Gödel, stated: "Has Wittgenstein lost his mind? Does he mean it seriously?" (Wang 1996:197) And wrote to Karl Menger that Wittgenstein's comments demonstrate a willful misunderstanding of the incompleteness theorems writing:

"It is clear from the passages you cite that Wittgenstein did "not" understand [the first incompleteness theorem] (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite, namely a mathematical theorem within an absolutely uncontroversial part of mathematics (finitary number theory or combinatorics)." (Wang 1996:197)

Since the publication of Wittgenstein's Nachlass in 2000, a series of papers in philosophy have sought to evaluate whether the original criticism of Wittgenstein's remarks was justified. Floyd and Putnam (2000) argue that Wittgenstein had a more complete understanding of the incompleteness theorem than was previously assumed. They are particularly concerned with the interpretation of a Gödel sentence for an ω-inconsistent theory as actually saying "I am not provable", since the theory has no models in which the provability predicate corresponds to actual provability. Rodych (2003) argues that their interpretation of Wittgenstein is not historically justified, while Bays (2004) argues against Floyd and Putnam's philosophical analysis of the provability predicate. Berto (2009) explores the relationship between Wittgenstein's writing and theories of paraconsistent logic.

r

  1. Jones J. P., Undecidable diophantine equations
  2. Martin Davis, Diophantine Equations & Computation
  3. Martin Davis, The Incompleteness Theorem
  4. Wilhelm Ackermann: Begründung des ,,tertium non datur'" mittels der Hilbertschen Theorie der Widerspruchsfreiheit. In: Math. Ann. Band 93, 1925, S. 1--36 (springerlink.com).
  5. John von Neumann: Zur Hilbertschen Beweistheorie. In: Math. Zeitschr. Band 26, 1927, S. 1---46 (springerlink.com).
  6. Zach 2006, p. 418, Zach 2003, p. 33
  7. Jacques Herbrand: Sur la non-contradiction de l´arithmétique, Journal für reine und angewandte Mathematik, Band 166, 1931, S.1-8 (mit Vorwort von Helmut Hasse), englische Übersetzung in Heijenoort From Frege to Gödel, Harvard UP, 1967, The consistency of arithmetic, S. 618-628
  8. John W. Dawson, Jr., 1997. Logical Dilemmas: The Life and Work of Kurt Gödel, A.K. Peters, Wellesley Mass, ISBN 1-56881-256-6. 76
  9. Wittgenstein's Remarks on Gödel's Theorem, by Graham Priest, published in Wittgenstein's lasting significance, edited by Max Kölbel, Bernhard Weiss, Psychology Press, 8 Apr 2004, pages 207-227

Autoren

http://en.wikipedia.org/w/index.php?title=G%C3%B6del%27s_incompleteness_theorems&oldid=478418644