Namespaces
Variants
Actions

Difference between revisions of "Hilbert 2nd problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m
m
Line 44: Line 44:
 
====Introduction of infinite sets====
 
====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:<ref>Netz</ref>
+
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.”<ref>For related modern mathematical notions, see [[Abstraction, mathematical]], [[Abstraction of actual infinity]], [[Abstraction of potential realizability]], and [[Infinity]]</ref>
 +
 
 +
With respect to magnitudes:<ref>Netz</ref>
 
::a potential infinity was something endlessly extendible, and yet forever finite;
 
::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.
 
::an actual infinity was something such as the number of points on a line.
Line 50: Line 52:
 
::a potentially infinite set was, for example, a finite collection of numbers that can be enlarged as much as one wished
 
::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
 
::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.<ref>Netz</ref>
 
Important early examples of uses of infinity and the infinite include these:
 
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:<ref>Spalt cited in O'Connor and Robertson (2002)</ref>
 
* Euclid skirted the notion of the actually infinitely large in proving that the primes are potentially infinite. This is how he stated his theorem:<ref>Spalt cited in O'Connor and Robertson (2002)</ref>
Line 56: Line 58:
 
* Archimedes, however, appears to have investigated actually infinite numbers of objects:<ref>Netz, Saito, and Tchernetska cited in O'Connor and Robertson (2002)</ref>
 
* Archimedes, however, appears to have investigated actually infinite numbers of objects:<ref>Netz, Saito, and Tchernetska cited in O'Connor and Robertson (2002)</ref>
 
::... 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...
 
::... 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.<ref>Kirschner 2.6 Mathematics</ref>
 
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<ref>O'Connor and Robertson, (2002)</ref>
 
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<ref>O'Connor and Robertson, (2002)</ref>
 
+
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.<ref>O'Connor and Robertson, (2002). The property that an infinite set can be put into one-to-one correspondence with a proper subset of itself is today known as the [[Hilbert infinite hotel]] property.</ref>
Galileo produced the standard one-to-one correspondence between the positive integers and their squares, but termed this a “paradox” that results “unavoidably” from what we know today as the [[Hilbert infinite hotel]] property of infinite sets<ref>O'Connor and Robertson, (2002)</ref>
 
 
::... 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.
 
::... 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, however, Gauss himself argued against the “actually” infinite:<ref>Waterhouse cited in O’Connor and Robertson (2002)</ref>
+
As recently as 1831, however, Gauss himself argued against the actually infinite:<ref>Waterhouse cited in O’Connor and Robertson (2002)</ref>
::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.
+
::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 methods for using actual infinities that were as rigorous as those the Greeks developed for potential infinities.<ref>Netz</ref>
Bolzano had no such 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:<ref>Bolzano cited in O’Connor and Robertson (1996) (2002) (2005)</ref>
+
Certainly Bolzano had no such 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:<ref>Bolzano cited in O’Connor and Robertson (1996) (2002) (2005)</ref>
 
 
 
:1. he defined the idea of a set
 
: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.
+
:::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
 
: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
+
:::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.
 
: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.
  
Line 110: Line 110:
  
 
* 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.
 
* 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.
 +
 +
* 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
 
* Netz, R. “Methods of Infinity,” ''The Archimedes Palimpsest'', URL: http://archimedespalimpsest.org/about/scholarship/method-infinity.php

Revision as of 21:04, 25 June 2015

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:[1]

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.

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:[2][3]

  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:[4]

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[5], “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.

19th century 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:[6]

... 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.[7]

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.”[8]

With respect to magnitudes:[9]

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.[10] 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:[11]
Prime numbers are more than any assigned magnitude of prime numbers.
  • Archimedes, however, appears to have investigated actually infinite numbers of objects:[12]
... 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.[13] 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[14] 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.[15]

... 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, however, Gauss himself argued against the actually infinite:[16]

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 methods for using actual infinities that were as rigorous as those the Greeks developed for potential infinities.[17] Certainly Bolzano had no such 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:[18]

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.

By 1872, procedures involving infinite sets had employed both in constructions of irrational real numbers (Weierstrass, Dedekind, and Cantor) and also in equally important constructions of rational numbers and of integers.

Reflection on all of this led to an acceptance of infinite sets. Further, it led to new questions arising from the realization that (apparently) all the material needed for analysis, including all rational and irrational numbers, could be constructed out of the natural numbers using set-theoretic means:[19]

  • What further could be said about the relevant set-theoretic procedures and the assumptions of logic that 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?

Developments in logic

Axiomatization of arithmetic

Developments in set theory

Axiomatization of geometry

Development of Hilbert’s program

Subsequent variants and reinterpretations of Hilbert’s program

Notes

  1. Hilbert (1902)
  2. Calude and Chaitin
  3. Pon
  4. Chaitin (2000), p. 12.
  5. O’Connor and Robertson (1997)
  6. Dedekind (1888) cited in Gillies p. 8
  7. Dasgupta p. 29
  8. For related modern mathematical notions, see Abstraction, mathematical, Abstraction of actual infinity, Abstraction of potential realizability, and Infinity
  9. Netz
  10. Netz
  11. Spalt cited in O'Connor and Robertson (2002)
  12. Netz, Saito, and Tchernetska cited in O'Connor and Robertson (2002)
  13. Kirschner 2.6 Mathematics
  14. O'Connor and Robertson, (2002)
  15. O'Connor and Robertson, (2002). The property that an infinite set can be put into one-to-one correspondence with a proper subset of itself is today known as the Hilbert infinite hotel property.
  16. Waterhouse cited in O’Connor and Robertson (2002)
  17. Netz
  18. Bolzano cited in O’Connor and Robertson (1996) (2002) (2005)
  19. Reck, 2.2 The Foundations of Arithmetic

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].
  • Hilbert, D. "Mathematische Probleme" Nachr. K. Ges. Wiss. Göttingen, Math.-Phys. Klasse (Göttinger Nachrichten) , 3 (1900) 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. "Mathematical problems" Bull. Amer. Math. Soc. , 8 (1902) 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

  • 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.
  • 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.
  • 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.
How to Cite This Entry:
Hilbert 2nd problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hilbert_2nd_problem&oldid=36516