As I've recently been genning up on some of my undergraduate courses, I took a passing interest in the Part II Cambridge Maths Tripos questions from the exams sat earlier this year.
One question, from the Logic and Set Theory course (p63 at the above link), that caught my eye was the following:
If a theory $T$ in a language $L$ has arbitrarily large finite non-rigid models, show that $T$ also has an infinite non-rigid model.
I'm somewhat stumped by this!
Without the "non-rigid" bit, I'm familiar with the standard compactness argument for showing that arbitrarily large models imply infinite models — essentially we add to the theory $T$ axioms of the form "$\phi_n$ :the model is at least size $n$" to form $T'$; as any finite subset of $T'$ contains only finitely many $\phi_n$s, it is satisfiable by a sufficiently large (finite) model for $T$, which we are told exists; hence by compactness $T'$ has a model, which will necessarily be infinite to satisfy all the $\phi_n$s.
The above question appears to be wanting a slight adaption to this argument, but that's easier said than done. For example, it would be nice if we could attach axioms to the theory that would encapsulate "the model is non-rigid", whereupon we could use the same argument outlined above. The problem however is that this would involve axiomatising "the model is non-rigid" and I'm not sure how to show that's possible in first-order logic — indeed, I'm not even sure if it is possible.
Given that the compactness argument would only require axioms to be satsifiable in sufficiently large finite models, I wondered if I could somehow axiomatise the idea of a non-trivial automorphism on a finite subset of the model, but I could only do this by specifying a particular size for the subset, which then became too strong a condition to be guaranteed satisfiable by the larger finite models that the argument relies on.
Is anyone able to point me in the right direction?
Best Answer
Let $L' = L\cup \{\sigma\}$, where $\sigma$ is a unary function symbol not in $L$. Let $T'$ be $T$ together with axioms asserting that $\sigma$ is a non-trivial-automorphism (non-triviality is $\exists x\, \sigma(x)\neq x$). Now every non-rigid model of $T$ has an expansion to a model of $T'$. In particular, $T'$ has arbitrarily large finite models, so by compactness, $T'$ has an infinite model. The reduct of this model to $L$ is a model of $T$ which is non-rigid (witnessed by the interpretation of the function symbol $\sigma$).
Let me add a bit to answer the question in the title. The trick in the last paragraph produces an $L'$-theory $T'$ with the property that a model $M\models T$ is non-rigid if and only if there is some $M'\models T'$ such that $M = M'|_L$. This shows that the non-rigid models of $T$ form a pseudoelementary class, i.e., the class of $L$-reducts of the class of models of a first-order $L'$-theory in an expanded language $L'\supseteq L$. Alternatively, if $L$ is finite, one could say that non-rigidity is expressible in existential second-order logic (using one second-order existential quantifier to express the existence of the non-trivial automorphism). The nice thing about pseudoelementary classes / classes definable in existential second-order logic is that we can still apply standard compactness arguments to them, by applying compactness to a first-order theory in an expanded language, as I did above.
But you asked whether non-rigidity is first-order axiomatizable, i.e., whether the non-rigid models of $T$ form an elementary class. The answer is no: Let $M = (\mathbb{N},<)$, and note that $M$ is rigid. Now let $M'$ be an elementary extension of $M$. $M'$ is a discrete linear order with a minimum element but no maximum element, so it looks like $\mathbb{N}$ followed by copies of $(\mathbb{Z},<)$ in some order (e.g. $M'$ could be $(\mathbb{N}+\mathbb{Z},<)$. So $M'$ is non-rigid, since the elements of each copy of $\mathbb{Z}$ can be shifted up and down in that copy of $\mathbb{Z}$. Since $M\equiv M'$, this shows that neither rigidity nor non-rigidity are first-order axiomatizable.
In fact, a much stronger statement is true - weakening the hypothesis of the statement you asked about, and generalizing the observation about the theory of $(\mathbb{N},<)$ above:
Every theory with infinite models has an infinite non-rigid model. And hence, by compactness, every theory with arbitrarily large finite models (rigid or not) has an infinite non-rigid model.
The proof is a bit too involved to get into here (I would have to define Skolem functions and indiscernible sequences), but the key word to search for is Ehrenfeucht-Mostowski models.