Isolated d.c.e. degrees and $Σ_1$ induction
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913980056862720 |
|---|---|
| author | Liu, Yiqun Liu, Yong Peng, Cheng |
| author_facet | Liu, Yiqun Liu, Yong Peng, Cheng |
| contents | A Turing degree is d.c.e. if it contains a set that is the difference of two c.e. sets. A d.c.e. degree $\mathbf{d}$ is isolated by a c.e. degree $\mathbf{a}<\mathbf{d}$ if all c.e. degrees that are below $\mathbf{d}$ are also below $\mathbf{a}$; $\mathbf{d}$ is isolated from above by a c.e. degree $\mathbf{a}>\mathbf{d}$ if all c.e. degrees that are above $\mathbf{d}$ are also above $\mathbf{a}$. In this paper, we study the inductive strength of both isolated and upper isolated d.c.e. degrees from the point of view of reverse recursion theory. We show that (1) $P^{-} + BΣ_1 + \text{Exp} \vdash IΣ_1 \leftrightarrow$ There is an isolated proper d.c.e. degree below $\mathbf{0}'$; (2) $P^{-} + BΣ_1 + \text{Exp} \vdash IΣ_1 \leftrightarrow$ There is an upper isolated proper d.c.e. degree below $\mathbf{0}'$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_05951 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Isolated d.c.e. degrees and $Σ_1$ induction Liu, Yiqun Liu, Yong Peng, Cheng Logic 03F30, 03D28, 03H15 A Turing degree is d.c.e. if it contains a set that is the difference of two c.e. sets. A d.c.e. degree $\mathbf{d}$ is isolated by a c.e. degree $\mathbf{a}<\mathbf{d}$ if all c.e. degrees that are below $\mathbf{d}$ are also below $\mathbf{a}$; $\mathbf{d}$ is isolated from above by a c.e. degree $\mathbf{a}>\mathbf{d}$ if all c.e. degrees that are above $\mathbf{d}$ are also above $\mathbf{a}$. In this paper, we study the inductive strength of both isolated and upper isolated d.c.e. degrees from the point of view of reverse recursion theory. We show that (1) $P^{-} + BΣ_1 + \text{Exp} \vdash IΣ_1 \leftrightarrow$ There is an isolated proper d.c.e. degree below $\mathbf{0}'$; (2) $P^{-} + BΣ_1 + \text{Exp} \vdash IΣ_1 \leftrightarrow$ There is an upper isolated proper d.c.e. degree below $\mathbf{0}'$. |
| title | Isolated d.c.e. degrees and $Σ_1$ induction |
| topic | Logic 03F30, 03D28, 03H15 |
| url | https://arxiv.org/abs/2508.05951 |