Effectiveness for Embedded Spheres and Balls

✍ Scribed by Joseph S. Miller

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 179 KB
• Volume: 66
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(04)80384-0

✦ Synopsis

We consider arbitrary dimensional spheres and closed balls embedded in R n as Π 0 1 classes. Such a strong restriction on the topology of a Π 0 1 class has computability theoretic repercussions. Algebraic topology plays a crucial role in our exploration of these consequences; the use of homology chains as computational objects allows us to take algorithmic advantage of the topological structure of our Π 0 1 classes. We show that a sphere embedded as a Π 0 1 class is necessarily located, i.e., the distance to the class is a computable function, or equivalently, the class contains a computably enumerable dense set of computable points. Similarly, a ball embedded as a Π 0 1 class has a dense set of computable points, though not necessarily c.e. To prove location for balls, it is sufficient to assume that both it and its boundary sphere are Π 0 1 . However, the converse fails, even for arcs; using a priority argument, we prove that there is a located arc in R 2 without computable endpoints. Finally, the requirement that the embedding map itself be computable is shown to be stronger than the other effectiveness criteria considered. A characterization in terms of computable local contractibility is stated; the proof will be the subject of a sequel.