Weak presentations of computable partial orderings (Q2784777)

An infinite partial order is computable if it is isomorphic to the natural numbers equipped with some recursive order relation. This paper explores a weakening of that notion: a set \(P\) of natural numbers supports a given partial order if the order is isomorphic to \(P\) equipped with some order relation that has a recursive extension. The authors prove various results about the existence of supporting and nonsupporting sets. For example, every infinite computable linear order is supported by any infinite r.e. set. On the other hand, there exists an infinite computable partial order such that every nonrecursive r.e. degree contains an r.e. set that does not support the order.NEWLINENEWLINEFor the entire collection see [Zbl 0970.00012].