Linear extensions of partial orders and Reverse Mathematics

We introduce the notion of τ-like partial order, where τis one of the linear order types ω, ω*, ω+ω*, and ζ. For example, being ω-like means that every element has finitely many predecessors, while being ζ-like means that every interval is finite. We consider statements of the form "any τ-like partial order has a τ-like linear extension" and "any τ-like partial order is embeddable into τ" (when τ is ζ this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to BΣ^0_2 or to ACA_0 over the usual base system RCA_0.

No reviews yet.

No comments yet.