We examine the degree structure of equivalence relations on under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in. We show that every equivalence relation has continuum many self-full strong minimal covers, and that needn't be a strong minimal cover of a self-full degree. Finally, we show that the theory of the degree structure as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic.
On The Structure Of Computable Reducibility On Equivalence Relations Of Natural Numbers
San Mauro L.
2023-01-01
Abstract
We examine the degree structure of equivalence relations on under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in. We show that every equivalence relation has continuum many self-full strong minimal covers, and that needn't be a strong minimal cover of a self-full degree. Finally, we show that the theory of the degree structure as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic.File | Dimensione | Formato | |
---|---|---|---|
on-the-structure-of-computable-reducibility-on-equivalence-relations-of-natural-numbers.pdf
non disponibili
Tipologia:
Documento in Versione Editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
422.42 kB
Formato
Adobe PDF
|
422.42 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.