Well-Orders Realized by C.E. Equivalence Relations

Nikolay Bazhenov, Maxim Zubkov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


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.

Язык оригиналаанглийский
Название основной публикацииRevolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings
РедакторыUlrich Berger, Arno Pauly, Johanna N.Y. Franklin, Florin Manea
ИздательSpringer Science and Business Media Deutschland GmbH
Число страниц11
ISBN (печатное издание)9783031087394
СостояниеОпубликовано - 2022
Событие18th Conference on Computability in Europe, CiE 2022 - Swansea, Великобритания
Продолжительность: 11 июл 202215 июл 2022

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том13359 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


Конференция18th Conference on Computability in Europe, CiE 2022

Предметные области OECD FOS+WOS



Подробные сведения о темах исследования «Well-Orders Realized by C.E. Equivalence Relations». Вместе они формируют уникальный семантический отпечаток (fingerprint).