6
$\begingroup$

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

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

  • 0
    @Brian: How does your formula show that $0 < 2$ in $\langle \mathbb{Q} , + , \cdot \rangle$?2012-12-01
  • 0
    @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*!2012-12-01
  • 0
    @Brian: $\sqrt{2}$ might be irrational in my world, but after spending five days enjoying _pivo_ in Prague my world is far from rational.2012-12-01
  • 0
    @Arthur: But such a splendid irrationality!2012-12-01
  • 0
    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$).2012-12-01

2 Answers 2

4

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.

  • 0
    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$"?2016-05-10
  • 0
    @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.)2016-05-10
  • 0
    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.2016-05-10
  • 0
    @hengxin It's essentially by definition. Read, for example, the [Wikipedia article on Elementary equivalence](https://en.wikipedia.org/wiki/Elementary_equivalence).2016-05-10
  • 0
    I got it. Thanks for your time.2016-05-10
3

1) Using Lagrange's four square theorem $$a

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

  • 0
    Note that you have constants and you need the automorphisms to preserve them. $-1\neq 1$.2012-12-01
  • 0
    @AsafKaragila oops, edited bold claim to humble question :)2012-12-01
  • 0
    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?!2012-12-01
  • 0
    @Mathbb: I should probably point out that $(\mathbb C,+)$ and $(\mathbb R,+)$ are isomorphic. The dimension argument is incorrect here.2012-12-01