Show that $X$ is not definable in $(\Bbb{R}, <)$

model-theory

The question is as follows:

Let $X = \{(x, y, z) \in \Bbb R^3 : z = x + y\}$. Show that $X$ is not definable in $(\Bbb R, <)$.

I tried to show that $(\Bbb R, <)$ has only two subsets that are definable, namely $\Bbb R$ and the empty set using an automorphism argument. Since $X$ is neither of these sets it is not definable in $(\Bbb R, <)$. I feel like this approach is wrong. Any help would be greatly appreciated.

Best Answer

Hint: Show that for any finite subset $A$ of $\mathbb{R}$, and any element $b\notin A$, there is an automorphism of $(\mathbb{R},<)$ which fixes the elements of $A$ but moves $b$.

Now obtain a contradiction to the above fact under the assumption that $X$ is definable.

Related Solutions

[Math] Show that binary < "less than" relation is not definable on set of Natural Numbers with successor function

Suppose that $\varphi ( x , y )$ is a first-order formula defining the relation $<$ in $\mathcal{N} = ( \mathbb{N} , S , 0 )$; that is $$\mathcal{N} \models \varphi ( m,n ) \quad\Leftrightarrow\quad m < n.$$ Note that if $\mathcal{M}$ is any elementary extension of $\mathcal{N}$ it must be that $\varphi (x,y)$ defines a strict total (linear) order on the universe of $\mathcal{M}$. Consider the structure $\mathcal{M} = ( M , s , 0 )$ where

$M = \mathbb{N} \cup ( \mathbb{Z} \times \{ 0 , 1 \} )$;
$s(m) = m+1$; $s(m,i) = (m+1,i)$.

Then $\mathcal{M}$ is an elementary extension of $\mathcal{N}$. Let $a_0 = (0,0)$ and $a_1 = (0,1)$. As $\varphi$ defines a strict total order on $M$ we may assume without loss of generality that $$\mathcal{M} \models \varphi ( a_0 , a_1 ).$$

Consider the following function $\sigma : M \to M$:

$\sigma ( m ) = m$; and
$\sigma ( m , i ) = ( m , 1-i )$ (i.e., $\sigma$ switches the two disjoint copies of $\mathbb{Z}$).

It is quite easy to show that $\sigma$ is an automorphism of $\mathcal{M}$, and therefore $$\mathcal{M} \models \varphi ( \sigma(a_0) , \sigma(a_1) ).$$ But as $\sigma ( a_0 ) = a_1$ and $\sigma ( a_1 ) = a_0$ we have that $$\mathcal{M} \models \varphi ( a_1 , a_0 ),$$ contradicting the fact that $\varphi$ defines a strict total order on $M$!

Show that the set of real numbers is not definable in the field of complex number

As Eric Wofsey said, actually building an automorphism of $\mathbb{C}$ which moves a real is difficult: while we can prove that for every transcendental real $r$ there is a field automorphism of $\mathbb{C}$ which moves $r$, this proof is $(i)$ a transfinite recursion argument and $(ii)$ relies on the axiom of choice.

There is, however, an automorphism argument which does work:

We'll show a stronger result - that for any transcendental real number $r$ and any formula $\varphi(x)$ such that $\mathbb{C}\models\varphi(r)$, there is a non-real complex number $s$ such that $\mathbb{C}\models\varphi(s)$. The argument uses automorphisms and elementary submodels, and goes as follows (outlined only - it's a good exercise to fill it all in):

Fix a transcendental real $r$, a transcendental non-real complex number $s$, and a formula $\varphi(x)$ such that $\mathbb{C}\models\varphi(r)$. Let $M$ be a countable elementary submodel of $\mathbb{C}$ which contains $r$ and $s$ - we know such an $M$ exists by the downward Lowenheim-Skolem theorem.
- Note that we've replacing the not-obviously-well-orderable field $\mathbb{C}$ by a countable, and hence well-orderable, field $M$. Intuitively, this should (and does) make the axiom of choice irrelevant here.
Now show that $M$ is a countable algebraically closed field of characteristic zero and infinite transcendence degree.
By a standard back-and-forth argument, there is an automorphism of $M$ swapping $r$ and $s$, so $M\models\varphi(s)$. Back-and-forth arguments are still recursive constructions, but they don't use transfinite recursion; also, this is probably a result you've already proved.
Remembering how $M$ and $\mathbb{C}$ are related, conclude that $\mathbb{C}\models\varphi(s)$ as desired.

Remark $1$. We can avoid elementary submodels entirely by working with Ehrenfeucht-Fraisse games instead; however, elementary submodel juggling is an important technique to learn.

Remark $2$. An even stronger fact is true: $\mathbb{C}$ is strongly minimal, meaning that for any model $N$ of $Th(\mathbb{C})$, every definable-with-parameters subset of $N$ is either finite or cofinite. (First, prove that $\mathbb{C}$ has quantifier elimination, and then show that every quantifier-free formula with parameters defines either a finite or a cofinite set; then lift this to every model of $Th(\mathbb{C})$.)

Best Answer

Related Solutions

[Math] Show that binary < "less than" relation is not definable on set of Natural Numbers with successor function

Show that the set of real numbers is not definable in the field of complex number

Related Question