First-order structure

A structure supplies a nonempty domain and an interpretation of every constant, operation, and relation symbol in its language.

A structure embedding is an injective map respecting constants and operations and preserving and reflecting relations. Equivalently it preserves all atomic formulas and their negations. It identifies the source with a substructure of the target. An elementary embedding additionally preserves every first-order formula.

An $L$-substructure of a first-order structure $A\subseteq B$ has a nonempty domain containing all named constants and closed under the functions of $B$, and each relation of $A$ is the restriction of the corresponding relation of $B$. Consequently every quantifier-free formula with parameters in $A$ has the same truth value in $A$ and $B$. This is weaker than being an elementary substructure, which preserves all first-order formulas.

A substructure $M\subseteq N$ is simply closed when each existential quantifier-free formula over $M$ realized in $N$ is already realized in $M$. A single quantified variable suffices in the definition; iterating covers finite tuples. This property is also called existential closure in this specified extension. It is weaker than being an elementary substructure.

The satisfaction relation says that the finite code $e$ of a first-order formula is true in a set-sized first-order structure $A$ at assignment $\vec{a}$. It is defined uniformly in set theory by recursion on the finite syntax tree: evaluate atomic relations, Boolean operations and quantifiers over the given domain. A code includes only finitely many subformulas, and their truth relations are sets. This does not define a truth predicate for the ambient universe, whose domain is not a set. Finite relation closure for set-theoretic coding gives an explicit closure criterion ensuring that these truth relations are computed correctly in a transitive set.

A substructure $M\subseteq N$ is elementary when every first-order formula with parameters from $M$ has the same truth value in $M$ and $N$.

A substructure $M\subseteq N$ is elementary if and only if, whenever $N\models \exists x\phi (x,\bar{a})$ with parameters $\bar{a}$ from $M$, some witness $b\in M$ satisfies $N\models \phi (b,\bar{a})$.

After choosing a Skolem function for each existential formula, the Skolem hull of $A\subseteq N$ is the smallest subset containing $A$ and closed under those functions. The Tarski-Vaught test makes it an elementary substructure of $N$, and in a countable language an infinite hull has cardinality at most $|A|+{\aleph }_0$.

For each existential first-order formula $\exists y\phi (y,\mathbf{x})$ in a structure, a Skolem function selects a witness when one exists, with an arbitrary default when none exists. An expansion containing these functions satisfiesA subset closed under all such functions is elementary in the original language by the Tarski-Vaught test. Simultaneously choosing these functions is performed in the ordinary classical metatheory with choice.

A Skolem expansion adjoins a Skolem function for every existential first-order formula. Iterating through the successively enlarged languages, and taking their union, gives a language with witness functions even for first-order formulas involving previously added functions. Starting from a language of size $\kappa$, the resulting language has size at most $\kappa +{\aleph }_0$. A hull closed under its functions is a Skolem hull and is elementary in the expanded structure by the Tarski-Vaught test.

A structure $M$ is a model of $T$ when $M\models \sigma$ for every sentence $\sigma \in T$.

An element $a$ of a structure $M$ is definable without parameters when some first-order formula $\phi (x)$ uniquely identifies it:

A Paris model of a complete extension $T$ of ZFC is a set model $M\models T$ in which every internal ordinal is a definable element of a first-order structure without parameters.

Let $N$ be a well-founded model of set theory of a complete theory $T\supseteq \mathsf{ZFC}$, and let $M$ be a Paris model of $T$. If the internal ordinals of $M$ admitted an external descending sequence ${\alpha }_0{\ni }^M{\alpha }_1{\ni }^M\cdots$, choose formulas ${\phi }_n$ defining them. Completeness makes $M$ and $N$ satisfy the same sentences, so the unique ordinals defined by the ${\phi }_n$ in $N$ would form an externally descending membership sequence. This contradicts well-foundedness of $N$.

Under the hypothesis of Paris models are well-founded when their complete theory has a well-founded model, a Paris model $M$ is well-founded. Every automorphism of $M$ is then the identity by external epsilon induction: once all members of $x$ are fixed, extensionality gives $\pi (x)=\{\pi (y):y{\in }^{M}x\}=x$. Hence $M$ is a rigid first-order structure.

An automorphism is a bijection from a structure to itself that preserves every operation and relation in its language.

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

After adjoining a unary function symbol $f$, injectivity, surjectivity, preservation of each operation, and preservation in both directions of each relation form an axiom scheme whose models interpret $f$ as an automorphism.

A family $(f_g{)}_{g\in G}$ of automorphisms satisfying $f_g{f}_h=f_{gh}$ defines a group action. It is faithful exactly when distinct indices define distinct automorphisms, equivalently when $G$ embeds in the automorphism group.

A first-order structure is rigid when its identity map is its only automorphism. Every finite linear order is rigid, whereas $(\mathbb{Z},<)$ is nonrigid because every translation is an order automorphism.

If a theory has arbitrarily large finite nonrigid models, expand its language by a unary function $f$, axiomatize that $f$ is an automorphism, require $f$ to move some element, and add sentences demanding at least $n$ elements for every $n$. Every finite fragment has a sufficiently large finite nonrigid model, so compactness supplies an infinite nonrigid model.