A strengthened, combinatorially natural version of the finite Ramsey theorem is true but cannot be proved within Peano arithmetic. Proved by Jeff Paris and Leo Harrington, it was the first widely publicized example of a mathematically natural statement, rather than one constructed purely for logical purposes, that is independent of Peano arithmetic.
Facts
StatementThe theorem holds that a strengthened form of the finite Ramsey theorem, one true statement of Ramsey theory expressible in the language of Peano arithmetic, cannot be proved inside Peano arithmetic itself, making it a natural example of a true arithmetical statement independent of that system. 1 Proof YearProved by Jeff Paris and Leo Harrington in 1977. Connections
Sources
1. Paris-Harrington Theorem (Wikipedia)
Wikimedia Foundationlead paragraph, first sentence
In mathematical logic, the Paris-Harrington theorem states that a certain claim in Ramsey theory, namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system.
body text, attribution sentence
Roughly speaking, Jeff Paris and Leo Harrington (1977) showed that the strengthened finite Ramsey theorem is unprovable in Peano arithmetic
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.