The theory of ceers computes true arithmetic (Q2187270): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1909.09401 / rank | |||
Normal rank |
Revision as of 03:01, 19 April 2024
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