Hilbert’s Second Problem, Gödel’s Incompleteness Theorems, and Consistency Proofs for Peano Arithmetic

G. Stolyarov II
 
Issue CXCV - May 23, 2009
Recommend this page.

A sample image
Kurt Gödel’s work on Hilbert’s second problem – which challenged mathematicians to prove the consistency of the axioms of arithmetic – led to some of the most significant results in twentieth-century mathematics, Gödel’s incompleteness theorems. Gödel’s first incompleteness theorem shows that systems having at least the properties of Peano arithmetic cannot be both complete and consistent. Gödel’s second incompleteness theorem shows that no system with such properties can be proved consistent within itself, unless it is an inconsistent system. Following Gödel’s 1931 publication of these theorems, mathematicians’ approach to Hilbert’s second problem changed dramatically – leading eventually to Gerhard Gentzen’s consistency proof for Peano arithmetic in 1936 and Gödel’s own consistency proof in 1958. Both of these proofs abided by the limitations of Gödel’s incompleteness theorems, and it is still disputed whether Hilbert would have considered them solutions to his second problem. Here, the formulations and implications of Hilbert’s second problem, Gödel’s incompleteness theorems, and the later work of Gentzen and Gödel will be explored, and some of the proofs involved in this work will be broadly outlined.
 
Peano Arithmetic
 
The Italian mathematician Giuseppe Peano (1858-1932) presented his axiomatization of arithmetic in an 1889 book, entitled, The Principles of Arithmetic Presented by a New Method.[1] According to Eric Weisstein,[2] the following five axioms are sufficient to describe the set of natural numbers N under Peano arithmetic:
 
Axiom 1. 0 є N. (Zero is a natural number.)
Axiom 2. For each x є N, there exists exactly one x’ є N, called the successor of x.
Axiom 3. For any x є N, x’ ≠ 0. (Zero is not the successor of any natural number.)
Axiom 4. For x, y є N, x = y if and only if x’ = y’. (If two natural numbers are equal, then their successors are equal. The converse also holds.)
Axiom 5. If M is a subset of N such that the following two conditions hold:
i)                    0 є M
ii)                  If x є M, then x’ є M.
Then it follows that M = N. (This axiom is also known as the Principle of Induction.)
 
These axioms enable the definition of such operations as addition and multiplication. For instance, we can define addition (denoted “+”) via the following two properties:
i)                    x’ =  x + 1 for all x є N (where 1 = 0’). This means that each number’s successor is equal to the original number plus the successor of zero. 
ii)                  x + y’ = (x + y)’ for all x, y є N. This means that a number x plus the successor of a number y is the same as the successor of the sum of x and y.
Multiplication (denoted “*”)  can likewise be defined by the following properties:
i)                    x =  x * 1 for all x є N (where 1 = 0’). This means that any number multiplied by the successor of zero is equal to the original number.
ii)                  x * y’ = (x * y) + x for all x, y є N. This means that a number x multiplied by the successor of a number y is the same as sum of the product of x and y and an additional x.
 
Hilbert’s Second Problem
 
In 1900, speaking before the International Congress of Mathematicians in Paris, David Hilbert (1862-1943) asked the mathematicians of the twentieth century “to prove that [the axioms of arithmetic] are not contradictory, that is, that a definite number of logical steps based upon them can never lead to contradictory results.”[3] It is instructive to examine Hilbert’s remarks on his second problem so as to get an understanding of what, in his mind, counted as a solution.

Hilbert believed that in the foundations of arithmetic, like in all “foundations of a science, …
no statement within the realm of the science whose foundation we are testing is held to be correct unless it can be derived from [the] axioms by means of a finite number of logical steps.”[4] Hilbert therefore wanted verification that any true statement in arithmetic could be shown to be provable by a deduction from the axioms of arithmetic consisting of finitely many steps.
 
Thus, Hilbert believed that it was important to produce a finitistic proof for the consistency of the arithmetical axioms. According to Solomon Feferman,
Hilbert concluded that in order to prove the consistency of various formal systems for mathematics that embody the actual infinite, one must use only concepts and reasoning dealing solely with finite objects in a completely finitary way. However, Hilbert did not make precise exactly what methods are finitary (also called finitistic), but only gave examples.[5]
Whether Hilbert’s finitistic criterion can possibly be met is a matter of dispute among mathematicians, as we will later discuss.
 
Proving the consistency of the axioms of arithmetic has important implications for proving the consistency of the axioms of geometry as well. Hilbert explained that  "[i]n geometry, the proof of the compatibility of the axioms can be effected by constructing a suitable field of numbers, such that analogous relations between the numbers of this field correspond to the geometrical axioms… [T]he desired proof for the compatibility of the geometrical axioms is made to depend upon the theorem of the compatibility of the arithmetical axioms."[6]

Hilbert was convinced that “a direct method is needed for the proof of the compatibility of the arithmetical axioms” and that “it must be possible to find a direct proof for the compatibility of the arithmetical axioms, by means of a careful study and suitable modification of the known methods of reasoning in the theory of irrational numbers.”[7] Hilbert did not, however, define what he meant by a “direct proof,” and as a result there has been considerable dispute to this day on what would or would not satisfy the criteria for solving his second problem. 

 
The Importance of Non-Contradiction
 
Why was it crucial to prove the non-contradictory nature of the axioms of arithmetic? Several reasons can be given, the first of them suggested by Hilbert himself:  “if contradictory attributes be assigned to a concept, I say, that mathematically the concept does not exist.[8] For Hilbert, the ability to consistently use a mathematical concept in all cases to which it could apply was the equivalent of the existence of such a concept – and in this manner Hilbert justified the mathematical existence of imaginary numbers. For Hilbert, the proof of the consistency of the axioms of arithmetic would be “at the same time the proof of the mathematical existence of the complete system of real numbers or of the continuum.”[9] Hilbert wanted such a proof so that “the doubts which have been expressed occasionally as to the existence of the complete system of real numbers will become totally groundless.”[10] Hilbert also noted that such a recognition “corresponds best also to what experience and intuition tell us,”[11] so a part of Hilbert’s motivation was to confirm mathematically what seemed evident to humans as a result of observing reality.
 
Moreover, a logical system in which even a single contradiction is present suffers from a fatal defect: in such a system, it is possible to prove absolutely anything.[12] Following the argument illustrated by Robert Brown, let us assume that in some given system, statement A and its negation “not A” (denoted ~A) are both true. Now we can take another statement – B – which can be any statement one wishes. Then the statement “~B implies A” is also true, since any implication whose consequent is true is also true. Since “~B implies A” is true, its contrapositive, “~A implies B,” is also true. Because we assumed that ~A is true, it follows by modus ponens that B is true. We recall that B can be any statement, so any statement can be shown to be true within a system that admits even one contradiction. This does not leave much usefulness or relevance for the self-contradictory system. In the words of Brown, “A contradiction contaminates anything it touches, because asserting it is ‘true’ or ’false’ gets you into equal amounts of trouble, because there are always clever ways of inserting it into logical statements that corrupt the downstream processing of the truth tables.”[13]
 
Completeness and Consistency

Before delving into Kurt Gödel's work on Hilbert’s second problem, it is useful to introduce formal definitions of the terms completeness and consistency, which in mathematics have much stricter meanings than they do in everyday language. According to Torkel Franzén, a formal system is complete if “for every sentence A in the language of the system, either A or its negation is a theorem of the system, i.e. can be derived using the axioms and rules of inference.”[14] A formal system is consistent if “there is no A such that both A and its negation can be derived.”[15] The consistency of a formal system is equivalent to the impossibility of deriving any contradictory statements from the axioms of the system. What Hilbert was interested in, and what Kurt Gödel’s incompleteness theorems clarified, are questions pertaining to completeness and consistency with regard to Peano arithmetic in the sense of the definitions above.

Neither completeness nor consistency of a system are necessarily tied to the truth-value of the statements within that system: “The concepts of consistency and completeness are purely syntactical concepts, meaning that they are all about formal rules and formulas, and don't involve any notion of truth or falsity.”[16]  It is possible to make statements regarding the completeness and consistency of systems whose contents have no relevance to the real world and thus which it would be nonsensical to label as “true” or “false.” However, if the contents of a system can be given a meaningful, substantive interpretation, then it might be possible to describe them as true and to claim that their truth follows from the system’s consistency. It was in this sense that Hilbert considered the mathematical existence of imaginary numbers to be true.

Franzén emphasizes that “Consistency in the sense of Gödel's theorem… is a purely formal and mathematical matter.”[17] Gödel's incompleteness theorems do not pertain to systems which are not framed in the language of mathematics – such as political, religious, esthetic, economic, biological, and literary systems and bodies of thought. Virtually every such system is incomplete in the formal mathematical sense; for instance, “the Constitution doesn't say anything about whether or not dancing the polka in Congress is allowed.”[18] But this insight does not require Gödel's work for us to recognize; rather, it is evident to the sensible observer. As we will subsequently see, Gödel's work did have important, non-trivial, and much more interesting implications for the field of mathematics itself.

Gödel's Incompleteness Theorems

The incompleteness theorems of Kurt Gödel (1906-1978) revolutionized mathematicians’ understanding of Hilbert’s second problem and made apparent significant limitations regarding how it might be possible to prove the consistency of the axioms of arithmetic. Since an inconsistent system – one which admits contradictions – allows one to prove anything at all, the limitations described by Gödel's incompleteness theorems apply only to consistent systems. Gödel's theorems address limitations regarding what can be proved within a consistent system. The theorems were published by Gödel in his 1931 paper, "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I."[19] The work to which Gödel responded, Principia Mathematica, was written by Bertrand Russell and Alfred North Whitehead; its three volumes were first published during the years from 1910 to 1913, and its major endeavor was “putting forward a logical foundation for mathematics in the form of a (far from transparent) system of axioms and rules of reasoning within which all of the mathematics known at the time could be formulated and proved.”[20] Gödel’s results applied not only to the system of Principia Mathematica but also to Peano arithmetic and other systems with characteristics that will be described below. 

How was Gödel able to use arithmetic to describe formulas that could make statements about themselves? Gödel developed a way of formulating each statement in Peano arithmetic as a natural number – known as the Gödel number for that statement.[21] According to Haim Gaifman, the assignment of Gödel numbers to formulas “makes it possible to express within a formal theory of numbers the basic syntactic, and proof-theoretic, notions of the system itself.”[22]
 
Gödel assigned a natural number to each basic symbol in Peano arithmetic. It is possible to follow this procedure with any symbols used in arithmetic – such as +, =, 0, 1, *, and quantifiers such as “for all” and “there exists.” As a result, it is possible to express each formula in arithmetic as a sequence of natural numbers.[23] Now we consider a formula F of length s – that is, a formula in Peano arithmetic that uses s symbols and so can be expressed as a sequence of some s natural numbers q1, ..., qs. We can construct the Gödel number k of formula F as follows:
k = p1^q1* p2^q2* ...* ps^qs, where pi is the ith prime number.[24] Since each distinct formula will be represented by a distinct sequence of natural numbers, it will have a unique Gödel number by this approach.
 
It is possible to restore the formula F from k. The fundamental theorem of arithmetic states that every natural number can be uniquely factored into prime numbers.[25] Thus, every Gödel number k can be uniquely factored into a product of prime numbers and can thus be expressed in the form p1^q1* p2^q2* ...* ps^qs, from which it is possible to arrive at formula F by extracting the sequence of numbers q1, ..., qs. Because each formula in Peano arithmetic can be associated with a natural number, it follows that there are countably many such formulas, as there are countably many natural numbers.
 
Gödel then proceeded to construct a Gödel number g, which corresponds to the following sentence: “There does not exist a natural number m such that m is the Gödel number of a sequence of sentences forming a proof for the sentence with Gödel number g.”[26] We can call the preceding sentence G and state it in a different way: G: “G is unprovable in Peano arithmetic.”[27] The sentence G talks about its own provability and is therefore self-referential. It is not immediately obvious how the Gödel number g might be found – as for any procedure that finds it, “the result of this calculation, g, appears in the sentence itself, and therefore affects the calculation.”[28]  Gödel used the technique of diagonalization to prove that g must exist. We illustrate Gödelian diagonalization using notation and reasoning presented by Ben Yandell.[29]
 
For some variable x, we can assign Gödel numbers to any statement in Peano arithmetic which includes x as a free variable. We can denote any such statement Ai(x), where i is a natural number. We can then construct the following table:
 
Statements about x Statements where a natural number has been substituted for x
A1(x) A1(1) A1(2) A1(3) A1(4) A1(5) A1(6) A1(7) A1(8)
A2(x) A2(1) A2(2) A2(3) A2(4) A2(5) A2(6) A2(7) A2(8)
A3(x) A3(1) A3(2) A3(3) A3(4) A3(5) A3(6) A3(7) A3(8)
A4(x) A4(1) A4(2) A4(3) A4(4) A4(5) A4(6) A4(7) A4(8)
A5(x) A5(1) A5(2) A5(3) A5(4) A5(5) A5(6) A5(7) A5(8)
A6(x) A6(1) A6(2) A6(3) A6(4) A6(5) A6(6) A6(7) A6(8)
A7(x) A7(1) A7(2) A7(3) A7(4) A7(5) A7(6) A7(7) A7(8)
A8(x) A8(1) A8(2) A8(3) A8(4) A8(5) A8(6) A8(7) A8(8)
 
Because there are countably many statements in Peano arithmetic, there are also countably many provable statements in Peano arithmetic. We can think of a master list of such provable statements – expressed in terms of the statements’ Gödel numbers. Then we can make statements with respect to that list. In the table above, we can consider the statements on the diagonal of the table (in bold) and arrange them in a separate list:   
A1(1), A2(2), A3(3), A4(4), A5(5), A6(6), A7(7), A8(8), …, Ai(i), …
 
Each of the statements on this list has an associated Gödel number. We can name these Gödel numbers as follows:
a1(1), a2(2), a3(3), a4(4), a5(5), a6(6), a7(7), a8(8), …, ai(i), …
 
Now we can make the following statement: “For each x, ax(x) is not on the list of provable statements.” We note that this is itself a statement about x which includes x as a free variable. Thus, it is by definition in the list of statements about x in the first column of the table above. Thus, there exists some natural number n such that An(x) is the statement, “For each x, ax(x) is not on the list of provable statements.” The statement An(n) can describe itself, since it implies that for x = n, an(n) is not on the list of provable statements and therefore that An(n) is not provable. The Gödel number an(n) of An(n) is therefore the desired number g, and An(n) is the self-referential Gödel sentence G.[30]
 
Gödel next examined the truth-value of the sentence G. G says that it is unprovable in Peano arithmetic, and it is in fact unprovable, as demonstrated by Gödel’s diagonalization argument. Therefore, G is a true statement since it correctly describes its own unprovable status. Thus, Gödel found a true but unprovable statement within Peano arithmetic. The truth of G cannot be ascertained within the system of Peano arithmetic itself. Rather, we require metamathematical reasoning – reasoning outside the mathematical system in question – in order to determine its truth.[31]
 
Gödel used a proof by contradiction to show that G is true. What would happen if G were a false statement? Then the statement “G is unprovable in Peano arithmetic,” which is G, would be false. Then it would follow that G is provable in Peano arithmetic. If G were proved true, then it would be true that G is unprovable in Peano arithmetic, which is a contradiction of the assertion that G was proved true in Peano arithmetic. If G were proved false, then ~G would be proved true, which would mean that “G is provable in Peano arithmetic” would be true, so a proof for the truth of G would exist in Peano arithmetic. This would mean that Peano arithmetic simultaneously contains proofs of both the truth and falsity of G – a contradiction. If G were a false statement, then Peano arithmetic would be an inconsistent system. The only way for Peano arithmetic to be a consistent system is for G to be both true and unprovable in Peano arithmetic.[32]
 
The above reasoning was utilized by Gödel in the proof of his first incompleteness theorem, which states that
Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory.[33]

Theories to which Gödel’s first incompleteness theorem applies cannot be described via a finite body of axioms – since no list of axioms will suffice to enable one to prove all true statements within the system. Moreover, it is not even possible to find for such systems “an infinite list of axioms, with the requirement that we can mechanically check if each statement is an axiom or not. In computer science, this is known as having a recursive set of axioms.”[34] For Peano arithmetic, then, “you can never discover the complete list of axioms. Each time you add a statement as an axiom, there will always be another statement out of reach.”[35] Gödel’s first incompleteness theorem “shows that we cannot formally specify the sum total of our mathematical knowledge.”[36]
 
Gödel’s proof of the existence of true but unprovable statements can be applied not only to Peano arithmetic itself but to any system which gives one the capacity to assign Gödel numbers to statements. Such a system must be “expressive enough to define the set of natural numbers or develop basic properties of the natural numbers,”[37] so it is possible to have complete and consistent systems which cannot be used to define the natural numbers. Not just defining the natural numbers but defining the natural numbers as a set is essential for Gödel’s first incompleteness theorem to apply to a system:
You must also be able to express the concept "'x' is a natural number" using your axioms and first-order logic. There are plenty of systems that contain the natural numbers and are complete. For example, both the real numbers and complex numbers have complete axiomatizations.[38]
Systems such as Euclidean geometry and real closed fields – fields which have “the same first-order properties as the field of real numbers”[39] – can also be completely axiomatized and are both complete and consistent.[40]
 
Moreover, Gödel’s theorem applies only to systems which are defined to have a recursively enumerable set of axioms – where a recursively enumerable set is one that “constitutes the range of a recursive function.”[41] The set of all true statements about the natural numbers is not recursively enumerable; if it were taken as the set of axioms for Peano arithmetic, then the resulting system would be both complete and consistent – but one would rightly question its usefulness if its axioms cannot be enumerated.[42] “Given a random statement, there will be no way to know if it is an axiom of your system. If I give you a proof, in general there will be no way for you to check if that proof is valid.”[43]
 
Gödel’s second incompleteness theorem is a corollary to the first. Its implications for mathematics are even stronger:

"For any formal recursively enumerable (i.e., effectively generated) theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent."[44]

In other words, Gödel’s second theorem states thatNo consistent system [fulfilling the conditions above] can be used to prove its own consistency.”[45] An outline of the proof of Gödel’s second theorem can be given by considering what has already been demonstrated in the proof of his first theorem.[46] We can take some system T within which the Gödel sentence G: “G is unprovable in T” is both true and unprovable. We assume that T is recursively enumerable and contains the requisite basic arithmetical truths and truths about formal provability. By Gödel’s first theorem, if system T is consistent, then G must exist. We can abbreviate “T is consistent” as “T-con.” Therefore, the following reasoning can demonstrate the truth of Gödel’s second theorem.
1.      T-con implies G. This is true by Gödel’s first theorem.
2.      T-con is provable implies G is provable. This is true since if the implication in step 1 is true, we can prove the consequent by proving the antecedent.
3.      G is unprovable implies T-con is unprovable. This is the contrapositive of step 2.
4.      G is unprovable. This is true by Gödel’s first theorem.
5.      Therefore, T-con is unprovable. This is true by modus ponens applied to steps 3 and 4.
Thus, Gödel’s second incompleteness theorem follows from his first, and the axioms of Peano arithmetic cannot be used as the beginning of the process of proving their own consistency.
 
Status of Hilbert’s Second Problem: It Depends on Definitions
 
Gödel’s second incompleteness theorem states that it is impossible to prove the consistency for a recursively enumerable theory within the framework of that theory itself. Thus, the framework of Peano arithmetic cannot be used to prove the consistency of the axioms of Peano arithmetic. If this was Hilbert’s intention when asking for a “direct proof” of the consistency of the arithmetical axioms, then Gödel’s second incompleteness theorem illustrated that such an endeavor is impossible. Moreover, more advanced systems such as real analysis and number theory – which incorporate arithmetic fully – cannot be proved consistent starting with the axioms of Peano arithmetic.[47]
 
A commonly accepted definition of a “direct proof” is “a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems without making any further assumptions.”[48] Another definition is “an argument that establishes the truth of a statement by making direct use of the hypotheses, as opposed to a proof by contradiction.”[49] No mention is made in these definitions of the system in which the theorems, lemmas, and hypotheses used are contained. By these definitions, if the statement, “The axioms of Peano arithmetic are consistent,” is proved using the theorems, lemmas, and hypotheses of a system other than Peano arithmetic – and the proof is not a proof by contradiction – then the proof is a valid direct proof. If Hilbert shared the prevailing current understanding of what a direct proof is, then he might have considered his second problem to have been solved after all – as numerous consistency proofs for Peano arithmetic have been produced outside of the framework of Peano arithmetic itself.
 
Hilbert, in response to Gödel’s work, did not acknowledge a defeat for his program of rigorously establishing the consistency of the arithmetical axioms as a foundation for mathematics. He did not even think that Gödel’s results rendered impossible the endeavor of providing a finitistic proof for the axioms of artithmetic. Hilbert wrote in his 1934 preface to Volume I of Grundlagen der Mathematik:

"I would like to emphasize the following: the view, which temporarily arose and which maintained that certain recent results of Gödel show that my proof theory can’t be carried out, has been shown to be erroneous. In fact that result shows only that one must utilize the finitary standpoint in a sharper way for the farther reaching consistency proofs…"[50]

Gödel himself did not initially view his incompleteness theorems as defeating any of Hilbert’s program. He wrote:

"I wish to note expressly that [this theorem does] not contradict Hilbert’s formalistic viewpoint. For this viewpoint presupposes only the existence of a consistency proof in which nothing but finitary means of proof is used, and it is  conceivable that there exist finitary proofs that cannot be expressed in the formalism…"[51]

However, a few years of exchanges with John von Neumann (1903 – 1957), who held the view that “Peano Arithmetic already encompasses all that can be done finitistically,”[52] eventually led Gödel to change his mind. If von Neumann was right, then no finitistic proof of the consistency of the arithmetical axioms can be found – because the only such consistency proofs can be done outside the system of arithmetic itself. According to Feferman, most mathematicians today agree with von Neumann. Instead of pursuing a finitistic proof for the arithmetical axioms’ consistency, “much work has gone into extended (or relativized) forms of Hilbert’s program using constructive though non-finitistic means for consistency proofs.”[53]

 
But while Hilbert may have been mistaken in seeking a finitistic proof of the consistency of the arithmetical axioms, he may not have been wrong in thinking that a direct proof was possible.     We will next briefly address two of the consistency proofs that have been originated since the publication of Gödel’s incompleteness theorems.
 
Proofs of the Consistency of the Arithmetical Axioms
 
Gödel’s second theorem showed that the consistency of a system cannot be proved within that system. It is a common mistake, however, to suppose that the system within which such consistency can be proved must be stronger than the original system.  According to Franzén, “The misconception consists in the notion that any such theory T’ in which ‘T is consistent’ is provable must be stronger than T. This is not true. All that Gödel's second theorem shows is that T’ cannot be the same as T.”[54] If the system T’ within which the consistency of T can be proved needs only to be different from T, then Gödel’s incompleteness theorems do not pose any insurmountable difficulties for the enterprise of mathematics. If we do not necessarily have to fall back on a stronger system (whose consistency also cannot be proved within it) to prove the consistency of the system in question, then we do not have to face the infinite regress of having to prove the consistency of increasingly stronger systems by invoking systems that are stronger still but whose consistency is not proved.

In 1936, Gerhard Gentzen (1909-1945) proved the consistency of the arithmetical axioms from within a system that is not stronger than Peano arithmetic in all respects. Gentzen combined primitive recursive arithmetic, the “quantifier-free formalization of the natural numbers,”[55] with quantifier-free transfinite induction, “an extension of mathematical induction to well-ordered sets,”[56] up to the ordinal ε0.[57] The ordinal numbers are used in Gentzen’s proof. The finite ordinals are the natural numbers, and the least infinite ordinal is ω – the cardinality of the set of integers, which is countably infinite. The epsilon numbers, of which ε0 is the smallest, are “a collection of transfinite numbers whose defining property is that they are fixed points of an exponential map.”[58] The ordinal ε0 is the limit of the sequence ω, ωω, ω^( ωω); it is also the smallest number which solves the equation ωε =  ε for ε.[59] The epsilon numbers cannot be obtained via finite applications of addition or multiplication to natural numbers, which makes Gentzen’s chosen system different from Peano arithmetic. Gentzen’s chosen system is also not stronger than Peano arithmetic because it lacks the ability to use quantifiers to describe the natural numbers. The system with which Gentzen starts “doesn't prove ordinary mathematical induction for all formulae, while first-order arithmetic does.”[60]
 
Ordinals smaller than ε0 were used by Gentzen to identify proofs in first-order arithmetic. Then Gentzen showed that “if there is a proof of contradiction [of the arithmetical axioms], then there is an infinite descending sequence of ordinals < ε0 produced by a primitive recursive operation on proofs corresponding to a quantifier-free formula.”[61] Such an infinite descending sequence of ordinals contradicts the principle of transfinite induction. If transfinite induction holds for a formula, then this means that the formula “does not define an infinite descending sequence of ordinals smaller than ε0.”[62]  Hence, the existence of a contradiction derivable from the arithmetical axioms would lead to a contradiction in the proof. Genzten’s proof for the consistency of the arithmetical axioms was an indirect proof, but was nonetheless significant in proving such consistency without transgressing the limitations shown to exist by Gödel.
 
Gödel’s last published paper in the journal Dialectica gave another proof of the consistency of the arithmetical axioms in 1958. In this paper, titled, “On a Hitherto Unexploited Extension of the Finitary Standpoint,” Gödel showed the consistency of Heyting arithmetic, a system which adopts all of the axioms of Peano arithmetic “but uses intuitionistic logic as its rules of inference,”[63] for which the law of the excluded middle does not necessarily hold. Earlier, in 1933, Gödel obtained the result that “If a formula φ is provable from the axioms of Peano arithmetic then φN is provable from the axioms of intuitionistic Heyting arithmetic.”[64] This result “shows that if Heyting arithmetic is consistent then so is Peano arithmetic.”[65] Gödel’s Dialectica paper connected Heyting arithmetic with “a finite type extension of primitive recursive arithmetic, the so-called System T.”[66] Gödel found a way to express a correspondence between every formula in Heyting arithmetic and an analogous formula in System T. According to Thomas Strahm, "Gödel's functional interpretation can be seen as a possible realization of the so-called modified Hilbert program in the sense that it enables a reduction of a classical system to a quantifier-free theory of functionals of finite type, thereby reducing the consistency problem for the classical theory to the consistency of a quantifier-free system of higher-type recursion."[67]
 
The consistency of System T would therefore show the consistency of Heyting arithmetic and therefore the consistency of Peano arithmetic. Primitive recursive arithmetic was proved to be consistent by Wilhelm Ackermann in 1924.[68] Since “the axioms for T are essentially those of primitive recursive arithmetic, except that the variables can be of any finite type,”[69] and primitive recursive arithmetic is consistent, it follows that System T is consistent, and so Peano arithmetic is consistent.
 
The Implications of Gödel’s Incompleteness Theorems
 
Contrary to many widespread impressions, Gödel’s incompleteness theorems do not invalidate the consistency of the axioms of arithmetic nor even show that such consistency cannot be proven. Rather, as Torkel Franzén explains, “Gödel's theorem implies that the consistency of T cannot be proved in T. Why should this be an argument against our accepting the axioms and methods of T?”[70] Gödel himself delivered a proof of the consistency of the arithmetical axioms in 1958, although it will always be an open question whether Hilbert would have considered this proof a satisfactory solution to his second problem if he had lived to see it. Nor does Gödel’s work show anything about the impossibility of obtaining objective truth, as is often alleged. Franzén lists as one of the non sequiturs that many people draw from Gödel’s theorems the idea that they “show that it is not possible to prove that an objective reality exists…”[71] Gödel’s theorems do not pertain to the issue of the existence of an objective reality. As Franzén explains, "’proof’, in Gödel's theorem, is always proof in some particular formal system T. Gödel's theorem can be used to conclude that for any such T there is a true G in the language of T which is not provable in T. It doesn't follow that G is unprovable in any absolute sense. On the contrary, G is always trivially provable in some other theory T'. Whether G is provable in some more interesting sense, for example in the sense of being a consequence of axioms which we can recognize as true, is a matter that Gödel's theorem doesn't tell us anything about."[72]

What Gödel’s incompleteness theorems accomplished for mathematics is much more important than misconceptions of the theorems would imply. According to John W. Dawson, Jr., “Gödel… saw his incompleteness theorems not as demonstrating the inadequacy of the axiomatic method but as showing that the derivation of theorems cannot be completely mechanized. He believed they justified the role of intuition in mathematical research.”[73] Gödel showed, in effect, that it is not possible to reduce all mathematics to just a series of mechanical deductions from axioms; rather, in any sufficiently powerful system, there will always be a role for the mathematician’s own creativity. Such mathematical systems will always have propositions that cannot be derived from any finite set of axioms, and at some point the mathematician has to decide whether to treat these propositions as additional axioms. In proving the consistency of a system from outside that system, the mathematician has to make a choice about which other system to use in order for the proof to both be valid and meaningful.

Mathematics has historically been a highly creative endeavor, and Gödel’s incompleteness theorems affirmed that this will always be the case. In the words of Haim Gaifman, “while [Gödel’s] theorem has profound effects in the foundations of mathematics and on our view of formal systems, it has had very little effect on mathematical practice.”[74] Mathematicians both before and after Gödel used and continue to use both deductive reasoning and other kinds of judgment in deciding how to approach their field. Gödel’s incompleteness theorems made mathematicians aware of the possibility that certain problems may be unsolvable within the system in which they are being examined, “but a special case needs to be made in each instance where there is reason to believe that incompleteness should be a matter of mathematical concern.”[75] It is not the case that the very existence of some incompleteness in many mathematical systems fundamentally cripples mathematicians in any significant way. Franzén emphasizes that "Gödel’s first incompleteness theorem by no means refutes [the] optimistic view of Hilbert’s [that every mathematical problem is solvable]. What it does establish is that Hilbert’s optimism cannot be justified by exhibiting any single formal system within which all mathematical problems are solvable, even if we restrict ourselves to arithmetical problems."[76]

Far from dealing any kind of “fatal blow” to mathematics, Gödel’s incompleteness theorems offered new directions for it. For instance, “[t]he concepts and methods Gödel introduced in his incompleteness paper are central to all of modern computer science.”[77] Two major applications of Gödel’s work include the unsolvability of the halting problem – which asks whether it is ever possible to know via an algorithm whether any particular program will run forever or stop running eventually – and “the demonstration that no program that does not alter a computer's operating system can detect all programs that do.”[78] Some would even go so far as Jürgen Schmidhuber and call Gödel the “founder of theoretical computer science.”[79] Schmidhuber argues that computer science was “a discipline that did not yet officially exist [in 1931] but was effectively created through Gödel's work.”[80] By showing some fundamental limitations to how the consistency of mathematical systems can be proved, Gödel opened up an entirely new field of human endeavor which has brought unprecedented benefits to billions of people.

 
Works Cited
 
Books and Journal Articles

Dawson Jr., John W.  2006. “Gödel and the limits of logic.” Plus Magazine. Issue 39. Available at http://plus.maths.org/issue39/features/dawson/. Accessed 15 February 2009.

Feferman, Solomon. 2006. “The nature and significance of Gödel’s incompleteness theorems.”
Lecture for the Princeton Institute for Advanced Study Gödel Centenary Program, Nov. 17, 2006. Available at http://math.stanford.edu/~feferman/papers/Godel-IAS.pdf. Accessed 15 February 2009.

Franzén, Torkel.
2005. Gödel's Theorem: An Incomplete Guide to its Use and Abuse. Wellesley, Massachusetts: A K Peters, Ltd.

Gaifman, Haim. 2000. “
What Gödel’s Incompleteness Result Does and Does Not Show.” The Journal of Philosophy, August 2000. pp. 462-470. Available at www.columbia.edu/~hg17/godel-incomp4.pdf. Accessed 5 March 2009.

Gödel, Kurt. 1931. “On formally undecidable propositions of Principia Mathematica and related systems I.” In Solomon Feferman, editor, Kurt Gödel: Collected Works, volume 1, pp. 144-195. Oxford University Press, 1986. German text, parallel English translation. Available at http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf. Accessed 10 February 2009.

Hilbert, David. 1900. “Mathematical Problems.” Lecture delivered before the International Congress of Mathematicians at Paris. Available at http://aleph0.clarku.edu/~djoyce/hilbert/problems.html. Accessed 8 February 2009.

Podnieks, Karlis. 1992. What is Mathematics: Gödel’s Theorem and Around. Available at http://www.ltn.lv/~podnieks/index.html. Accessed 10 February 2009.

Strahm, Thomas. 2008. “Introduction.” Dialectica, Volume 62, Issue 2. Special Issue: Gödel’s Dialectica Interpretation. Available at http://www.ucalgary.ca/~rzach/logblog/2008/11/50th-birthday-of-dialectica.html. Accessed 15 February 2009.

Yandell, Ben. H. The Honors Class: Hilbert’s Problems and Their Solvers. Natick, MA: A. K. Peters, Ltd., 2002.

Zach, Richard. 2001. Hilbert’s Finitism: Historical, Philosophical, and Metamathematical Perspectives. Dissertation, University of California, Berkeley. Available at http://www.ucalgary.ca/~rzach/static/hilbert.pdf. Accessed 15 February 2009.

 

Websites
Brown, Robert G. 2007. “Fun with Logic: Contradictions and Null Results. Available at http://www.phy.duke.edu/~rgb/Philosophy/axioms/axioms/node30.html. Accessed 8 February 2009.

“Direct Proof.” Answers.com. Available at http://www.answers.com/topic/direct-proof. Accessed 10 February 2009.

“Direct Proof.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/Direct_proof. Accessed 10 February 2009.

“ε0.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/Epsilon_nought.  Accessed 15 February 2009.

Franzén, Torkel. “Gödel on the Net.” Available at
http://www.sm.luth.se/~torkel/eget/godel.html. Accessed 8 February 2009.

“Fundamental Theorem of Arithmetic.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic. Accessed 9 February 2009.

“Gentzen’s Consistency Proof.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof.  Accessed 15 February 2009.

“Gödel’s Incompleteness Theorem.” BambooWeb Dictionary. Available at
http://www.bambooweb.com/articles/g/%C3%B6/G%C3%B6del%27s_incompleteness_theorem.html. Accessed 10 February 2009.

“Gödel’s Incompleteness Theorem.” EconomicExpert.com. Available at
http://www.economicexpert.com/a/Godel:s:incompleteness:theorem.htm. Accessed 15 February 2009.

“Gödel’s Theorem.” Everything2.com. Available at
http://everything2.com/title/Godel%2527s%2520theorem. Accessed 9 February 2009.

“Gödel-Gentzen negative translation.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/G%C3%B6del%E2%80%93Gentzen_negative_translation. Accessed 15 February 2009.

“Heyting Arithmetic.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/Heyting_arithmetic. Accessed 15 February 2009.

“Kurt Gödel.” 2007. Stanford Encyclopedia of Philosophy. Available at
http://plato.stanford.edu/entries/goedel/. Accessed 15 February 2009.

“Peano Axioms.” Wikipedia, the Free Encyclopedia. Available at
http://en.wikipedia.org/wiki/Peano_axioms. Accessed 8 February 2009.

“Primitive recursive arithmetic.” Wikipedia, the Free Encyclopedia. Available at http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic. Accessed 15 February 2009.

“Real closed field.” Wikipedia, the Free Encyclopedia. Available at http://en.wikipedia.org/wiki/Real_closed_fields. Accessed 10 February 2009.

Sakharov, Alex and Weisstein, Eric W. "Recursively Enumerable Set." From MathWorld--A Wolfram Web Resource. Available at http://mathworld.wolfram.com/RecursivelyEnumerableSet.html. Accessed 10 February 2009.

Schmidhuber, Jurgen. “Kurt Gödel.” Available at http://www.idsia.ch/~juergen/goedel.html. Accessed 15 February 2009.

Suber, Peter. 2002. “Gödel’s Proof.” Available at http://www.earlham.edu/~peters/courses/logsys/g-proof.htm.  Accessed 15 February 2009.

“Transfinite induction.” Wikipedia, the Free Encyclopedia. Available at http://en.wikipedia.org/wiki/Transfinite_induction. Accessed 15 February 2009.

Weisstein, Eric W. "Peano's Axioms." From MathWorld--A Wolfram Web Resource. Available at http://mathworld.wolfram.com/PeanosAxioms.html. Accessed 10 February 2009.



[1] “Peano Axioms.” Wikipedia, the Free Encyclopedia.

[2] Weisstein, “Peano’s Axioms”

[3] Hilbert 1900

[4] Hilbert 1900

[5] Feferman 2006, p. 12

[6] Hilbert 1900

[7] Hilbert 1900

[8] Hilbert 1900

[9] Hilbert 1900

[10] Hilbert 1900

[11] Hilbert 1900

[12] Brown 2007

[13] Brown 2007

[14] Franzén, “Gödel on the Net.”

[15] Franzén, “Gödel on the Net.”

[16] Franzén, “Gödel on the Net.”

[17] Franzén, “Gödel on the Net.”

[18] Franzén, “Gödel on the Net.”

[19] “Gödel’s Theorem,” Everything2.com

[20] Franzén 2005, p. 2

[21] Podnieks 1992, Section 5.2

[22] Gaifman 2000, p. 2

[23] Podnieks 1992, Section 5.2

[24] “Gödel’s Theorem,” Everything2.com

[25] “Fundamental theorem of arithmetic,” Wikipedia, the Free Encyclopedia

[26] “Gödel’s Theorem,” Everything2.com

[27] Podnieks 1992, Section 5.3

[28] “Gödel’s Theorem,” Everything2.com

[29] Yandell 2002, pp. 48-49

[30] The table and reasoning in the preceding paragraph are adapted from Yandell 2002, pp. 48-49.

[31] “Gödel’s Theorem,” Everything2.com

[32] Adapted from Yandell 2002, p. 49

[33] “Gödel’s incompleteness theorems,” Wikipedia, the Free Encyclopedia

[34] “Gödel’s Incompleteness Theorem,” BambooWeb Dictionary

[35] “Gödel’s Incompleteness Theorem,” BambooWeb Dictionary

[36] Franzén 2005, p. 7

[37] “Gödel’s incompleteness theorems,” Wikipedia, the Free Encyclopedia

[38] “Gödel’s Incompleteness Theorem,” BambooWeb Dictionary

[39] “Real closed field,” Wikipedia, the Free Encyclopedia

[40] “Gödel’s incompleteness theorems,” Wikipedia, the Free Encyclopedia

[41] Sakharov and Weisstein, “Recursively Enumerable Set”

[42] “Gödel’s incompleteness theorems,” Wikipedia, the Free Encyclopedia

[43] “Gödel’s Incompleteness Theorem,” BambooWeb Dictionary

[44] “Gödel’s incompleteness theorems,” Wikipedia, the Free Encyclopedia

[45] “Gödel’s Incompleteness Theorem,” EconomicExpert.com

[46] The proof outline that follows was adapted from Peter Suber, “Gödel’s Proof.”

[47] “Gödel’s Incompleteness Theorem,” EconomicExpert.com

[48] “Direct Proof,” Wikipedia, the Free Encyclopedia

[49] “Direct Proof,” Answers.com

[50] Quoted in Feferman 2006, p. 13

[51] Gödel 1931, Collected Works Vol. I , p. 195, quoted in Feferman 2006, p. 13

[52] Feferman 2006, p. 13

[53] Feferman 2006, p. 13

[54] Franzén, “Gödel on the Net.”

[55] “Primitive recursive arithmetic,” Wikipedia, the Free Encyclopedia

[56] “Transfinite induction,” Wikipedia, the Free Encyclopedia

[57] “Gentzen’s consistency proof,” Wikipedia, the Free Encyclopedia

[58] “ε0,” Wikipedia, the Free Encyclopedia

[59] “ε0,” Wikipedia, the Free Encyclopedia

[60] “Gentzen’s consistency proof,” Wikipedia, the Free Encyclopedia

[61] “Gentzen’s consistency proof,” Wikipedia, the Free Encyclopedia

[62] “Gentzen’s consistency proof,” Wikipedia, the Free Encyclopedia

[63] “Heyting arithmetic,” Wikipedia, the Free Encyclopedia

[64] “Gödel-Gentzen negative translation,” Wikipedia, the Free Encyclopedia

[65] “Gödel-Gentzen negative translation,” Wikipedia, the Free Encyclopedia

[66] “Dialectica interpretation,” Wikipedia, the Free Encyclopedia

[67] Strahm 2008

[68] Zach 2001, p. 1

[69] “Kurt Gödel,” Stanford Encyclopedia of Philosophy

[70] Franzén, “Gödel on the Net.”

[71] Franzén 2005, p. 2

[72] Franzén, “Gödel on the Net.”

[73] Dawson 2006

[74] Gaifman 2000, p. 1

[75] Franzén 2005, p. 6

[76] Franzén 2005, p. 16

[77] Dawson 2006

[78] Dawson 2006

[79] Schmidhuber, “Kurt Gödel”

[80] Schmidhuber, “Kurt Gödel”

­­___________

 

Recommend this page.

This TRA feature has been edited in accordance with TRA Statement of Policy.

Click here to return to TRA's Issue CXCV Index.

Learn about Mr. Stolyarov's novel, Eden against the Colossus, here.

Read Mr. Stolyarov's new comprehensive treatise, A Rational Cosmology, explicating such terms as the universe, matter, space, time, sound, light, life, consciousness, and volition, here.

Read Mr. Stolyarov's new four-act play, Implied Consent, a futuristic intellectual drama on the sanctity of human life, here.