First-order structure

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

This is a structure for a first-order language, with finitary interpretations of its nonlogical symbols.

A canonical first-order structure is generated by closed-term names: each element is the interpretation of a closed term. In a first-order language without function symbols this says each element is named by a constant. The constant-name convention for canonical first-order structures agrees with this one in the function-free setting. Logical equality identifies different names for the same element.

In a first-order structure, an interpretation assigns a relation of the specified arity to each predicate symbol, a total function of the specified arity to each function symbol, and an element to each constant symbol. Evaluation of first-order terms and truth of logical formulas are then defined recursively. This specifies how symbols acquire their meanings on the underlying set.

An embedding of first-order structures is an injective function preserving function symbols and constants and both preserving and reflecting every relation symbol. Its image is a substructure. Satisfaction of an atomic diagram of a structure in an expansion gives such an embedding of first-order structures by sending each named element to its new interpretation; literal inclusion requires fixing the interpretations of those names.

An assignment in a first-order structure chooses a domain element for each variable. It determines the value of every first-order term and the truth of every first-order formula, once the interpretations of symbols are fixed. A first-order sentence has no free variables, so its truth is independent of the assignment in a first-order structure. Quantification changes the value assigned to the bound variable while retaining the other values.

A term-generated model has every element denoted by a closed term of its original language. Each element is then parameter-free definable by an equation $x=t$. A term model of a complete Henkin theory is a syntactic construction with this property, but “term-generated” can be stated for an arbitrary structure without choosing such a construction.

The standard successor structure has the natural numbers as domain, the successor function $s(n)=n+1$, and the named element zero. Its complete first-order theory is the theory of successor. Without addition, multiplication, or order, elements outside the zero-generated component are possible in other models of the same complete theory.

A definable set in a first-order structure $M$ is the set of tuples satisfying one first-order formula, possibly with a specified finite tuple of parameters $\mathbf{b}$ from the structure. A set definable over $B\subseteq M$ uses parameters from $B$. Parameter-free definability uses no extra named elements. The distinction matters: any singleton becomes definable if its own element is allowed as a parameter, while many singletons are not definable without parameters. Finite Boolean combinations of definable sets are definable, using logical conjunction, logical disjunction and logical negation.

A function $f:M^n\to M$ is a definable function if its graph of a function is a definable set. Equivalently, a first-order formula $\theta (\mathbf{x},y)$ defines exactly the pairs with $y=f(\mathbf{x})$. Totality and uniqueness mean $M\models \forall \mathbf{x}\exists !y\theta (\mathbf{x},y)$. The same definition with restricted domains gives definable partial functions. A function need not be a symbol of the language to be definable; the graph can be specified through the existing relations and operations.

A definable set has parameter-free definability when its defining first-order formula uses only the original first-order language, with no additional constants naming elements. Constants already present in the language are allowed. Every such set is invariant under all automorphisms of a first-order structure. For example, zero in the constant-free additive integers is defined by $x+x=x$, while the singleton containing one is not parameter-free definable because negation is an additive automorphism moving it. Invariance is a necessary condition in every structure, and becomes sufficient for finite sets in a countable omega-saturated model.

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.

The underlying set of elements over which the quantifiers of a first-order structure range. Relation symbols are interpreted as finitary relations on this set, and function symbols as functions on it.

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.

A structure isomorphism is a bijective structure embedding: it preserves constants and functions, and both preserves and reflects relations. Its inverse has the same properties. It therefore preserves truth of every first-order formula, by structural induction, so it preserves realization and omission of parameter-free types.

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.

The values of all closed terms in a first-order structure form a substructure when the first-order language has at least one constant. The constant ensures nonemptiness, and applying a function symbol to closed-term values again gives a closed-term value. Relations are restricted from the ambient first-order structure. Every universal sentence true in the ambient first-order structure remains true in this substructure.

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.

An embedding of first-order structures is existential when every existential formula with parameters from the source has the same truth value in the source and target. Forward preservation follows from being a structure embedding; reflection is the additional requirement. Applying compactness theorem to the target's diagram of a structure and the source's elementary diagram places the target inside an elementary extension of the source.

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$.

An injective map between subsets of structures is partial elementary when it preserves every first-order formula on tuples from its domain. This is stronger than a partial embedding, which only preserves quantifier-free formulas. In countable models, successive one-point extensions in both directions produce an elementary isomorphism by the back-and-forth method.

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})$.

The witness criterion characterizes an elementary substructure, and hence preservation of all first-order formulas with parameters from the substructure.

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.

Replacing an existentially quantified variable by a fresh Skolem function of the preceding universally quantified variables. A witness independent of all universal variables is represented by a fresh constant. The operation preserves satisfiability after expanding the first-order signature; it is not generally logical equivalence for arbitrary interpretations of the new symbols.

A first-order sentence consisting of a block of universal quantifiers followed by a quantifier-free formula, obtained by Skolemization in an expanded first-order signature. Its matrix can additionally be put into conjunctive normal form to obtain clausal form.

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:

Every element of a pointwise definable model is uniquely specified by a formula with no added parameters. Finite tuples are then uniquely specified by conjunctions of their defining formulas. For a complete theory these formulas isolate the tuple types, so such a model is an atomic model. The converse fails: a countable dense linear order without endpoints with a named point is atomic, while its other points are moved by structure automorphisms fixing that point.

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.

For a fixed prime $p$, put $s_p(0)=0$ and $s_p(n)=(-1{)}^{v_p(n)}n$ for $n\ne 0$, where $v_p(n)$ is its P-adic valuation. Additivity of the valuation on products proves $s_p(mn)=s_p(m)s_p(n)$. Changing sign does not change the valuation, so $s_p^2$ is the identity. Thus this is a structure automorphism of $(\mathbb{Z},\cdot )$. At $p=2$ it fixes one and sends two to minus two, so it does not preserve the addition graph or the nonnegative integers. Automorphism invariance of parameter-free definability therefore excludes both from definability in this multiplicative 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.

Rigidity here means absence of nonidentity automorphisms of a first-order structure; it does not assert the mechanical rigidity of a rod-and-hinge framework.

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.