We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of $I$-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of $(mathbb{N},+, imed)$.

Andrews, U., Schweber, N., Sorbi, A. (2020). The theory of ceers computes true arithmetic. ANNALS OF PURE AND APPLIED LOGIC, 171(8) [10.1016/j.apal.2020.102811].

The theory of ceers computes true arithmetic

Sorbi Andrea
2020-01-01

Abstract

We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of $I$-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of $(mathbb{N},+, imed)$.
2020
Andrews, U., Schweber, N., Sorbi, A. (2020). The theory of ceers computes true arithmetic. ANNALS OF PURE AND APPLIED LOGIC, 171(8) [10.1016/j.apal.2020.102811].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S016800722030035X-main.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 594.14 kB
Formato Adobe PDF
594.14 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/1110354