On the Computability of Region-Based Euclidean Logics

摘要

By a Euclidean logic, we understand a formal language whose variables range over subsets of Euclidean space, of some fixed dimension, and whose non-logical primitives have fixed meanings as geometrical properties, relations and operations involving those sets. In this paper, we consider first-order Euclidean logics with primitives for the properties of connectedness and convexity, the binary relation of contact and the ternary relation of being closer-than. We investigate the computational properties of the corresponding first-order theories when variables are taken to range over various collections of subsets of 1-, 2- and 3-dimensional space. We show that the theories based on Euclidean spaces of dimension greater than 1 can all encode either first- or second-order arithmetic, and hence are undecidable. We show that, for logics able to express the closer-than relation, the theories of structures based on 1-dimensional Euclidean space have the same complexities as their higher-dimensional counterparts. By contrast, in the absence of the closer-than predicate, all of the theories based on 1-dimensional Euclidean space considered here are decidable, but non-elementary.