Kanamori–McAloon theorem

In mathematical logic, the Kanamori–McAloon theorem, due to Template:Harvtxt, 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\to \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,\dots ,m-1\}{]}^n\to \mathbb{N}$, there exists a set $H\in [\{0,1,\dots ,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

• Template:Citation

Template:Mathlogic-stub