1
$\begingroup$

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}, +$))?

$\endgroup$
1
  • $\begingroup$ Sure. If $Y\subseteq\mathbb Q^d$ is definable in $(\mathbb Q,+,\le)$, then $Y\cap\mathbb N^d$ is definable in $(\mathbb N,+)$ by quantifier elimination of $(\mathbb Q,+,\le)$. $\endgroup$ Oct 26, 2012 at 14:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.