Hilbert's twenty-fourth problem

Last updated

Hilbert's twenty-fourth problem is a mathematical problem that was not published as part of the list of 23 problems (known as Hilbert's problems) but was included in David Hilbert's original notes. The problem asks for a criterion of simplicity in mathematical proofs and the development of a proof theory with the power to prove that a given proof is the simplest possible. [1]

The 24th problem was rediscovered by German historian Rüdiger Thiele in 2000, noting that Hilbert did not include the 24th problem in the lecture presenting Hilbert's problems or any published texts. Hilbert's friends and fellow mathematicians Adolf Hurwitz and Hermann Minkowski were closely involved in the project but did not have any knowledge of this problem.

This is the full text from Hilbert's notes given in Rüdiger Thiele's paper. The section was translated by Rüdiger Thiele. [1] : 2 

The 24th problem in my Paris lecture was to be: Criteria of simplicity, or proof of the greatest simplicity of certain proofs. Develop a theory of the method of proof in mathematics in general. Under a given set of conditions there can be but one simplest proof. Quite generally, if there are two proofs for a theorem, you must keep going until you have derived each from the other, or until it becomes quite evident what variant conditions (and aids) have been used in the two proofs. Given two routes, it is not right to take either of these two or to look for a third; it is necessary to investigate the area lying between the two routes. Attempts at judging the simplicity of a proof are in my examination of syzygies and syzygies [Hilbert misspelled the word syzygies] between syzygies (see Hilbert 42, lectures XXXII–XXXIX). The use or the knowledge of a syzygy simplifies in an essential way a proof that a certain identity is true. Because any process of addition [is] an application of the commutative law of addition etc. [and because] this always corresponds to geometric theorems or logical conclusions, one can count these [processes], and, for instance, in proving certain theorems of elementary geometry (the Pythagoras theorem, [theorems] on remarkable points of triangles), one can very well decide which of the proofs is the simplest. [Author's note: Part of the last sentence is not only barely legible in Hilbert's notebook but also grammatically incorrect. Corrections and insertions that Hilbert made in this entry show that he wrote down the problem in haste.]

— David Hilbert, Mathematische Notizbücher

In 2002, Thiele and Larry Wos published an article on Hilbert's twenty-fourth problem with a discussion about its relation to various issues in automated reasoning, logic, and mathematics. [2]

Related Research Articles

Automated theorem proving is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a major motivating factor for the development of computer science.

<span class="mw-page-title-main">David Hilbert</span> German mathematician (1862–1943)

David Hilbert was a German mathematician and philosopher of mathematics and one of the most influential mathematicians of his time.

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.

<span class="mw-page-title-main">Hilbert's problems</span> 23 mathematical problems stated in 1900

Hilbert's problems are 23 problems in mathematics published by German mathematician David Hilbert in 1900. They were all unsolved at the time, and several proved to be very influential for 20th-century mathematics. Hilbert presented ten of the problems at the Paris conference of the International Congress of Mathematicians, speaking on August 8 at the Sorbonne. The complete list of 23 problems was published later, in English translation in 1902 by Mary Frances Winston Newson in the Bulletin of the American Mathematical Society. Earlier publications appeared in Archiv der Mathematik und Physik.

Proof theory is a major branch of mathematical logic and theoretical computer science within which proofs are treated as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of a given logical system. Consequently, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature.

<span class="mw-page-title-main">Metamathematics</span> Study of mathematics itself

Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics owes itself to David Hilbert's attempt to secure the foundations of mathematics in the early part of the 20th century. Metamathematics provides "a rigorous mathematical technique for investigating a great variety of foundation problems for mathematics and logic". An important feature of metamathematics is its emphasis on differentiating between reasoning from inside a system and from outside a system. An informal illustration of this is categorizing the proposition "2+2=4" as belonging to mathematics while categorizing the proposition "'2+2=4' is valid" as belonging to metamathematics.

OTTER is an automated theorem prover developed by William McCune at Argonne National Laboratory in Illinois. Otter was the first widely distributed, high-performance theorem prover for first-order logic, and it pioneered a number of important implementation techniques. Otter is an acronym for Organized Techniques for Theorem-proving and Effective Research.

In mathematics, Hilbert's program, formulated by German mathematician David Hilbert in the early 1920s, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies. As a solution, Hilbert proposed to ground all existing theories to a finite, complete set of axioms, and provide a proof that these axioms were consistent. Hilbert proposed that the consistency of more complicated systems, such as real analysis, could be proven in terms of simpler systems. Ultimately, the consistency of all of mathematics could be reduced to basic arithmetic.

<span class="mw-page-title-main">Proof assistant</span> Software tool to assist with the development of formal proofs by human–machine collaboration

In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by human–machine collaboration. This involves some sort of interactive proof editor, or other interface, with which a human can guide the search for proofs, the details of which are stored in, and some steps provided by, a computer.

In mathematics, Hilbert's syzygy theorem is one of the three fundamental theorems about polynomial rings over fields, first proved by David Hilbert in 1890, that were introduced for solving important open questions in invariant theory, and are at the basis of modern algebraic geometry. The two other theorems are Hilbert's basis theorem, which asserts that all ideals of polynomial rings over a field are finitely generated, and Hilbert's Nullstellensatz, which establishes a bijective correspondence between affine algebraic varieties and prime ideals of polynomial rings.

Hilbert's twenty-second problem is the penultimate entry in the celebrated list of 23 Hilbert problems compiled in 1900 by David Hilbert. It entails the uniformization of analytic relations by means of automorphic functions.

In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer programs that allow computers to reason completely, or nearly completely, automatically. Although automated reasoning is considered a sub-field of artificial intelligence, it also has connections with theoretical computer science and philosophy.

Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction, as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε0", is neither weaker nor stronger than the system of Peano axioms. Gentzen argued that it avoids the questionable modes of inference contained in Peano arithmetic and that its consistency is therefore less controversial.

<span class="mw-page-title-main">Mutilated chessboard problem</span> On domino tiling after removing two corners

The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks:

Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?

In linear algebra, a linear relation, or simply relation, between elements of a vector space or a module is a linear equation that has these elements as a solution.

The history of the Church–Turing thesis ("thesis") involves the history of the development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, functions whose values are algorithmically computable. It is an important topic in modern mathematical theory and computer science, particularly associated with the work of Alonzo Church and Alan Turing.

<span class="mw-page-title-main">Brouwer–Hilbert controversy</span> Foundational controversy in twentieth-century mathematics

The Brouwer–Hilbert controversy was a debate in twentieth-century mathematics over fundamental questions about the consistency of axioms and the role of semantics and syntax in mathematics. L. E. J. Brouwer, a proponent of the constructivist school of intuitionism, opposed David Hilbert, a proponent of formalism. Much of the controversy took place while both were involved with Mathematische Annalen, the leading mathematical journal of the time, with Hilbert as editor-in-chief and Brouwer as a member of its editorial board. In 1928, Hilbert had Brouwer removed from the editorial board of Mathematische Annalen.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable.

Lawrence T. Wos (1930–2020) was an American mathematician, a researcher in the Mathematics and Computer Science Division of Argonne National Laboratory.

<span class="mw-page-title-main">Rüdiger Thiele</span>

Rolf-Rüdiger Thiele is a German mathematician and historian of mathematics, known for his historical research on Hilbert's twenty-fourth problem.

References

  1. 1 2 Thiele, Rüdiger (January 2003). "Hilbert's Twenty-Fourth Problem" (PDF). The American Mathematical Monthly. 110 (1). Mathematical Association of America: 1–24. doi:10.1080/00029890.2003.11919933.
  2. ↑ Thiele, Rüdiger; Wos, Larry (2002). "Hilbert's Twenty-Fourth Problem". Journal of Automated Reasoning. 29 (1): 67–89. doi:10.1023/A:1020537107897. ISSN   0168-7433.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.