Computably discrete represented spaces
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_ | 1866917138254528512 |
|---|---|
| author | Neumann, Eike Pauly, Arno Pradic, Cécilia Valenti, Manlio |
| author_facet | Neumann, Eike Pauly, Arno Pradic, Cécilia Valenti, Manlio |
| contents | In computable topology, a represented space is called computably discrete if its equality predicate is semidecidable. While any such space is classically isomorphic to an initial segment of the natural numbers, the computable-isomorphism types of computably discrete represented spaces exhibit a rich structure. We show that the widely studied class of computably enumerable equivalence relations (ceers) corresponds precisely to the computably Quasi-Polish computably discrete spaces. We employ computably discrete spaces to exhibit several separating examples in computable topology. We construct a computably discrete computably Quasi-Polish space admitting no decidable properties, a computably discrete and computably Hausdorff precomputably Quasi-Polish space admitting no computable injection into the natural numbers, a two-point space which is computably Hausdorff but not computably discrete, and a two-point space which is computably discrete but not computably Hausdorff. We further expand an example due to Weihrauch that separates computably regular spaces from computably normal spaces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07020 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computably discrete represented spaces Neumann, Eike Pauly, Arno Pradic, Cécilia Valenti, Manlio Logic Logic in Computer Science General Topology 54G20, 54D15, 03F60, 03D78 In computable topology, a represented space is called computably discrete if its equality predicate is semidecidable. While any such space is classically isomorphic to an initial segment of the natural numbers, the computable-isomorphism types of computably discrete represented spaces exhibit a rich structure. We show that the widely studied class of computably enumerable equivalence relations (ceers) corresponds precisely to the computably Quasi-Polish computably discrete spaces. We employ computably discrete spaces to exhibit several separating examples in computable topology. We construct a computably discrete computably Quasi-Polish space admitting no decidable properties, a computably discrete and computably Hausdorff precomputably Quasi-Polish space admitting no computable injection into the natural numbers, a two-point space which is computably Hausdorff but not computably discrete, and a two-point space which is computably discrete but not computably Hausdorff. We further expand an example due to Weihrauch that separates computably regular spaces from computably normal spaces. |
| title | Computably discrete represented spaces |
| topic | Logic Logic in Computer Science General Topology 54G20, 54D15, 03F60, 03D78 |
| url | https://arxiv.org/abs/2504.07020 |