Tarski-Vaught test

From Wikipedia, the free encyclopedia

The Tarski-Vaught test (sometimes called Tarski's criterion) is a result in model theory which characterizes the elementary substructures of a given structure using definable sets. It is often used to determine whether a substructure of a structure is elementary, and is particularly useful in the construction of elementary substructures. Formally,

For a given first-order language $\mathcal{L}$ , let $\mathcal{N}$ be a structure with domain

N

, and $\mathcal{M}$ be a substructure of $\mathcal{N}$ with domain

M

(written $\mathcal{M}\subseteq\mathcal{N}$ ). Then $\mathcal{M}$ is an elementary substructure of $\mathcal{N}$ (written $\mathcal{M}<\mathcal{N}$ ) if and only if for every nonempty $A\subseteq N$ definable in $\mathcal{N}$ with parameters from

M

A

contains an element of

M

[edit] Proof

First suppose $\mathcal{M}<\mathcal{N}$ . Let $A\subseteq N$ be nonempty and definable in $\mathcal{N}$ using $\varphi(x,x_1,\ldots,x_n)$ with parameters $b_1,\ldots,b_n\in M$ . We must prove $A\cap M\ne\emptyset$ . Since $A\ne\emptyset$ , we have

$\mathcal{N}\models\exists x\varphi[b_1,\ldots,b_n]$

(Note that the bracket notation here is used to indicate the semantic evaluation of the free variables of the formula.) But then, by definition of an elementary substructure,

$\mathcal{M}\models\exists x\varphi[b_1,\ldots,b_n]$

Thus there exists an $a\in M$ such that $\mathcal{M}\models\varphi[a,b_1,\ldots,b_n]$ . Again by definition of elementary substructure, $\mathcal{N}\models\varphi[a,b_1,\ldots,b_n]$ , so $a\in A$ . Thus $A\cap M\ne\emptyset$ as desired.

Conversely, suppose every nonempty subset of $N$ definable in $\mathcal{N}$ with parameters from $M$ contains an element of $M$ . We prove $\mathcal{M}<\mathcal{N}$ by induction on formulas. The atomic and boolean cases are immediate from definitions since $\mathcal{M}\subseteq\mathcal{N}$ . Suppose the result holds for $\psi(x,x_1,\ldots,x_n)$ and consider $\exists x\psi$ . Since $M\subseteq N$ , it is immediate that for any $a_1,\ldots,a_n\in M$ , if $\mathcal{M}\models\exists x\psi[a_1,\ldots,a_n]$ , then $\mathcal{N}\models\exists x\psi[a_1,\ldots,a_n]$ . Suppose now $\mathcal{M}\not\models\exists x\psi[a_1,\ldots,a_n]$ for some $a_1,\ldots,a_n\in M$ . Thus for all $a\in M$ ,

$\mathcal{M}\not\models\psi[a,a_1,\ldots,a_n]$

so by the induction hypothesis, for all $a\in M$ ,

(*) $\mathcal{N}\not\models\psi[a,a_1,\ldots,a_n]$

Now consider the set $A\subseteq N$ defined in $\mathcal{N}$ by $\psi(x,x_1,\ldots,x_n)$ using parameters $a_1,\ldots,a_n$ . If there exists $b\in N$ such that $\mathcal{N}\models\psi[b,a_1,\ldots,a_n]$ , then $A\ne\emptyset$ . By our hypothesis then, there exists an $a\in A\cap M$ . But this contradicts (*). Thus $\mathcal{N}\not\models\exists x\psi[a_1,\ldots,a_n]$ . It follows that $\mathcal{M}<\mathcal{N}$ as desired. Q.E.D.

[edit] Example

Consider the structure $\mathcal{N}=(\mathbb{N},<)$ consisting of the naturals with the usual ordering. Let $\mathcal{M}=(P,<_P)$ be the substructure consisting of the prime naturals with the induced ordering. Is $\mathcal{M}$ an elementary substructure of $\mathcal{N}$ ? Tarski's criterion provides an immediate negative answer since, for example, the number $4$ is definable in $\mathcal{N}$ without parameters by the formula