Reverse mathematics and initial intervals (Q386152)

The authors explore the logical strength of several characterizations of countable partial orders in the framework of reverse mathematics. Two central results address work of \textit{R. Bonnet} [Colloq. Math. Soc. Janos Bolyai 10, 189--198 (1975; Zbl 0321.06003)]. An initial interval (i.e.~downward closed subset) of a partial order is an \textsl{ideal} if every pair of elements has a common upper bound in the interval. An \textsl{antichain} is a set of pairwise incomparable elements. Bonnet showed that a partial order has no infinite antichains if and only if every initial interval is a finite union of ideals. The authors prove that the countable version of the forward direction of Bonnet's biconditional is provably equivalent to ACA\(_0\) over RCA\(_0\). They also show that the converse is provable in WKL\(_0\) and not provable in RCA\(_0\). The following countable restriction of another result of Bonnet is also analyzed: A countable partial order is scattered (i.e.~contains no subset order isomorphic to the rationals) and has no infinite antichains if and only if it has countably many initial intervals. The forward direction of this biconditional is equivalent to ATR\(_0\) over ACA\(_0\), while the converse is provable in WKL\(_0\) and not provable in RCA\(_0\). The authors also examine a version of a result of \textit{P. Erdős} and \textit{A. Tarski} [Ann. Math. (2) 44, 315--329 (1943; Zbl 0060.12602)]. They show that ACA\(_0\) is equivalent to: If a partial order contains no infinite pairwise incompatible sets then it has no arbitrarily large pairwise incompatible sets. The final section of the paper mentions initial drafts of related work due to Igusa and due to Bienvenue, Patey, and Shafer.