MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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)$. – Emil Jeřábek Oct 26 '12 at 14:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.