Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

I study model theory and I have questions about relations which are definable in a structure or not. I found three examples from exercises and i want to do them:

Is the relation $<$ on $\Bbb{Q}$ definable in the structure $(\Bbb{Q},+,\cdot,0,1)$ that is does there exists a formula $\phi=\phi(x_0,x_1)$ sucht that for all $p,q$ in $\Bbb{Q}$, $p<q$ if and only if $(\Bbb{Q},+,\cdot,0,1)$ realized $\phi[p,q]$ ?

Is the relation $<$ on $\Bbb{Q}$ definable in the structure $(\Bbb{Q},+,0,1)$ ?

Is the relation $+$ on $\Bbb{Q}$ definable in the structure $(\Bbb{Q},<,0,1)$ ?

I have done this already for the integers with the successor function, but I don't know how to do this in this three cases. I think the first relation is definable, but the other two not. Can someone help me? Thank you :)

share|cite|improve this question
@Brian: How does your formula show that $0 < 2$ in $\langle \mathbb{Q} , + , \cdot \rangle$? – arjafi Dec 1 '12 at 12:28
@Arthur: Isn’t $\sqrt 2$ rational in your world? :-) Clearly my subconscious knew what it was doing when it had me write appears to define! – Brian M. Scott Dec 1 '12 at 12:31
@Brian: $\sqrt{2}$ might be irrational in my world, but after spending five days enjoying pivo in Prague my world is far from rational. – arjafi Dec 1 '12 at 12:37
@Arthur: But such a splendid irrationality! – Brian M. Scott Dec 1 '12 at 12:40
Well, in $(\Bbb Z,+,\cdot)$ it is definable by using the fact that every positive integer can be written as the sum of $4$ squares. This can be extended to the rationals, too ($\exists$ pos.integer $b$: $\ x\cdot b$ is pos.integer) $\iff x>0$). – Berci Dec 1 '12 at 12:42

For the first, use Lagrange's Four Square Theorem, as others have said.

For the second, I believe that you can show that the structure $\langle \mathbb{Q} \times \mathbb{Z} , (0,0) , (1,0) , \hat{+} \rangle$ where $\hat{+}$ is defined by $$(m,i) \mathop{\hat{+}} (n,j) = (m+n,i+j)$$ is an elementary extension of $\langle \mathbb{Q} , 0 , 1 , + \rangle$ (with the obvious embedding). The function $f : \mathbb{Q} \times \mathbb{Z} \to \mathbb{Q} \times \mathbb{Z}$ defined by $$f ( m,i) = (m,-i)$$ is an automorphism of $\langle \mathbb{Q} \times \mathbb{Z} , (0,0) , (1,0) , \hat{+} \rangle$, and should be enough to witness that $<$ is not definable. (This makes use of the fact that if $\varphi(x,y)$ defines a linear ordering in $\langle \mathbb{Q} , 0 , 1 , + \rangle$, then it defines a linear ordering in all elementary extesnions of $\langle \mathbb{Q} , 0 , 1 , + \rangle$.)

For the third, note that any strictly increasing bijection $f: \mathbb{Q} \to \mathbb{Q}$ satisfying $f(0) = 0$ and $f(1) = 1$ is an automorphism of $\langle \mathbb{Q} , 0 , 1 , < \rangle$. Just pick any of these which is not linear to witness that $+$ is not definable in the structure.

share|cite|improve this answer
Why is "if $\varphi(x,y)$ defines a linear ordering in $\langle \mathbb{Q} , 0 , 1 , + \rangle$, then it defines a linear ordering in all elementary extensions of $\langle \mathbb{Q} , 0 , 1 , + \rangle$"? – hengxin May 10 at 2:48
@hengxin Because $\langle \mathbb{Q} , 0 , 1 , + \rangle$ and any elementary extension are elementarily equivalent, and so satisfy the same sentences. In particular, the sentences which say that $\varphi(x,y)$ is a linear ordering. ($\forall x \forall y \forall z ( (\varphi(x,y) \wedge \varphi(y,z) ) \rightarrow \varphi (x,z) )$, etc.) – arjafi May 10 at 2:56
It is not clear to me why $\langle \mathbb{Q}, 0, 1, + \rangle$ and any elementary extension are elementarily equivalent. Would you mind explaining it in more details? Or maybe I should open a new post for that. Great thanks. – hengxin May 10 at 3:22
@hengxin It's essentially by definition. Read, for example, the Wikipedia article on Elementary equivalence. – arjafi May 10 at 3:27
I got it. Thanks for your time. – hengxin May 10 at 3:47

1) Using Lagrange's four square theorem $$a<b\equiv \neg(a=b)\land \exists x,y,u,w\colon a+x\cdot x+y\cdot y+z\cdot z+w\cdot w=b$$

2) How can you distinguish $(\mathbb Q,+)$ from $(\mathbb Q[i],+)$?

3) Note that $$x\mapsto\begin{cases}2x&x\le \frac13\\\frac12(x+1) &x\ge\frac13\end{cases}$$ is an automorphism of the ordered set $(\mathbb Q,<)$.

share|cite|improve this answer
Note that you have constants and you need the automorphisms to preserve them. $-1\neq 1$. – Asaf Karagila Dec 1 '12 at 12:52
@AsafKaragila oops, edited bold claim to humble question :) – Hagen von Eitzen Dec 1 '12 at 12:56
I can distinguish them by the dimension, the first is a vector space form dimension 1 and the second a vector space of dimension 2. Can you look up to $(\Bbb{Q}[i],+,0,1)$ and than make a automorphism that do not preserve the relation and then you can conclude that it also doesn't hold in the smaller model?! – Mathbb Dec 1 '12 at 12:59
@Mathbb: I should probably point out that $(\mathbb C,+)$ and $(\mathbb R,+)$ are isomorphic. The dimension argument is incorrect here. – Asaf Karagila Dec 1 '12 at 13:04

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.