Mathematical logic and foundations Model theory: basic notions Proposition

Tarski–Vaught test

Builds on Elementary substructure Substructure Structure Well-formed formula

Statement

Let $L$ be a signature and let $\mathcal{M}$ be a substructure of an $L$ -structure $\mathcal{N}$ , with domains $M \subseteq N$ . Then $\mathcal{M}$ is an elementary substructure of $\mathcal{N}$ if and only if the following holds. For every $L$ -formula $\varphi(x_1, \dots, x_n, y)$ and all $a_1, \dots, a_n \in M$ , if $\mathcal{N} \models \exists y \, \varphi(a_1, \dots, a_n, y)$ , then there is $b \in M$ with $\mathcal{N} \models \varphi(a_1, \dots, a_n, b)$ .

Remarks

The condition mentions truth only in $\mathcal{N}$ , which makes it easier to check than the definition. The forward direction is direct: if $\mathcal{N} \models \exists y \, \varphi(\bar a, y)$ , then $\mathcal{M} \models \exists y \, \varphi(\bar a, y)$ , so some $b \in M$ has $\mathcal{M} \models \varphi(\bar a, b)$ , hence $\mathcal{N} \models \varphi(\bar a, b)$ . For the converse, one proves by induction on $\varphi$ that $\mathcal{M} \models \varphi(\bar a)$ if and only if $\mathcal{N} \models \varphi(\bar a)$ . Atomic formulas agree because $\mathcal{M}$ is a substructure, the connectives are immediate, and the condition handles the existential quantifier.

Example of use: in the proof of the downward Löwenheim–Skolem theorem, one closes a subset of $N$ under witnesses for all existential formulas. The test then shows that the result is an elementary substructure.

Going deeper

For a student

The Tarski–Vaught test is the standard tool to build elementary substructures. It underlies the downward Löwenheim–Skolem theorem and the construction of Skolem hulls. Combined with automorphisms of $\mathcal{N}$ that fix finitely many elements of $M$ , it also proves results such as $(\Q, <) \preceq (\R, <)$ : if $\mathcal{N} \models \exists y \, \varphi(\bar a, y)$ , an automorphism fixing $\bar a$ moves a witness into $\Q$ .

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`60SA99BER7`
URI	`m2://60SA99BER7`
Kind	statement, proposition
Writing	W0 stub
MSC	03C07
Status	This copy of the site has no build data. Run `m2 status 60SA99BER7`.
About	Elementary substructure
Uses	Elementary substructure, Substructure, Structure, Well-formed formula
Changed	2 November 2026