Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T21:07:38.956Z Has data issue: false hasContentIssue false

LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS

Published online by Cambridge University Press:  03 May 2016

EKATERINA FOKINA
Affiliation:
KURT GÖDEL RESEARCH CENTER FOR MATHEMATICAL LOGIC UNIVERSITY OF VIENNA VIENNA, AUSTRIA E-mail: ekaterina.fokina@univie.ac.at
BAKHADYR KHOUSSAINOV
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF AUCKLAND AUCKLAND, NEW ZEALAND E-mail: bmk@cs.auckland.ac.nz
PAVEL SEMUKHIN
Affiliation:
KURT GÖDEL RESEARCH CENTER FOR MATHEMATICAL LOGIC UNIVERSITY OF VIENNA VIENNA, AUSTRIA E-mail: pavel.semukhin@gmail.com
DANIEL TURETSKY
Affiliation:
KURT GÖDEL RESEARCH CENTER FOR MATHEMATICAL LOGIC UNIVERSITY OF VIENNA VIENNA, AUSTRIA E-mail: turetsd4@univie.ac.at
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let E be a computably enumerable (c.e.) equivalence relation on the set ω of natural numbers. We say that the quotient set $\omega /E$ (or equivalently, the relation E) realizes a linearly ordered set ${\cal L}$ if there exists a c.e. relation ⊴ respecting E such that the induced structure ( $\omega /E$ ; ⊴) is isomorphic to ${\cal L}$ . Thus, one can consider the class of all linearly ordered sets that are realized by $\omega /E$ ; formally, ${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$ . In this paper we study the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E. One can also define the following pre-order $ \le _{lo} $ on the class of all c.e. equivalence relations: $E_1\le _{lo} E_2 $ if every linear order realized by E 1 is also realized by E 2. Following the tradition of computability theory, the lo-degrees are the classes of equivalence relations induced by the pre-order $ \le _{lo} $ . We study the partially ordered set of lo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the lo-degrees.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2016