# Definable relations

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 :)

-
@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.

-
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,<)$.

-
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