Minimal covers in the Weihrauch degrees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914992518856704 |
|---|---|
| author | Lempp, Steffen Miller, Joseph S. Pauly, Arno Soskova, Mariya I. Valenti, Manlio |
| author_facet | Lempp, Steffen Miller, Joseph S. Pauly, Arno Soskova, Mariya I. Valenti, Manlio |
| contents | In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem $f$ is a minimal cover or strong minimal cover of a problem $h$. We show that strong minimal covers only exist in the cone below $\mathsf{id}$ and that the Weihrauch lattice above $\mathsf{id}$ is dense. From this, we conclude that the degree of $\mathsf{id}$ is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_12676 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Minimal covers in the Weihrauch degrees Lempp, Steffen Miller, Joseph S. Pauly, Arno Soskova, Mariya I. Valenti, Manlio Logic Logic in Computer Science 03D30 03D78 In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem $f$ is a minimal cover or strong minimal cover of a problem $h$. We show that strong minimal covers only exist in the cone below $\mathsf{id}$ and that the Weihrauch lattice above $\mathsf{id}$ is dense. From this, we conclude that the degree of $\mathsf{id}$ is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic. |
| title | Minimal covers in the Weihrauch degrees |
| topic | Logic Logic in Computer Science 03D30 03D78 |
| url | https://arxiv.org/abs/2311.12676 |