Editing Gödel's incompleteness theorems (section)

=== Undecidable statements provable in larger systems ===

These are natural mathematical equivalents of the Gödel "true but undecidable" sentence. They can be proved in a larger system which is generally accepted as a valid form of reasoning, but are undecidable in a more limited system such as Peano Arithmetic.

In 1977, [[Jeff Paris (mathematician)|Paris]] and [[Leo Harrington|Harrington]] proved that the [[Paris–Harrington theorem|Paris&ndash;Harrington principle]], a version of the infinite [[Ramsey theorem]], is undecidable in (first-order) [[Peano arithmetic]], but can be proved in the stronger system of [[second-order arithmetic]]. Kirby and Paris later showed that [[Goodstein's theorem]], a statement about sequences of natural numbers somewhat simpler than the Paris&ndash;Harrington principle, is also undecidable in Peano arithmetic.

[[Kruskal's tree theorem]], which has applications in computer science, is also undecidable from Peano arithmetic but provable in set theory. In fact Kruskal's tree theorem (or its finite form) is undecidable in a much stronger system ATR<sub>0</sub> codifying the principles acceptable based on a philosophy of mathematics called [[impredicativity|predicativism]].<ref name="Simpson2009">S. G. Simpson, ''Subsystems of Second-Order Arithmetic'' (2009). Perspectives in Logic, ISBN 9780521884396.</ref>  The related but more general [[graph minor theorem]] (2003) has consequences for [[computational complexity theory]].