Gödel’s Incompleteness Theorems2019/03/12
An Incomplete History of Logic
In the 18th and 19th century, the rapid expansion of exact sciences necessitated the creation for a general method to reason about and solve problems. Mathematicians utilized the axiomatic method used by ancient Greeks to create and analyze new branches of mathematics. Axioms of these systems were regarded to be self-evident. In the case of Euclidean geometry, the axioms modelled space, and the system was thus considered true and consistent. However, Euclid’s parallel axiom was not immediately self-evident like his first four, yet it was shown to still be independent of the others. This meant that different geometries, like Riemannian geometry, could be constructed by rejecting the parallel axiom.
Riemannian geometry unravelled new and interesting theorems, but as a deviant to “true” Euclidean geometry, its consistency was no longer apparent. Fortunately, Riemannian geometry could be modelled by Euclidean geometry, and thus its consistency depends only on the consistency of Euclidean geometry. David Hilbert took it a step further and interpreted Euclid’s axioms into algebraic truths. This again only deferred the question of consistency by appealing to another axiomatic system. At the same time, as the formalization of mathematics created great variety and broader terms, the foundation of mathematics began to suffer from a lack of clarity made apparent by Russell’s paradox. So Hilbert proposed a program that contained a finite set of axioms to ground all of mathematics and contained an “absolute proof” of its own consistency.
The first step towards an absolute proof of consistency involved the “complete formalization” of some deductive system. This system or calculus involved “signs” and “strings” of “signs” completely devoid of meaning, but could be manipulated into other “strings” in some well-defined manner. By analyzing the structure of a given calculus, Hilbert hoped to show that contradictory “strings” as defined by the system could not both be constructed. But in 1931, Kurt Gödel published his incompleteness theorems stating
- Any consistent formal system contains true statements that it cannot prove nor disprove.
- Any consistent formal system cannot prove its own consistency.
This implied that such undertakings like Principia Mathematica by Alfred Whitehead and Bertrand Russell or Leibniz’s “universal mathematics” were flawed and impossible contrary to the general belief at the time.
On Formally Undecidable Propositions of Principia Mathematica and Related Systems
Gödel’s proof is applied to some system strong enough to describe arithmetic. In his original paper, Gödel used an adaptation of Principia Mathematica. The system assumed here is Hofstadter’s Typographical Number Theory (TNT).1 TNT contains 20 symbols, 5 axioms, 8 rules of inference, and it can codify all of arithmetic. For example, the phrase is an even number in TNT could be where is represented by the free variable .
The first step is to assign a unique code number to each symbol as in the following table:
Then for any sequence of symbols with corresponding code numbers , let the Gödel number for be
where indicates the th prime number.2 Thus the symbol has Gödel number . The statement has Gödel number . Similarly, proofs, which are just sequences of statements, have unique Gödel numbers constructed the same way.3, 4
Thus all the rules of inference which state which strings can be transformed into which strings, can be reinterpreted as statements about numbers, specifically the Gödel numbers of those strings. Every well defined operation on strings, has an equivalent well defined arithmetical5 operation on numbers. Subsequently, a proof with Gödel number being a valid proof for a theorem with Gödel number represents some arithmetical relationship between and 6 denoted as
TNT is now equipped to do some meta-mathematical introspection. The phrase is a theorem in TNT is logically equivalent to the TNT-statement .
One last piece of machinery is required to complete Gödel’s proof. Suppose is a TNT-statement with one free variable . The process of replacing all instances of with a specified constant results in a new statement whose Gödel number is denoted as
Take for example the statement with Gödel number . Then
This corresponds to replacing the free variable with the numeral to obtain . This is again an arithmetical function describable by TNT.7
Now we can consider the statement
with Gödel number . Replacing the free variable with the number results in
This new statement called has a Gödel number, and this number is equal to . Furthermore, is a statement in the system of TNT that represents the meta-mathematical statement The statement whose Gödel number is is not a theorem in TNT. In other words, says, . Gödel further proved that is provable if and only if its formal negation is provable.8 Since TNT is a consistent system,9 neither nor are provable. By meta-mathematical reasoning, this implies that , which asserts a definite numerical property of the natural numbers, is true. is a true TNT-statement that cannot be proven in TNT.
TNT is incomplete,10 and this proof is not unique to TNT. Even if was added as an axiom to TNT to create TNT-, this new system has its own Gödel sentence that is also true and not provable. Every consistent system is incomplete.
The exact system is called austere TNT and is described in full in Chapter 8 of Gödel, Escher, Bach: an Eternal Golden Braid.
For a system of symbols, it’s common to just assign each symbol a single base numeral. Then for any string of symbols, replace each by its corresponding base numeral, and the resulting base number is the Gödel number for that string. The numeral must be assigned to a symbol that can never appear first in a valid formula of the system. For TNT, Hofstadter assigns each symbol a 3-digit “codon,” and Gödel numbers are constructed by concatenating codons into a single base 10 number.
Every Gödel number is unique due to the fundamental theorem of arithmetic.
To make the Gödel number of a proof, an additional 21st symbol is needed to act as a punctuation mark delimiting each statement or line of a proof. Alternatively, the standard method is to translate the sequence of statements into a sequence of their Gödel numbers , and let the “super Gödel number” of the sequence to be .
“arithMETical” is used in place of “arithMETic” to distinguish it from “aRITHmetic” as is used elsewhere.
The process of checking if two Gödel numbers form a “proof-pair” involves 1) translating both numbers to their TNT-counterparts, 2) verifying that the last statement of the proof matches the theorem to be proved, and 3) verifying that each statement in the proof is either an axiom or can be obtained by combining previous lines through valid rules. This algorithm is primitive recursive and is therefore provably representable in TNT.
The exact formulation of this function is extremely complex and is done in Gödel’s papers. Page 81 of Gödel’s Proof offers a brief attempt.
This statement is a simpler, but stronger assertion than what Gödel actually proved. Gödel showed that if is provable, then is provable; and if is provable, then arithmetic is -inconsistent.
Proving consistency of a system usually involves finding a formula in that system that cannot be proven, since if a system were inconsistent, then all formulas could be proven. In TNT, all axioms are tautological, and all rules of inference preserve tautologicalness. Thus the formula which is not a tautology, cannot be proven.
TNT is syntactically incomplete. A system is syntactically complete if for every sentence of the system, either or is a theorem. This property is also called Gödel completeness.
Berto, Francesco. There’s Something about Gödel: the Complete Guide to the Incompleteness Theorem. Wiley-Blackwell, 2009.
Detlefsen, Michael. “Completeness and the ends of axiomatization.” Interpreting Gödel. Ed. Juliette Kennedy. Cambridge: Cambridge UP, 2014.
Hofstadter, Douglas R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Basic Books, Inc., 1979.
Nagel, Ernest, and James R. Newman. Gödel's Proof. New York: New York UP, 1958.
Smith, Peter. An Introduction to Gödel’s Theorems. 2nd ed., Cambridge University Press, 2013.
Smullyan, Raymond M. Gödel’s Incompleteness Theorems. Oxford University Press, 1992.
Styazhkin, N. I. History of Mathematical Logic from Leibniz to Peano. Cambridge: The M.I.T. P, 1969.