Reverse mathematics and initial intervals

DOI10.1016/J.APAL.2013.11.002zbMATH Open1284.03137DBLPjournals/apal/FrittaionM14arXiv1303.2926OpenAlexW2094092842WikidataQ61834871 ScholiaQ61834871MaRDI QIDQ386152FDOQ386152

Authors: Emanuele Frittaion, Alberto Marcone 

Publication date: 16 December 2013

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

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.

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• Infinite saturated orders
• Reverse Mathematics and Π¹₂ Comprehension
• Reverse mathematics, well-quasi-orders, and Noetherian spaces
• The Reverse Mathematics of wqos and bqos
• Interval orders and reverse mathematics
• (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE
• Necessary use of \(\Sigma ^1_{1}\) induction in a reversal
• 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)