Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
@Brian: How does your formula show that $0 < 2$ in $\langle \mathbb{Q} , + , \cdot \rangle$? –  Arthur Fischer 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. –  Arthur Fischer 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
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.