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

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 q

_{1}, ..., q

_{s}. We can construct the Gödel number k of formula F as follows:

k = p

_{1}^q

_{1}* p

_{2}^q

_{2}* ...* p

_{s}^q

_{s}, where p

_{i }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 p

_{1}^q

_{1*}p

_{2}^q

_{2}* ...* p

_{s}^q

_{s}, from which it is possible to arrive at formula F by extracting the sequence of numbers q

_{1}, ..., q

_{s}. 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 A

_{i}(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 |
||||||||

A_{1}(x) |
A_{1}(1) |
A_{1}(2) |
A_{1}(3) |
A_{1}(4) |
A_{1}(5) |
A_{1}(6) |
A_{1}(7) |
A_{1}(8) |
… |

A_{2}(x) |
A_{2}(1) |
A_{2}(2) |
A_{2}(3) |
A_{2}(4) |
A_{2}(5) |
A_{2}(6) |
A_{2}(7) |
A_{2}(8) |
… |

A_{3}(x) |
A_{3}(1) |
A_{3}(2) |
A_{3}(3) |
A_{3}(4) |
A_{3}(5) |
A_{3}(6) |
A_{3}(7) |
A_{3}(8) |
… |

A_{4}(x) |
A_{4}(1) |
A_{4}(2) |
A_{4}(3) |
A_{4}(4) |
A_{4}(5) |
A_{4}(6) |
A_{4}(7) |
A_{4}(8) |
… |

A_{5}(x) |
A_{5}(1) |
A_{5}(2) |
A_{5}(3) |
A_{5}(4) |
A_{5}(5) |
A_{5}(6) |
A_{5}(7) |
A_{5}(8) |
… |

A_{6}(x) |
A_{6}(1) |
A_{6}(2) |
A_{6}(3) |
A_{6}(4) |
A_{6}(5) |
A_{6}(6) |
A_{6}(7) |
A_{6}(8) |
… |

A_{7}(x) |
A_{7}(1) |
A_{7}(2) |
A_{7}(3) |
A_{7}(4) |
A_{7}(5) |
A_{7}(6) |
A_{7}(7) |
A_{7}(8) |
… |

A_{8}(x) |
A_{8}(1) |
A_{8}(2) |
A_{8}(3) |
A_{8}(4) |
A_{8}(5) |
A_{8}(6) |
A_{8}(7) |
A_{8}(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:

A

_{1}(1), A

_{2}(2), A

_{3}(3), A

_{4}(4), A

_{5}(5), A

_{6}(6), A

_{7}(7), A

_{8}(8), …, A

_{i}(i), …

Each of the statements on this list has an associated Gödel number. We can name these Gödel numbers as follows:

a

_{1}(1), a

_{2}(2), a

_{3}(3), a

_{4}(4), a

_{5}(5), a

_{6}(6), a

_{7}(7), a

_{8}(8), …, a

_{i}(i), …

Now we can make the following statement: “For each x, a

_{x}(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 A

_{n}(x) is the statement, “For each x, a

_{x}(x) is not on the list of provable statements.” The statement A

_{n}(n) can describe itself, since it implies that for x = n, a

_{n}(n) is not on the list of provable statements and therefore that A

_{n}(n) is not provable. The Gödel number a

_{n}(n) of A

_{n}(n) is therefore the desired number

*g*, and A

_{n}(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 that “No 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

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,

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,

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

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

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. *

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.

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”

___________

**G. Stolyarov II is a science fiction novelist, independent
philosophical essayist, poet, amateur mathematician, composer,
contributor to Enter Stage Right, Le Quebecois Libre, Rebirth of Reason, and the Ludwig von Mises Institute, Senior Writer for The Liberal Institute, former weekly columnist for GrasstopsUSA.com, and Editor-in-Chief of The Rational Argumentator, a magazine championing the principles of reason, rights, and progress. Mr. Stolyarov’s new blog, ****The Progress of Liberty**,
offers a combination of commentary, multimedia presentations,
educational materials, and suggestions for effective activism in favor
of individual freedom. Mr. Stolyarov also publishes his articles on Helium.com and Associated Content
to assist the spread of rational ideas. He holds the highest Clout
Level (10) possible on Associated Content. Mr. Stolyarov has also
written a science fiction novel, **Eden against the Colossus****, a non-fiction treatise, A Rational Cosmology, and a play,**

**Implied Consent.****He has made YouTube Videos since the beginning of 2008, which have been watched over 32,000 times to date.**

**Mr. Stolyarov can be contacted at gennadystolyarovii@yahoo.com.**

** **

**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.