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

ATRpartial orderreverse mathematicsscatteredarithmetical transfinite recursionincomparableincompatibleinitial intervalstrong antichain

Mathematics Subject Classification ID

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

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
• Publication:4946096
• 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

• scientific article; zbMATH DE number 3501550 (Why is no real title available?)
• 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
• 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)

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

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)