Examples - Model Theory - Cambridge III notes

12 Examples

Theorem 12.1. $ACF$ has quantifier elimination.

Proof. We will show that condition Theorem 11.4(iii) holds.

So we need to show that for any finitely generated $A$ , $T \cup D (A)$ is complete.

Fix a finitely generated $L$ -structure $A$ and show $ACF \cup D (A)$ is complete. Use Los-Vaught test. Fix $K_{1}, K_{2} ⊨ ACF \cup D (A)$ uncountable, wiht $| K_{1} | = | K_{2} |$ . $A$ is a finitely generated integral domain contained in $K_{1}, K_{2}$ .

So since $A$ contains $1$ , it determines the characteristic. So $char (K_{1}) = char (K_{2})$ . So $K_{1} ≅ K_{2}$ (in $L_{rings}$ ).

Need an $L_{A}$ -isomorphism, i.e. an isomorphism $Φ : K_{1} \to K_{2}$ preserving $A$ . Consider $F_{i}$ the fraction field of $A$ in $K_{i}$ . The field of fractions of an integral domain is unique up to isomorphism, i.e. $\exists τ : F_{1} \to F_{2}$ preserves $A$ pointwise.

$A$ is finitely generated (hence finite $trdeg$ ), so $trdeg (K_{1} ∕ F_{1}) = trdeg (K_{2} ∕ F_{2})$ . Therefore $τ$ extends to $τ^{*} : K_{1} \to K_{2}$ fixing $A$ pointwise. So $K_{1} ≅_{L_{A}} K_{2}$ . □

Definition 12.2 (Constructible). Let $F$ be a field. We say that $X \subseteq F^{n}$ is constructible if it is a boolean combination of subsets of $F^{n}$ defined by $p (x_{1}, \dots, x_{n}) = 0$ for $p (\bar{x}) \in F [\bar{x}]$ .

Corollary 12.3 (Chevalley’s Theorem). Assuming that:

$K ⊨ ACF$
$X \subseteq K^{n}$ a constructible set

Then the projection

Y = {(a_{1}, \dots, a_{n - 1}) \in K^{n - 1} : (\bar{a}, b) \in X for some b \in K}

of $X$ is also constructible.

Definition 12.4 (Rado graph). Let $L = {E}$ , with $E$ a binary relation. A Rado or Random graph is a graph $(V, E)$ such that $V \neq \emptyset$ and for any finite disjoint $X, Y \subseteq V$ there is some $v \in V$ such that:

$E (v, x)$ for all $x \in X$
$\neg (v, y)$ for all $y \in Y$

We denote the theory of Rado graphs as $R C$ . It consists of

Graph axioms (irreflexive and symmetric).
For any $k \geq 1$ and $l \geq 1$ ,

$\forall x_{1}, \dots, x_{k}, \forall y_{1}, \dots, y_{l} (\underset{i, j}{\land} x_{i} \neq y_{j} \to \exists v (\underset{i, j}{\land} E (v, x_{i}) \land \neg E (v, y_{j}))) .$

Facts:

$R G$ is $ℵ_{0}$ -categorical.
If $M ⊨ R G$ then every finite graph is an induced subgraph.
Suppose $M, N ⊨ R G$ are two coutnable models, and $f : X \to Y$ is a graph isomorphism between $X \subseteq M$ (finite) and $Y \subseteq M$ (finite). Then $f$ extends to an isomorphism from $M$ to $N$ .

Theorem 12.5. $R G$ has quantifier elimination.

Proof. Option 1: Show $R G \cup D (A)$ , with $A$ a finite graph is complete.

Option 2: Use (ii) of Theorem 11.4. Fix $M, N ⊨ R G$ , $A \subseteq M \cap N$ . Fix a quantifier-free formula $φ (x_{1}, \dots, x_{n}, y)$ , $\bar{a} \in A^{n}$ . Assume that there exists $b \in M$ , $M ⊨ φ (\bar{a}, b)$ . Want to show $\exists c \in N$ such that $N ⊨ φ (\bar{a}, c)$ .

Write $φ (\bar{x}, y)$ in disjunction normal form:

\lor_{s = 1}^{k} \land_{t = 1}^{l_{s}} 𝜃_{s, t} (\bar{x}, y)

where $𝜃_{s, t} (\bar{x}, y)$ is atomic or negated atomic. There is some $s \subseteq k$ such that $M ⊨ \land_{t = 1}^{l_{s}} 𝜃_{s, t} (\bar{a}, b)$ .

Each of $𝜃_{s, t} (\bar{x}, y)$ is one of $x_{i} = x_{j}$ , $x_{i} = y$ , $E (x_{i}, x_{j})$ , $E (x_{i}, y)$ and negations.

If $x_{i} = y$ appears then $b = a_{i} \in A \subseteq N$ and so $N ⊨ φ (\bar{a}, b)$ .

We may assume $x_{i} = y$ does not appear in $𝜃_{s, t}$ . Let

\begin{array}{l} X & = {a_{i} : M ⊨ E (a_{i}, b)} \subseteq \bar{a} \\ Y & = {a_{i} : M ⊨ \neg E (a_{i}, b)} \subseteq \bar{a} \end{array}

Then $X$ and $Y$ are finite and disjoint. So we have $c \in N$ such that

\begin{array}{l} N & ⊨ E (a_{i}, c) \forall a_{i} \in X \\ N & ⊨ \neg E (a_{i}, c) \forall a_{i} \in Y \\ c & \notin {a_{i}, \dots, a_{n}} \end{array}

So $N ⊨ \land_{t = 1}^{l_{s}} 𝜃_{s, t} (\bar{a}, c)$ and thus $N ⊨ φ (\bar{a}, c)$ . □