Hindman’s theorem for sums along the full binary tree, $$\Sigma ^0_2$$-induction and the Pigeonhole principle for trees
Copyright policy )Hindman’s theorem for sums along the full binary tree, $$\Sigma ^0_2$$-induction and the Pigeonhole principle for trees
AbstractWe formulate a restriction of Hindman’s Finite Sums Theorem in which monochromaticity is required only for sums corresponding to rooted finite paths in the full binary tree. We show that the resulting principle is equivalent to$$\Sigma ^0_2$$Σ20-induction over$$\mathsf {RCA}_0$$RCA0. The proof uses the equivalence of this Hindman-type theorem with the Pigeonhole Principle for trees$${\mathsf {T}\,}{\mathsf {T}}^1$$TT1with an extra condition on the solution tree.
- Sapienza University of Rome Italy
- Roma Tre University Italy
Applications of computability and recursion theory, Hindman's theorem, Reverse mathematics; Hindman's theorem; Pigeonhole principle; induction, Ramsey theory, reverse mathematics, Pigeonhole principle, Foundations of classical theories (including reverse mathematics), Second- and higher-order arithmetic and fragments, induction
Applications of computability and recursion theory, Hindman's theorem, Reverse mathematics; Hindman's theorem; Pigeonhole principle; induction, Ramsey theory, reverse mathematics, Pigeonhole principle, Foundations of classical theories (including reverse mathematics), Second- and higher-order arithmetic and fragments, induction
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!