List of long mathematical proofs

This is a list of unusually long mathematical proofs. Such proofs often use computational proof methods and may be considered non-surveyable.

As of 2011, the longest mathematical proof, measured by number of published journal pages, is the classification of finite simple groups with well over 10,000 pages. There are several proofs that would be far longer than this if the details of the computer calculations they depend on were published in full.

Long proofs

The length of unusually long proofs has increased with time. As a rough rule of thumb, 100 pages in 1900, or 200 pages in 1950, or 500 pages in 2000 is unusually long for a proof.

Long computer calculations

There are many mathematical theorems that have been checked by long computer calculations. If these were written out as proofs, many would be far longer than most of the proofs above. There is not really a clear distinction between computer calculations and proofs, as several of the proofs above, such as the 4-color theorem and the Kepler conjecture, use long computer calculations as well as many pages of mathematical argument. For the computer calculations in this section, the mathematical arguments are only a few pages long, and the length is due to long but routine calculations. Some typical examples of such theorems include:

Long proofs in mathematical logic

Kurt Gödel showed how to find explicit examples of statements in formal systems that are provable in that system but whose shortest proof is absurdly long. For example, the statement:

"This statement cannot be proved in Peano arithmetic in less than a googolplex symbols"

is provable in Peano arithmetic but the shortest proof has at least a googolplex symbols. It has a short proof in a more powerful system: in fact, it is easily provable in Peano arithmetic together with the statement that Peano arithmetic is consistent (which cannot be proved in Peano arithmetic by Gödel's incompleteness theorem).

In this argument, Peano arithmetic can be replaced by any more powerful consistent system, and a googolplex can be replaced by any number that can be described concisely in the system.

Harvey Friedman found some explicit natural examples of this phenomenon, giving some explicit statements in Peano arithmetic and other formal systems whose shortest proofs are ridiculously long (Smoryński 1982). For example, the statement

"there is an integer n such that if there is a sequence of rooted trees T1, T2, ..., Tn such that Tk has at most k+10 vertices, then some tree can be homeomorphically embedded in a later one"

is provable in Peano arithmetic, but the shortest proof has length at least 10002, where 02 = 1 and n+12 = 2(n2) (tetrational growth). The statement is a special case of Kruskal's theorem and has a short proof in second order arithmetic.

See also

References

  1. ^ Lamb, Evelyn (26 May 2016). "Two-hundred-terabyte maths proof is largest ever: A computer cracks the Boolean Pythagorean triples problem — but is it really maths?". Nature.
  2. ^ Heule, Marijn J. H. (2017). "Schur Number Five". arXiv:1711.08076 [cs.LO].

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.