|
|
Random numbers and recursively enumerable closed subsets of incomplete metric spaces
Vasco Brattka, in:
ICALP 2002: International Colloquium on Automata,Languages, and Programming ,
Lecture Notes in Computer Science , Springer, Berlin 2002, 950-961
Abstract
A closed subset of a computable metric space is called r.e. closed if
all open rational balls which intersect the set can be effectively enumerated
and it is called effectively separable, if it contains a dense computable sequence.
Both notions are closely related and in case of Euclidean space (and complete computable metric spaces
in general) they actually coincide.
However, in case of incomplete metric spaces these notions are distinct.
We use the immune set of natural random numbers to construct a recursive immune tree which
shows that there exists an r.e. closed subset of some incomplete subspace of Cantor space
which is not effectively separable.
Finally, we transfer this example to the incomplete space of rational numbers (considered
as a subspace of Euclidean space).
© 2002 Springer-Verlag Berlin
Electronical Versions