Kanamori–McAloon theorem explained

In mathematical logic, the Kanamori–McAloon theorem, due to, 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 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 → N} where X\subseteq 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 N , there exists an m\in N such that for all regressive f:[\{ 0 , 1 ,\ldots,m -1 \}] ^{n → 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