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 ⊆ N {\displaystyle s\subseteq \mathbb {N} } of non-negative integers, let min ( s ) {\displaystyle \min(s)} denote the minimum element of s {\displaystyle s} . Let [ X ] n {\displaystyle [X]^{n}} denote the set of all n-element subsets of X {\displaystyle X} . A function f : [ X ] n → N {\displaystyle f:[X]^{n}\rightarrow \mathbb {N} } where X ⊆ N {\displaystyle X\subseteq \mathbb {N} } is said to be regressive if f ( s ) < min ( s ) {\displaystyle f(s)<\min(s)} for all s {\displaystyle s} not containing 0. The Kanamori–McAloon theorem states that the following proposition, denoted by ( ∗ ) {\displaystyle (*)} in the original reference, is not provable in PA:
For every n , k ∈ N {\displaystyle n,k\in \mathbb {N} } , there exists an m ∈ N {\displaystyle m\in \mathbb {N} } such that for all regressive f : [ { 0 , 1 , … , m − 1 } ] n → N {\displaystyle f:[\{0,1,\ldots ,m-1\}]^{n}\rightarrow \mathbb {N} } , there exists a set H ∈ [ { 0 , 1 , … , m − 1 } ] k {\displaystyle H\in [\{0,1,\ldots ,m-1\}]^{k}} such that for all s , t ∈ [ H ] n {\displaystyle s,t\in [H]^{n}} with min ( s ) = min ( t ) {\displaystyle \min(s)=\min(t)} , we have f ( s ) = f ( t ) {\displaystyle 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