Simple proof that Automorphisms preserve definable subsets?

Question

I've been looking all over for a proof of this result, but I haven't really found anything. Is anyone aware of a particularly simple or elegant one?

Answer 1

Unfortunately, at this basic level in model theory, you're going to have to get your hands dirty with induction on the complexity of terms and formulas, there's no way around it. Fortunately, once you do a proof or two like this, you'll find they become routine.

"Automorphisms preserve definable subsets" means that if $\sigma\in \text{Aut}(M)$, $\varphi(\overline{x})$ is a formula, and $\overline{a}$ is a tuple from $M$, then $M\models \varphi(\overline{x})$ if and only if $M\models \varphi(\sigma(\overline{x}))$. It's straightforward to prove this by induction on the complexity of terms and formulas.

Step 1: Show by induction on terms that if $t$ is a term, then $\sigma(t^M(\overline{a})) = t^M(\sigma(\overline{a}))$ (it's almost immediate from the fact that $\sigma$ preserves functions and constants).

Step 2: Check that $\sigma$ preserves atomic formulas ($\sigma$ preserves equality and relations on elements, and you can use the result of Step 1 to plug in terms).

Step 3: Show that $\sigma$ preserves all formulas by induction. The only place you have to do anything is for the existential quantifier: if $b$ is a witness to $\exists x\, \psi(\overline{a},x)$ then $\sigma(b)$ is a witness to $\exists x\, \psi(\sigma(\overline{a}),x)$.