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.

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)