Consider the class of sets of the form $X \cap Y$ where $X \subseteq \mathbb{N}^d$ is defined in FO($\mathbb{N}, +$) and $Y \subseteq \mathbb{Q}^d$ is defined in FO($\mathbb{Q}, +, \leq$). Clearly, this class includes the semilinear sets, since they can be described as $X \cap \mathbb{Q}^d$. Is the converse true? Do all sets of this class are semilinear (i.e. definable in FO($\mathbb{N}, +$))?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
