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 R,+,<,Z can be defined in the structure R,+,<,1. This result is achieved by obtaining a topological characterization of R,+,<,1-definable relations in the family of R,+,<,Z-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 R,+,<,1,X. The above characterization allows us to prove that there is no intermediate structure between R,+,<,Z and R,+,<,1. We also show that a R,+,<,Z-definable relation is R,+,<,1-definable if and only if its intersection with every R,+,<,1-definable line is R,+,<,1-definable. This gives a noneffective but simple characterization of R,+,<,1-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

    Classifications

    Mathematics Subject Classification 20201

    Consultation statistics

    This page has been seen 1959 times.
    This article's PDF has been downloaded 230 times.