How to prove that a set is not definable using an automorphism?

Question

Given a structure (Z,<) how would you prove it is not definable. I know we have to find an automorphism and show that a fixed point before the transformation is in the structure and then the fixed point after the transformation is not in the structure, but how would I write that formally?

Answer 1

In general, to show that a set $A$ is not definable in a structure $\mathcal{M}$, you can argue as follows:

• First, find some function $f:\mathcal{M}\rightarrow\mathcal{M}$ which satisfies $f(a)\not\in A$ for some $a\in A$ and which is an isomorphism.

  • Of course, you'll have to prove that the $f$ you come up with is in fact an isomorphism!

• Next, you'll use the general fact that isomorphisms respect formulas: if $\mathcal{A},\mathcal{B}$ are structures in the same language, $i:\mathcal{A}\rightarrow\mathcal{B}$ is an isomorphism, and $a_1,...,a_n\in\mathcal{A}$ and $\varphi$ is a formula with $n$ free variables, then $$\mathcal{A}\models\varphi(a_1,...,a_n)\quad\iff\quad\mathcal{B}\models\varphi(i(a_1),..., i(a_n)).$$ Of course, this is a general theorem which you only have to prove once.

  • Note that in our case, we only care about formulas of one free variable. In general, if you want to show that a set $A\subseteq\mathcal{M}^n$ of $n$-tuples is not definable in $\mathcal{M}$, you care about formulas of $n$ free variables.

• We can now finish the proof as follows. Suppose $A$ were definable by some formula $\varphi$. Let $f,a$ be as in the first bulletpoint - that is, $f$ is an automorphism of $\mathcal{M}$, $a\in A$, and $f(a)\not\in A$. Then since $a\in A$ we have $\mathcal{M}\models\varphi(a)$, so by the previous bulletpoint we know $\mathcal{M}\models\varphi(f(a))$; but then $f(a)\in A$, a contradiction. So we're done. And again, this only has to be done once since it's always the same argument.

So really the key point is: find an automorphism moving a point from inside the set to outside the set. Once you've done that, a general result and a general argument will show that the set is not definable.

---

Everything I've written above is for parameter-free definability. It's a good exercise to try to figure out how parameters change the situation:

What is an "isomorphism-flavored" sufficient condition that a set $A\subseteq\mathcal{M}$ not be definable in $\mathcal{M}$ with arbitrary parameters?

---

It's also worth noting that while "non-automorphism stable" implies undefinability, the converse is false:

Show that the set of primes is not definable in $\mathcal{N}=(\mathbb{N}; +)$ even though $\mathcal{N}$ has no nontrivial automorphisms.

This may require techniques you've not seen yet, but it can in fact be done (and indeed very few sets/functions are definable in $(\mathbb{N};+)$!); in my opinion, the nicest proof is via Ehrenfeucht-Fraisse games. Regardless, the point is that automorphisms don't tell you everything about definability.