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 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 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.
Reverse mathematics and initial intervals
FRITTAION, Emanuele;MARCONE, Alberto Giulio
2014-01-01
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 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 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.File | Dimensione | Formato | |
---|---|---|---|
initial intervals APAL.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Non pubblico
Dimensione
743.66 kB
Formato
Adobe PDF
|
743.66 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.