Ordered structures and computability
Open AccessWe consider three questions surrounding computable structures and orderings.First, we make progress toward answering a question of Downey, Hirschfeldt, and Goncharov by showing that for a large class of countable linear orderings, the Turing degree spectrum of the successor relation is closed upward in the c.e. degrees.Next we consider computable partial orders (specifically, finitely branching trees) with, in addition to their ordered structure, finite-range functions (coloring functions) on the collection of chains of length n in the ordering. In the style of Ramsey, we prove the existence of a monochromatic substructure and analyze the axiomatic content of this theorem in the context of reverse mathematics. Then we provide a bound on the complexity of the monochromatic substructure in the case that the coloring function is computable.Finally, we consider computable algebraic structures (in particular, groups and semigroups) and the algorithmic complexity of orderings of their elements. We give conditions sufficient to ensure that a group has orderings of arbitrary computability theoretic complexity (in a strong sense), discuss an interesting example, and give a useful representation of the orderings of a computable semigroup as paths in a computable binary tree.
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.