Computability of Products of Chainable Continua
- PDF / 612,471 Bytes
- 18 Pages / 439.642 x 666.49 pts Page_size
- 82 Downloads / 183 Views
Computability of Products of Chainable Continua 1 · Zvonko Iljazovi´c1 ˇ Matea Celar
Accepted: 31 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We examine conditions under which a semicomputable set in a computable topological space is computable. In particular, we examine topological pairs (A, B) with the following property: if X is a computable topological space and f : A → X is an embedding such that f (A) and f (B) are semicomputable sets in X, then f (A) is a computable set in X. Such pairs (A, B) are said to have computable type. It is known that (K, {a, b}) has computable type if K is a Hausdorff continuum chainable from a to b. It is also known that (I n , ∂I n ) has computable type, where I n is the ndimensional unit cube and ∂I n is its boundary in Rn . We generalize these results by proving the following: if Ki is a nontrivial Hausdorff continuum chainable from ai n to bi for i ∈ {1, . . . , n}, then ( i=1 Ki , B) has computable type, where B is the set n of all (x1 , . . . , xn ) ∈ i=1 Ki such that xi ∈ {ai , bi } for some i ∈ {1, . . . , n}. Keywords Computable topological space · Computable set · Semicomputable set · Product of chainable continua
1 Introduction If f : Rn → R is a computable function (in the sense of computable analysis [18, 24]), then f (x) is a computable number for each computable point x ∈ Rn . On the other hand, if y ∈ R is a computable number, then the equation f (x) = y need not have a computable solution even if there exists x ∈ Rn such that f (x) = y. Namely, there exists a computable function f : R → R such that f −1 ({0}) is a nonempty compact set which does not contain a computable number [19]. This work has been fully supported by Croatian Science Foundation under the project 7459 CompStruct. Zvonko Iljazovi´c
[email protected] ˇ Matea Celar [email protected] 1
Department of Mathematics, Faculty of Science, University of Zagreb, Zagreb, Croatia
Theory of Computing Systems
In this paper we consider conditions under which, for such a function f , the set f −1 ({0}) contains a computable point, moreover under which f −1 ({0}) is a computable set. A compact subset S of Euclidean space Rn is said to be computable if S can be effectively approximated by a finite set of rational points with arbitrary precision. On the other hand, a compact set S ⊆ Rn is said to be semicomputable if the complement of S in Rn can be effectively exhausted by rational open balls (which is equivalent to the fact that S = f −1 ({0}) for some computable function f : Rn → R). While each computable set is semicomputable, a semicomputable set need not be computable. In fact, as mentioned, there exists a nonempty semicomputable set S ⊆ R which does not contain any computable point. This implies that such an S cannot be computable, namely in any computable set the set of all computable points belonging to that set is dense in it. So we might say that such an S is actually “far away from being computable”. On the other hand, if a, b ∈ R, a < b, then the
Data Loading...
