The Reverse Mathematics of CAC for trees

MaRDI QIDQ6400826zbMATH OpenFDO

Authors Julien Cervelle, William Gaudelier, Ludovic Patey

Publication date 1 June 2022

Abstract: CAC for trees is the statement asserting that any infinite subtree of $mathbb{N}^{<mathbbN}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical viewpoint. We prove that TAC for trees is robust, that is, there exist several characterizations, some of which already appear in the literature, namely, the tree antichain theorem (TCAC) introduced by Conidis, and the statement SHER introduced by Dorais et al. We show that CAC for trees is computationally very weak, in that it admits probabilistic solutions.

This page was built for publication: The Reverse Mathematics of CAC for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400826)