Linear orders realized by C.e. Equivalence relations

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


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.



    Upload a copy of this work     Papers currently archived: 89,621

External links

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

Through your library

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.


Added to PP

23 (#576,881)

6 months
8 (#155,393)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

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.
Word problems and ceers.Valentino Delle Rose, Luca San Mauro & Andrea Sorbi - 2020 - Mathematical Logic Quarterly 66 (3):341-354.
Initial Segments of the Degrees of Ceers.Uri Andrews & Andrea Sorbi - 2022 - Journal of Symbolic Logic 87 (3):1260-1282.

Add more citations

References found in this work

Add more references