Approaches to definability of a set in a structure

94 Views Asked by At

I want to show that:

$\mathbb{N}$ is not definable in $(\mathbb{R}, 0, 1, \times)$.

The only thing I know is some definitions and a theorem that uses the method of automation, namely:

Theorem: if $\pi$ is an automorphism of a structure $\mathfrak{M}$, then for every formula $\Phi$ with $n$ free variable $x_{1},..., x_{n}$ and every $n$ tuple $n,..., n$ in the universe of $\mathfrak{M}$

$\mathfrak{M}$ $\models$ $\Phi$ [ $x_{1}\mapsto$ $a_{1}$, ... , $x_{n}\mapsto$ $a_{n}$ ]$\iff$ $\mathfrak{M}$ $\models$ $\Phi$ [ $x_{1}\mapsto$ $\pi$($a_{1}$), ... , $x_{n}\mapsto$ $\pi$($a_{n}$) ].

Now my question is that

1- How can I make an automorphism and use this theorem?

2- And my other question that may seem absurd, what are approaches for proving the definability of a set in a given structure?

1

There are 1 best solutions below

2
On BEST ANSWER

The important point of the theorem you mention is that if $\mathbb{N}$ would be definable, then this set should be invariant under automorphisms. That is, if $\phi(x)$ is the formula that defines $\mathbb{N}$ and $\pi: \mathbb{R} \to \mathbb{R}$ is an automorphism, then: $$ a \in \mathbb{N} \quad\Longleftrightarrow\quad \mathbb{R} \models \phi(a) \quad\Longleftrightarrow\quad \mathbb{R} \models \phi(\pi(a)) \quad\Longleftrightarrow\quad \pi(a) \in \mathbb{N}. $$

So if we take for example $\pi(x) = x^3$, then this is easily seen to be an automorphism of $\mathbb{R}$ (with inverse $\pi^{-1}(x) = x^{1/3}$). Then this does not preserve the set $\mathbb{N}$, because for example $2$ is not in the image of $\pi$.

In all of the above we of course consider $\mathbb{R}$ as a structure in the language you mentioned, i.e. as $(\mathbb{R}, 0, 1, \times)$.