It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self full degrees. We show that the poset of finite strings of natural numbers, under the relation of being an initial segment, can be embedded as an initial segment of the degrees of ceers with infinitely many classes. A further refinement of the proof shows that one can also embed the free distributive lattice generated by the lower semilattice finite strings of natural numbers, under the relation of being an initial segment, as an initial segment of the degrees of ceers with infinitely many classes
Andrews, U., Sorbi, A. (2022). Initial segments of the degrees of ceers. THE JOURNAL OF SYMBOLIC LOGIC, 87(3), 1260-1282 [10.1017/jsl.2022.14].
Initial segments of the degrees of ceers
Andrea Sorbi
2022-01-01
Abstract
It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self full degrees. We show that the poset of finite strings of natural numbers, under the relation of being an initial segment, can be embedded as an initial segment of the degrees of ceers with infinitely many classes. A further refinement of the proof shows that one can also embed the free distributive lattice generated by the lower semilattice finite strings of natural numbers, under the relation of being an initial segment, as an initial segment of the degrees of ceers with infinitely many classesFile | Dimensione | Formato | |
---|---|---|---|
initial_segments_of_the_degrees_of_ceers.pdf
accesso aperto
Tipologia:
Post-print
Licenza:
PUBBLICO - Pubblico con Copyright
Dimensione
466.85 kB
Formato
Adobe PDF
|
466.85 kB | Adobe PDF | Visualizza/Apri |
initial-segments-of-the-degrees-of-ceers.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
390.25 kB
Formato
Adobe PDF
|
390.25 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1205016