论文标题
树木CAC的相反数学
The Reverse Mathematics of CAC for trees
论文作者
论文摘要
树木的CAC声称，$ \ Mathbb {n}^{<\ Mathbb {n}} $的任何无限子树都具有无限的路径或无限的抗小节。在本文中，我们从反向数学观点研究了该定理的计算强度。我们证明，树木的TAC是强大的，也就是说，存在几种特征，其中一些已经出现在文献中，即Comidis引入的Trees Antichain Theorem（TCAC），以及Dorais等人介绍的声明。我们表明，树木的CAC在计算上非常弱，因为它可以接受概率解决方案。
CAC for trees is the statement asserting that any infinite subtree of $\mathbb{N}^{<\mathbb{N}}$ 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.
