Reverse mathematics and initial intervals

DOI10.1016/J.APAL.2013.11.002MaRDI QIDQ386152zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emanuele Frittaion, Alberto Marcone

Publication date 16 December 2013

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.2926

zbMATH Keywords

arithmetical transfinite recursionATRincomparableincompatibleinitial intervalpartial orderreverse mathematicsscatteredstrong antichain

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of the initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We show that the left to right directions of these theorems are equivalent to ACA_0 and ATR_0, respectively. On the other hand, the opposite directions are both provable in WKL_0, but not in RCA_0. We also prove the equivalence with ACA_0 of the following result of Erd"os and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains.

Review text

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.

Recommendations

• Infinite saturated orders
• Reverse Mathematics of Separation Theorems in Lattice Theory
• scientific article; zbMATH DE number 2236636
• scientific article; zbMATH DE number 1421071
• Linear extensions of partial orders and reverse mathematics
• Ordering free products in reverse mathematics
• The minimal size of infinite maximal antichains in direct products of partial orders
• Interval orders and reverse mathematics
• scientific article; zbMATH DE number 2236637
• Reverse mathematics and Ramsey's property for trees

Cites work

• Borel quasi-orderings in subsystems of second-order arithmetic
• Diagonally non-computable functions and fireworks
• From well-quasi-ordered sets to better-quasi-ordered sets
• scientific article; zbMATH DE number 3501550 (Why is no real title available?)
• On families of mutually exclusive sets
• Reverse mathematics and the equivalence of definitions for well and better quasi-orders
• Subsystems of second order arithmetic
• The Galvin-Prikry theorem and set existence axioms
• The maximal linear extension theorem in second order arithmetic
• The metamathematics of scattered linear orderings
• Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer.
• Weak axioms of determinacy and subsystems of analysis I: δ20 games

Cited in

(11)

• Interval orders and reverse mathematics
• Reverse mathematics, well-quasi-orders, and Noetherian spaces
• Necessary use of \(\Sigma ^1_{1}\) induction in a reversal
• Linear extensions of partial orders and reverse mathematics
• Partial orders and immunity in reverse mathematics
• The reverse mathematics of wqos and bqos
• Partial orders and immunity in reverse mathematics
• Forward analysis for WSTS. III: Karp-Miller trees
• Reverse Mathematics and Π¹₂ Comprehension
• (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE
• Infinite saturated orders

This page was built for publication: Reverse mathematics and initial intervals

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