The theory of ceers computes true arithmetic (Q2187270)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The theory of ceers computes true arithmetic |
scientific article |
Statements
The theory of ceers computes true arithmetic (English)
0 references
2 June 2020
0 references
The paper is devoted to the study of the partial order of computably enumerable equivalence relations (ceers). It is shown that the theory of the partial order of ceers under computable reduction is 1-equivalent to true arithmetic. It is also proved that the same result holds for the structure comprised of the dark ceers and the structure comprised of the light ceers. The same is shown for the structure of \(\mathcal{I}\)-degrees in the dark, light, or complete structure. In each case, it is proved that there is an interpretable copy of \((\mathbb{N}, +, \times)\).
0 references
computably enumerable equivalence relation
0 references
computable reducibility on equivalence relations
0 references