Annals of Pure and Applied Logic 165 (3):858-879 (2014)

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 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 ACA0 and ATR0, respectively. On the other hand, the opposite directions are both provable in WKL0, but not in RCA0. We also prove the equivalence with ACA0 of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/j.apal.2013.11.002
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,639
Through your library

References found in this work BETA

Subsystems of Second-Order Arithmetic.Stephen G. Simpson - 2004 - Studia Logica 77 (1):129-129.
Weak Axioms of Determinacy and Subsystems of Analysis I: Δ20 Games.Kazuyuki Tanaka - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (6):481-491.

View all 9 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

The Dirac Delta Function in Two Settings of Reverse Mathematics.Sam Sanders & Keita Yokoyama - 2012 - Archive for Mathematical Logic 51 (1-2):99-121.
Questioning Constructive Reverse Mathematics.I. Loeb - 2012 - Constructivist Foundations 7 (2):131-140.
Open Questions in Reverse Mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Reverse Mathematics: The Playground of Logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
Reverse Mathematics of Separably Closed Sets.Jeffry L. Hirst - 2006 - Archive for Mathematical Logic 45 (1):1-2.
Interval Orders and Reverse Mathematics.Alberto Marcone - 2007 - Notre Dame Journal of Formal Logic 48 (3):425-448.
Reverse Mathematics of Prime Factorization of Ordinals.Jeffry L. Hirst - 1999 - Archive for Mathematical Logic 38 (3):195-201.
Derived Sequences and Reverse Mathematics.Jeffry L. Hirst - 1993 - Mathematical Logic Quarterly 39 (1):447-453.
Reverse Mathematics and Completeness Theorems for Intuitionistic Logic.Takeshi Yamazaki - 2001 - Notre Dame Journal of Formal Logic 42 (3):143-148.
Reverse Mathematics and a Ramsey-Type König's Lemma.Stephen Flood - 2012 - Journal of Symbolic Logic 77 (4):1272-1280.


Added to PP index

Total views
9 ( #853,838 of 2,331,388 )

Recent downloads (6 months)
1 ( #588,490 of 2,331,388 )

How can I increase my downloads?


My notes