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 classes
2022
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].
File in questo prodotto:
File 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1205016