Gödel's incompleteness theorems

	Cogito ergo sum; Logic and rhetoric
	Key articles
	Logical fallacy; Syllogism; Argument;
	General logic
	Two wrongs make a right; SeekFind; Not an argument; Envenenar o poço; Fact; TDK;
	Bad logic
	No True Scotsman; Escape hatch; Appeal to confidence; Appeal to bias; False dilemma; کلمات قلمبه سلمبه; v - t - e

Kurt Friedrich Gödel

\pagecolor {Red}{\begin{aligned}\sum _{n}n^{-s}&=0\\\Re (s)&=\ ?\end{aligned}}

This article/section deals with mathematical concepts appropriate for a student in late university or graduate level.

Gödel's incompleteness theorems demonstrate that, in any consistent, sufficiently advanced mathematical system, it is impossible to prove or disprove everything.

More specifically, the first incompleteness theorem states that, in any consistent axiomatic formulation of number theory which is "rich enough" there are statements which cannot be proven or disproven within that formulation. The second incompleteness theorem states that number theory cannot be used to prove its own consistency.

The theorem applies also to any theory which includes number theory, as long as the theory is consistent and as long as the theory is expressed as is usual in mathematics, following rules such as that the axioms and proof procedures are determined from the start and the expressions are of finite length. One major example of such a larger theory in mathematics is set theory, for in set theory one can define numbers and the operations on numbers, and prove the ordinary principles of arithmetic.

Idea of proof[edit]

Kurt Gödel (1906–1978) demonstrated this by encoding the liar paradox into number theory itself: for every formal theory T that contains enough arithmetic, it is possible to construct a well-formed mathematical statement that, very informally, says "I am not provable in theory T".^[1]^[2] By the assumption of consistency, we know that this statement is true (for, if it were false, then it could be proven, which would be inconsistent). But in virtue of its being true, it cannot be proven (for that is what it says). The final link in the chain of reasoning is the notion of "rich enough," which means that a system contains enough formalism as to be able to describe a statement which refers to itself as an unprovable statement. This is achieved, in part, by showing that (1) statements of formal logic can be associated with numbers in arithmetic and (2) a formal proof can be shown to correspond to arithmetical computations on those associated numbers.^{[note 1]}

In case that you think you can get around this by adding this true (but unprovable) statement as an additional axiom in arithmetic (after all, you know that it is true), what happens is that the proof changes so that it generates yet another statement that refers to its own unprovability from the new, enlarged set of axioms. For example, if theory T has a statement G saying "I am not provable in theory T", you could try moving to a new theory T* = T + G that includes G as an axiom. In it, G is provable (trivially, as it's an axiom), but the new theory has a new statement G* saying "I am not provable in theory T*", ad infinitum.^[2]

Common misconceptions[edit]

Not every mathematical theory is necessarily incomplete[edit]

The "arithmetic" that the theorem refers to is more than just addition, subtraction, multiplication and division with whole numbers. It also includes statements about "all numbers" or "some numbers," for example, statements about prime numbers; "there is no largest prime number." And there are parts of arithmetic which can be proven to be complete (there is one such part which excludes multiplication), as well as other interesting and complicated areas of mathematics which have been proven to be complete and consistent. So one should be careful when saying that "arithmetic" or "mathematics" is incomplete. Some mathematical theories are complete, for example, Tarski's axiomatization of Euclidean geometry; its completeness does not contradict Gödel's theorem because it does not contain number theory.^[3]

Also, there is even a proof that arithmetic (in the sense of the incompleteness theorems) is consistent; but that proof relies on methods that go beyond that arithmetic. For details, see Gentzen's consistency proof.^[4]

"True but unprovable"?[edit]

People tend to get confused about the assertion that Gödel's statement is "true but unprovable". In particular, what Gödel's theorem absolutely definitely most certainly doesn't say is that humans possess some kind of superior unformalizable intuition that allows them to see mathematical truths that cannot be captured by "mere math" or "mere logic".^[5]

In first-order logic, Gödel's completeness theorem says that every formula that is logically valid — roughly speaking, true in every model — is syntactically provable. Thus, every formula that is necessarily true in every model of first-order arithmetic is provable from the axioms of first-order arithmetic. And Gödel's statement is, in fact, not true in every model of first-order arithmetic: ie. it is true in any standard model of arithmetic but false in some non-standard models of arithmetic

The problem is that first-order arithmetic is not powerful enough to capture one specific definition of natural numbers and restrict it only to the standard model of arithmetic, the ordinary natural numbers we all know and love (0, 1, 2, …).^{[note 2]} Gödel's statement happens to be true in the standard model, but in non-standard models, in addition to the standard numbers, there are other numbers not reachable by repeatedly incrementing from 0, chains of extra numbers that extend infinitely in both directions (similar to, but distinct from, integer numbers). In non-standard models, there are Gödelian encodings of proofs that do not, in general, adequately map to valid logical proofs — it also allows infinite chains that decode into something like "Gödel's statement is true, because not-not-Gödel's statement is true, because not-not-not-not-Gödel's statement is true, ad infinitum". So there are non-standard models where Gödel's statement is, in fact, false: they have "proof encodings" that actual first-order logic would not accept as proofs.^[6]

Unlike first-order logic, second-order logic does not have an analogue of the completeness theorem. In particular, while second-order arithmetic is powerful enough to describe only the standard model of arithmetic and eliminate all non-standard numbers, there is no deductive system for second-order logic that is simultaneously logically sound, complete, and has a proof-checking algorithm.^{[note 3]}^[7] But then, humans cannot reason using such a system either; they are not more powerful in this respect than computer programs or any other formalized process.

God and other "unknowables"[edit]

Some people get tempted to use Gödel's theorem as an escape hatch for their own pet theories that they consider "true but unprovable". Math cannot prove everything, therefore logical discussion of God is futile, so there! However, Gödel's theorem has a precise mathematical formulation, and so do the mathematical concepts of logical truth and provability; to even consider the truth or provability of a statement, it first needs to be formalized in the language of mathematical logic. "God", as an idea grounded in our imprecise maps of the real world, is clearly not a well-defined logical formula whose truth or falsehood is even meaningful to consider as a consequence of purely mathematical theories. This argument falls into not even wrong territory.

However, Gödel's theorems do allow more reserved theists to say "Just because something is not provable within our world does not mean that it is not true or that it shouldn't be believed".

As it happens, Gödel, himself, believed that God existed and even formulated an ontological proof around God’s existence ^[8] His proof, however, depends on the acceptance of certain foundational axioms that can be argued against.^[9] (For example, Gödel states that if a property is positive, then that property’s opposite/inverse/negative cannot be positive. While this might seem obvious, facially, counter-examples abound. eg. The property of being worn out after an workout can be positive, but so can the property of feeling fine after a workout)

External links[edit]

Weisstein, Eric W.. "Gödel's First Incompleteness Theorem". MathWorld.
Weisstein, Eric W.. "Gödel's Second Incompleteness Theorem". MathWorld.

Notes[edit]

↑ A novel idea in Gödel's time; he created an encoding, called Gödel numbering, that translated formulas of logic, as strings of symbols, into very large natural numbers. These days, the possibility of encoding strings as very large numbers, and string manipulations as arithmetic operations on them, is not surprising to anyone who understands how computers work.
↑ First-order logic in general is very limited in pinning down specific models; by the Löwenheim–Skolem theorem, any first-order theory with an infinite model (and first-order arithmetic is obviously one of these) has an infinite number of meaningfully different infinite models. Heck, said theorem even proves there exists a countable model of the axioms of real numbers, despite Cantor's proof that the set of real numbers is uncountable.
↑ Because if we could encode an algorithm for checking proofs in such a deductive system for second-order arithmetic, we could prove Gödel's incompleteness theorem for it, in contradiction of either soundness or completeness.

References[edit]

↑ Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte für Mathematik und Physik, v. 38 n. 1, pp. 173–198. doi 10.1007/BF01700692
↑ ^2.0 ^2.1 Douglas Hofstadter, 1979. Gödel, Escher, Bach: An Eternal Golden Braid. Vintage Books. ISBN 0-465-02685-0. 1999 reprint: ISBN 0-465-02656-7.
↑ Tarski, Alfred; Givant, Steven (1999). Tarski's system of geometry. 5. pp. 175–214. doi:10.2307/421089. ISSN 1079-8986. JSTOR 421089. MR 1791303.
↑ *Gentzen, Gerhard (1936). Die Widerspruchsfreiheit der reinen Zahlentheorie. 112. pp. 493–565. doi:10.1007/BF01565428. English translation: Gentzen, Gerhard (1969). Szabo, M. E.. ed. Collected Papers of Gerhard Gentzen. Studies in logic and the foundations of mathematics (Hardcover ed.). Amsterdam: North-Holland. ISBN 978-0-7204-2254-2.
↑ Known as the Penrose–Lucas argument, advocated, among other publications, in Penrose, Roger (1989). Shadows of the Mind: A Search for the Missing Science of Consciousness. Oxford University Press. p. 457. ISBN 978-0-19-853978-0. Works with counterarguments are too numerous to list, but see the Stanford Encyclopedia of Philosophy for a selection.
↑ Yudkowsky, Eliezer. "Godel's Completeness and Incompleteness Theorems".
↑ W. V. Quine (1970). Philosophy of Logic. Prentice Hall. ISBN 9780674665637.
↑ Robert Marks and Samuel Haug, Gödel Says God Exists and Proves It. Mind Matters, 7 June 2021.
↑ See the Wikipedia article on Gödel's ontological proof.

[3] A novel idea in Gödel's time; he created an encoding, called Gödel numbering, that translated formulas of logic, as strings of symbols, into very large natural numbers. These days, the possibility of encoding strings as very large numbers, and string manipulations as arithmetic operations on them, is not surprising to anyone who understands how computers work.

[7] First-order logic in general is very limited in pinning down specific models; by the Löwenheim–Skolem theorem, any first-order theory with an infinite model (and first-order arithmetic is obviously one of these) has an infinite number of meaningfully different infinite models. Heck, said theorem even proves there exists a countable model of the axioms of real numbers, despite Cantor's proof that the set of real numbers is uncountable.

[9] Because if we could encode an algorithm for checking proofs in such a deductive system for second-order arithmetic, we could prove Gödel's incompleteness theorem for it, in contradiction of either soundness or completeness.

[1] Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte für Mathematik und Physik, v. 38 n. 1, pp. 173–198. doi 10.1007/BF01700692

[geb-2] 2.0 ^2.1 Douglas Hofstadter, 1979. Gödel, Escher, Bach: An Eternal Golden Braid. Vintage Books. ISBN 0-465-02685-0. 1999 reprint: ISBN 0-465-02656-7.

[4] Tarski, Alfred; Givant, Steven (1999). Tarski's system of geometry. 5. pp. 175–214. doi:10.2307/421089. ISSN 1079-8986. JSTOR 421089. MR 1791303.

[5] *Gentzen, Gerhard (1936). Die Widerspruchsfreiheit der reinen Zahlentheorie. 112. pp. 493–565. doi:10.1007/BF01565428. English translation: Gentzen, Gerhard (1969). Szabo, M. E.. ed. Collected Papers of Gerhard Gentzen. Studies in logic and the foundations of mathematics (Hardcover ed.). Amsterdam: North-Holland. ISBN 978-0-7204-2254-2.

[6] Known as the Penrose–Lucas argument, advocated, among other publications, in Penrose, Roger (1989). Shadows of the Mind: A Search for the Missing Science of Consciousness. Oxford University Press. p. 457. ISBN 978-0-19-853978-0. Works with counterarguments are too numerous to list, but see the Stanford Encyclopedia of Philosophy for a selection.

[lw-8] Yudkowsky, Eliezer. "Godel's Completeness and Incompleteness Theorems".

[10] W. V. Quine (1970). Philosophy of Logic. Prentice Hall. ISBN 9780674665637.

[11] Robert Marks and Samuel Haug, Gödel Says God Exists and Proves It. Mind Matters, 7 June 2021.

[12] See the Wikipedia article on Gödel's ontological proof.

[1]

[2]

[note 1]

[3]

[4]

[5]

[note 2]

[6]

[note 3]

[7]

[8]

[9]

Gödel's incompleteness theorems

Contents