Hilbert’s Second Problem and Gödel’s Incompleteness Theorems

In a talk given at the Second International Congress of Mathematicians in the year 1900, David Hilbert (one of the greatest mathematicians of his day) outlined what he considered to be ten of the unsolved problems of mathematics, believing that by pointing to the unsolved problems in mathematics, he would be able to give direction to the mathematical world. Among these problems (which included the continuum hypothesis), he included the consistency of arithmetic, which is now known as “Hilbert’s Second Problem”.

Many of the problems outlined by Hilbert have since been solved, but a few of them remain unsolved (Kantor 1996) (Note: Hilbert listed a total of twenty-three unsolved problems, but chose to lecture only on ten of them. The remaining problems were published in the Proceedings of the Congress of Mathematics). While there is  still controversy over whether or not Hilbert’s Second Problem has been solved, it is clear that the consistency of arithmetic cannot be formulated within arithmetic itself, as proven by Kurt Gödel in 1931 by the Second Incompleteness Theorem. Both the First and the Second Incompleteness Theorems as proven by Gödel had great implications for the rest of mathematics, especially, given the nature of Hilbert’s project and his reasons for wanting the consistency of mathematics to be proven, for the dispute between the classical mathematicians and the intuitionists.

Finitism and Hilbert’s Second Problem 

In the midst of the dispute over mathematical justification and the foundations of arithmetic between classical mathematicians and intuitionists, David Hilbert, hoping to settle the dispute, offered a new theory of the foundation of mathematics. The classical mathematicians, he claimed, were correct in adhering to the notion of a completed infinite and refusing to give up the Law of the Excluded Middle, but the intuitionists were justified both in questioning the foundations of arithmetic and in demanding proper justification for rules of inference; hoping to preserve the Law of the Excluded Middle and the notion of a completed infinite while appealing to the epistemological concerns of the intuitionists, he sought to provide a theory whose justification could be accepted by both the classical mathematicians and the intuitionists.

In his new theory of the foundation of mathematics, which he called Finitism, Hilbert argued that the foundation of mathematics lies in a mental faculty – namely, that of intuition; it is through the power of mathematical intuition that we are able to grasp mathematical symbols (which he thought were concrete objects) and “apprehend truths about them and their relationships” (George and Velleman 2002, p. 148),  engaging in finitary reasoning (he was, however, not at all clear about precisely what finitary reasoning was). Because Finitism’s foundation lies in intuition alone, Hilbert claimed, it does not need further justification: “in fact, the collection of finitary truths about symbols and finitarily correct principles of reasoning is what constitutes the framework that renders possible “all scientific thought, understanding and communication” (Ibid., p. 148).

Hilbert attempted to show that it was possible to formulate claims in arithmetic using finitism with a method using lines (like “|” for “1”, “||” for “2”, “|||” for “3”, and so on) and basic rules of arithmetic to represent basic equations. He was hopeful, and believed that his finitist project would effect a reconciliation between the classical mathematicians and the intuitionists: he had formulated arithmetic within finitism without appealing to anything but the faculty of intuition that he postulated, and he hoped that, if arithmetic could be shown to be consistent using only “the means available within finitism”, all infinitary mathematics could be reduced to finitary
mathematics without the fear of paradox, and the dispute between the classical mathematicians and the intuitionists would be resolved (Ibid., p. 152).

It was with this in mind that, in 1900, at the Second International Congress of Mathematicians, Hilbert included the consistency of arithmetic in his list of the unsolved problems of mathematics. The problems of mathematics Hilbert presented accomplished precisely what he meant them to accomplish: they pointed the greatest mathematicians to the most pressing unsolved problems within mathematics, and encouraged much progress within mathematics. In 1931, one of the most influential and brilliant young mathematicians of the time, Kurt Gödel, presented his two Incompleteness Theorems, in which he proved that the consistency of arithemetic cannot be proven within arithmetic itself, ending the promise of Hilbert’s finitist project.

Gödel’s Incompleteness Theorems

In order for any theory to be consistent, it must be shown that it is not possible that, in our theory, we can derive some sentence and the negation of that sentence. In addition, any proof of consistency, if it is to be trusted, should not appeal to any reasoning higher than that used by the system which it is about – which is why Hilbert wanted the proof of the consistency of arithmetic to be proved within the finitist system. In 1931, however, Kurt Gödel showed that it was not possible to prove the consistency of arithmetic within arithmetic itself, in his First and Second
Incompleteness Theorems.

In the First Incompleteness Theorem, Gödel proved that if a formal theory of arithmetic is consistent, then it is incomplete. In other words, the First Incompleteness Theorem shows that, if a formal theory of arithmetic, T, is consistent, then there will be some sentence, G, and there will exist no proof of either it nor of its negation within T, making T incomplete. To prove this, Gödel came up with a formal theory of arithmetic, complete with a numbering scheme in which every expression, function, relation, number, etc., was given a ‘Gödel Number’ – making it possible for Gödel to express nearly everything within Peano Arithmetic using only numbers (Gödel numbers, but numbers nonetheless). Most importantly, he showed that, using the Gödel numbering system, it was possible to express recursive relations in Peano Arithmetic.

The fact that he was able to express recursive relations within Peano Arithmetic using the numbering system he created made it possible for him to show that, in the formal theory he was working in (which we will call T), there existed some sentence which could not be proven in T, and whose negation could not be proved either. Because T is consistent, Gödel was able to show that, for any consistent formal theory, there would exist some theorem which would not be a theorem in that formal theory. All formal theories of arithmetic, if consistent, are incomplete.

Building on what he had proven in the First Incompleteness Theorem, Gödel presented the Second Incompleteness Theorem, in which he proved that if a formal theory of arithmetic is consistent, it cannot prove that it is consistent. If the formal theory we are working with, T, is a consistent extension of Peano Arithmetic, then the consistency of T, Con(T), cannot be formulated within T itself; in fact, if Con(T) can be formulated within T, this proves that T is inconsistent.

Classicist and Intuitionist Interpretations of Godel’s Theorems

Gödel showed that it was possible, as Hilbert had thought, to talk about consistency and proof without appealing to reasoning not found in the system in which one was working – realizing part of Hilbert’s hopes for the consistency of arithmetic. The hopes Hilbert had, however, and the finitist project he thought could accomplish them, were dashed when Gödel showed with the First and Second Incompleteness Theorem both that if arithmetic was consistent, it would be incomplete, and that, if one could formulate the consistency of arithmetic within arithmetic, it would prove that arithmetic was inconsistent.

There exists some disagreement about whether or not this solves Hilbert’s Second Problem, as Gödel did not prove the consistency of arithmetic, rather, he showed that arithmetic was not consistent. Hilbert had thought that if the consistency of arithmetic could be shown, then the dispute between the classical mathematicians and the intuitionists would be resolved, but, with the Incompleteness Theorems, not only did the disagreement between the two schools of mathematics continue, but both the classical mathematicians and the intuitionists interpreted the
Incompleteness Theorems differently.

The classical mathematicians believed that mathematical reality is already determined and complete, and that it was the role of the mathematician to study the truths of mathematical reality. Because they thought that the truths of mathematics were true independently of what could be proven true by mathematicians, they interpreted the First Incompleteness Theorem as proving their point: the truths of mathematics are not true because we can prove them, and some truths exist that are not provable.

Not surprisingly, the intuitionists balked at this interpretation. Having already rejected the notion of a determined, complete mathematical reality, they claimed that Gödel’s First and Second Incompleteness Theorem should be interpreted as showing that “provable” (like “real number”) is an indefinitely extensible concept: the truths, they claimed, exist insofar as we can prove them.

Although the intuitionist school of mathematics is relatively small, and classical mathematicians compose the majority of the mathematicians today, Hilbert’s hopes for a reconciliation between the two schools has not been realized. Even more importantly, the foundations of arithmetic, and the justification for the inference rules used in mathematics, is still in question. Though Hilbert’s finitism project collapsed, the intuitionists and classical mathematicians both continue to defend their justifications (or lack of justifications) for the inference rules they use: the classical mathematicians stubbornly refusing to give up the Law of Excluded Middle, and the intuitionists claiming that, since there is no justification for the Law of Excluded Middle, it ought to be discarded.

Bibliography

George, Alexander and Velleman, Daniel J. (2002). Philosophies of Mathematics. Malden,
Mass.: Blackwell.

Kantor, Jean-Michel (1996). “Hilbert’s Problems and Their Sequels”. The Mathematical
Intelligencer, Vol. 18, No. 1: 21-30.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: