Alexis Bès ; Christian Choffrut - Theories of real addition with and without a predicate for integers

lmcs:6094 - Logical Methods in Computer Science, May 26, 2021, Volume 17, Issue 2 - https://doi.org/10.23638/LMCS-17(2:18)2021
Theories of real addition with and without a predicate for integersArticle

Authors: Alexis Bès ; Christian Choffrut

    We show that it is decidable whether or not a relation on the reals definable in the structure $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ can be defined in the structure $\langle \mathbb{R}, +,<, 1 \rangle$. This result is achieved by obtaining a topological characterization of $\langle \mathbb{R}, +,<, 1 \rangle$-definable relations in the family of $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$-definable relations and then by following Muchnik's approach of showing that the characterization of the relation $X$ can be expressed in the logic of $\langle \mathbb{R}, +,<,1, X \rangle$. The above characterization allows us to prove that there is no intermediate structure between $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$ and $\langle \mathbb{R}, +,<, 1 \rangle$. We also show that a $\langle \mathbb{R}, +,<, \mathbb{Z} \rangle$-definable relation is $\langle \mathbb{R}, +,<, 1 \rangle$-definable if and only if its intersection with every $\langle \mathbb{R}, +,<, 1 \rangle$-definable line is $\langle \mathbb{R}, +,<, 1 \rangle$-definable. This gives a noneffective but simple characterization of $\langle \mathbb{R}, +,<, 1 \rangle$-definable relations.


    Volume: Volume 17, Issue 2
    Published on: May 26, 2021
    Accepted on: April 28, 2021
    Submitted on: February 12, 2020
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic

    Consultation statistics

    This page has been seen 1077 times.
    This article's PDF has been downloaded 165 times.