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 within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, 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 nearly u ...
, similar to that of the
Paris–Harrington theorem In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This has been described by some (suc ...
. 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 mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
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 maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ran ...
element of s. Let n denote the set of all ''n''-element
subsets In mathematics, 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 subset of ...
of X. A function f: n\rightarrow\mathbb where X\subseteq\mathbb is said to be ''regressive'' if f(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 combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This has been described by some (suc ...
*
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'' eventually terminates at 0. Kirby and Paris showed that it is unprovable in Pea ...
*
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. History The theorem was conjectured by Andrew Vázsonyi and proved by ...


References

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