Linear extensions of partial orders and Reverse Mathematics


Abstract in English

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

Download