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