SAS

Abstract

We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain principle and ascending/descending sequence principle for such orders, and show that the latter is strictly stronger than the latter. We then show that every $\emptyset'$-computable structure (or even just of c.e. degree) has the same degree spectrum as some computably enumerable (co-c.e.) partial order, and hence that there is a c.e. (co-c.e.) partial order with spectrum equal to the set of nonzero degrees.

A copy of the submitted paper can be found at http://www.nd.edu/~cholak/papers/ceorderings.pdf