LINEAR ORDERS REALIZED BY CE EQUIVALENCE RELATIONS

Fokina, Ekaterina, Khoussainov, Bakhadyr, Semukhin, Pavel and Turetsky, Daniel (2016) LINEAR ORDERS REALIZED BY CE EQUIVALENCE RELATIONS. JOURNAL OF SYMBOLIC LOGIC, 81 (2). pp. 463-482.

Text CeLinOrd.pdf - Unspecified Download (345kB)

Abstract

<jats:title>Abstract</jats:title><jats:p>Let<jats:italic>E</jats:italic>be a computably enumerable (c.e.) equivalence relation on the set<jats:italic>ω</jats:italic>of natural numbers. We say that the quotient set<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline1" /><jats:tex-math>$\omega /E$</jats:tex-math></jats:alternatives></jats:inline-formula>(or equivalently, the relation<jats:italic>E</jats:italic>)<jats:italic>realizes</jats:italic>a linearly ordered set<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline2" /><jats:tex-math>${\cal L}$</jats:tex-math></jats:alternatives></jats:inline-formula>if there exists a c.e. relation ⊴ respecting<jats:italic>E</jats:italic>such that the induced structure (<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline4" /><jats:tex-math>$\omega /E$</jats:tex-math></jats:alternatives></jats:inline-formula>; ⊴) is isomorphic to<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline5" /><jats:tex-math>${\cal L}$</jats:tex-math></jats:alternatives></jats:inline-formula>. Thus, one can consider the class of all linearly ordered sets that are realized by<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline6" /><jats:tex-math>$\omega /E$</jats:tex-math></jats:alternatives></jats:inline-formula>; formally,<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline7" /><jats:tex-math>${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$</jats:tex-math></jats:alternatives></jats:inline-formula>. In this paper we study the relationship between computability-theoretic properties of<jats:italic>E</jats:italic>and algebraic properties of linearly ordered sets realized by<jats:italic>E</jats:italic>. One can also define the following pre-order<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline8" /><jats:tex-math>$ \le _{lo} $</jats:tex-math></jats:alternatives></jats:inline-formula>on the class of all c.e. equivalence relations:<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline9" /><jats:tex-math>$E_1 \le _{lo} E_2 $</jats:tex-math></jats:alternatives></jats:inline-formula>if every linear order realized by<jats:italic>E</jats:italic><jats:sub>1</jats:sub>is also realized by<jats:italic>E</jats:italic><jats:sub>2</jats:sub>. Following the tradition of computability theory, the<jats:italic>lo</jats:italic>-degrees are the classes of equivalence relations induced by the pre-order<jats:inline-formula><jats:alternatives><jats:graphic xmlns:xlink="http://www.w3.org/1999/xlink" orientation="portrait" mime-subtype="gif" mimetype="image" position="float" xlink:type="simple" xlink:href="S0022481215000110_inline10" /><jats:tex-math>$ \le _{lo} $</jats:tex-math></jats:alternatives></jats:inline-formula>. We study the partially ordered set of<jats:italic>lo</jats:italic>-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the<jats:italic>lo</jats:italic>-degrees.</jats:p>

Item Type:	Article
Uncontrolled Keywords:	linear orders, equivalence relations, computability
Depositing User:	Symplectic Admin
Date Deposited:	02 Nov 2016 11:19
Last Modified:	19 Jan 2023 07:37
DOI:	10.1017/jsl.2015.11
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001054