The expressive power of first-order topological languages
Ernest Davis · Journal of Logic and Computation · 2013
We consider the expressive power of the first-order structure Ω, C where Ω is either of two of different domains of extended regions in Euclidean space, and C(x,y) is the topological relation "Region x is in contact with region y."We prove two main theorems:• Let P[Q] be the domain of bounded, non-empty, rational polyhedra in two-or threedimensional Euclidean space.A relation Γ over P[Q] is definable in the structure P[Q], C if and only if Γ is arithmetic and invariant under rational PL-homeomorphisms of the space to itself.We also extend this result to a number of other domains, including the domain of all polyhedra and the domain of semi-algebraic regions.• Let R be the space of bounded, non-empty, closed regular regions. in n-dimensional Euclidean space.Any analytical relation over lower-dimensional (i.e.empty interior) compact point sets that is invariant under homeomorphism is implicitly definable in the structure R, C .