22 2140

# Decidability of Definability Issues in the Theory of Real Addition

Alexis Bès
Univ. Paris Est Creteil Address for correspondence: Univ. Paris Est Creteil,
LACL, F-94010 Creteil, France.

Received July 2022; accepted November 2022. LACL  F-94010 Creteil  France
<EMAIL_ADDRESS>Christian Choffrut
IRIF (UMR 8243)  CNRS and Université Paris 7 Denis Diderot  France
<EMAIL_ADDRESS>
###### Abstract

Given a subset of $X\subseteq\mathbb{R}^{n}$ we can associate with every point
$x\in\mathbb{R}^{n}$ a vector space $V$ of maximal dimension with the property
that for some ball centered at $x$, the subset $X$ coincides inside the ball
with a union of lines parallel to $V$. A point is singular if $V$ has
dimension $0$.

In an earlier paper we proved that a
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relation $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable if and only if the number of
singular points is finite and every rational section of $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable, where a rational section is a set
obtained from $X$ by fixing some component to a rational value.

Here we show that we can dispense with the hypothesis of $X$ being
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable by requiring that the
components of the singular points be rational numbers. This provides a
topological characterization of first-order definability in the structure
$\langle\mathbb{R},+,<,1\rangle$. It also allows us to deliver a self-
definable criterion (in Muchnik’s terminology) of
$\langle\mathbb{R},+,<,1\rangle$\- and
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability for a wide class of
relations, which turns into an effective criterion provided that the
corresponding theory is decidable. In particular these results apply to the
class of so-called $k-$recognizable relations which are defined by finite
Muller automata via the representation of the reals in a integer basis $k$,
and allow us to prove that it is decidable whether a $k-$recognizable relation
(of any arity) is $l-$recognizable for every base $l\geq 2$.

††volume: 188††issue: 1

Decidability of Definability Issues in the Theory of Real Addition

##  1 Introduction

In his seminal work on Presburger Arithmetic [18], Muchnik provides a
characterization of definability of a relation $X\subseteq\mathbb{Z}^{n}$ in
$\langle\mathbb{Z},+,<\rangle$ in terms of sections of $X$ and local
periodicity properties of $X$. It also shows that the characterization can be
expressed as a $\langle\mathbb{Z},+,<,X\rangle$-sentence, and thus can be
decided if $\langle\mathbb{Z},+,<,X\rangle$ is decidable. As an application
Muchnik proves that it is decidable whether a $k-$recognizable relation
$X\subseteq\mathbb{Z}^{n}$ is $\langle\mathbb{Z},+,<\rangle$-definable. Recall
that given an integer $k\geq 2$, $X$ is $k-$recognizable if it is recognizable
by some finite automaton whose inputs are the base-$k$ encoding of integers
(see [8]).

The present paper continues the line of research started in [2], which aims to
extend Muchnik’s results and techniques to the case of reals with addition.
Consider the structure $\langle\mathbb{R},+,<,1\rangle$ of the additive
ordered group of reals along with the constant $1$. It is well-known that the
subgroup $\mathbb{Z}$ of integers is not first-order-definable in this
structure. Let $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ denote the expansion
of $\langle\mathbb{R},+,<,1\rangle$ with the unary predicate
“$x\in\mathbb{Z}$”. In [2] we prove a topological characterization of
$\langle\mathbb{R},+,<,1\rangle$-definable relations in the family of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations, and use it to
derive, on the one hand, that it is decidable whether or not a relation on the
reals definable in $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ can be defined in
$\langle\mathbb{R},+,<,1\rangle$ and on the other hand that there is no
intermediate structure between $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ and
$\langle\mathbb{R},+,<,1\rangle$ (since then, the latter result has been
generalized by Walsberg [23] to a large class of $o-$minimal structures)

We recall the topological characterization of $\langle\mathbb{R},+,<,1\rangle$
in $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$, [2, Theorem 6.1]. We say that
the neighborhood of a point $x\in\mathbb{R}^{n}$ relative to a relation
$X\subseteq\mathbb{R}^{n}$ has a stratum if there exists a direction such that
the intersection of X with any sufficiently small neighborhood around $x$ is
the trace of a union of lines parallel to the given direction. When $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable, all points have strata, except
finitely many which we call singular. In [2] we give necessary and sufficient
conditions for a $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$ to be $\langle\mathbb{R},+,<,1\rangle$-definable,
namely (FSP): it has finitely many singular points and (DS): all intersections
of $X$ with arbitrary hyperplanes parallel to $n-1$ axes and having rational
components on the remaining axis are
$\langle\mathbb{R},+,<,1\rangle$-definable. We asked whether it is possible to
remove the assumption that the given relation is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable. In the present paper we
prove that the answer is positive if a new assumption is added, see below. Let
us first explain the structure of the proof in [2]. The necessity of the two
conditions (FSP) and (DS) is easy. The difficult part was their sufficiency
and it used very specific properties of the
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations, in particular
the fact that $\langle\mathbb{R},+,<,1\rangle$\- and
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations are locally
indistinguishible. In order to show the existence of a
$\langle\mathbb{R},+,<,1\rangle$-formula for $X$ we showed two intermediate
properties, (RB): for every nonsingular point $x$, there exists a basis of the
strata subspace composed of vectors with rational components, and (FI): there
are finitely many “neighborhood types”, i.e., the equivalence relation $x\sim
y$ on $\mathbb{R}^{n}$ which holds if there exists $r>0$ such that ($x+w\in
X\leftrightarrow y+w\in X$ for every $|w|<r$) has finite index.

When passing from the characterization of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations to the
characterization of general ones the topological characterization uses the
same intermediate properties but they are much more delicate to establish and
an extra condition (RSP) is required: all singular points of $X$ have rational
components. Moreover we show that this characterization is effective under
natural conditions. Indeed, if every nonempty
$\langle\mathbb{R},+,<,1,X\rangle$-definable relation contains a point with
rational components, then the $\langle\mathbb{R},+,<,1\rangle$-definability of
$X$ is expressible in the structure $\langle\mathbb{R},+,<,1,X\rangle$ itself.
The crucial point is the notion of _quasi-singular_ points generalizing that
of singular points. We were forced to consider this new notion because the
$\langle\mathbb{R},+,<,1,X\rangle$-predicate which defines singular points in
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ no longer defines them in general
structures. In so doing we can turn the criterion for
$\langle\mathbb{R},+,<,1\rangle$-definability into an effective criterion
provided that the theory of $\langle\mathbb{R},+,<,1,X\rangle$ is decidable.
More precisely we show that for every decidable expansion ${\mathcal{M}}$ of
$\langle\mathbb{R},+,<,1\rangle$ such that every nonempty
${\mathcal{M}}$-definable relation contains a point with rational components,
one can decide whether or not a given ${\mathcal{M}}$-definable relation is
$\langle\mathbb{R},+,<,1\rangle$-definable.

We extend the result of $\langle\mathbb{R},+,<,1\rangle$-definability of a
general relation to that of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability. Every relation on the
reals can be uniquely decomposed into some relations on the integers and some
relations on the unit hypercubes ([10], see also [13]). This decomposition
yields a simple characterization of the
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations, which is
expressible in $\langle\mathbb{R},+,<,\mathbb{Z},X\rangle$ provided that all
nonempty $\langle\mathbb{R},+,<,\mathbb{Z},X\rangle$-definable relations
contain a point with rational components. Combining the result on
$\langle\mathbb{R},+,<,1\rangle$-definability for the reals and Muchnik’s
result on $\langle\mathbb{Z},+,<,1\rangle$-definable integer relations we show
that for every decidable expansion ${\mathcal{N}}$ of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ such that every nonempty
${\mathcal{N}}$-definable relation contains a point with rational components,
one can decide whether or not a given ${\mathcal{N}}$-definable relation is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable.

We also study a particularly significant case. The notion of
$k$-recognizability for relations on integers can be extended to the case of
relations on reals, by considering Muller automata which read infinite words
encoding reals written in base $k$, see [9, Definition 1]. The class of
$k-$recognizable relations coincides with the class of relations definable in
some expansion of $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ of the form
$\langle\mathbb{R},\mathbb{Z},+,<,X_{k}\rangle$ where $X_{k}$ is a base
dependent ternary predicate [9, section 3]. This expansion satisfies the above
required condition since it has a decidable theory and every nonempty
$k-$recognizable relation contains a point with rational components. The
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations define a
subclass which has a very specific relevance since it coincides with the class
of relations which are $k-$recognizable for every $k\geq 2$ [4, 5, 6]. A
consequence of our result is that given a $k-$recognizable relation it can be
decided if it is $\ell-$recognizable for all bases $\ell\geq 2$. This falls
into the more general issue of finding effective characterizations of
subclasses of $k-$recognizable relations. A previous result of this type was
proved by Milchior in [17] by showing that it is decidable whether or not a
weakly $k-$recognizable subset of $\mathbb{R}$ is definable in
$\langle\mathbb{R},+,<,1\rangle$, where “weak” is defined as a natural
condition on the states of a deterministic automaton.

We give a short outline of our paper. Section 2 gathers basic definitions and
notation. In Section 3 we recall the main useful definitions and results from
[2] in order to make the paper selfcontained. In Section 4 we show that the
conjunction of conditions (RSP), (RB) and (FI) characterizes the
$\langle\mathbb{R},+,<,1\rangle$-definable relations. In Section 5 we deal
with the self-definable criterion of
$\langle\mathbb{R},+,<,1\rangle$-definability. We introduce the crucial notion
of quasi-singular point and show that it is definable in
$\langle\mathbb{R},+,<,1,X\rangle$. We also provide an alternative, inductive,
formulation of $\langle\mathbb{R},+,<,1\rangle$-definability for $X$: every
relation obtained from $X$ by assigning fixed real values to arbitrary
components contains finitely many quasi-singular points. We then show how to
extend the results to the case of $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$.
In Section 6 we show that the self-definable criterion of
$\langle\mathbb{R},+,<,1\rangle$-definability (resp.
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability) of a relation
$X\subseteq\mathbb{R}^{n}$ can be turned into an effective criterion provided
that $X$ is definable in a suitable decidable theory, and apply the result to
the class of $k$-recognizable relations.

#### Other related work.

Muchnik’s approach, namely expressing in the theory of the structure a
property of the structure itself, can be used in other settings. We refer the
interested reader to the discussion in [22, Section 4.6] and also to [19, 1,
17] for examples of such structures. A similar method has already been used in
1966, see [15, Thm 2.2.] where the authors are able to express in Presburger
theory whether or not a Presburger subset is the Parikh image of a context-
free language.

The theory of (expansions of) dense ordered groups has been studied
extensively in model theory, in particular in connection with o-minimality,
see e.g. [11, 12]. Let us also mention a recent series of results by Hieronymi
which deal with expansions of $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$, and
in particular with the frontier of decidability for such expansions, see,
e.g., [16] and its bibliography.

##  2 Preliminaries

Throughout this work we assume the vector space $\mathbb{R}^{n}$ is provided
with the metric $L_{\infty}$ (i.e., $|x|=\max_{1\leq i\leq n}|x_{i}|$). Let
$B(x,r)$ denote the open ball centered at $x\in\mathbb{R}^{n}$ and of radius
$r>0$. Given $x,y\in\mathbb{R}^{n}$ let $[x,y]$ (resp. $(x,y)$) denote the
closed segment (resp. open segment) with extremities $x,y$. We use also
notations such as $[x,y)$ or $(x,y]$ for half-open segments.

Let us specify our logical conventions and notations. We work within first-
order predicate calculus with equality. We identify formal symbols and their
interpretations. We are mainly concerned with the structures
$\langle\mathbb{R},+,<,1\rangle$ and
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$. Given a structure $\cal M$ with
domain $D$ and $X\subseteq D^{n}$, we say that $X$ is definable in $\cal M$,
or $\cal M$-definable, if there exists a formula $\varphi(x_{1},\dots,x_{n})$
in the signature of $\cal M$ such that $\varphi(a_{1},\dots,a_{n})$ holds in
$\cal M$ if and only if $(a_{1},\dots,a_{n})\in X$ (this corresponds to the
usual notion of definability without parameters).

The $\langle\mathbb{R},+,<,1\rangle$-theory admits quantifier elimination in
the following sense, which can be interpreted geometrically as saying that a
$\langle\mathbb{R},+,<,1\rangle$-definable relation is a finite union of
closed and open polyhedra.

###### Theorem 2.1

[14, Thm 1] Every formula in $\langle\mathbb{R},+,<,1\rangle$ is equivalent to
a finite Boolean combination of inequalities between linear combinations of
variables with coefficients in $\mathbb{Z}$ (or, equivalently, in
$\mathbb{Q}$).

In particular every nonempty $\langle\mathbb{R},+,<,1\rangle$-definable
relation contains a point with rational components.

##  3 Local properties of real relations

Most of the definitions and results in this section are taken from [2]. These
are variants of notions and results already known in computational geometry,
see e.g. [3, 7] for the case of $\langle\mathbb{R},+,<,1\rangle$-definable
relations. We only give formal proofs for the new results. In the whole
section we fix $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$.

###  3.1 Strata

The following clearly defines an equivalence relation.

###### Definition 3.1

Given $x,y\in\mathbb{R}^{n}$ we write $x\sim_{X}y$ or simply $x\sim y$ when
$X$ is understood, if there exists a real $r>0$ such that the translation
$w\mapsto w+y-x$ is a one-to-one mapping from $B(x,r)\cap X$ onto $B(y,r)\cap
X$.

###### Example 3.2

Let $X$ be a closed subset of the plane delimited by a square. There are ten
$\sim_{X}$-equivalence classes: the set of points interior to the square, the
set of points interior to its complement, the four vertices and the four open
edges.

Let ${\mathcal{C}l}(x)$ denote the $\sim$-equivalence class to which $x$
belongs.

###### Definition 3.3

  1. 1.

Given a non-zero vector $v\in\mathbb{R}^{n}$ and a point $y\in\mathbb{R}^{n}$,
let $L_{v}(y)=\\{y+\alpha v\ |\ \alpha\in\mathbb{R}\\}$ be the line passing
through $y$ in the direction $v$. More generally, if
$X\subseteq\mathbb{R}^{n}$ let $L_{v}(X)$ denote the set $\bigcup_{x\in
X}L_{v}(x)$.

  2. 2.

A non-zero vector $v\in\mathbb{R}^{n}$ is an $X$-_stratum_ at $x$ (or simply a
_stratum_ when $X$ is understood) if there exists a real $r>0$ such that

$B(x,r)\cap L_{v}(X\cap B(x,r))\subseteq X.$ (1)

This can be seen as saying that inside the ball $B(x,r)$, the relation $X$ is
a union of lines parallel to $v$. By convention the zero vector is also
considered as a stratum.

  3. 3.

The set of $X$-strata at $x$ is denoted $\text{Str}_{X}(x)$ or simply
$\text{Str}(x)$.

###### Proposition 3.4

[2, Proposition 3.4] For every $x\in\mathbb{R}^{n}$ the set $\text{\em
Str}{(}x)$ is a vector subspace of $\mathbb{R}^{n}$.

###### Definition 3.5

The _dimension_ dim$(x)$ of a point $x\in\mathbb{R}^{n}$ is the dimension of
the subspace $\text{Str}{(}x)$. We say that $x$ is a $d$-point if $d=\dim(x)$.
Moreover if $d=0$ then $x$ is said to be $X$-_singular_ , or simply _singular_
, and otherwise it is _nonsingular_.

###### Example 3.6

(Example 3.2 continued) Let $x\in\mathbb{R}^{2}$. If $x$ belongs to the
interior of the square or of its complement, then
$\text{Str}{(}x)=\mathbb{R}^{2}$. If $x$ is one of the four vertices of the
square then we have $\text{Str}{(}x)=\\{0\\}$, i.e., $x$ is singular. Finally,
if $x$ belongs to an open edge of the square but is not a vertex, then
$\text{Str}{(}x)$ has dimension 1, and two points of opposite edges have the
same strata subspace, while two points of adjacent edges have different strata
subspaces.

It can be shown that all strata at $x$ can be defined with respect to a common
value $r$ in expression (1).

###### Proposition 3.7

[2, Proposition 3.9] For every $x\in\mathbb{R}^{n}$ there exists a real $r>0$
such that for every $v\in\text{\em Str}{(}x)\setminus\\{0\\}$ we have

$B(x,r)\cap L_{v}(X\cap B(x,r))\subseteq X.$

###### Definition 3.8

A _$X$ -safe radius_ (or simply a _safe radius_ when $X$ is understood) for
$x$ is a real $r>0$ satisfying the condition of Proposition 3.7. Clearly if
$r$ is safe then so are all $0<s\leq r$. By convention every real is a safe
radius if $\text{Str}{(}x)=\\{0\\}$.

###### Example 3.9

(Example 3.2 continued) For an element $x$ in the interior of the square or
the interior of its complement a safe radius is the (minimal) distance from
$x$ to the edges of the square. If $x$ is a vertex then
$\text{Str}{(}x)=\\{0\\}$ and every $r>0$ is safe for $x$. In all other cases
$r$ can be chosen as the minimal distance of $x$ to a vertex.

###### Remark 3.10

If $x\sim y$ then $\text{\em Str}(x)=\text{\em Str}(y)$, therefore given an
$\sim$-equivalence class $E$, we may define $\text{Str}{(}E)$ as the set of
common strata of all $x\in E$.

Observe that the converse is false. In Example 3.2 for instance, points in the
interior and points in the complement of the interior of the square have the
same set of strata, namely $\mathbb{R}^{2}$, but are not $\sim-$equivalent.

It is possible to combine the notions of strata and of safe radius.

###### Lemma 3.11

[2, Lemma 3.13] Let $x\in\mathbb{R}^{n}$ and $r$ be a safe radius for $x$.
Then for all $y\in B(x,r)$ we have $\text{\em Str}{(x)}\subseteq\text{\em
Str}{(y)}$.

###### Example 3.12

(Example 3.2 continued) Consider a point $x$ on an (open) edge of the square
and a safe radius $r$ for $x$. For every point $y$ in $B(x,r)$ which is not on
the edge we have $\text{Str}{(}x)\subsetneq\text{Str}{(}y)=\mathbb{R}^{2}$.
For all other points we have $\text{Str}{(}x)=\text{Str}{(}y)$.

Inside a ball whose radius is safe for the center, all points along a stratum
are $\sim$-equivalent.

###### Lemma 3.13

Let $x$ be non-singular, $v\in\text{Str}{(}x)\setminus\\{0\\}$, and $r$ be
safe for $x$. For every $z\in B(x,r)$ we have $L_{v}(z)\cap
B(x,r)\subseteq{\mathcal{C}l}(z)$.

###### Proof 3.14

Let $z^{\prime}\in L_{v}(z)\cap B(x,r)$, and $s>0$ be such that both
$B(z,s),B(z^{\prime},s)$ are included in $B(x,r)$. For every $w\in B(0,s)$ we
have $z^{\prime}+w\in L_{v}(z+w)$ thus $z+w\in X\leftrightarrow
z^{\prime}+w\in X$.

###  3.2 Relativization to affine subspaces

We relativize the notion of singularity and strata to an affine subspace
$S\subseteq\mathbb{R}^{n}$. The next definition should come as no surprise.

###### Definition 3.15

Given a subset $X\subseteq\mathbb{R}^{n}$, an affine subspace
$S\subseteq\mathbb{R}^{n}$ and a point $x\in S$, we say that a vector
$v\in\mathbb{R}^{n}\setminus\\{0\\}$ parallel to $S$ is an $(X,S)$-_stratum
for the point_ $x$ if for all sufficiently small $r>0$ it holds

$B(x,r)\cap L_{v}(X\cap B(x,r)\cap S)\subseteq X.$ (2)

By convention the zero vector is also considered as a $(X,S)$-stratum. The set
of $(X,S)$-strata of $x$ is denoted $\text{Str}_{(X,S)}(x)$. We define the
equivalence relation $x\sim_{(X,S)}y$ on $S$ as follows: $x\sim_{(X,S)}y$ if
and only if there exists a real $r>0$ such that $x+w\in X\leftrightarrow
y+w\in X$ for every $w\in\mathbb{R}^{n}$ parallel to $S$ and such that
$|w|<r$. A point $x\in S$ is $(X,S)$-_singular_ if it has no $(X,S)$-stratum.
For simplicity when $S$ is the space $\mathbb{R}^{n}$ we maintain the previous
terminology and speak of $X$-strata and $X$-singular points. We say that a
real $r>0$ is $(X,S)$-_safe_ if (2) holds for every nonzero $(X,S)-$stratum
$v$.

###### Remark 3.16

Singularity and nonsingularity do not go through restriction to affine
subspaces. E.g., in the real plane, let $X=\\{(x,y)\ |\ y<0\\}$ and
$S=\\{(x,y)\mid x=0\\}$. Then the origin is not $X-$singular but it is
$(X,S)-$singular. All other elements of $S$ admit $(0,1)$ as an
$(X,S)-$stratum thus they are not $(X,S)-$singular. The opposite situation may
occur. In the real plane, let $X=\\{(x,y)\ |\ y<0\\}\cup S$. Then the origin
is $X-$singular but it is not $(X,S)-$singular.

####  3.2.1 Relativization of the space of strata

###### Lemma 3.17

Let $S$ be an affine hyperplane of $\mathbb{R}^{n}$ and $x\in S$. Let $V$ be
the vector subspace generated by
$\text{Str}_{X}(x)\setminus\text{Str}_{(X,S)}(x)$. If $V\not=\\{0\\}$ then
$\text{Str}_{X}(x)=V+\text{Str}_{(X,S)}(x)$, and otherwise
$\text{Str}_{X}(x)\subseteq\text{Str}_{(X,S)}(x)$.

###### Proof 3.18

It is clear that if $V=\\{0\\}$ then every $X$-stratum of $S$ is an
$(X,S)$-stratum.

Now assume there exists $v\in\text{Str}_{X}(x)\setminus\text{Str}_{(X,S)}(x)$.
It suffices to prove that all $w\in\text{Str}_{(X,S)}(x)$ belong to
$\text{Str}_{X}(x)$. Let $s>0$ be simultaneously $(X,S)-$safe and $X-$safe for
$x$. Let $0<s^{\prime}<s$ be such that $L_{v}(z)\cap S\subseteq B(x,s)$ for
every $z\in B(x,s^{\prime})$. Let $y_{1},y_{2}\in B(x,s^{\prime})$ be such
that $y_{1}-y_{2}$ and $w$ are parallel. It suffices to prove the equivalence
$y_{1}\in X\leftrightarrow y_{2}\in X$ . Let $y^{\prime}_{1}$ (resp.
$y^{\prime}_{2}$) denote the intersection point of $L_{v}(y_{1})$ and $S$
(resp. $L_{v}(y_{2})$ and $S$). We have $y_{1},y^{\prime}_{1}\in B(x,s)$,
$v\in\text{Str}_{X}{(x)}$, and $s$ is $X-$safe for $x$, thus $y_{1}\in
X\leftrightarrow y^{\prime}_{1}\in X$. Similarly we have $y_{2}\in
X\leftrightarrow y^{\prime}_{2}\in X$. Now $y^{\prime}_{1},y^{\prime}_{2}\in
B(x,s)$, $y^{\prime}_{1}-y^{\prime}_{2}$ and $w$ are parallel, and
$w\in\text{Str}_{(X,S)}(x)$, which implies $y^{\prime}_{1}\in X\leftrightarrow
y^{\prime}_{2}\in X$ and thus finally $y_{1}\in X\leftrightarrow y_{2}\in X$.

###### Corollary 3.19

Let $S$ be an hyperplane of $\mathbb{R}^{n}$ with underlying vector subspace
$V$, and let $x\in S$ be non-singular. If $\text{Str}_{X}(x)\setminus V$ is
nonempty then $\text{Str}_{(X,S)}(x)=\text{Str}_{X}(x)\cap V$.

####  3.2.2 Relativization of the $\sim$-relation

###### Lemma 3.20

Let $S$ be an hyperplane of $\mathbb{R}^{n}$, $y,z\in S$, and $v\neq\\{0\\}$
be a common $X-$stratum of $y,z$ not parallel to $S$. If $y\sim_{(X,S)}z$ then
$y\sim_{X}z$.

###### Proof 3.21

Assume $y\sim_{(X,S)}z$, and let $r>0$ be $(X,S)-$ and $X-$ safe both for $y$
and $z$. Since $v$ is not parallel to $S$, there exists $s>0$ such that for
every $w\in\mathbb{R}^{n}$ with $|w|<s$, the intersection point of
$L_{v}(y+w)$ (resp. $L_{v}(z+w)$) and $S$ exists because $\dim(S)=n-1$ and
belongs to $B(y,r)$ (resp. $B(z,r)$). It suffices to show that $y+w\in
X\leftrightarrow z+w\in X$. Let $y+w^{\prime}$ be the intersection point of
$L_{v}(y+w)$ and $S$.

By our hypothesis on $s$, $y+w^{\prime}$ belongs to $B(y,r)$. Moreover $r$ is
$X-$safe for $y$, $v\in\text{Str}_{X}(y)$, and $w^{\prime}-w$ is parallel to
$v$, therefore $y+w\in X\leftrightarrow y+w^{\prime}\in X$. Similarly we have
$z+w\in X\leftrightarrow z+w^{\prime}\in X$. Now $|w^{\prime}|<r$, thus by our
assumptions $y\sim_{(X,S)}z$ we have $y+w^{\prime}\in X\leftrightarrow
z+w^{\prime}\in X$ and therefore $y+w\in X\leftrightarrow z+w\in X$.

Next we consider a particular case for $S$ which plays a crucial role in
expressing the characterisation stated in the main theorem. It is also a tool
for reasoning by induction in Section 4.3.

###### Definition 3.22

Given an index $0\leq i<n$ and a real $c\in\mathbb{R}$ consider the hyperplane

$H=\mathbb{R}^{i}\times\\{c\\}\times\mathbb{R}^{n-i-1}.$

The intersection $X\cap H$ is called a _section_ of $X$. It is a _rational
section_ if $c$ is a rational number. We define
$\pi_{H}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n-1}$ as
$\pi_{H}(x_{1},\dots,x_{n})=(x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n})$.

The following facts are easy consequences of the above definitions: for all
$x,y\in H$ and $v$ a vector parallel to $H$ we have:

  1. 1.

$x\sim_{(X,H)}y$ if and only if $\pi_{H}(x)\sim_{\pi_{H}(X)}\pi_{H}(y)$

  2. 2.

$v\in\text{Str}_{(X,H)}(x)$ if and only if
$\pi_{H}(v)\in\text{Str}_{\pi_{H}(X)}(\pi_{H}(x))$. In particular $x$ is
$(X,H)-$singular if and only if $\pi_{H}(x)$ is $\pi_{H}(X)-$singular.

###  3.3 Intersection of lines and equivalence classes

In this section we describe the intersection of a $\sim$-class $E$ with a line
parallel to some $v\in\text{Str}{(}E)$. It relies on the notion of adjacency
of $\sim$-classes.

###### Definition 3.23

Let $E$ be a nonsingular $\sim$\- class and let $v$ be one of its strata. A
point $x$ is $v-$_adjacent_ _to_ $E$ if there exists $\epsilon>0$ such that
for all $0<\alpha\leq\epsilon$ we have $x+\alpha v\in E$.

###### Example 3.24

(Example 3.2 continued) We specify Example 3.2 by choosing the square as the
unit square with vertices $(0,0),(0,1),(1,0)$ and $(1,1)$. All elements of the
bottom open edge of the square belong to the same $\sim$-class $E$. The vector
$v=(1,0)$ is a stratum of $E$. The vertex $(0,0)$ is $v-$adjacent to $E$.
Similarly every element of $E$ is also $v-$adjacent to $E$. However the vertex
$(1,0)$ is not $v-$adjacent to $E$ (but it is $(-v)-$adjacent to $E$).

The notion of adjacency is a property of the $\sim$-class.

###### Lemma 3.25

[2, Lemma 5.2] Let $F$ be a $\sim$-class.

  1. 1.

For all $x,y\in F$, all nonzero vectors $v$ and all $\sim$-classes $E$, $x$ is
$v$-adjacent to $E$ if and only if $y$ is $v$-adjacent to $E$.

  2. 2.

For each vector $v$ there exists a most one $\sim$-class $E$ such that $F$ is
$v$-adjacent to $E$.

Consequently, if for some $x\in F$ and some vector $v$, $x$ is $v$-adjacent to
$E$ it makes sense to say that the class $F$ is $v$-adjacent to $E$.

###### Lemma 3.26

[2, Corollary 5.6] Let $x\in\mathbb{R}^{n}$ be non-singular,
$E={\mathcal{C}l}(x)$ and let $v\in\text{\em Str}{(}x)\setminus\\{0\\}$. The
set $L_{v}(x)\cap E$ is a union of disjoint open segments (possibly infinite
in one or both directions) of $L_{v}(x)$, i.e., of the form $(y-\alpha
v,y+\beta v)$ with $0<\alpha,\beta\leq\infty$ and $y\in E$.

If $\alpha<\infty$ (resp. $\beta<\infty$) then the point $y-\alpha v$ (resp.
$y+\beta v$) belongs to a $\sim$-class $F\not=E$ such that
$\text{dim}(F)<\text{dim}(E)$ and $F$ is $v$-adjacent (resp. $(-v)-$adjacent)
(or simply _adjacent_ when $v$ is understood) to $E$.

##  4 Characterizations of $\langle\mathbb{R},+,<,1\rangle$-definable
relations

###  4.1 Characterization in
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations

We recall our previous characterization of
$\langle\mathbb{R},+,<,1\rangle$-definable among
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations.

###### Theorem 4.1

[2, Theorem 6.1] Let $n\geq 1$ and let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable. Then $X$ is
$\langle{\mathbb{R},+,<,1}\rangle$-definable if and only if the following two
conditions hold

(FSP) There exist only finitely many $X-$singular points.

(DS) Every rational section of $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable.

The necessity of condition (FSP) is proved by Proposition 4.6 of [2] and that
of (DS) is trivial since a rational section is the intersection of two
$\langle\mathbb{R},+,<,1\rangle$-definable relations. The proof that
conditions (FSP) and (DS) are sufficient uses several properties of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations which are listed
in the form of a proposition below.

###### Proposition 4.2

Let $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable. The following holds.

(RSP) The components of the $X$-singular points are rational numbers [2,
Proposition 4.6].

(FI) The equivalence relation $\sim$ has finite index and thus the number of
different vector spaces $\text{\em Str}{(}x)$ is finite when $x$ runs over
$\mathbb{R}^{n}$ [2, Corollary 4.5].

(RB) For all nonsingular points $x$, the vector space $\text{Str}{(}x)$ has a
rational basis in the sense that it can be generated by a set of vectors with
rational components [2, Proposition 4.7].

###  4.2 Characterization in arbitrary relations

Now we aim to characterize $\langle\mathbb{R},+,<,1\rangle$-definability for
an arbitrary relation $X\subseteq\mathbb{R}^{n}$. We prove that the conditions
(FSP),(DS),(RSP) are sufficient, i.e., compared to Theorem 4.1 one can remove
the condition “$X$ is $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable” and
add condition (RSP).

###### Theorem 4.3

Let $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$. Then $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable if and only if it satisfies the
three conditions (FSP), (DS), (RSP)

(FSP) It has only finitely many singular points.

(DS) Every rational section of $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable.

(RSP) Every singular point has rational components.

Observe that the three conditions are needed, as shown by the following
relations which are not $\langle\mathbb{R},+,<,1\rangle$-definable.

  * •

Consider the binary relation $X=\\{(x,x)\ |\ x\in\mathbb{Z}\\}$. The singular
elements of $X$ are precisely the elements of $X$, thus $X$ satisfies (RSP)
but not (FSP). It satisfies (DS) because every rational section of $X$ is
either empty or equal to the singleton $\\{(x,x)\\}$ for some
$x\in\mathbb{Z}$, thus it is $\langle\mathbb{R},+,<,1\rangle$-definable.

  * •

The binary relation $X=\mathbb{R}\times\mathbb{Z}$ has no singular point thus
it satisfies (FSP) and (RSP). However it does not satisfy (DS) since, e.g.,
the rational section $\\{0\\}\times\mathbb{Z}$ is not
$\langle\mathbb{R},+,<,1\rangle$-definable.

  * •

The unary relation $X=\\{\sqrt{2}\\}$ admits $\sqrt{2}$ as unique singular
point, thus it satisfies (FSP) but not (RSP). It satisfies (DS) since every
rational section of $X$ is empty.

Now we prove Theorem 4.3.

###### Proof 4.4

The necessity of the first two conditions is a direct consequence of Theorem
4.1, that of the third condition is due to Proposition 4.2.

Now we turn to the other direction which is the bulk of the proof and we
proceed in two steps. First we show that properties (FSP), (DS) and (RSP)
imply properties (RB) and (FI) (Claims 1 and 2) and then based on these two
properties we show that there exists a
$\langle\mathbb{R},+,<,1\rangle$-formula defining $X$.

###### Claim 1

If $X$ satisfies conditions (FSP), (DS) and (RSP) then it satisfies condition
(RB).

###### Proof 4.5

We prove that for every non-singular point $x\in\mathbb{R}^{n}$,
$\text{Str}{(}x)$ has a rational basis. If $n=1$ this follows from the fact
that for every $x\in\mathbb{R}$ the set $\text{Str}{(}x)$ is either equal to
$\\{0\\}$ or equal to $\mathbb{R}$, thus we assume $n\geq 2$.

For every $i\in\\{1,\ldots,n\\}$ let
$H_{i}=\\{(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}\mid x_{i}=0\\}$. Let us call
_rational $i-$hyperplane_ any hyperplane $S$ of the form
$S=\\{(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}\mid x_{i}=c\\}$ where
$c\in\mathbb{Q}$. The underlying vector space of $S$ is $H_{i}$.

Let $x$ be a $d-$point with $d\geq 1$, i.e., a point for which
$V=\text{Str}{(}x)$ has dimension $d$. For $d=n$ the result is obvious. For
$1\leq d<n$ we prove the result by induction on $d$.

Case $d=1$: It suffices to show that every $1-$point $x$ has a stratum in
$\mathbb{Q}^{n}$. Let $v\in\text{Str}{(}x)\setminus\\{0\\}$, and let $r>0$ be
safe for $x$. We can find $i\in\\{1,\dots,n\\}$ and two distinct rational
$i-$hyperplanes $S_{1}$ and $S_{2}$, not parallel to $v$, such that $L_{v}(x)$
intersects $S_{1}$ (resp. $S_{2}$) inside $B(x,r)$, say at some point $y_{1}$
(resp. $y_{2}$). By Lemma 3.13 we have $y_{1}\sim x$. By Corollary 3.19 it
follows that

$\text{Str}_{(X,S_{1})}(y_{1})=\text{Str}_{X}(y_{1})\cap
H_{i}=\text{Str}_{X}(x)\cap H_{i}$

and the rightmost expression is reduced to $\\{0\\}$ since $d=1$ and $v\not\in
H_{i}$. This implies that $y_{1}$ is $(X,S_{1})-$singular, i.e., that
$\pi_{S_{1}}(y_{1})$ is $\pi_{S_{1}}(X)-$singular. Similarly $y_{2}$ is
$(X,S_{2})-$singular, i.e., $\pi_{S_{2}}(y_{2})$ is $\pi_{S_{2}}(X)-$singular.

By condition (DS) the rational sections $X\cap S_{1}$ (resp. $X\cap S_{2}$)
are $\langle\mathbb{R},+,<,1\rangle$-definable, thus the $(n-1)-$ary relations
$\pi_{S_{1}}(X)$ (resp. $\pi_{S_{2}}(X)$) are also
$\langle\mathbb{R},+,<,1\rangle$-definable, and by our hypothesis (RSP) this
implies that $\pi_{S}(y_{1})$ (resp. $\pi_{S}(y_{2})$) has rational
components. Thus the same holds for $y_{1}$ and $y_{2}$, and also for
$y_{1}-y_{2}$, and the result follows from the fact that
$y_{1}-y_{2}\in\text{Str}_{X}(x)$.

Case $2\leq d<n$: Let $I\subseteq\\{1,\dots,n\\}$ denote the set of indices
$i$ such that $V\not\subseteq H_{i}$. We have
$V\subseteq\bigcap_{i\in\\{1,\dots,n\\}\setminus I}H_{i}$ thus $\dim(V)\leq
n-(n-|I|)=|I|$, and it follows from our assumption $\dim(V)=d\geq 2$ that
$|I|\geq 2$.

Now we prove that $V=\sum_{i\in I}(V\cap H_{i})$. It suffices to prove
$V\subseteq\sum_{i\in I}(V\cap H_{i})$, and this in turn amounts to prove that
$\dim(\sum_{i\in I}(V\cap H_{i}))=d$. For every $1\leq i\leq n$ we have

$\dim(V+H_{i})=\dim(V)+\dim(H_{i})-\dim(V\cap H_{i}).$

Now if $i\in I$ then $\dim(V+H_{i})>\dim(H_{i})$, i.e., $\dim(V+H_{i})=n$,
which leads to $\dim(V\cap H_{i})=d+(n-1)-n=d-1$. Thus, in order to prove
$\dim(\sum_{i\in I}(V\cap H_{i}))=d$ it suffices to show that there exist
$i,j\in I$ such that $V\cap H_{i}\neq V\cap H_{j}$. Assume for a contradiction
that for all $i,j\in I$ we have $V\cap H_{i}=V\cap H_{j}$. Then for every
$i\in I$ we have

$V\cap H_{i}=V\cap\bigcap_{j\in I}{H_{j}}\subseteq\bigcap_{j\not\in
I}{H_{j}}\cap\bigcap_{j\in I}H_{j}=\\{0\\}$

which contradicts the fact that $\dim(V\cap H_{i})=d-1\geq 1$.

We proved that $V=\sum_{i\in I}(V\cap H_{i})$, thus it suffices to prove that
for every $i\in I$, $V\cap H_{i}$ has a rational basis. Let $v$ be an element
of $V\setminus H_{i}$, and let $r$ be safe for $x$. We can find a rational
$i-$hyperplane $S$ not parallel to $v$ and such that the intersection point of
$S$ and $L_{v}(x)$, say $y$, belongs to $B(x,r)$. By Lemma 3.13 (applied to
$z=x$) we have $y\sim x$. Corollary 3.19 then implies

$\text{Str}_{(X,S)}(y)=\text{Str}_{X}(y)\cap H_{i}=\text{Str}_{X}(x)\cap
H_{i}=V\cap H_{i}$

which yields

$\text{Str}_{\pi_{S}(X)}(y)=\pi_{S}(V\cap H_{i}).$

Now by condition (DS), $X\cap S$ is
$\langle\mathbb{R},+,<,1\rangle$-definable, and $\pi_{S}(X)$ as well.
Therefore by Proposition 4.2 applied to $X\cap S$, the relation $X\cap S$
satisfies (RB) thus $\pi_{S}(V\cap H_{i})$ has a rational basis, and this
implies that $V\cap H_{i}$ also has a rational basis.

###### Claim 2

If $X$ satisfies conditions (FSP), (DS) and (RSP) then it satisfies condition
(FI).

###### Proof 4.6

Before proving the claim we need a simple definition.

###### Definition 4.7

Given $X\subseteq\mathbb{R}^{n}$ and a $\sim$-class $E$, we define the
_isolated part of $E$_ as the subset

$Z=\\{x\in E\ |\ L_{v}(x)\subseteq E\text{ for all nonzero vectors
}v\in\text{Str}{(}E)\\}.$

A subset of $\mathbb{R}^{n}$ is $X$-_isolated_ (or simply _isolated_ when $X$
is understood) if it is equal to the isolated part of some $\sim$-class.

###### Example 4.8

Let $X\subseteq\mathbb{R}^{2}$ be defined as $X=L_{1}\cup L_{2}$ where $L_{1}$
denotes the horizontal axis and $L_{2}$ denotes the open half-line
$L_{2}=\\{(x_{1},x_{2})\ |\ x_{2}=1\text{ and }x_{1}>0\\}$. In this case there
are three $\sim$-classes, namely $E_{1}=X$, $E_{2}=\\{(0,1)\\}$ and
$E_{3}=\mathbb{R}^{2}\setminus(E_{1}\cup E_{2})$. Let us describe the isolated
part for each of these $\sim$-classes. A point belongs to the isolated part of
a $\sim$-class if whatever stratum is chosen, all points in the direction are
trapped in the class. For instance for the $\sim$-class $E_{1}=X$, we can show
that the isolated part is obtained by deletion of the half-line $L_{2}$ of
$X$, whose points are clearly not trapped. Indeed the subspace
$\text{Str}{(}E_{1})$ is generated by the vector $(1,0)$. Therefore for every
$v\in\text{Str}{(}E_{1})$, if $x\in L_{1}$ then $L_{v}(x)=L_{1}\subseteq
E_{1}$, and if $x\in L_{2}$ then the line $L_{v}(x)$ intersects $E_{2}$ thus
$L_{v}(x)\not\subseteq E_{1}$. This shows the isolated part of $E_{1}$ is
equal to $L_{1}$. The $\sim$-class $E_{2}$ has dimension $0$ thus obviously it
is equal to its isolated part. Finally the isolated part of $E_{3}$ is empty
since the vector $v=(0,1)$ is a stratum of $E_{3}$ and for every $x\in E_{3}$
the line $L_{v}(x)$ intersects $E_{1}$.

###### Lemma 4.9

Let $X\subseteq\mathbb{R}^{n}$ satisfy (FSP), (DS) and (RSP). We have

  1. 1.

Let $E$ be a $\sim$-class and $Z$ be its isolated part. Then $Z$ is a finite
union of affine subspaces with underlying vector subspace $\text{Str}{(}E)$
each containing a point with rational components.

  2. 2.

There exist finitely many isolated subsets.

###### Proof 4.10

By induction on $n$. For $n=1$ if $X$ is equal to $\mathbb{R}$ or to the empty
set, the only isolated set is $X$ and it obviously satisfies $(1)$. Otherwise
a nonempty isolated set $Z$ consists of equivalent points of a $\sim$-class of
dimension $0$, i.e., it is a union of singular points. Now by (FSP) and (DS)
there exist finitely many such points and they have rational components, which
implies $(1)$ and $(2)$.

Now let $n\geq 1$. All isolated sets $Z$ included in a $\sim$-class $E$ of
dimension $0$ satisfy $(1)$, and moreover there are finitely many such sets
$Z$. Thus it suffices to consider the case where $Z\neq\emptyset$ and
$\text{Str}{(}E)\neq\\{0\\}$.

Let $v\in\text{Str}{(}E)\setminus\\{0\\}$ and let $i\in\\{1,\ldots,n\\}$ be
such that $v\not\in H_{i}$. For every $z\in Z$ we have $L_{v}(z)\subseteq Z$,
thus $Z$ intersects the hyperplane $H_{i}$. All elements of $Z\cap H_{i}$ are
$\sim_{X}$-equivalent thus they are also $\sim_{(X,H_{i})}$-equivalent.
Furthermore for every $x\in Z\cap H_{i}$ we have
$\text{Str}_{(X,H_{i})}(x)=\text{Str}_{X}(x)\cap H_{i}$ by Corollary 3.19 and
thus for every $w\in\text{Str}_{X}(x)\cap H_{i}$ we have $L_{w}(x)\subseteq
Z\cap H_{i}$. This shows that $\pi_{H_{i}}(x)$ belongs to a
$\pi_{H_{i}}(X)-$isolated set, hence $\pi_{H_{i}}(Z)$ is included in a
$\pi_{H_{i}}(X)-$isolated set, say $W\subseteq\pi_{H_{i}}(H_{i})$.

Now by condition (DS) the set $\pi_{H_{i}}(X)$ is
$\langle\mathbb{R},+,<,1\rangle$-definable, thus by Theorem 4.1 it satisfies
also (FSP). By our induction hypothesis it follows that $W$ can be written as
$W=\bigcup^{p}_{j=1}W_{j}$, where either all $W_{j}$’s are parallel affine
subspaces with underlying vector space $\pi_{H_{i}}(\text{Str}{(}E))$ each
containing some point with rational components (by $(1)$), or each $W_{j}$ is
reduced to a point with rational components (by $(1)$). Every $W_{j}$ which
intersects $\pi_{H_{i}}(Z)$ satisfies $W_{j}\subseteq\pi_{H_{i}}(Z)$, which
shows that $\pi_{H_{i}}(Z)=\bigcup_{j\in J}W_{j}$ for some
$J\subseteq\\{1,\dots,p\\}$. That is, we have $Z\cap H_{i}=\bigcup_{j\in
J}W^{\prime}_{j}$ where each $W^{\prime}_{j}=\pi^{-1}_{H_{i}}(W_{j})$. Observe
that if $x$ belongs to $W_{j}$ and has rational components then the point
$x^{\prime}=\pi^{-1}_{H_{i}}(x)$ also has rational components. Now $Z=(Z\cap
H_{i})+\text{Str}{(}E)$ thus $Z=\bigcup_{j\in
J}(W^{\prime}_{j}+\text{Str}{(}E))$. Since the underlying vector space of each
$W^{\prime}_{j}$ is included in $\text{Str}{(}E)$, this proves $(1)$.

Concerning $(2)$ we observe that $Z$ is completely determined by $Z\cap
H_{i}$, i.e., $\pi_{H_{i}}(Z)$. By our induction hypothesis there are finitely
many $\pi_{H_{i}}(X)-$isolated parts $W=\bigcup^{p}_{j=1}W_{j}$ and each
$X$-isolated part is determined by a subset of the form $\bigcup_{j\in
J}W_{j}$ for some $J\subseteq\\{1,\dots,p\\}$. This proves point $(2)$.

Now we turn to the proof of Claim 2. Lemma 4.9 shows that the number of
$\sim$-classes having a nonempty isolated part is finite. It thus suffices to
prove that for every $0\leq d\leq n$ there exist finitely many $d$-classes $E$
having an empty isolated part.

For $d=0$ the result follows from $(FSP)$ and the fact that each $0-$class is
a union of singular points. For $d=n$ there exist at most two $d-$classes,
which correspond to elements in the interior of $X$ or the interior of its
complement.

For $0\leq d<n$ we reason by induction on $d$. Observe first that if a
$\sim$-class $E$ has dimension $d$ and has an empty isolated part, then there
exist $x\in E$ and $v\in\text{Str}{(}E)\setminus\\{0\\}$ such that
$L_{v}(x)\not\subseteq E$. By Lemma 3.26 this implies that there exist $y\in
L_{v}(x)$ and a $\sim$-class $F$ such that $y\in F$, $F$ is adjacent to $E$,
$\dim(F)<\dim(E)$, and $[x,y)\subseteq{\mathcal{C}l}(x)$. Now by our induction
hypothesis there exist finitely many $\sim$-classes with dimension less than
$d$. Thus in order to prove the claim, it suffices to show that there are
finitely many $d$-classes to which some $d^{\prime}$-class with $d^{\prime}<d$
is adjacent.

In order to meet a contradiction, assume that there exists a
$d^{\prime}-$class $F$ which is adjacent to infinitely many $d$-classes, say
$E_{j}$ with $j\in J$. We may furthermore assume that for each class $E_{j}$
there is no integer $d^{\prime}<d^{\prime\prime}<d$ such that some
$d^{\prime\prime}$-class is adjacent to $E_{j}$. Because of Lemma 3.25 it is
enough to fix an element $y$ in $F$ and investigate the classes to which it is
adjacent.

We first consider the case $d^{\prime}=0$.

Because of condition (FSP), for some real $s>0$ the point $y$ is the unique
singular point in $B(y,s)$. Moreover for every $j\in J$, $F$ is adjacent to
$E_{j}$, thus there exists a point $x_{j}\in E_{j}$ such that
$[x_{j},y)\subseteq E_{j}$. Let $\mathit{HL}_{j}$ denote the open halfline
with endpoint $y$ and containing $x_{j}$. Observe that we necessarily have
$\mathit{HL}_{j}\cap B(y,s)\subseteq{\mathcal{C}l}(x_{j})$. Indeed, by Lemma
3.26 the condition $\mathit{HL}_{j}\cap B(y,s)\subsetneq{\mathcal{C}l}(x_{j})$
implies that there exists a point $z=y+\alpha(x_{j}-y)\in B(y,s)$ such that
$\alpha>1$ and $\text{dim}(z)<d$. Since $y$ is the unique singular point in
$B(y,s)$ this implies $\text{dim}(z)>0$ but then because of
$[x_{j},z)\subseteq{\mathcal{C}l}(x_{j})$ the maximality condition stipulated
for $d^{\prime}$ is violated.

Let $z_{j}$ be the point on $\mathit{HL}_{j}$ at distance $\frac{s}{2}$ from
$y$ and let $z$ be adherent to the set $\\{z_{j}\ |\ j\in J\\}$. The point $z$
is nonsingular since $y$ is the unique singular point in the ball $B(y,s)$.
Let $v\in\text{Str}{(}z)\setminus\\{0\\}$. Consider some
$\ell\in\\{1,\ldots,n\\}$, some rational $\ell-$hyperplane $S$ such that
$z\not\in S$ and some real $0<t<\frac{s}{2}$ such that $L_{v}(B(z,t))\cap
S\subseteq B(z,\frac{s}{2})$. The ball $B(z,t)$ contains infinitely many non
$\sim$-equivalent points, and by Lemma 3.20 their projections on $S$ in the
direction $v$ are non $\sim_{(X,S)}$-equivalent. But by condition (DS) the
relation $X\cap S$ is $\langle\mathbb{R},+,<,1\rangle$-definable, thus
$\pi_{S}(X)$ satisfies condition (FI) of Proposition 4.2, a contradiction.

Now we consider the case where $d^{\prime}>0$.

Choose some $v\in\text{Str}{(}y)$ and let $r$ be a safe radius for $y$. We can
find $0<s<r$, $k\in\\{1,\dots,n\\}$ and some $k-$hyperplane $S$ not parallel
to $v$ such that $L_{v}(B(y,s))\cap S\subseteq B(y,r)$. By definition of $y$,
$B(y,s)$ intersects infinitely many pairwise distinct $d-$classes. Given two
non $\sim$-equivalent $d$-points $z_{1},z_{2}\in B(y,s)$, and their respective
projections $w_{1},w_{2}$ over $S$ along the direction $v$, we have
$w_{1}\not\sim_{(X,S)}w_{2}$ by Lemma 3.20. This implies that there exist
infinitely many $\sim_{(X,S)}$-classes. However by condition (DS), the
relation $X\cap S$ is $\langle\mathbb{R},+,<,1\rangle$-definable, thus
$\pi_{S}(X)$ satisfies condition (FI) of Proposition 4.2, a contradiction.

Now we turn to the proof of Theorem 4.3. Observe that $X$ is equal to the
union of $\sim$-classes of its elements, thus by Claim 2, in order to prove
that $X$ is $\langle\mathbb{R},+,<,1\rangle$-definable it suffices to prove
that all $\sim_{X}$-classes are $\langle\mathbb{R},+,<,1\rangle$-definable.
More precisely, we prove that each $\sim$-class $E$ is definable from
$\sim$-classes $F$ with smaller dimension, i.e., that $E$ is definable in the
expansion of $\langle\mathbb{R},+,<,1\rangle$ obtained by adding a predicate
for each such $F$. We proceed by induction on the dimension $d$ of
$\text{Str}{(}E)$.

If $d=0$ then $E$ is a union of singular points, and by (FSP) and (RSP) it
follows that $E$ is a finite subset of $\mathbb{Q}^{n}$ thus is
$\langle\mathbb{R},+,<,1\rangle$-definable.

Assume now $0<d\leq n$. By Claim 1 there exists a rational basis
$V(E)=\\{v_{1},\dots,v_{d}\\}$ of $\text{Str}{(}E)$. Let $Z\subseteq E$ be the
isolated part of $E$ and let $E^{\prime}=E\setminus Z$. By Lemma 4.9 $(1)$,
$Z$ is a finite union of parallel affine subspaces with underlying vector
space $V(E)$ each containing a point with rational components, thus $Z$ is
$\langle\mathbb{R},+,<,1\rangle$-definable. It remains to prove that
$E^{\prime}$ is $\langle\mathbb{R},+,<,1\rangle$-definable. We use the
following characterization of $E^{\prime}$.

###### Lemma 4.11

For every $x\in\mathbb{R}^{n}$, we have $x\in E^{\prime}$ if and only if there
exist $1\leq p\leq d$ and a sequence of pairwise distinct elements
$x_{0},\dots,x_{p}\in\mathbb{R}^{n}$ such that $x_{0}=x$ and

  1. 1.

for every $0\leq k\leq p-1$, $x_{k+1}-x_{k}\in V(E)$ and $[x_{k},x_{k+1})$
does not intersect any $\sim$-class of strictly smaller dimension than
$\dim(E)$

  2. 2.

if $F={\mathcal{C}l}(x_{p})$ then $F$ is $(x_{p-1}-x_{p})$-adjacent to $E$ and
$\dim(F)<\dim(E)$.

###### Proof 4.12

We first prove that the conditions are sufficient. We prove by backward
induction that $[x_{k},x_{k+1})\subseteq E$ for every $0\leq k\leq p-1$. This
will imply that $x=x_{0}\in E$, and the fact that $x_{p}-x$ belongs to
$\text{Str}{(}E)$ and $\dim(F)<\dim(E)$ will lead to $x\in E^{\prime}$. Set
$k=p-1$. By Point 2 of Lemma 3.25 the element $x_{p}$ is
$(x_{p-1}-x_{p})$-adjacent to $E$, thus $[x_{p-1},x_{p})$ intersects $E$.
Moreover $[x_{p-1},x_{p})$ does not intersect any $\sim$-class $G$ such that
$\dim(G)<\dim(E)$, thus by Lemma 3.26 we have $[x_{p-1},x_{p})\subseteq E$.
For $0\leq k<p-1$, by our induction hypothesis we have $x_{k+1}\in E$.
Moreover $[x_{k},x_{k+1})$ does not intersect any $\sim$-class $G$ such that
$\dim(G)<\dim(E)$, thus $[x_{k},x_{k+1})\subseteq E$ again by Lemma 3.26.

We prove the necessity. By definition of $E^{\prime}$ and Lemma 3.26 there
exist $v\in\text{Str}{(E)}$ and $y\in L_{v}(x)$ such that $[x,y)\subseteq E$
and $y\not\in E$. Decompose $v=\alpha_{1}v_{i_{1}}+\cdots+\alpha_{p}v_{i_{p}}$
where $0<i_{1}<\cdots<i_{p}\leq d$ and $\alpha_{1},\cdots,\alpha_{p}\not=0$.
We can assume w.l.o.g that $y$ is chosen such that $p$ is minimal and
furthermore that $\alpha_{p}$ is minimal too. For $0\leq k<p$ set
$x_{k}=x+\alpha_{1}v_{i_{1}}+\cdots+\alpha_{k}v_{i_{k}}$. By minimality of $p$
and $\alpha_{p}$, the segments $[x_{0},x_{1}),\ldots,[x_{p-1},x_{p})$
intersect no class of dimension less than $\dim(E)$. Then $y=x_{p}$ is
$(x_{p-1}-x_{p})$-adjacent to $E$.

In order to prove that $E^{\prime}$ is
$\langle\mathbb{R},+,<,1\rangle$-definable it suffices to show that we can
express in $\langle\mathbb{R},+,<,1\rangle$ the existence of a sequence
$x_{0},\dots,x_{p}\in\mathbb{R}^{n}$ which satisfies both conditions of Lemma
4.11. Observe that $V(E)$ is finite and each of its element is
$\langle\mathbb{R},+,<,1\rangle$-definable, thus we can express in
$\langle\mathbb{R},+,<,1\rangle$ the fact that a segment is parallel to some
element of $V(E)$. Moreover by (FI) there exist finitely many $\sim$-classes
$F$ such that $\dim(F)<\dim(E)$, and all such classes are
$\langle\mathbb{R},+,<,1\rangle$-definable by our induction hypothesis. This
allows us to express condition $(1)$ in $\langle\mathbb{R},+,<,1\rangle$. For
$(2)$ we use again the fact that there are only finitely many classes $F$ to
consider and that all of them are $\langle\mathbb{R},+,<,1\rangle$-definable.

###  4.3 An alternative noneffective formulation.

In this section we re-formulate Theorem 4.3 in terms of (generalized)
projections of $X$ by building on the notion of generalized section which
extends that of section, in the sense that it allows us to fix several
components.

###### Definition 4.13

Given $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$, a generalized section of $X$
is a relation of the form

$X_{s,a}=\\{(x_{1},\ldots,x_{n})\in X\mid
x_{s_{1}}=a_{{1}},\ldots,x_{s_{r}}=a_{{r}}\\}$ (3)

where $r>0$, $s=(s_{1},\dots,s_{r})$ is an $r-$tuple of integers with $1\leq
s_{1}<\cdots<s_{r}\leq n$, and $a=(a_{{1}}.\ldots,a_{{r}})$ is an $r-$tuple of
reals. When $r=0$ we define $X_{s,a}=X$ by convention, i.e., $X$ is a
generalized section of itself. If $r>0$ then the section is said to be proper.
If all elements of $a$ are rational numbers then $X_{s,a}$ is called a
rational generalized section of $X$.

In the above definition, each $X_{s,a}$ is a subset of $\mathbb{R}^{n}$. If we
remove the $r$ fixed components $x_{s_{1}},\ldots,x_{s_{r}}$ we can see
$X_{s,a}$ as a subset of $\mathbb{R}^{n-r}$, which will be called a
generalized projection of $X$ (resp. a rational generalized projection of $X$
if $X_{s,a}$ is a rational generalized section of $X$).

###### Proposition 4.14

For every $n\geq 1$, a relation $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,1\rangle$-definable if and only if every rational
generalized projection of $X$ has finitely many singular points and these
points have rational components.

###### Proof 4.15

The proof goes by induction on $n$. The case $n=1$ is obvious. Assume now
$n>1$.

Let $X$ be $\langle\mathbb{R},+,<,1\rangle$-definable and let $Y$ be a
rational generalized projection of $X$. If $Y=X$ then the result follows from
Theorem 4.3. If $Y$ is proper then $Y$ is definable in
$\langle{\mathbb{R},+,<,1,X}\rangle$ thus it is also
$\langle\mathbb{R},+,<,1\rangle$-definable, and the result follows from our
induction hypothesis.

Conversely assume that every rational generalized projection of $X$ has
finitely many singular points and they have rational components. We show that
$X$ satisfies all three conditions of Theorem 4.3. Conditions (FSP) and (RSP)
follow from our hypothesis and the fact that $X$ is a rational generalized
projection of itself. It remains to prove condition (DS) namely that every
rational section of $X$ is $\langle\mathbb{R},+,<,1\rangle$-definable. This
amounts to proving that every rational projection $Z$ of $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable. Now every generalized projection
$Y$ of $Z$ is also a generalized projection of $X$, thus by our induction
hypothesis $Y$ has finitely many singular points and they have rational
components. Since $Z$ is a proper projection of $X$, by our induction
hypothesis it follows that $Z$ is $\langle\mathbb{R},+,<,1\rangle$-definable.

##  5 A definable criterion for $\langle\mathbb{R},+,<,1\rangle$-definability
in suitable structures

In this section we prove that for every $n\geq 1$ and
$X\subseteq\mathbb{R}^{n}$, if every nonempty
$\langle\mathbb{R},+,<,1,X\rangle$-definable relation contains a point with
rational components then we can state a variant of Proposition 4.14 which is
expressible in $\langle\mathbb{R},+,<,1,X\rangle$. This means that there
exists a $\langle\mathbb{R},+,<,1,X\rangle$-sentence (uniform in $X$) which
expresses the fact that $X$ is $\langle\mathbb{R},+,<,1\rangle$-definable.
This provides a _definable_ criterion for
$\langle\mathbb{R},+,<,1\rangle$-definability, similar to Muchnik’s result
[18] for definability in Presburger Arithmetic. We also extend these ideas to
the case of $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability.

In this section ${\mathcal{S}_{X}}$ stands for the structure
$\langle\mathbb{R},+,<,1,X\rangle$.

###  5.1 Quasi-singular points

We aim to express $\langle\mathbb{R},+,<,1\rangle$-definability of a relation
$X\subseteq\mathbb{R}^{n}$ in the structure ${\mathcal{S}_{X}}$ itself. A
natural approach is to express the conditions of Proposition 4.14 as an
${\mathcal{S}_{X}}$-sentence, however the formulation involves the set
$\mathbb{Q}$ as well as the set of $X$-singular elements. On the one hand
$\mathbb{Q}$ is not necessarily ${\mathcal{S}_{X}}$-definable, and on the
other hand the naive definition of $X-$singularity involves the operation of
multiplication which is also not necessarily ${\mathcal{S}_{X}}$-definable.
For the special case where $X$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable, we introduced in [2,
Lemma 4.9] an ad hoc definition. Yet this definition does not necessarily hold
when the relation $X$ is no longer assumed to be
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable. In order to overcome this
difficulty we introduce a weaker property but that is still definable in
${\mathcal{S}_{X}}$. This proves to be sufficient to establish our result.

###### Definition 5.1

Let $X\subseteq\mathbb{R}^{n}$, $x\in\mathbb{R}^{n}$, and $r,s$ be two reals
such that $0<s<r$.

  * •

a vector $v\in\mathbb{R}^{n}$ is an $(r,s)$-_quasi-stratum_ of $x$ if $|v|\leq
s$ and $(y\in X\leftrightarrow y+v\in X)$ holds for all $y\in\mathbb{R}^{n}$
such that $y,y+v\in B(x,r)$.

  * •

We say that $x\in\mathbb{R}^{n}$ is $X-$_quasi-singular_ if it does not
satisfy the following property:

$\begin{array}[]{l}\text{there exist reals }r,s>0\text{ such that the set of
$(r,s)$-{quasi-strata} of $x$ is nonempty, closed, }\\\ \text{and is stable
under }v\mapsto v/2.\vspace*{-6mm}\end{array}$ (4)

It is not difficult to check that if $x$ is not singular and $r$ is safe, then
every stratum of $x$ is an $(r,s)$-quasi-stratum for $0<s<r$. However even for
$r$ safe, there may exist $(r,s)$-quasi-strata of $x$ which are not strata of
$x$, as shown in the following example.

###### Example 5.2

Let $n=2$, $X=(\mathbb{Z}\cup\\{-{3\over 2},-{1\over 2},{1\over 2},{3\over
2}\\})\times\mathbb{R}$, and $x=(0,0)$. Then $\text{\em Str}{(}x)$ is
generated by the vector $(0,1)$, and every real $r>0$ is safe for $x$. Given
$0<s<r$, the $(r,s)$-quasi-strata of $x$ can be characterized as follows:

  * •

if $r>{5\over 2}$ then the $(r,s)$-quasi-strata of $x$ are vectors of the form
$(0,l)$ with $|l|\leq s$ (i.e these are the strata of $x$ with norm at most
$s$).

  * •

if $r\leq{5\over 2}$ then these are vectors of the form $({k\over 2},l)$ where
$k\in\mathbb{Z}$, $k\leq 2r$, and $|({k\over 2},\ell)|\leq s$. Note that for
$s<{1\over 2}$, these are exactly the strata of $x$ with norm at most $s$.

###### Lemma 5.3

Let $X\subseteq\mathbb{R}^{n}$. The set of quasi-singular elements of $X$ is
${\mathcal{S}_{X}}$-definable. Moreover the property “$X$ has finitely many
quasi-singular elements” is ${\mathcal{S}_{X}}$-definable (uniformly in $X$) .

###### Proof 5.4

The property that $v$ is an $(r,s)$-stratum of $x$ can be expressed by the
formula

$\phi(X,x,r,s,v)\equiv 0<|v|<s\wedge\forall y\ (y,y+v\in
B(x,r)\rightarrow(y\in X\leftrightarrow y+v\in X)).$

The set of $X$-quasi-singular elements can be defined by the formula

$\begin{array}[]{ll}QS(x,X)\equiv&\neg\exists r\exists s\
((0<s<r)\wedge\exists v(\phi(X,x,r,s,v))\wedge\\\ &\forall v\
(\phi(X,x,r,s,v)\rightarrow\phi(X,x,r,s,\frac{v}{2}))\wedge\\\ &\forall v\
(((|v|<s)\wedge\forall\epsilon>0(\exists u\
(\phi(X,x,r,s,u)\wedge|v-u|<\epsilon)))\rightarrow\phi(X,x,r,s,v)))\end{array}$
(5)

The finiteness of the set of quasi-singular points can be expressed by the
formula

$\begin{array}[]{ll}FS(X)\equiv&(\exists t>0\ \forall x\
(QS(x,X)\rightarrow|x|<t))\\\ &\wedge(\exists u>0(\forall x\forall
y((QS(x,X)\wedge QS(y,X)\wedge x\not=y)\rightarrow|x-y|>u)))\end{array}$ (6)

###### Lemma 5.5

Let $X\subseteq\mathbb{R}^{n}$. If $x$ is not quasi-singular then for some
reals $0<s<r$ there exists an $(r,s)$-quasi-stratum of $x$ and every
$(r,s)$-quasi-stratum of $x$ is a stratum of $x$.

###### Proof 5.6

In this proof “quasi-stratum” stands for “$(r,s)$-quasi-stratum”. We consider
the negation of $QS$. The matrix of the formula consists of four conjuncts.
The second conjunct asserts that there exists a quasi-stratum. The third
conjunct asserts that if a vector $v$ is a quasi-stratum then for all integers
$p\leq 0$ the vector $2^{p}v$ is a quasi-stratum. Also if $p\geq 0$ and
$|2^{p}v|<s$ then $2^{p}v$ is a quasi-stratum. Indeed, because $B(x,r)$ is
convex, if $y$ and $y+2v$ belong to $B(x,r)$ then $y+v$ belongs to $B(x,r)$
and we have

$y\in X\leftrightarrow y+v\in X\leftrightarrow z=y+2v\in X.$ (7)

This generalizes to any $p\geq 0$ provided $|2^{p}v|<s$.

We will show that if $v$ is quasi-stratum, then it is a stratum, i.e., if
$y,z\in B(x,r)$ and $z\in L_{v}(y)$ then $y\in X\leftrightarrow z\in X$. To
fix ideas set $z=y+2^{\ell}\beta v$ for some real $0<\beta<1$. Let
$\alpha_{q}=\sum_{-q<i<0}a_{i}2^{i}$ with $a_{i}\in\\{0,1\\}$, be a sequence
of dyadic rationals converging to $\beta$. Since $|2^{i}v|<s$ holds for all
$-q<i<0$, every $2^{i}v$ is a quasi-stratum and therefore so is $\alpha_{q}v$.
Arguing as in (7) we see that for all $t,t+\alpha_{q}v\in B(x,r)$ we have
$t\in X\leftrightarrow t+\alpha_{q}v\in X$. Because $\alpha_{q}<1$ this shows
that all $\alpha_{q}v$ are quasi-strata. The last conjunct implies that $\beta
v$ is a quasi-stratum and again using the same argument as in (7) we get

$y\in X\leftrightarrow y+\beta v\in X\leftrightarrow y+2\beta
v\leftrightarrow\cdots\leftrightarrow z=y+2^{\ell}\beta v\in X$

###### Lemma 5.7

For every $X\subseteq\mathbb{R}^{n}$, every $X-$singular element is $X-$quasi-
singular.

###### Proof 5.8

If $x\in\mathbb{R}^{n}$ is not $X-$quasi-singular then there exist $0<s<r$ and
an $(r,s)$-quasi-stratum, which is a stratum by Lemma 5.5.

###### Lemma 5.9

If $X\subseteq\mathbb{R}^{n}$ is $\langle\mathbb{R},+,<,1\rangle$-definable,
every $X-$quasi-singular element is $X-$singular.

###### Proof 5.10

We prove that if $x\in\mathbb{R}^{n}$ is not $X-$singular then it is not
quasi-singular, i.e., that it satisfies $\neg QS(x,X)$, cf. Expression (5). We
find suitable values of $r,s$ such that the set of $(r,s)$-quasi-strata of $x$
coincides with the set of strata $v$ of $x$ such that $|v|\leq s$. The result
will then follow from the fact that $\text{Str}{(}x)$ is a non-trivial vector
subspace.

The relation $X$ is $\langle\mathbb{R},+,<,1\rangle$-definable thus by [2,
Corollary 4.4] there exists $r>0$ such that inside the ball $B(x,r)$, $X$
coincides with a finite collection of cones. By cone we mean an intersection
of open or closed halfspaces delimited by finitely many, say $k$, hyperplanes
of dimension $n-1$ and containing $x$. Without loss of generality we can
assume that $r$ is safe. We show that a suitable value for $s$ is
$s=\frac{1}{k}r$.

Since $r$ is safe, every stratum $v$ of $x$ with $|v|\leq s$ is also an
$(r,s)$-quasi-stratum of $x$. Conversely let $v$ be an $(r,s)$-quasi-stratum
of $x$, and assume for a contradiction that $v\not\in\text{Str}{(}x)$. Then
there exists a point $y\in B(x,r)$ such that the line $L_{v}(y)$ intersects
$X$ and its complement inside $B(x,r)$. Let $h$ be any homothety with ratio
$0<\lambda\leq 1$ centered at $x$ such that the segment $L_{v}(h(y))\cap
B(x,r)$ has length greater than $r$. Then, within $B(x,r)$, the line
$L_{v}(h(y))$ decomposes into $2\leq p\leq k$ segments which are alternatively
inside and outside $X$. One of these segments has length at least
$\frac{1}{p}r\geq s\geq|v|$. We obtain that for some $z\in L_{v}(h(y))$ we
have $z,z+v\in B(x,r)$ and $z\in X\leftrightarrow z+v\not\in X$, which
contradicts our assumption that $v$ is an $(r,s)$-quasi-stratum of $x$.

Note that in Lemma 5.9 the condition that $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable cannot be removed. Consider, e.g.,
$X=\mathbb{R}\times\mathbb{Q}$. Then it can be shown that for all
$x\in\mathbb{R}^{2}$ we cannot find any reals $0<s<r$ for which the set of
$(r,s)$-quasi-strata of $x$ is closed, and this implies that $x$ is $X-$quasi-
singular. However $x$ is not $X-$singular since $(1,0)$ is an $X-$stratum for
$x$.

###  5.2 Alternative characterization of
$\langle\mathbb{R},+,<,1\rangle$-definability in ${\mathcal{S}_{X}}$.

We can state the following variant of Theorem 4.3 for
${\mathcal{S}_{X}}$-definable relations under the hypothesis that all nonempty
${\mathcal{S}_{X}}$-definable relations $Y$ contain a point with rational
components (recall that ${\mathcal{S}_{X}}$ stands for the structure
$\langle\mathbb{R},+,<,1,X\rangle$ where $X$ is some fixed but arbitrary
relation). Observe that this implies that all definable finite subsets $Y$ of
$\mathbb{R}^{n}$ are included in $\mathbb{Q}^{n}$. Indeed, for all points
$y\in Y$ with rational components the set $Y\setminus\\{y\\}$ is
${\mathcal{S}_{X}}$-definable.

###### Proposition 5.11

Let $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$ be such that every nonempty
${\mathcal{S}_{X}}$-definable relation contains a point with rational
components. Then $X$ is $\langle\mathbb{R},+,<,1\rangle$-definable if and only
if every generalized projection of $X$ has finitely many quasi-singular
points.

###### Proof 5.12

We proceed by induction on $n$.

Case $n=1$. Assume first that $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable. The only generalized projection of
$X$ that need to be studied is $X$ itself. Now by Theorem 4.3, $X$ has
finitely many singular points, and by Lemma 5.9 these are precisely its quasi-
singular points.

Conversely assume that every generalized projection of $X$ has finitely many
quasi-singular points. If the generalized projection is not $X$, then it is a
singleton and there is nothing to check. It remains to consider the case where
the projection is equal to $X$. By Lemma 5.7 this implies that $X$ has
finitely many singular points. Now $X\subseteq\mathbb{R}$ thus the set of
$X-$singular points coincides with the topological boundary $Bd(X)$ of $X$. It
follows that $Bd(X)$ is finite, i.e., $X$ is the union of finitely many
intervals. Moreover $Bd(X)$ is ${\mathcal{S}_{X}}$-definable and by our
assumption on ${\mathcal{S}_{X}}$ it follows that $Bd(X)\subseteq\mathbb{Q}$
thus every $X-$singular point is rational. The result follows from Theorem
4.3.

Case $n>1$. Assume first that $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable. The relation satisfies property
(FSP) of Theorem 4.3 and by Lemma 5.9 it has finitely many quasi-singular
points. It thus suffices to consider proper subsets of $X$. Assume without
loss of generality that the projections are obtained by freezing the $0<p\leq
n$ first components. For every $a=(a_{1},\dots,a_{p})\in\mathbb{R}^{p}$,
consider the projection

$X_{a}=\\{(x_{p+1},\dots,x_{n})\in\mathbb{R}^{n-p}\mid(a_{1},\dots,a_{p},x_{p+1},\dots,x_{n})\in
X\\}.$

Consider the set $A$ of elements $a=(a_{1},\dots,a_{p})\in\mathbb{R}^{p}$ such
that the relation $X_{a}$ has infinitely many quasi-singular points. Using
expression (6), the set $A$ is ${\mathcal{S}_{X}}$-definable, thus it is
$\langle\mathbb{R},+,<,1\rangle$-definable because so is $X$. If this set were
nonempty, by Theorem 2.1 it would contain an element of $\mathbb{Q}^{p}$,
which means that there exists a rational generalized projection of $X$ which
has infinitely many quasi-singular points, a contradiction.

Conversely assume that every generalized projection of $X$ has finitely many
quasi-singular points, and let us prove that $X$ satisfies all conditions of
Theorem 4.3. Condition (DS) follows from the fact that every rational section
of $X$ is a generalized projection of $X$ thus is
$\langle\mathbb{R},+,<,1\rangle$-definable by our induction hypothesis. For
conditions (FSP) and (RSP), we observe that $X$ is a generalized projection of
itself thus the set of $X-$quasi-singular points is finite. By Lemma 5.3 this
set is ${\mathcal{S}_{X}}$-definable thus it is a subset of $\mathbb{Q}^{n}$
by our assumption on ${\mathcal{S}_{X}}$, and the result follows from Lemma
5.7.

###  5.3 Defining $\langle\mathbb{R},+,<,1\rangle$-definability

The formulation of conditions in Proposition 5.11 allows us to express
$\langle\mathbb{R},+,<,1\rangle$-definability as a sentence in the structure
${\mathcal{S}_{X}}$ itself.

###### Theorem 5.13

Let $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$ be such that every nonempty
${\mathcal{S}_{X}}$-definable relation contains a point with rational
components. There exists a ${\mathcal{S}_{X}}$-sentence $\Phi_{n}$ (which is
uniform in $X$) which holds in ${\mathcal{S}_{X}}$ if and only if $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable.

###### Proof 5.14

Let $[n]$ denote the set $\\{1,\ldots,n\\}$. By Proposition 5.11 it suffices
to express the fact that every generalized projection of $X$ has finitely many
quasi-singular points. This leads us to consider all possible generalized
projections obtained by freezing a subset $[n]\setminus I$ of components as in
Definition 4.13. Let $\mathbb{R}^{I}$ denote the product of copies of
$\mathbb{R}$ indexed by $I$ and for all $x,y\in\mathbb{R}^{I}$ set
$|x-y|_{I}=|(x+z)-(y+z)|$ for any $z\in\mathbb{R}^{[n]\setminus I}$. For
$x\in\mathbb{R}^{I}$ and $r\geq 0$ set
$B_{I}(x,r)=\\{y\in\mathbb{R}^{I}\mid|x-y|_{I}<r\\}$. We use the pair $(n,I)$
as a parameter for the predicates $\phi,QS,FS$ (see Lemma 5.3). The symbol
$\xi$ stands for the subvector with frozen components (we have
$\xi\in\mathbb{R}^{[n]\setminus I}$). With some abuse of notation we write
$\xi+z$ for $\xi\in\mathbb{R}^{[n]\setminus I}$ and $z\in\mathbb{R}^{I}$, that
is, if $\xi=(\xi_{i})_{i\in\mathbb{R}^{[n]\setminus I}}$ and $z=(z_{i})_{i\in
I}$ then $\xi+z=(w_{1},\dots,w_{n})$ with $w_{i}=z_{i}$ if $i\in I$ and
$w_{i}=\xi_{i}$ otherwise. We can define the predicates $\phi_{n,I}$,
$QS_{n,I}$ and $FS_{n,I}$ as follows:

$\begin{array}[]{ll}\phi_{n,I}(X,\xi,x,r,s,v)\equiv&\xi\in\mathbb{R}^{[n]\setminus
I}\wedge x,v\in\mathbb{R}^{I}\wedge 0<|v|_{I}<s\\\ &\wedge\forall
y\in\mathbb{R}^{I}(y,y+v\in B_{I}(x,r)\rightarrow(\xi+y\in
X\leftrightarrow\xi+y+v\in X))\end{array}$
$\begin{array}[]{ll}QS_{n,I}(x,\xi,X)\equiv&\neg\exists r\exists
s((0<s<r)\wedge\exists v\ (\phi_{n,I}(X,\xi,x,r,s,v))\\\ &\wedge\forall v\
(\phi_{n,I}(X,\xi,x,r,s,v)\rightarrow\phi_{n,I}(X,\xi,x,r,s,\frac{v}{2}))\\\
&\wedge\forall u\ (((|u|_{I}<s)\wedge\forall\epsilon>0(\exists v\
(\phi_{n,I}(X,\xi,x,r,s,v)\wedge|v-u|_{I}<\epsilon)))\\\
&\phantom{xxxxxxxxxxxxxxxxx}\rightarrow\phi_{n,I}(X,\xi,x,r,s,u)))\end{array}$
$\begin{array}[]{ll}FS_{n,I}(X,\xi)\equiv&(\exists t>0\forall x\
(QS_{n,I}(x,\xi,X)\rightarrow|x|_{I}<t)\\\ &\wedge(\exists s>0(\forall
x\forall y((QS_{n,I}(x,\xi,X)\wedge QS_{n,I}(y,\xi,X)\wedge
x\not=y)\rightarrow|x-y|_{I}>s)\end{array}$

This leads to the following definition of $\Phi_{n}$:

$\Phi_{n}\equiv\bigwedge_{I\subseteq[n]}\forall\xi\in\mathbb{R}^{[n]\setminus
I}\ \ FS_{n,I}(X,\xi).$ (8)

###### Remark 5.15

One can prove that Theorem 5.13 does not hold anymore if we remove the
assumption that every nonempty ${\mathcal{S}_{X}}$-definable relation contains
a point with rational components. Indeed consider $n=1$ (the case $n\geq 1$
easily reduces to this case) and a singleton set
$X=\\{x\\}\subseteq\mathbb{R}$. Then by Theorem 2.1, $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable if and only if $x\in\mathbb{Q}$.
Thus if there exists a ${\mathcal{S}_{X}}$-sentence $\Phi_{n}$ which expresses
that $X$ is $\langle\mathbb{R},+,<,1\rangle$-definable, then it is easy to
transform $\Phi_{n}$ into a $\langle\mathbb{R},+,<,1\rangle$-formula
$\Phi^{\prime}_{n}(x)$ which defines $\mathbb{Q}$ in
$\langle\mathbb{R},+,<,1\rangle$, and this contradicts Theorem 2.1.

###  5.4 Extensions to $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability

We extend the previous results to the case of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability. Here
${\mathcal{T}_{X}}$ stands for the structure
$\langle\mathbb{R},+,<,\mathbb{Z},X\rangle$ with $n\geq 1$ and
$X\subseteq\mathbb{R}^{n}$. We prove that if every nonempty
${\mathcal{T}_{X}}$-definable relation contains a point with rational
components then one can express the property that $X$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable with a
${\mathcal{T}_{X}}$-sentence.

The construction is based on the decomposition of any set of reals into
“integer” and “fractional” sets, which allows us to reduce the
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability of $X$, on one hand to
the $\langle\mathbb{Z},+,<\rangle$-definability of some subsets of
$\mathbb{Z}^{n}$ and on the other hand to the
$\langle\mathbb{R},+,<,1\rangle$-definability of a collection of subsets of
$[0,1)^{n}$. In order to express these two kinds of properties in
${\mathcal{T}_{X}}$, we rely respectively on Muchnik’s Theorem [18] and on
Theorem 5.13.

We start with a property which holds for all relations under no particular
assumption. Given a relation $X\subseteq\mathbb{R}^{n}$ consider the
denumerable set of distinct restrictions of $X$ to unit hypercubes, i.e.,

$\tau_{a}\big{(}X\cap([a_{1},a_{1}+1),\cdots,[a_{n},a_{n}+1))\big{)}$

where $a=(a_{1},\cdots,a_{n})\in\mathbb{Z}^{n}$ and $\tau_{a}$ is the
translation $x\mapsto x-a$. Let $\Delta_{m}$ denote this collection of sets
where $m$ runs over some denumerable set $M$. For each $m\in M$, let
$\Sigma_{m}\subseteq\mathbb{Z}^{n}$ satisfy the condition

$x\in\Sigma_{m}\leftrightarrow
x+\Delta_{m}=X\cap\big{(}[x_{1},x_{1},+1),\cdots,[x_{n},x_{n},+1)\big{)}$

Observe that the decomposition

$X=\bigcup_{m\in M}\Sigma_{m}+\Delta_{m}$ (9)

is unique by construction. In the particular case of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations we have the
following result.

###### Proposition 5.16

([10, Theorem 7], see also [13]) A relation $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable if and only if in the
decomposition (9) the following three conditions hold:

(FU) the set $M$ in (9) is finite.

(IP) each $\Sigma_{m}$ is $\langle\mathbb{Z},+,<\rangle$-definable.

(FP) each $\Delta_{m}$ is $\langle\mathbb{R},+,<,1\rangle$-definable.

###### Proposition 5.17

For all $n\geq 1$ and $X\subseteq\mathbb{R}^{n}$, if every nonempty
${\mathcal{T}_{X}}$-definable relation contains a point with rational
components then there exists a ${\mathcal{T}_{X}}$-sentence $\Gamma_{n}$
(uniform in $X$) which holds if and only if $X$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable

###### Proof 5.18

In view of Proposition 5.16 it suffices to show that the three conditions are
expressible in $\langle{\mathbb{R},+,<,\mathbb{Z},X}\rangle$. Let $\Phi(X)$ be
the ${\mathcal{T}_{X}}$-formula which states that $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable, see equation (8).

Condition (FU): Let $x\approx y$ denote the equivalence relation which says
that the two points $x$ and $y$ belong to the same $\Sigma_{m}$ in the
decomposition 9. It is expressed by the ${\mathcal{T}_{X}}$-formula

$x\in\mathbb{Z}^{n}\wedge y\in\mathbb{Z}^{n}\wedge\forall z\in[0,1)^{n}\
(x+z\in X\leftrightarrow y+z\in X)$ (10)

The finiteness of the number of classes is expressed by the
${\mathcal{T}_{X}}$-formula

$\exists N\ \forall x\in\mathbb{Z}^{n}\ \exists y\in\mathbb{Z}^{n}\
(|y|<N\wedge y\approx x)$

Condition (IP): By [18, Thm 1] for every $Y\subseteq\mathbb{Z}^{n}$ there
exists a $\langle{\mathbb{Z},+,<,Y}\rangle$-formula $\Psi(Y)$ (uniform in $Y$)
which holds if and only if $Y$ is $\langle{\mathbb{Z},+,<}\rangle$-definable.
Let $\Psi^{*}(Y)$ denote the
$\langle{\mathbb{R},\mathbb{Z},+,<,Y}\rangle$-formula obtained from $\Psi(Y)$
by relativizing all quantifiers to $\mathbb{Z}$. Given
$Y\subseteq\mathbb{Z}^{n}$ (seen as a subset of $\mathbb{R}^{n}$), the formula
$\Psi^{*}(Y)$ holds in $\langle{\mathbb{R},\mathbb{Z},+,<,Y}\rangle$ if and
only if $Y$ is $\langle{\mathbb{Z},+,<}\rangle$-definable. Thus we can express
in ${\mathcal{T}_{X}}$ the fact that all $\approx$-equivalence classes are
$\langle{\mathbb{Z},+,<}\rangle$-definable with the formula

$\forall x\in\mathbb{Z}^{n}\Psi^{*}((y\in\mathbb{Z}^{n}\wedge y\approx x))$

Condition (FP): The fact that every hypercube of $X$ of unit side is
$\langle\mathbb{R},+,<,1\rangle$-definable is expressed by

$\forall x_{1},\ldots x_{n}\in\mathbb{Z}^{n}\ \Phi((0\leq
y_{1}<1\wedge\cdots\wedge 0\leq
y_{n}<1\wedge(x_{1}+y_{1},\cdots,x_{n}+y_{n})\in X)).$

##  6 Application to decidability

###  6.1 Deciding $\langle\mathbb{R},+,<,1\rangle$-definability and
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability

Theorem 5.13 and Proposition 5.17 prove the existence of definable criteria
for $\langle\mathbb{R},+,<,1\rangle$-definability and
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability for a given relation
$X$, respectively. If $X$ is definable in some decidable expansion of
$\langle\mathbb{R},+,<,1\rangle$ (resp.
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$) then we can obtain effective
criteria. This can be formulated as follows.

###### Theorem 6.1

Let ${\mathcal{M}}$ be any decidable expansion of
$\langle\mathbb{R},+,<,1\rangle$ such that every nonempty
${\mathcal{M}}$-definable relation contains a point with rational components.
Then it is decidable whether a ${\mathcal{M}}$-definable relation
$X\subseteq\mathbb{R}^{n}$ is $\langle\mathbb{R},+,<,1\rangle$-definable.

###### Proof 6.2

Assume that $X$ is ${\mathcal{M}}$-definable by the formula $\psi(x)$. In
Equation (8), if we substitute $\psi(x)$ for every occurrence of $x\in X$ then
we obtain a ${\mathcal{M}}$-sentence which holds if and only if $X$ is
$\langle\mathbb{R},+,<,1\rangle$-definable, and the result follows from the
decidability of ${\mathcal{M}}$.

###### Theorem 6.3

Let ${\mathcal{N}}$ be any decidable expansion of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ such that every nonempty
${\mathcal{N}}$-definable relation contains a point with rational components.
Then it is decidable whether a ${\mathcal{N}}$-definable relation
$X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable (resp. whether a
${\mathcal{N}}$-definable relation $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,1\rangle$-definable).

###### Proof 6.4

The claim about $\langle\mathbb{R},+,<,1\rangle$-definability follows
immediately from the fact that ${\mathcal{N}}$ satisfies the conditions of
Theorem 6.1. For $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definability, we
use the same idea as for the proof of Theorem 6.1, but instead of $\Phi_{n}$
we use the sentence $\Gamma_{n}$ of Proposition 5.17.

###  6.2 Application to recognizable numerical relations

We finally apply the results of Section 6.1 to the class of $k$-recognizable
relations on reals.

Let us recall that given an integer base $k\geq 2$ and a non-negative real
$x$, a $k$-encoding of $x$ is any right infinite word on the alphabet
$\Sigma_{k}=\\{0,\ldots,k-1\\}\cup\\{\star\\}$ of the form $w=a_{p}\ldots
a_{1}\star a_{0}a_{-1}a_{-2}\ldots$ such that $a_{i}\in\\{0,\ldots,k-1\\}$ for
every $i\leq p$ and $x=\sum_{i\leq p}a_{i}k^{i}$. The definition extends to
the case of negative reals $x$ by using the $k$’s complement representation
method where the leftmost digit equals $k-1$: a $k-$encoding of $x$ is a right
infinite word on the alphabet $\Sigma_{k}$ of the form $w=a_{p}\ldots
a_{1}\star a_{0}a_{-1}a_{-2}\ldots$ where $a_{p}=k-1$ and
$x=-k^{p}+\sum_{i\leq p-1}a_{i}k^{i}$. Note that every real has infinitely
many $k$-encodings.

In order for an automaton to be able to process $n$-tuples of representations
in base $k$ of reals we prefix it, if necessary, with as few occurrences of
$0$ for the nonnegative components or $k-1$ to the negative components so that
the $n$ components have the same length to the left of the symbol $\star$.
This does not change the numerical values represented. By identifying a real
with its $k$-encodings, relations of arity $n$ on $\mathbb{R}$ can thus be
viewed as subsets of $n$-tuples of sequences on
$\\{0,\ldots,k-1\\}\cup\\{\star\\}$, i.e., as subsets of

$(\\{0,\ldots,k-1\\}^{n})^{*}\\{\overbrace{(\star,\ldots,\star)}^{n\text{\tiny
times}}\\}(\\{0,\ldots,k-1\\}^{n})^{\omega}$

###### Definition 6.5

A relation $X\subseteq\mathbb{R}^{n}$ is $k$-_recognizable_ if the set of
$k$-encodings of its elements is recognized by some deterministic Muller-
automaton.

The collection of recognizable relations has a natural logical
characterization.

###### Theorem 6.6

[9, Thm 5 and 6] Let $k\geq 2$ be an integer. A subset of $\mathbb{R}^{n}$ is
$k$-recognizable if and only if it is definable in
$\langle\mathbb{R},\mathbb{Z},+,<,X_{k}\rangle$ where
$X_{k}\subseteq\mathbb{R}^{3}$ is such that $X_{k}(x,y,z)$ holds if and only
if $y$ is a power of $k$ and $z$ is the coefficient of $y$ in some
$k-$encoding of $x$.

Consequently, since the emptiness problem for recognizable relations is
decidable, the theory of $\langle\mathbb{R},\mathbb{Z},+,<,X_{k}\rangle$ is
decidable.

Moreover the class of $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable
relations enjoys the following characterization.

###### Theorem 6.7

[4, 5, 6] A subset of $\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable if and only if it is
$k$-recognizable for every integer $k\geq 2$.

As a consequence, deciding whether a $k$-recognizable relation is
$l-$recognizable for every base $l\geq 2$ amounts to decide whether it is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable. We can prove the
following result.

###### Theorem 6.8

Given an integer $k\geq 2$, it is decidable whether a $k$-recognizable
relation $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable (resp. whether a
$k-$recognizable relation $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,<,1\rangle$-definable).

###### Proof 6.9

By Theorems 6.3 and 6.6 it suffices to prove that every nonempty
$k$-recognizable relation $Y\subseteq\mathbb{R}^{n}$ contains an element in
$\mathbb{Q}^{n}$. By our assumption the set of $k$-encodings of elements of
$Y$ is nonempty and is recognized by a finite Muller automaton, thus it
contains an ultimately periodic $\omega-$word, which is the $k-$encoding of
some element of $\mathbb{Q}^{n}$.

### Acknowledgment

We wish to thank the anonymous referees and Françoise Point for their useful
comments and suggestions.

## References

  * [1] Bès A.  Expansions of MSO by cardinality relations.  Logical Methods in Computer Science, 2013. 9(4). doi:10.2168/LMCS-9(4:18)2013.
  * [2] Bès A, and Choffrut C.  Theories of real addition with and without a predicate for integers.  Logical Methods in Computer Science, 2021. 17(2):18. doi:10.23638/LMCS-17(2:18)2021.
  * [3] Bieri H, and Nef W.  Elementary set operations with d-dimensional polyhedra.  Workshop on Computational Geometry, Springer, 1988 pp. 97–112. doi:10.1007/3-540-50335-8_28.
  * [4] Boigelot B, and Brusten J.  A generalization of Cobham’s theorem to automata over real numbers.  Theor. Comput. Sci., 2009. 410(18):1694–1703. doi:10.1016/j.tcs.2008.12.051.
  * [5] Boigelot B, and Brusten J, and Bruyère V.  On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases.  Logical Methods in Computer Science, 2010. 6(1):1–17. doi:10.2168/LMCS-6(1:6)2010.
  * [6] Boigelot B, and Brusten J, and Leroux J.  A Generalization of Semenov’s Theorem to Automata over Real Numbers.  Automated Deduction - CADE-22, 22nd International Conference on Automated Deduction, Montreal, Canada, August 2-7, 2009. Proceedings, 2009 pp. 469–484. doi:10.1007/978-3-642-02959-2_34.
  * [7] Boigelot B, and Brusten J, and Degbomont JF.  Automata-Based Symbolic Representations of Polyhedra.  Proc. LATA 2012, LNCS vol. 7183, 2012 pp. 3–20. doi:10.1007/978-3-642-28332-1_2.
  * [8] Bruyère V, and Hansel G, and Michaux C, and Villemaire R.  Logic and $p$-recognizable sets of integers.  Bull. Belg. Math. Soc. Simon Stevin 1994. 1(2):191–238. doi:10.36045/bbms/1103408547.
  * [9] Boigelot B, and Rassart S, and Wolper P.  On the Expressiveness of Real and Integer Arithmetic Automata (Extended Abstract).  Automata, Languages and Programming, 25th International Colloquium, ICALP’98, Aalborg, Denmark, July 13-17, 1998, Proceedings, 1998 pp. 152–163.
  * [10] Bouchy F, and Finkel A, and Leroux J.  Decomposition of decidable first-order logics over integers and reals  15th International Symposium on Temporal Representation and Reasoning. IEEE, 2008. doi:10.1109/TIME.2008.22.
  * [11] Dolich A, and Goodrick J.  Strong theories of ordered Abelian groups.  Fundamenta Mathematicae 236, 2017 pp. 269–296.
  * [12] Dolich A, and Miller C, and Steinhorn C.  Structures having o-minimal open core.  Transactions of the American Mathematical Society, 2020. 362(3):1371–1411. URL https://www.jstor.org/stable/40590872.
  * [13] Feferman S, and Vaught RL.  The first order properties of products of algebraic systems  Fundam. Math. vol.47, 1959 pp. 57–103. ISSN: 0016-2736.
  * [14] Ferrante J, and Rackoff C.  A decision procedure for the first order theory of real addition with order.  SIAM J. on Computing, 1975. 4(1):69–76. doi:10.1137/0204006.
  * [15] Ginsburg S, and Spanier E.  Semigroups, Presburger formulas, and languages.  Pacific journal of Mathematics, 1966. 16(2):285–296.
  * [16] Hieronymi P.  When is scalar multiplication decidable?  Annals of Pure and Applied Logic, 2019. 170(10):1162–1175. doi:10.1016/j.apal.2019.05.001.
  * [17] Milchior A.  Büchi Automata Recognizing Sets of Reals Definable in First-Order Logic with Addition and Order  Proceedings of TAMC 2017 pp. 440–454. doi:10.48550/arXiv.1610.06027.
  * [18] Muchnik AA.  The definable criterion for definability in Presburger arithmetic and its applications.  Theor. Comput. Sci., 2003. 290(3):1433–1444. doi:10.1016/S0304-3975(02)00047-6.
  * [19] Point F, and Wagner FO.  Essentially periodic ordered groups.  Annals of Pure and Applied Logic, 2000. 105(1-3):261–291. doi:10.1016/S0168-0072(99)00053-6.
  * [20] Presburger M.  Uber die Vollstandigkeit eines gewissen Systems der Arithmetic ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt.  Compte-Rendus du 1er Congrès des Mathématiciens des pays slaves, Warsaw, 1929.
  * [21] Semenov AL.  Presburgerness of predicates regular in two number systems (in Russian).  Sibirsk. Mat. Zh., 18, (1977) 403–418, English translation, Siberian Math. J., 1977\. 18:289–299.
  * [22] Semenov AL, Soprunov S, and Uspensky VA.  The Lattice of Definability. Origins, Recent Developments, and Further Directions.  Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014 pp. 23–38. doi:10.1007/978-3-319-06686-8_3.
  * [23] Walsberg E.  Generalizing a theorem of Bès and Choffrut.  arXiv preprint, 2020, URL https://arxiv.org/abs/2002.10508.
  * [24] Weispfenning V.  Mixed Real-Integer Linear Quantifier Elimination.  Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC ’99, 1999 pp. 129–136. doi:10.1145/309831.309888.