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

Given a set $s\subseteq \mathbb {N}$ of non-negative integers, let $\min(s)$ denote the minimum element of $s$. Let $[X]^{n}$ denote the set of all n-element subsets of $X$.

A function $f:[X]^{n}\rightarrow \mathbb {N}$ where $X\subseteq \mathbb {N}$ is said to be regressive if $f(s)<\min(s)$ for all $s$ 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 $n,k\in \mathbb {N}$, there exists an $m\in \mathbb {N}$ such that for all regressive $f:[\{0,1,\ldots ,m-1\}]^{n}\rightarrow \mathbb {N}$, there exists a set $H\in [\{0,1,\ldots ,m-1\}]^{k}$ such that for all $s,t\in [H]^{n}$ with $\min(s)=\min(t)$, we have $f(s)=f(t)$.

See also

• Paris–Harrington theorem
• Goodstein's theorem
• Kruskal's tree theorem

References

• 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