FANDOM


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 M2 of T extending M, and a structure M3 extending M2 such that M3 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 ST 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 ST actually is consistent. Let M2 be a model. Then M2 is a model of T. Also, S contains all the quantifier-free statements in S, which exactly constitute the diagram of M. So M2 is a model of the diagram of M, i.e., M2 is an extension of M.

Finally, since M2 satisfies the universal theory of the elementary diagram of M, we can embed M2 into some model M3 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. QEDclaim

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:

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 Kn be the amalgam of $ \mathbb{F}_{2^{p^k}} $ as p ranges over all primes. It is known that Kn is pseudo-finite for each n. Also, KnKn+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 SOLn(x1,...,xn) 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.