Hilbert 2nd problem

In his 1990 lecture to the International Congress of Mathematicians in Paris, David Hilbert presented a list of open problems in mathematics. He expressed the 2nd of these problems, known variously as the compatibility of the arithmetical axioms and the consistency of arithmetic, as follows:

When we are engaged in investigating the foundations of a science, we must set up a system of axioms which contains an exact and complete description of the relations subsisting between the elementary ideas of that science. The axioms so set up are at the same time the definitions of those elementary ideas; and no statement within the realm of the science whose foundation we are testing is held to be correct unless it can be derived from those axioms by means of a finite number of logical steps. Upon closer consideration the question arises: Whether, in any way, certain statements of single axioms depend upon one another, and whether the axioms may not therefore contain certain parts in common, which must be isolated if one wishes to arrive at a system of axioms that shall be altogether independent of one another.

But above all I wish to designate the following as the most important among the numerous questions which can be asked with regard to the axioms: To prove that they are not contradictory, that is, that a definite number of logical steps based upon them can never lead to contradictory results.

Hilbert’s 2nd problem arose from a principle that had only recently emerged in his thought, namely, that “mathematical existence is nothing other than consistency.”

In the decades that followed his lecture, Hilbert made this 2nd problem more explicit by developing “a formal system of explicit assumptions” (see Axiom and Axiomatic method) upon which he intended to base the methods of mathematical reasoning. He then stipulated that any such system must be shown to have these characteristics:

1. the assumptions should be "independent" of one another (see Independence)
2. the assumptions should be “consistent” (free of contradictions) (see Consistency)
3. the assumptions should be “complete” (represents all the truths of mathematics) (see Completeness)
4. there should be a procedure for deciding whether any statement expressed using the system is true or not) (see Decision problem and Undecidability)

Hilbert's 2nd problem is said by some to have been solved, albeit in a negative sense, by K. Gödel (see Hilbert problems and Gödel incompleteness theorem).

And yet, in his 2000 Distinguished Lecture to the Carnegie Mellon University School of Computer Science, Gregory Chaitin began his remarks as follows:

I’d like to make the outrageous claim, that has a little bit of truth, that actually all of this that’s happening now with the computer taking over the world, the digitalization of our society, of information in human society, you could say in a way is the result of a philosophical question that was raised by David Hilbert at the beginning of the century.

The philosophical question to which Chaitin was referring is the surmise at the heart of Hilbert’s 2nd problem. The title Chaitin gave to his lecture was “A Century of Controversy Over the Foundations of Mathematics.”

The question for us today is this:

How are we to view this century-old-and-more controversy?

“There can be no other way,” we are told, “than from our own position of understanding and sophistication…. [W]e have to try to appreciate the difference between our viewpoint and that of mathematicians centuries ago.” This article attempts to assist our appreciation of that difference.

Non-mathematical issues

As is the case for other, especially older programs and periods of mathematics, the history of Hilbert’s program was complicated by non-mathematical issues. Some authors were slow to publish their results; others published only selectively, leaving some important results to be published by students and successors. The works of still others, though published, were partially or completely ignored.

As a first example, consider the work of Galileo. His concerns about the “paradoxical” property of infinite sets are often mentioned in published discussions of the potentially infinite and the actually infinite. Yet, even today, doubts are expressed about whether or not Galileo had influence either on Cantor, the mathematician whose name is most often and most closely associated with the notion of iinfinite sets, or on any other mathematician.

Further, consider Gauss’ well-known comment about actual infinites in the work of Cantor and the latter’s response:

Gauss: I protest against the use of infinite magnitude as something completed, which in mathematics is never permissible. Infinity is merely a facon de parler, the real meaning being a limit which certain ratios approach indefinitely near, while others are permitted to increase without restriction.

Cantor: I answered [Gauss] thoroughly, and on this point did not accept the authority of Gauss, which I respect so highly in all other areas ...

There is some doubt that even today, 130 years after these words were written, that we really understand properly the meaning either of Gauss’ comment or of Cantor’s response.

Again, consider the work of Bolzano. His paper “Paradoxes of the Infinite” contains some remarkable results related to the theory of infinite sets:

• the word “set” appears here for the first time
• examples of 1-1 correspondences between the elements of an infinite set and the elements of a proper subset

Yet Bolzano himself never published these results. The paper itself was not published until 1851, three years after his death, by one of his students. Further, Cantor appears not to have become aware of Bolzano’s paper until 1882, some years after he began his own work on infinite sets, which was motivated by the Arithmetization of analysis. Nor did Cantor mention Bolzano's paper in his own work until 1883

A related historical anomaly is that while Bolzano both knew of and referred to Galileo’s work on the infinite, Cantor did neither.

As a final example, consider that Frege’s work “seems to have been largely ignored by his contemporaries.”

• Three [of six] reviews of the “revolutionary” Begriffsschrift,” including one by no less than Venn, show that their authors were either uninterested in Frege's innovations or had completely misunderstood them.
• The Grundlagen only received a single review, and that one was “a devastatingly hostile” one, by Cantor, whose ideas were [ironically] the closest to Frege's.
• Die Grundgesetze der Arithmetik … except for one review by Peano, was ignored by his contemporaries.

It was not until Russell acknowledged Frege’s work as the trailblazing foundation for the Principia that the greatness of his accomplishment was recognized. Russell himself contrasted the greatness of Frege’s contributions with the limited nature of his influence among his contemporaries as follows:

In spite of the epoch-making nature of [Frege's] discoveries, he remained wholly without recognition until I drew attention to him in 1903.

As a consequence of these and other non-mathematical issues, some mathematical results were achieved multiple times, albeit in slightly different forms or using somewhat different methods, by different authors.

Historical roots of Hilbert’s program

By about 1820, mathematicians had developed deductively a large part of analysis using the real numbers and their properties as a starting point.

During the 50 years that followed, in a program that came to be known as the Arithmetization of analysis, Bolzano, Cauchy, Weierstrass, Dedekind, Cantor, and others succeeded in “reducing” analysis to the arithmetic of natural numbers $\mathbb{N}$.

Dedekind himself expressed this as follows:

... every theorem of algebra and higher analysis, no matter how remote, can be expressed as a theorem about natural numbers, -- a declaration I have heard repeatedly from the lips of Dirichlet.

In the final three decades of the 19th century, efforts were underway to axiomatize the whole of mathematics.

It thus became clear that (with the aid of a certain amount of set theoretic and logical apparatus) the entire body of traditional pure mathematics could be constructed rigorously starting from the theory of natural numbers.

These efforts proceeded piecemeal and depended greatly on concurrent developments in logic. The major contributors were these:

• Cantor and Frege in set theory
• Dedekind and Peano in arithmetic
• Hilbert in geometry
• many others in abstract algebras (groups, rings, and fields)

Introduction of infinite sets

In mathematics, uses of infinity and the infinite (and great concerns about those uses) are as old as Grecian urns. Greek mathematicians followed Aristotle in dividing such uses into two major types, one called “potential infinity”, the other called “actual infinity.”

With respect to magnitudes:

a potential infinity was something endlessly extendible, and yet forever finite;

an actual infinity was something such as the number of points on a line.

Similarly, with respect to sets:

a potentially infinite set was, for example, a finite collection of numbers that can be enlarged as much as one wished

an actually infinite set was, for example, the complete collection of all such natural numbers

Ancient Greek mathematicians developed rigourous methods for using potential infinities. However, with the apparent exception of Archimedes noted below, they avoided using actual infinities. Important early examples of uses of infinity and the infinite include these:

• Euclid skirted the notion of the actually infinitely large in proving that the primes are potentially infinite. This is how he stated his theorem:

Prime numbers are more than any assigned magnitude of prime numbers.

• Archimedes, however, appears to have investigated actually infinite numbers of objects:

... certain objects, infinite in number, are "equal in magnitude" to others [implying] that not all such objects, infinite in number, are so equal. ... [thus] infinitely many objects [of] definite, and different magnitudes … are manipulated in a concrete way, apparently by something rather like a one-one correspondence...

Oresme, an early (12th century) mathematician, examined infinite sets using a method prescient of Cantor’s method of one-to-one correspondence. Oresme demonstrated that two actually infinite sets (the set of odd natural numbers and the set of all natural numbers) could be “different” and “unequal” and yet “equinumerous” with one another. He concluded that notions of equal, greater, and less do not apply to the infinite.

Mathematical induction, as a technique for proving the truth of propositions for an infinite (indefinitely large) number of values, was used for hundreds of years before any rigorous formulation of the method was made

Galileo produced the standard one-to-one correspondence between the positive integers and their squares, reminiscent of Oresme’s work. He termed this a “paradox” that results “unavoidably” from the property of infinite sets and concluded, alike with Oresme, that infinite sets are incomparable.

... the totality of all numbers is infinite, and that the number of squares is infinite.; neither is the number of squares less than the totality of all numbers, nor the latter greater than the former; and, finally, the attributes "equal", "greater", and "less" are not applicable to the infinite, but only to finite quantities.

As recently as 1831, Gauss himself argued against the actually infinite:

I protest against the use of infinite magnitude as something completed, which in mathematics is never permissible. Infinity is merely a facon de parler, the real meaning being a limit which certain ratios approach indefinitely near, while others are permitted to increase without restriction.

For the most part, however, mathematicians of the 19th and 20th centuries developed and readily took up methods for using actual infinities that were as rigorous as those the Greeks developed for potential infinities. Certainly Bolzano had no concerns about the “paradoxical” property of infinite sets. Indeed, his theories of mathematical infinity anticipated Cantor's theory of infinite sets. His contribution to the understanding of the nature of the infinite was threefold:

1. he defined the idea of a set

I call a set a collection where the order of its parts is irrelevant and where nothing essential is changed if only the order is changed.

2. he argued that the infinite set does exist

if the integers are a set, then arbitrarily large subsets of integers are subsets of the set of integers, which must itself be actually infinite

3. he gave examples to show that, unlike for finite sets, the elements of an infinite set could be put in 1-1 correspondence with elements of one of its proper subsets.

The actual infinite is said to have entered algebra in the 1850s in Dedekind’s work with quotient constructions for modular arithmetic:

[T]he whole system of infinitely many functions of a variable congruent to each other modulo p behaves here like a single concrete number in number theory.… The system of infinitely many incongruent classes—infinitely many, since the degree may grow indefinitely—corresponds to the series of whole numbers in number theory.

By 1872, procedures involving infinite sets were employed in constructions of irrational real numbers developed during the Arithmetization of analysis by Weierstrass, Dedekind, and Cantor. “Thus analysis [had been] not reduced simply to the theory of natural numbers, but to the theory of natural numbers together with the theory of infinite sets.”

The realization that (apparently) all the material needed for analysis could be constructed out of the natural numbers using set-theoretic means led to these new questions:

• What further could be said about set-theoretic procedures and assumptions of logic, both of which underlay these accounts of the real numbers?
• Do we have to take the natural numbers themselves as simply given, or can anything further be said about those numbers, perhaps by reducing them to something even more fundamental?

In the 1870s, however, the notions of set and class themselves appeared straightforward. Their highly problematic aspects did not become apparent until the various paradoxes of set theory and the theory of transfinite sets.

Early development of mathematical logic

The history of logic has been described, “with some slight degree of oversimplification,” as having three stages: (1) Greek logic, (2) Scholastic logic, and (3) mathematical logic. From ancient times through the first half of the 19th century, the state of logic was as follows:

• logic was understood to be “the laws of thought”
• the Aristotelian syllogism was the ultimate form of all reasoning
• the logic that a mathematician used did not affect the mathematics that she did

During the second half of the 19th century, the development of mathematical logic began with these two steps:

1. the algebraization of syllogistic logic
2. the development of the predicate calculus

Algebraization of syllogistic logic

The beginning of mathematical logic has been dated from the years in which Boole and De Morgan published their works on the algebraization of Aristotelian logic.

Whereas in [Greek and Scholastic logic] theorems were derived from ordinary language, [mathematical logic] proceeds in a contrary manner—it first constructs a purely formal system, and only later does it look for an interpretation in everyday speech.

Thus, with the advent of mathematical logic, the logic of the syllogism came to be treated as one interpretation of a calculus of logic.

Even before Boole’s work, important steps were taken towards the development of a calculus of logic.

• as early as 1830, Peacock suggested that the symbols for algebraic objects need not be understood only as numbers
• subsequently, De Morgan pursued the notion that the interpretations of symbols for algebraic operations were similarly arbitrary

More completely, De Morgan insisted on the purely formal or, as he put it, “symbolic” nature of algebra, the study of which has as it object “symbols and their laws of combination, giving a symbolic algebra which may hereafter become the grammar of a hundred distinct significant algebras.”

In 1847, in “a little book that De Morgan himself recognized as epoch-making,” Boole undertook the following:

• the goal: “to express traditional logic more perspicuously using the techniques of algebra” such that deduction becomes calculation
• the program: to develop an algebraic calculus and show that the doctrines of traditional logic can be expressed using this calculus.

In this early work, Boole extended De Morgan’s view about the formal nature of algebra by presenting the view that the essential character of the whole of mathematics is formal, somewhat as follows:

If any topic is presented in such a way that it consists of symbols and precise rules of operation upon these symbols, subject only to the requirement of inner consistency, this topic is part of mathematics.

In 1854, Boole published the completion of his efforts “to incorporate logic into mathematics by reducing it to a simple algebra, pointing out the analogy between algebraic symbols and those that represent logical forms, and beginning the algebra of logic that came to be called Boolean algebra.”

Boole eventually gave his uninterpreted calculus three interpretations, in terms of classes, of probabilities, and also of propositions. A modified version of the third interpretation of his calculus became modern propositional logic. This latter is today the lowest level of modern logic, but at the time and in effect, it was all of logic, because it was able to be used for Aristotelian syllogistic logic:

• it used symbols for statements rather than numbers
• it defined operations on statements rather than on numbers
• it defined deductions as equations and as the transformation of equations

No less than De Morgan himself praised Boole’s work as a remarkable proof that “the symbolic processes of algebra, invented as tools of numerical calculation, [are] competent to express every act of thought, and to furnish the grammar and dictionary of an all-containing system of logic.”

De Morgan’s praise overstated the capacity of Boole’s logic of propositions without quantification, in two ways:

1. it was insufficient to express important some statements of mathematics such as the law of mathematical induction, on which De Morgan himself had worked;
2. it was also inadequate to express some statements of ordinary language with a form such as, “If all horses are animals, then all heads of horses are heads of animals.”

However, if we understand De Morgan’s comment to be about a yet-to-be-developed logic with quantification, then we know that his optimism was not misplaced. Further, De Morgan himself extended Boole’s calculus with a law of duality that asserts for every proposition involving logical addition and multiplication, there is a corresponding proposition in which the words addition and multiplication are interchanged. More formally, we have De Morgan's formula:

If x and y are subsets of a set S, then

• the complement of the union of x and y is the intersection of the complements of x and y
• the complement of the intersection of x and y is the union of the complements of x and y

For three decades after Boole introduced his calculus in 1847, “most researchers interested in formal logic worked on extending and improving [his] system.”

Primary sources

• Bolzano, B. (1851). Paradoxien des Unendlichen (ed. by F. Pryhonsky), Leipzig: Reclam; [English translation by D. A. Steele, ‘’Paradoxes of the Infinite’’, London: Routledge & Kegan Paul, 1950].

• Dedekind, R. (1930-32). Gesammelte Mathematische Werke, Vols. 1-3, R. Fricke et al., eds., Vieweg.

• Hilbert, D. (1900). “Über den Zahlbegriff,” Jahresbericht der Deutschen, Mathematiker-Vereinigung 8, 180–184. (English translation in Ewald, W. (1996). From Kant to Hilbert: A source book in the foundations of mathematics, vol. 2, Oxford University Press.

• Hilbert, D.(1900). "Mathematische Probleme," Nachr. K. Ges. Wiss. Göttingen, Math.-Phys. Klasse (Göttinger Nachrichten) , 3 pp. 253–297 (Reprint: Archiv Math. Physik 3:1 (1901), 44-63; 213-237; also: Gesammelte Abh., dritter Band, Chelsea, 1965, pp. 290-329) Zbl 31.0068.03, URL: https://www.math.uni-bielefeld.de/~kersten/hilbert/rede.html, Accessed: 2015/06/03.

• Hilbert, D. (1902). "Mathematical problems," Bull. Amer. Math. Soc. , 8 pp. 437–479, MR1557926 Zbl 33.0976.07, (Reprint: ‘’Mathematical Developments Arising from Hilbert Problems’’, edited by Felix Brouder, American Mathematical Society, 1976), URL: http://aleph0.clarku.edu/~djoyce/hilbert/problems.html, Accessed: 2015/06/03.

References

• Bochenski, I M. (1956,[1961]) Formale Logik, North Holland, [English translation A History of Formal Logic, trans by Ivo Thomas, University of Notre Dame Press].

• Boyer, C.B. (1939). The Concepts of the Calculus. A Critical and Historical Discussion of the Derivative and the Integral, Columbia University Press, vii + 346 pages, URL: http://catalog.hathitrust.org/Record/000165835 Accessed: 2015/06/29.

• Boyer, C B. (1968) A History of Mathematics, John Wiley & Sons, URL: https://archive.org/stream/AHistoryOfMathematics/Boyer-AHistoryOfMathematics_djvu.txt, Accessed: 2015/06/29.

• Calude, C.S. and Chaitin, G.J. (1999). “Mathematics / Randomness everywhere, 22 July 1999,” Nature, Vol. 400, News and Views, pp. 319-320, URL: https://www.cs.auckland.ac.nz/~chaitin/nature.html, Accessed: 2015/06/19.

• Chaitin, G. (2000). “A Century of Controversy Over the Foundations of Mathematics,“ Journal Complexity -- Special Issue: Limits in mathematics and physics, Vol. 5, No. 5, May-June 2000, pp. 12-21, (Originally published in Finite Versus Infinite: Contributions to an Eternal Dilemma, Calude, C. S.; Paun, G. (eds.); Springer-Verlag, London, 2000, pp. 75–100), URL: http://www-personal.umich.edu/~twod/sof/assignments/chaitin.pdf Accessed 2015/05/30.

• Dasgupta, A. (2014). Set Theory: With an Introduction to Real Point Sets, DOI 10.1007/978-1-4614-8854-5__2, © Springer Science+Business Media New York 2014, URL: http://www.springer.com/us/book/9781461488538, Accessed: 2015/06/19.

• Ferreirós, J. (1996). “Hilbert, Logicism, and Mathematical Existence,” URL: http://personal.us.es/josef/HLME.pdf, Accessed: 2015/06/11.

• Gillies, D A. (1982). Frege, Dedekind, and Peano on the Foundations of Arithmetic, Van Gorcum & Comp., URL: http://www.thatmarcusfamily.org/philosophy/Course_Websites/Readings/Gillies%20-%20Frege%20Dedekind%20and%20Peano.pdf, Accessed: 2015/06/19.

• Grattan-Guinness, I. (1974). The rediscovery of the Cantor-Dedekind correspondence, Jahresbericht der Deutschen Mathematiker-Vereinigung 76 #2-3 (30 December 1974), 104-139, URL: http://catalog.hathitrust.org/Record/000165835 Accessed: 2015/06/30.

• Kanamori, A. (2012). “In Praise of Replacement” BSL.

• Kirschner, S. (2013). "Nicole Oresme", The Stanford Encyclopedia of Philosophy (Fall 2013 Edition), Edward N. Zalta (ed.), URL: http://plato.stanford.edu/archives/fall2013/entries/nicole-oresme/, Accessed: 2015/06/25.

• Netz, R. “Methods of Infinity,” The Archimedes Palimpsest, URL: http://archimedespalimpsest.org/about/scholarship/method-infinity.php, Accessed: 2015/06/22.

• Netz, R, Saito, K, and Tchernetska, N. (2001). “A new reading of Method Proposition 14 : preliminary evidence from the Archimedes palimpsest. I, SCIAMVS 2 (2001), 9-29.

• O'Connor, J J and Robertson, E F. (1996), “A history of set theory,” MacTutor History of Mathematics archive, URL:http://www-history.mcs.st-andrews.ac.uk/HistTopics/Beginnings_of_set_theory.html Accessed: 2015/06/10.

• O'Connor, J J and Robertson, E F. (1996), “Augustus De Morgan,” MacTutor History of Mathematics archive, URL: http://www-history.mcs.st-and.ac.uk/Biographies/DeMorgan.html Accessed: 2015/06/22.

• O’Connor, J J. and Robertson, E F. (1997) “An Overview of the History of Mathematics”, MacTutor History of Mathematics archive, URL: http://www-history.mcs.st-andrews.ac.uk/HistTopics/History_overview.html Accessed: 2015/06/18.

• O'Connor, J J and Robertson, E F. (2002), “Friedrich Ludwig Gottlob Frege,” MacTutor History of Mathematics archive, URL: :http://www-history.mcs.st-andrews.ac.uk/HistTopics/Infinity.html Accessed: 2015/06/10.

• O'Connor, J J and Robertson, E F. (2002), “Infinity,” MacTutor History of Mathematics archive, URL: :http://www-history.mcs.st-andrews.ac.uk/HistTopics/Infinity.html Accessed: 2015/06/10.

• O'Connor, J J and Robertson, E F. (2004), “George Boole,” MacTutor History of Mathematics archive, URL: http://www-history.mcs.st-and.ac.uk/Biographies/Boole.html Accessed: 2015/06/22.

• O'Connor, J J and Robertson, E F. (2005), “Bernard Bolzano,” MacTutor History of Mathematics archive, URL: http://www-history.mcs.st-and.ac.uk/Biographies/Bolzano.html Accessed: 2015/06/20.

• O'Connor, J J and Robertson, E F. (2015), “George Peacock,” MacTutor History of Mathematics archive, URL: http://www-history.mcs.st-and.ac.uk/Biographies/Peacock.html Accessed:2015/07/09.

• Pon, S. (2003). “Hilbert’s Second Problem: Foundations of Arithmetic,” Undergraduate paper for Math 163: History of Mathematics, U.C. San Diego, URL: https://www.math.ucsd.edu/programs/undergraduate/history_of_math_resource/history_papers/math_history_05.pdf, Accessed: 2015/06/09.

• Reck, E. (2012). "Dedekind's Contributions to the Foundations of Mathematics", The Stanford Encyclopedia of Philosophy (Winter 2012 Edition), Edward N. Zalta (ed.), URL: http://plato.stanford.edu/archives/win2012/entries/dedekind-foundations/. Accessed: 2015/06/20.

• Reck, E. (2013). "Frege, Dedekind, and the Origins of Logicism," History and Philosophy of Logic, Vol. 34, No. 3, pp. 242-265, URL: http://dx.doi.org/10.1080/01445340.2013.806397, Accessed: 2015/07/04.

• Renfro, D. (2014). “Did Galileo’s writings on nfinity influence Cantor?,” History of Science and Mathematics Stack Exchange, URL: http://hsm.stackexchange.com/questions/451/did-galileos-writings-on-infinity-influence-cantor, Accessed: 2014/06/24.

• Russell, B. (1945, [1972]) A History of Western Philosophy, Simon & Schuster, Inc.

• Spalt, D.D. (1990). "Die Unendlichkeiten bei Bernard Bolzano," Konzepte des mathematisch Unendlichen im 19. Jahrhundert, Göttingen, 189-218.

• Waterhouse, W.C. (1979). “Gauss on infinity,” Historia Math. Vol. 6, Issue 4, November 1979, pp. 430-436.