Elementary substructure

In model theory, given two structures $mathfrak\; A\_0$ and $mathfrak\; A$, both of a common signature $Sigma$, we say that $mathfrak\; A\_0$ is an elementary substructure of $mathfrak\; A$ (sometimes notated $mathfrak\; A\_0\; preceq\; mathfrak\; A$ [Monk 1976: 331 (= Def. 19.14)] ) iff

# $mathfrak\; A\_0$ is a substructure of $mathfrak\; A$, and
# For every finite tuple $vec\; a$ of the universe of $mathfrak\; A\_0$, and for every formula $phi(vec\; x)$ of the first-order language $mathcal\; L$ determined by the common signature $Sigma$, the “evaluated” formula $phi(vec\; a)$ has the same truth value for both $mathfrak\; A\_0$ and $mathfrak\; A$.

Formal definition

Let $mathfrak\; A\_0$ and $mathfrak\; A$ be mathematical structures, both of a common signature $Sigma$. We say that $mathfrak\; A\_0$ is an elementary substructure of $mathfrak\; A$, iff the following conditions hold:

Substructure relationship

We assumed in the first condition that $mathfrak\; A\_0$ be a substructure of $mathfrak\; A$.We shall utilize this fact tacitly in the second condition: each assignment $a\_0$ over $mathfrak\; A\_0$ is at the same time an assignment over $mathfrak\; A$,

Equivalent evaluations of each formula, using each "more restricted" assignment

We can formalize the second condition if we use the auxiliary concept "assignment": for every assignment $a\_0$ over $mathfrak\; A\_0$ (that is, $a\_0$ is a function from the set of variables of language $mathcal\; L$ to the universe of structure $mathfrak\; A\_0$), and for every formula $phi$ of language $mathcal\; L$, the following logical equivalence must hold::$mathfrak\; A\_0\; models\; phi\; [a\_0]\; ;mathrm\{if;and;only;if\};\; mathfrak\; A\; models\; phi\; [a\_0]$. [Note that logical equivalence is a statement in the metalanguage. Without using this notion, we can say: either both must be true or both must be false for the following two statements:
*$mathfrak\; A\_0\; models\; phi\; [a\_0]$
*$mathfrak\; A\; models\; phi\; [a\_0]$] [As mentioned, here is the point where we utilize tacitly the condition requiring substructure relationship: $a\_0$ is at the same time an assignment over the larger structure as well. This is the motivation behind the "asymmetric" nature of the condition.]

In other words, $mathfrak\; A\_0$ and $mathfrak\; A$ are elementarily equivalent over $mathcal\; L\_\{mathfrak\; A\_0\}$. Here $mathcal\; L\_\{mathfrak\; A\_0\}$ denotes the language $mathcal\; L$ augmented with constants, one for each member of the universe of $mathfrak\; A\_0$.

Equivalent statements

It can be proven that it suffices to require a weaker condition instead of $mathfrak\; A\_0\; subseteq\; mathfrak\; A$: it is enough if the corresponding universes stand in subset relationship, that is $A\_0\; subseteq\; A$. Together with the other condition about the equivalent evaluations, the subset relationship of the universes implies that substructure relationship holds as well. [Monk 1976: 331 (= Cor. 19.15)]

We say $mathfrak\; A$ is an elementary extension of $mathfrak\; A\_0$ if and only if $mathfrak\; A\_0$ is an elementary substructure of $mathfrak\; A$.

The Tarski-Vaught test is a very useful necessary and sufficient condition for determining, given a pair $mathfrak\; A\_0\; subset\; mathfrak\; A$, whether $mathfrak\; A\_0$ is an elementary substructure of $mathfrak\; A$.

See also

* Elementary embedding

Notes

References

*