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
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 -