Computably Enumerable Partial Orders

Article type: Research Article

Authors: Cholak, Peter A. | Dzhafarov, Damir D. | Schweber, Noah | Shore, Richard A.

Affiliations: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556 U.S.A. [email protected] | Department of Mathematics, University of California, Berkeley, Berkeley, California 94720 U.S.A. [email protected] | Department of Mathematics, University of California, Berkeley, Berkeley, California 94720 U.S.A. [email protected] | Department of Mathematics, Cornell University, Ithaca, NY 14853 U.S.A. [email protected]

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 former 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.

Keywords: Computably enumerable partial orders, chains and antichains

DOI: 10.3233/COM-12013

Journal: Computability, vol. 1, no. 2, pp. 99-107, 2012