A computable analysis of variable words theorems

Abstract : The Carlson-Simpson lemma is a combinatorial statement occurring in the proof of the Dual Ramsey theorem. Formulated in terms of variable words, it informally asserts that given any finite coloring of the strings, there is an infinite sequence with infinitely many variables such that for every valuation, some specific set of initial segments is homogeneous. Friedman, Simpson, and Montalban asked about its reverse mathematical strength. We study the computability-theoretic properties and the reverse mathematics of this statement, and relate it to the finite union theorem. In particular, we prove the Ordered Variable word for binary strings in ACA 0 .
Type de document :
Article dans une revue
Proceedings of the American Mathematical Society, American Mathematical Society, In press, 〈10.1090/proc/14269〉
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-01888789
Contributeur : Ludovic Patey <>
Soumis le : mardi 9 octobre 2018 - 15:14:47
Dernière modification le : mercredi 10 octobre 2018 - 01:23:11

Fichier

variable-words.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Lu Liu, Benoit Monin, Ludovic Patey. A computable analysis of variable words theorems. Proceedings of the American Mathematical Society, American Mathematical Society, In press, 〈10.1090/proc/14269〉. 〈hal-01888789〉

Partager

Métriques

Consultations de la notice

28

Téléchargements de fichiers

7