On the Lattices of Effectively Open Sets

摘要

We show that for many natural computable metric spaces and computable domains the first order theory of the lattice of effectively open sets is hereditarily undecidable. Moreover, for several important spaces (e.g., finite-dimensional Euclidean spaces and the domain Pω) this theory is m-equivalent to the first-order arithmetic.