A theory *T* is **inductive** if any union of an increasing chain of models of *T* (possibly of transfinite length) is a model of *T* as well.

An **∀∃-sentence** is a sentence of the form

- $ \forall x \exists y : \phi(x;y) $

with *x* and *y* tuples and $ \phi(x;y) $ quantifier-free. An **∀∃-theory** is a theory made of ∀∃-sentences.

It turns out that these two notions are essentially the same:

**Theorem:** Let *T* be a theory. The following are equivalent:

- (a) If $ \{M_\alpha : \alpha < \lambda\} $ is an increasing chain of models of
*T*(so $ M_\alpha \subset M_\beta $ for $ \alpha < \beta $), then the union $ \bigcup_{\alpha < \lambda} M_\alpha $ is a model of*T*. - (b) If $ M_1 \subset M_2 \subset \cdots $ is an increasing chain of models of
*T*, of length $ \omega $, then $ \bigcup_{i =1 }^\infty M_i $ is a model of*T*. - (c)
*T*is equivalent to an ∀∃-theory.

## ProofEdit

*Proof:* Clearly (a) implies (b), since (b) is the $ \lambda = \omega $ case of (a). The implication from (c) to (a) is also relatively straightforward. It boils down to the fact that if $ \{M_\alpha : \alpha < \lambda\} $ is an increasing chain of structures, and

- $ M_\alpha \models \forall x \exists y : \phi(x;y) \qquad (*) $

for all $ \alpha $, then

- $ \bigcup_{\alpha < \lambda} M_\alpha \models \forall x \exists y : \phi(x;y) $

Indeed, if *x = a* is a tuple from the union, then *a* is finite, so *a* comes from some specific $ M_\alpha $. By (*), there is some *b* in $ M_\alpha $ such that $ M_\alpha \models \phi(a;b) $. As $ \phi(x;y) $ is quantifier-free, $ \phi(a;b) $ also holds in the union. So for any *a* from the union, there is some *b* from the union such that $ \phi(a;b) $ holds, as claimed.

It remains to show that (b) implies (c). Let *T*_{∀∃} denote the set of all ∀∃-sentences implied by *T*. Any model of *T* is a model of *T*_{∀∃}. If we show the converse, then *T* is equivalent to the ∀∃-theory *T*_{∀∃}, and we are done.

**Claim:** Let *M* be a model of *T*_{∀∃}. Then there is a model *M*_{2} of *T* extending *M*, and a structure *M*_{3} extending *M*_{2} such that *M*_{3} is an elementary extension of *M*.

*Proof:* Elementary extensions of *M* are the same thing as models of the elementary diagram of *M*. Let *S* be the elementary diagram of *M*. Consider *S*_{∀}, the set of universal sentences over *M* which hold in *M*. If *S*_{∀} ∪ *T* is inconsistent, then there is some true universal statement about some element of *M* which contradicts *T*. That is, there is a universal formula $ \phi(x) $, and a tuple *a* from *M*, such that

- $ M \models \phi(a) $

and

- $ T \cup \{\phi(a)\} $ is inconsistent.

By the lemma on constants,

- $ T \vdash \forall x \neg \phi(x) $

Now the formula $ \neg \phi(x) $ is existential, so the sentence $ \forall x \neg \phi(x) $ is an ∀∃-sentence. In particular, it is part of *T*_{∀∃}, so it holds in *M*:

- $ M \models \forall x \neg \phi(x) $

But this contradicts the fact that $ M \models \phi(a) $.

Therefore *S*_{∀} ∪ *T* actually is consistent. Let *M*_{2} be a model. Then *M*_{2} is a model of *T*. Also, *S*_{∀} contains all the quantifier-free statements in *S*, which exactly constitute the diagram of *M*. So *M*_{2} is a model of the diagram of *M*, i.e., *M*_{2} is an extension of *M*.

Finally, since *M*_{2} satisfies the universal theory of the elementary diagram of *M*, we can embed *M*_{2} into some model *M*_{3} of the elementary diagram of *M*. But a model of the the elementary diagram of *M* is just an elementary extension of *M*. So we have produced the desired extensions. QED_{claim}

Now, given a model *M* of *T*_{∀∃}, we will prove that *M* is a model of *T*, completing the proof of the Theorem.

By the Claim, we can produce

- $ M = M_1 \subset M_2 \subset M_3 $

with $ M_1 \preceq M_3 $ and $ M_2 \models T $. Since $ M_1 \equiv M_3 $, $ M_3 $ is itself a model of $ T_{\forall \exists} $. So we can apply the claim to $ M_3 $, producing

- $ M = M_1 \subset M_2 \subset M_3 \subset M_4 \subset M_5 $

with $ M_3 \preceq M_5 $ and $ M_4 \models T $.

Continuing on in this fashion, one gets an infinite ascending chain of structures

- $ M = M_1 \subset M_2 \subset \cdots $

such that $ M_{2k} \models T $ and

- $ M_1 \preceq M_3 \preceq M_5 \preceq \cdots $.

By the Tarski-Vaught Theorem,

- $ M = M_1 \preceq \bigcup_{i = 1}^\infty M_{2i - 1} = \bigcup_{i = 1}^\infty M_i $.

And, since

- $ M_2 \subset M_4 \subset M_6 \subset \cdots $

is an increasing chain of models of *T*, of length $ \omega $,
we have

- $ \bigcup_{i =1}^\infty M_i = \bigcup_{i = 1}^\infty M_{2i} \models T $.

So *M* is an elementary substructure of a model of *T*. Therefore, *M* is a model of *T*.

So every model of *T*_{∀∃} is a model of *T*. Consequently, *T* is equivalent to the ∀∃-theory *T*_{∀∃}. This shows that (b) implies (c), completing the proof of the theorem. QED.

## ExamplesEdit

Many common theories have this property:

- Rings, groups, boolean algebras, anything equational
- Fields, differential fields, difference fields, integral domains
- Any model complete theory: an ascending chain of models will always be an elementary chain of models (by model completeness), so the union will still be a model.
- Any universal theory, such as
*T*_{∀}for*any*theory*T*. - DLO
- The random graph
- PAC fields

A simple example of a theory without this property is the theory of $ \mathbb{Z} $ as an ordered set. Note that

- $ \mathbb{Z} \subset \frac{1}{2}\mathbb{Z} \subset \frac{1}{4}\mathbb{Z} \subset \cdots $

is an ascending chain of models of this theory. (Each structure in this chain is isomorphic to $ \mathbb{Z} $, so certainly a model of its complete theory.) However, the union of this increasing chain is the ring $ \mathbb{Z}[1/2] $, which is a dense linear order. In particular, the statement

- $ \forall x \forall y : x < y \rightarrow \exists z : x < z < y $

holds in the limit, even though it is false in $ \mathbb{Z} $. So the limit is not a model of this theory.

For a more real-world example, the theory of pseudo-finite fields is not inductive. For example, let $ \mathbb{F}_q $ be the field with *q* elements. For each *n* > 0, let *K*_{n} be the amalgam of $ \mathbb{F}_{2^{p^k}} $ as *p* ranges over all primes. It is known that *K*_{n} is pseudo-finite for each *n*. Also, *K*_{n} ⊆ *K*_{n+1} for each *n*, so we have an ascending chain of pseudo-finite fields. However,

- $ \bigcup_{n = 1}^\infty K_n = \overline{\mathbb{F}_q} $

is algebraically closed, rather than pseudo-finite.

(On the other hand, the theory of pseudo-finite fields can be made to be model complete by adding in predicates SOL_{n}(*x*_{1},...,*x _{n}*) interpreted as

- $ \exists y : y^n = x_1 y^{n-1} + \cdots + x_{n-1} y + x_n $ )

## Inductive Theories and Existential ClosednessEdit

Inductive theories cooperate well with notions such as existential closedness and model companions. The main results are:

**Theorem:** Let *T* be inductive. Then every model of *T* can be embedded into an existentially closed model of *T*.

**Theorem:** Let *T* be inductive. Then *T* has a model companion if and only if the class of existentially closed models of *T* is an elementary class. If so, the models of the model companion of *T* are exactly the existentially closed models of *T*.