Computable choice functions for computable linear orderings
Let \(\alpha\) be a countable linear order-type. A block of \(\alpha\) is a subinterval \(B\) of \(\alpha\) such that for all \(a,b\in B, |[a,b]|<\infty\). \(B\) is a maximal block of \(\alpha\) if \(B\) is a block of \(\alpha\) and no proper superset of \(B\) is a block of \(\alpha\). A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. In the paper under review the authors obtain a partial characterization of the computable linear order-types for which each computable model has a computable choice set, and a full characterization in the relativized case: It is proved that every model of the linear order-type \(\alpha\) of Turing degree \(\leq {d}\) has a choice set \(\leq {d}\) iff \(\alpha\) can be written as a finite sum of order-types, each of which either has finitely many blocks, or has order-type \(n\times\eta\) for some integer \(n\). Here \(\eta\) is the order-type of the rational numbers.
- On effective linearly ordered sets of comparison functions
- scientific article; zbMATH DE number 4130139 (Why is no real title available?)
- scientific article; zbMATH DE number 1303201 (Why is no real title available?)
- On maximal block functions of computable \(\eta \)-like linear orderings
- The block relation in computable linear orders
This page was built for publication: Computable choice functions for computable linear orderings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4434504)
