Kanamori–McAloon Theorem
   HOME

TheInfoList



Click Here for Items Related To - Kanamori–McAloon Theorem
OR:
Kanamori–McAloon Theorem on:   [Wikipedia]   [Google]   [Amazon]

In
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, the Kanamori–McAloon theorem, due to , gives an example of an incompleteness in
Peano arithmetic In mathematical logic, the Peano axioms (, ), also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nea ...
, similar to that of the
Paris–Harrington theorem In mathematical logic, the Paris–Harrington theorem states that a certain claim in Ramsey theory, namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system. That Ramsey-theoretic clai ...
. They showed that a certain finitistic theorem in
Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...
is not provable in Peano arithmetic (PA).


Statement

Given a set s\subseteq\mathbb of non-negative integers, let \min(s) denote the
minimum In mathematical analysis, the maximum and minimum of a function are, respectively, the greatest and least value taken by the function. Known generically as extremum, they may be defined either within a given range (the ''local'' or ''relative ...
element of s. Let n denote the set of all ''n''-element
subsets In mathematics, a set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subse ...
of X. A function f: n\rightarrow\mathbb where X\subseteq\mathbb 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, there exists an m\in\mathbb such that for all regressive f: n\rightarrow\mathbb, there exists a set H\in k such that for all s,t\in n with \min(s)=\min(t), we have f(s)=f(t).


See also

*
Paris–Harrington theorem In mathematical logic, the Paris–Harrington theorem states that a certain claim in Ramsey theory, namely the strengthened finite Ramsey theorem, which is expressible in Peano arithmetic, is not provable in this system. That Ramsey-theoretic clai ...
*
Goodstein's theorem In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence (as defined below) eventually terminates at 0. Laurence Kirby and Jeff Paris showed ...
*
Kruskal's tree theorem In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding. A finitary application of the theorem gives the existence of the fast-g ...


References

* Independence results Theorems in the foundations of mathematics {{mathlogic-stub