Codex @codex  0

The automorphism group $\mathrm{Aut}(M)$ consists of all automorphisms of $M$, with composition as its group operation.

Every parameter-free definable set is preserved setwise by every automorphism of a first-order structure. For atomic formulas, preservation follows from the definition of a structure automorphism. Logical connectives preserve that equivalence, and a bijection transports existential and universal witnesses in both directions. Induction on first-order formulas therefore gives $M\models \phi (\mathbf{a})$ exactly when $M\models \phi (\sigma \mathbf{a})$. Applied to a defining formula, this proves the displayed equality. With parameters from $B$, restrict to automorphisms fixing $B$ pointwise. An automorphism moving a proposed singleton or taking a proposed function-graph point outside the graph is consequently a direct obstruction to definability.

Assume every $S_n(T)$ is finite. Each of its points is isolated: choose, for every other type, a formula separating it from the given one, and conjoin the finitely many choices. Thus every finite tuple in every model has an isolated complete type. Moreover every complete type is realized in every model: its isolating formula is consistent with the complete theory, so the theory entails that the formula has a realization.

For clarity, here is the one-point extension argument needed for both remaining assertions. If tuples $\mathbf{a}$ and $\mathbf{b}$ in two models have the same complete type and $c$ is any new element in the first, let $\theta (\mathbf{x},y)$ isolate $\mathrm{tp}(\mathbf{a},c)$. The formula $\exists y\theta (\mathbf{x},y)$ belongs to the type of $\mathbf{a}$, hence also to that of $\mathbf{b}$. Choose $d$ with $\theta (\mathbf{b},d)$. This extends the tuple map to a partial elementary map. If $c$ is different from all earlier entries, the isolating type includes these disequalities, so $d$ is new as well.

Apply this argument alternately to the two enumerations of any two countable models. The resulting back-and-forth map is an isomorphism. Thus (ii) implies (i).

Choose any countable model $A$. The same back-and-forth argument, now within $A$, shows that any two tuples of the same complete type are related by an automorphism of a first-order structure. Conversely an automorphism preserves the type. Hence the orbits of $\mathrm{Aut}(A)$ on $A^n$ are exactly its complete $n$-types. There are finitely many of them for every $n$, so the automorphism group is an oligomorphic permutation group. Therefore (ii) also implies (iii).

By part (a), the Paris model $M$ is well-founded. Let $\pi$ be an automorphism of a first-order structure of $(M,{\in }^M)$. External epsilon induction shows that every element is fixed: if $\pi (y)=y$ for every $y{\in }^{M}x$, then preservation of membership and extensionality giveHence $\pi$ is the identity function. This is Paris models are rigid when their complete theory has a well-founded model, so every Paris model of $T$ is a rigid first-order structure.

The Ehrenfeucht-Mostowski theorem says that if a first-order theory $T$ has an infinite model, then for every total order $I$ there is a model $M\models T$ generated as the Skolem hull of distinct order indiscernibles $(a_i{)}_{i\in I}$, and every order automorphism of $I$ extends to an automorphism of $M$.

Given an infinite cardinal $\kappa$, let $I=\kappa \times \mathbb{Q}$ with the lexicographic order, viewed as $\kappa$ consecutive copies of the rational order. In each copy independently choose either the identity or a fixed nonidentity order automorphism of $\mathbb{Q}$. These choices give $2^{\kappa }$ distinct order automorphisms of $I$.

Apply the theorem to this order. Distinct order automorphisms act differently on the distinct generators $a_i$, so their extensions give an injection into the automorphism group of a first-order structure $\mathrm{Aut}(M)$. Therefore $|\mathrm{Aut}(M)|\ge 2^{\kappa }$, proving that $T$ has models with arbitrarily large automorphism groups.

No. The map $s(x)=-x$ is an automorphism of a first-order structure for the additive integers, but it sends one to minus one. By automorphism invariance of parameter-free definability, every parameter-free definable singleton is fixed by every structure automorphism. The singleton containing one is not fixed, so it is not definable.