Kanamori–McAloon theorem

In mathematical logic, the Kanamori–McAloon theorem, due to Kanamori & McAloon (1987), gives an example of an incompleteness in Peano arithmetic, similar to that of the Paris–Harrington theorem. They showed that a certain finitistic theorem in Ramsey theory is not provable in Peano arithmetic (PA).

Statement

[edit]

Given a set of non-negative integers, let denote the minimum element of . Let denote the set of all n-element subsets of .

A function where is said to be regressive if for all not containing 0.

The Kanamori–McAloon theorem states that the following proposition, denoted by in the original reference, is not provable in PA:

For every , there exists an such that for all regressive , there exists a set such that for all with , we have .

See also

[edit]

References

[edit]
  • Kanamori, Akihiro; McAloon, Kenneth (1987), "On Gödel incompleteness and finite combinatorics", Annals of Pure and Applied Logic, 33 (1): 23–41, doi:10.1016/0168-0072(87)90074-1, ISSN 0168-0072, MR 0870685