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

{\displaystyle \forall x\exists y:\phi (x;y)}

with x and y tuples and {\displaystyle \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 {\displaystyle \{M_{\alpha }:\alpha <\lambda \}} is an increasing chain of models of T (so {\displaystyle M_{\alpha }\subset M_{\beta }} for {\displaystyle \alpha <\beta }), then the union {\displaystyle \bigcup _{\alpha <\lambda }M_{\alpha }} is a model of T.

(b) If {\displaystyle M_{1}\subset M_{2}\subset \cdots } is an increasing chain of models of T, of length {\displaystyle \omega }, then {\displaystyle \bigcup _{i=1}^{\infty }M_{i}} is a model of T.

(c) T is equivalent to an ∀∃-theory.

Proof[]

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

{\displaystyle M_{\alpha }\models \forall x\exists y:\phi (x;y)\qquad (*)}

for all {\displaystyle \alpha }, then

{\displaystyle \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 {\displaystyle M_{\alpha }}. By (*), there is some b in {\displaystyle M_{\alpha }} such that {\displaystyle M_{\alpha }\models \phi (a;b)}. As {\displaystyle \phi (x;y)} is quantifier-free, {\displaystyle \phi (a;b)} also holds in the union. So for any a from the union, there is some b from the union such that {\displaystyle \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 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 {\displaystyle \phi (x)}, and a tuple a from M, such that

{\displaystyle M\models \phi (a)}

and

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

By the lemma on constants,

{\displaystyle T\vdash \forall x\neg \phi (x)}

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

{\displaystyle M\models \forall x\neg \phi (x)}

But this contradicts the fact that {\displaystyle M\models \phi (a)}.

Therefore S∀ ∪ T 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

{\displaystyle M=M_{1}\subset M_{2}\subset M_{3}}

with {\displaystyle M_{1}\preceq M_{3}} and {\displaystyle M_{2}\models T}. Since {\displaystyle M_{1}\equiv M_{3}}, {\displaystyle M_{3}} is itself a model of {\displaystyle T_{\forall \exists }}. So we can apply the claim to {\displaystyle M_{3}}, producing

{\displaystyle M=M_{1}\subset M_{2}\subset M_{3}\subset M_{4}\subset M_{5}}

with {\displaystyle M_{3}\preceq M_{5}} and {\displaystyle M_{4}\models T}.

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

{\displaystyle M=M_{1}\subset M_{2}\subset \cdots }

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

{\displaystyle M_{1}\preceq M_{3}\preceq M_{5}\preceq \cdots }.

By the Tarski-Vaught Theorem,

{\displaystyle M=M_{1}\preceq \bigcup _{i=1}^{\infty }M_{2i-1}=\bigcup _{i=1}^{\infty }M_{i}}.

And, since

{\displaystyle M_{2}\subset M_{4}\subset M_{6}\subset \cdots }

is an increasing chain of models of T, of length {\displaystyle \omega }, we have

{\displaystyle \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.

Examples[]

Many common theories have this property:

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

{\displaystyle \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 {\displaystyle \mathbb {Z} }, so certainly a model of its complete theory.) However, the union of this increasing chain is the ring {\displaystyle \mathbb {Z} [1/2]}, which is a dense linear order. In particular, the statement

{\displaystyle \forall x\forall y:x<y\rightarrow \exists z:x<z<y}

holds in the limit, even though it is false in {\displaystyle \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 {\displaystyle \mathbb {F} _{q}} be the field with q elements. For each n > 0, let Kn be the amalgam of {\displaystyle \mathbb {F} _{2^{p^{k}}}} as p ranges over all primes. It is known that Kn is pseudo-finite for each n. Also, Kn ⊆ Kn+1 for each n, so we have an ascending chain of pseudo-finite fields. However,

{\displaystyle \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

{\displaystyle \exists y:y^{n}=x_{1}y^{n-1}+\cdots +x_{n-1}y+x_{n}} )

Inductive Theories and Existential Closedness[]

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. ::: ::: :::