2025/04/09 by Eike Neumann, Neumann, Eike, Arno Pauly +5 · 1 citation
Computer Science · Mathematics · #03D78 #03F60 #54D15 #54G20 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #General Topology (math.GN) #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2504.07020
openalex publication_date 2025/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.