1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ To address question 2: As far as I know, the only general strategy for showing that a set is definable is to try to write down a definition. On the other hand, there are a number of strategies for showing that a set is not definable. Here are three: (a) showing it is not invariant under automorphisms, (b) finding some property of the theory which is preserved under definable expansions (decidability, stability, etc) which is true of the theory, but not of the theory expanded by a new relation symbol naming the set, ... $\endgroup$ – Alex Kruckman Nov 28 '19 at 19:20
  • 1
    $\begingroup$ ... (c) understanding all definable sets by showing that the theory (or some concrete expansion of it) has quantifier elimination. $\endgroup$ – Alex Kruckman Nov 28 '19 at 19:23
  • 1
    $\begingroup$ For example, you can use (b) and (c) to show that the natural numbers are not even definable in the real numbers with the full field structure (addition and multiplication). (b): The theory of the real field is decidable; but not after naming the natural numbers, by Gödel's theorem. (c): the theory of the real ordered field has quantifier elimination, so every definable set is a boolean combination of solution sets to inequalities between polynomials. It follows that every definable set is a finite union of points and intervals, and the natural numbers are not of this form. $\endgroup$ – Alex Kruckman Nov 28 '19 at 19:27
  • 1
    $\begingroup$ Well, it's a bit vague. But in the example, suppose you know that the theory of the real field is decidable. This is sometimes known as Tarski's theorem. Suppose you also know that any theory which interprets arithmetic is undecidable (this is a consequence of Gödel's theorem). If $\mathbb{N}$ is definable in $\mathbb{R}$, then the theory of the real numbers interprets arithmetic (this means that the truth in $\mathbb{N}$ of sentences in the language of arithmetic can be checked in $\mathbb{R}$, by relativizing their quantifiers to the formula defining $\mathbb{N}$ in $\mathbb{R}$). $\endgroup$ – Alex Kruckman Nov 30 '19 at 14:55
  • 1
    $\begingroup$ This is a contradiction, so $\mathbb{N}$ is not definable in $\mathbb{R}$. Here the nice property of $\mathbb{R}$ used in the argument is decidability. But logicians study lots of properties of theories, many of which can also be used to show non-definability results. Another example: The field of complex numbers satisfies a property called stability (which says more or less that no formula in the language can linearly order an infinite sequence). On the other hand, the field of real numbers has a definable linear order. It follows that $\mathbb{R}$ is not definable in $\mathbb{C}$. $\endgroup$ – Alex Kruckman Nov 30 '19 at 15:01
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ yes you are right. good counterexample! Thank you very much. $\endgroup$ – Maryam Ajorlou Nov 30 '19 at 11:44
  • $\begingroup$ @MaryamAjorlou If you are satisfied with Mark's answer, you can accept it by clicking on the green check mark on the left (under the upvote/downvote buttons). This is a good thing to do, because it marks the question as answered. $\endgroup$ – Alex Kruckman Dec 2 '19 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.