Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.10015 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916322834644992 |
|---|---|
| author | Cole, Joshua |
| author_facet | Cole, Joshua |
| contents | For mass problems $P,Q\subseteq {\mathbb{N}^\mathbb{N}}$ (Baire space), $P$ is Medvedev reducible to $Q$ ($P\leq_sQ$) if for some Turing funcional $Φ$, $Φ(Q)\subseteq P$, and Medvedev equivalent to $Q$ if also $Q\leq_sP$. Shafer asked if every closed problem $P$ is Medvedev equivalent to a closed problem $Q$ with $Q\subseteq 2^\mathbb{N}$ (Cantor space). We show that this is not the case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10015 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A closed subset of Baire space not Medvedev equivalent to any closed set of Cantor space Cole, Joshua Logic 03D30 For mass problems $P,Q\subseteq {\mathbb{N}^\mathbb{N}}$ (Baire space), $P$ is Medvedev reducible to $Q$ ($P\leq_sQ$) if for some Turing funcional $Φ$, $Φ(Q)\subseteq P$, and Medvedev equivalent to $Q$ if also $Q\leq_sP$. Shafer asked if every closed problem $P$ is Medvedev equivalent to a closed problem $Q$ with $Q\subseteq 2^\mathbb{N}$ (Cantor space). We show that this is not the case. |
| title | A closed subset of Baire space not Medvedev equivalent to any closed set of Cantor space |
| topic | Logic 03D30 |
| url | https://arxiv.org/abs/2407.10015 |