The Expressivity of Quantifying over Regions
Ernest Davis · Journal of Logic and Computation · 2006
We categorize in recursion-theoretic terms the expressivity of a number of first-order languages that allow quantification over regions in Euclidean space. Specifically we show the following: (1) Let be any class of closed regions in Euclidean space that includes all simple polygons. Let C(x, y) be the relation, ‘region x is connected to region y’ and let Convex(x) be the property, ‘region x is convex’. Then any relation over that is analytical and invariant under affine transformations is first-order definable in the structure 〈, C, Convex〉. (2) Let be as in (1), and let Closer(x, y, z) be the relation ‘region x is closer to y than to z.’ Then any relation over that is analytical and invariant under orthogonal transformations is first-order definable in the structure 〈, Closer〉. (3) Let be the class of finite unions of intervals in the real line. Then any relation over that is analytical and invariant under linear transformations is first-order definable in the structure 〈, Closer〉. (4) If the class of regions is restricted to be polygons with rational vertices, then results analogous to (1–3) hold, substituting ‘arithmetical relation’ for ‘analytical relation’.