Weak presentations of computable partial orderings
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].
- Chains and antichains in partial orderings
- Weak presentations of computable ordered semigroups
- Weakly semirecursive sets and r.e. orderings
- A computably enumerable partial ordering without computably enumerable maximal chains and antichains
- Relative complexity for computable presentations of the conventional linear order on the set of naturals
- Order-computable sets
- Infinite chains and antichains in computable partial orderings
- Computer Science Logic
This page was built for publication: Weak presentations of computable partial orderings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784777)
