We 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) -induction over RCA(0). The proof uses the equivalence of this Hindman-type theorem with the Pigeonhole Principle for trees T T-1 with an extra condition on the solution tree.
Hindman's theorem for sums along the full binary tree, Sigma02-induction and the Pigeonhole principle for trees / Carlucci, Lorenzo; Tavernelli, Daniele. - In: ARCHIVE FOR MATHEMATICAL LOGIC. - ISSN 0933-5846. - 61:5-6(2022), pp. 827-839. [10.1007/s00153-021-00814-2]
Hindman's theorem for sums along the full binary tree, Sigma02-induction and the Pigeonhole principle for trees
Lorenzo Carlucci
;Daniele Tavernelli
2022
Abstract
We 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) -induction over RCA(0). The proof uses the equivalence of this Hindman-type theorem with the Pigeonhole Principle for trees T T-1 with an extra condition on the solution tree.| File | Dimensione | Formato | |
|---|---|---|---|
|
Carlucci_Hindman’s-theorem_2022.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
306.12 kB
Formato
Adobe PDF
|
306.12 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
