EUVIMEDSkopri EUVIMED
Crossref

Computably Enumerable Partial Orders

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

Computability · 2012

DOI: 10.3233/com-12013 ↗

At a glance

Journal article in Computability, 2012. Written by Peter A. Cholak and 3 co-authors. Cited 3 times so far (Crossref).

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

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.

Cite

APA

Cholak, P. A., Dzhafarov, D. D., Schweber, N., & Shore, R. A. (2012). Computably Enumerable Partial Orders. Computability. https://doi.org/10.3233/com-12013

Vancouver

Cholak PA, Dzhafarov DD, Schweber N, Shore RA. Computably Enumerable Partial Orders. Computability. 2012. doi:10.3233/com-12013

BibTeX
@article{Cholak2012,
  author = {Cholak, Peter A. and Dzhafarov, Damir D. and Schweber, Noah and Shore, Richard A.},
  title = {Computably Enumerable Partial Orders},
  journal = {Computability},
  year = {2012},
  doi = {10.3233/com-12013}
}
Start for free →