Linear orders realized by C.e. Equivalence relations

Journal of Symbolic Logic 81 (2):463-482 (2016)


LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure 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 = \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 ofEand algebraic properties of linearly ordered sets realized byE. 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 byE1is also realized byE2. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order$ \le _{lo} $. We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees.

Download options


    Upload a copy of this work     Papers currently archived: 72,879

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

13 (#776,463)

6 months
1 (#386,016)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Add more references

Citations of this work

The Theory of Ceers Computes True Arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.
Initial Segments of the Degrees of Ceers.Uri Andrews & Andrea Sorbi - 2022 - Journal of Symbolic Logic 87 (3):1260-1282.
Word Problems and Ceers.Valentino Delle Rose, Luca San Mauro & Andrea Sorbi - 2020 - Mathematical Logic Quarterly 66 (3):341-354.

Add more citations

Similar books and articles

Linearization of Definable Order Relations.Vladimir Kanovei - 2000 - Annals of Pure and Applied Logic 102 (1-2):69-100.
An Undecidable Linear Order That Is $N$-Decidable for All $N$.John Chisholm & Michael Moses - 1998 - Notre Dame Journal of Formal Logic 39 (4):519-526.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Maximal R.E. Equivalence Relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
? 0 N -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
Thin Equivalence Relations and Effective Decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
Coloring Linear Orders with Rado's Partial Order.Riccardo Camerlo & Alberto Marcone - 2007 - Mathematical Logic Quarterly 53 (3):301-305.