Namespaces
Variants
Actions

Difference between revisions of "Hilbert 2nd problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m
Line 5: Line 5:
 
::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.''
 
::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 later made this 2nd problem more explicit, first, by developing “a formal system of explicit assumptions” upon which he intended to base the methods of mathematical reasoning and, second, by stipulating that any such system must be shown to have these three characteristics:<ref>Calude and Chaitin (1999)</ref>
+
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:<ref>Calude and Chaitin (1999)</ref><ref>Pon</ref>
  
# it should be “consistent” (free of contradictions) (see [[Consistency]])
+
# the assumptions should be "independent" of one another (see [[Independence of an axiom system|Independence]])
# it should be “complete” (represents all the truth) (see [[Completeness (in logic)|Completeness]])
+
# the assumptions should be “consistent” (free of contradictions) (see [[Consistency]])
# it should be “decidable” (has a "procedure" for deciding whether anything expressed using the system is true or not) (see [[Decision problem]] and [[Undecidability]])
+
# the assumptions should be “complete” (represents all the truths of mathematics) (see [[Completeness (in logic)|Completeness]])
 +
# 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]]).
 
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]]).
Line 43: Line 44:
 
* Chaitin, G, “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.
 
* Chaitin, G, “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.
  
* [[Hilbert problems]], ''Encyclopedia of Mathematics''.
+
* 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.

Revision as of 16:44, 9 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.

Chaitin titled his lecture “A Century of Controversy Over the Foundations of Mathematics.” This article presents a brief history of this ongoing controversy.

19th century roots of Hilbert’s program

Development of Hilbert’s program

Subsequent variants and reinterpretations of Hilbert’s program

Notes

  1. Hilbert (1902)
  2. Calude and Chaitin (1999)
  3. Pon
  4. Chaitin (2000), p. 12.

Primary sources

  • 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

  • Calude, C.S. and Chaitin, G.J. “Mathematics / Randomness everywhere, 22 July 1999,” ‘’Nature,’’ Vol. 400, News and Views, pp. 319-320.
  • Chaitin, G, “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.
How to Cite This Entry:
Hilbert 2nd problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hilbert_2nd_problem&oldid=36458