TY - GEN

T1 - Well-Orders Realized by C.E. Equivalence Relations

AU - Bazhenov, Nikolay

AU - Zubkov, Maxim

N1 - Funding Information: The work of N. Bazhenov was supported by the Russian Science Foundation (project no. 18-11-00028). The work of M. Zubkov was supported by the Russian Science Foundation (project no. 18-11-00028) and performed under the development program of the Volga Region Mathematical Center (agreement no. 075-02-2020-1478). Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - We study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure (N/ E, ⊴ ) is isomorphic to L. In this line of research, there are many nontrivial results demonstrating complex interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E. For example, Gavryushkin, Khoussainov, and Stephan proved that there is a ceer E realizing only one order type—the type of ω+ 1 + ω∗. In this paper, we obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α< ω3. Informally speaking, our proofs develop methods of fine-tuning the behavior of limit points of L via computability-theoretic properties of E.

AB - We study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure (N/ E, ⊴ ) is isomorphic to L. In this line of research, there are many nontrivial results demonstrating complex interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E. For example, Gavryushkin, Khoussainov, and Stephan proved that there is a ceer E realizing only one order type—the type of ω+ 1 + ω∗. In this paper, we obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α< ω3. Informally speaking, our proofs develop methods of fine-tuning the behavior of limit points of L via computability-theoretic properties of E.

KW - Computable ordinal

KW - Computable structure theory

KW - Computably enumerable structure

KW - Equivalence relation

KW - Well-order

UR - http://www.scopus.com/inward/record.url?scp=85134154492&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/de5da316-c2dc-3b43-b93a-90bca0e530a7/

U2 - 10.1007/978-3-031-08740-0_2

DO - 10.1007/978-3-031-08740-0_2

M3 - Conference contribution

AN - SCOPUS:85134154492

SN - 9783031087394

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 23

BT - Revolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings

A2 - Berger, Ulrich

A2 - Pauly, Arno

A2 - Franklin, Johanna N.Y.

A2 - Manea, Florin

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th Conference on Computability in Europe, CiE 2022

Y2 - 11 July 2022 through 15 July 2022

ER -