Definability and decidability in expansions by generalized Cantor sets

Abstract

We determine the sets definable in expansions of the ordered real additive group by generalized Cantor sets. Given a natural number $r\ge 3$, we say a set $C$ is a generalized Cantor set in base $r$ if there is a non-empty $K\subseteq \{1,\dots ,r-2\}$ such that $C$ is the set of those numbers in $[0,1]$ that admit a base $r$ expansion omitting the digits in $K$. While it is known that the theory of an expansion of the ordered real additive group by a single generalized Cantor set is decidable, we establish that the theory of an expansion by two generalized Cantor sets in multiplicatively independent bases is undecidable.

Cited by in corpus (1)

• Generalizing a theorem of Bès and Choffrut