Computably enumerable partial orders

Details Computably enumerable partial orders Computably enumerable partial orders

2011-10-18

arxiv.org/abs/1110.4068v1

Mathematics

Logic

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computably enumerable partial orders does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computably enumerable partial orders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computably enumerable partial orders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-292790