A theory T is categorical if any two models of T are isomorphic.  If {\displaystyle \lambda } is a cardinal, T is said to be {\displaystyle \lambda }-categorical if T has a unique model of cardinality {\displaystyle \lambda }, up to isomorphism.

Both of these conditions imply that T is complete (i.e., all models of T) are elementarily equivalent. For {\displaystyle \lambda }-categoricity, this is the Łoś-Vaught Test.

Due to the Löwenheim-Skolem Theorem, almost no theories are categorical. Specifically, if T has an infinite model, then the upward Löwenheim-Skolem theorem ensures the existence of a strictly bigger model. Therefore T has at least two non-isomorphic models, and is not categorical. Consequently, the only categorical theories are the complete theories of finite structures.

The concept of {\displaystyle \lambda }-categoricity is a weakening of categoricity which has the advantage of being a non-trivial notion, while still implying completeness.

Contents

Examples[edit|edit source]

The last three examples can be seen roughly as follows. If F is a field, then an F-vector space V is determined up to isomorphism by its dimension (cardinality of a basis). If F is finite and V is infinite, then the dimension of V equals the cardinality of V. Hence any two F-vector spaces of the same size must be isomorphic.

If F is infinite, such as Q, then the cardinality of V is {\displaystyle |F|+\lambda }, where {\displaystyle \lambda } is the dimension of V over F. In particular, since Q is countable, if {\displaystyle |V|} or {\displaystyle \lambda } is uncountable, then {\displaystyle |V|=\lambda }. So for uncountable Q-vector spaces, the cardinality determines the dimension, and hence the isomorphism class. On the other hand, there are non-isomorphic countable Q-vector spaces, such as Q and Q2. So countable categoricity fails.

The case of ACF is handled similarly, using the fact that an algebraically closed field's isomorphism class is determined uniquely by the characteristic and the cardinality of a transcendence base over the prime field.

The {\displaystyle \aleph _{0}}-categoricity of DLO and the random graph can be seen using the Ryll-Nardzewski Theorem, by proving quantifier elimination in these theories and showing that there are few n-types over the empty set. On the other hand, these theories fail to be uncountably categorical because they are not stable.

[Łoś-Vaught Test]{#.C5.81o.C5.9B-Vaught_Test .mw-headline}[edit|edit source]

Theorem: If T is {\displaystyle \lambda }-categorical for some {\displaystyle \lambda \geq |T|}, and all models of T are infinite, then T is complete.

Proof: Let M and N be two models of T. We want to show that M ≡ N. By the Löwenheim-Skolem Theorem, we can find M' and N' of cardinality {\displaystyle \lambda }, with M' ≡ M and N' ≡ N. Then M' and N' are both models of T, because they are elementarily equivalent to models of T. By {\displaystyle \lambda }-categoricity, it follows that M' and N' are isomorphic. Hence they are elementarily equivalent. Now

{\displaystyle M\equiv M'\equiv N'\equiv N},

so M ≡ N. QED

This provides a relatively straightforward way of proving the completeness of the theory ACFp of algebraically closed fields in a fixed characteristic. As a consequence, one can conclude that the complex numbers are elementarily equivalent to the algebraic numbers. The completeness of ACF0 also implies that the theory of the complex numbers, as a pure field, is decidable. Consequently, Hilbert's Tenth Problem can be solved over the complex numbers. The completeness of ACF0 can also be seen as a form of the Lefschetz principle.

Countably Categorical Theories[edit|edit source]

Ryll-Nardzewski Theorem: Let M be a countable structure in a countable language. The following are equivalent:

Proof sketch: Let T be the complete theory of M. Let Sn(Ø) denote the set of n-types over the empty set. This is a compact boolean space. If Sn(Ø) is infinite, then it is not discrete, so there is some non-isolated point p ∈ Sn(Ø). Now by the Omitting Types Theorem, we can produce a countable model N of T in which the type p is not realized. By compactness and downward Löwenheim-Skolem, we can also produce a countable model of T in which the type p is realized. This implies that T is not {\displaystyle \aleph _{0}}-categorical.

So countable categoricity implies the finiteness of the type spaces. Conversely, suppose we know that the type spaces over the empty set are finite. Then given two countable models M and N of T, one can prove that M and N are isomorphic by a back-and-forth argument, implying countable categoricity. In fact, one can prove from the back-and-forth argument that if x ∈ M and y ∈ N are two tuples realizing the same type over the empty set, then there is an isomorphism from M to N sending x to y. In the case where M = N, this means that the automorphisms of M must act transitively on the set of n-tuples in M realizing each type. Since there are only finitely many n-types, there must be finitely many orbits. So the second bullet point implies the first and third bullet points.

On the other hand, the third bullet point implies the second bullet point. Specifically, suppose that Mn has finitely many orbits under Aut(M). Any 0-definable subset of Mn must be a finite union of orbits, and therefore there are only finitely many 0-definable subsets of Mn. Then the Stone space Sn(Ø) is dual under Stone duality to a finite boolean algebra, and is therefore itself finite. QED

From the Ryll-Nardzewski Theorem, one can prove that DLO and the theory of the Random Graph are {\displaystyle \aleph _{0}}-categorical. For example, in DLO, an n-type is completely determined by specifying the relative order of the n-variables. There are only finitely many possibilities, so the space of n-types is finite. In the Random Graph, an n-type is determined by specifying which of the n variables are equal, and which are connected. Again, there are only finitely many possibilities, so the type spaces are finite.

More generally, one has

Lemma: If T is a theory with quantifier-elimination in a signature with no constants, no functions, and finitely many relations, none of which are nullary, then T is complete and {\displaystyle \aleph _{0}}-categorical.

Proof: Completeness follows because every sentence {\displaystyle \phi } must be equivalent to a quantifier-free sentence, but the lack of constant symbols and nullary relations means that there are no atomic formulas without free variables, and so the only quantifier-free sentences are ⊤ and ⊥. In particular, {\displaystyle \phi } is equivalent modulo T to one of ⊤ or ⊥, so either {\displaystyle \phi } or {\displaystyle \neg \phi } is in T.

For {\displaystyle \aleph _{0}}-categoricity, note that the lack of function symbols ensures that in the free variables x1, ... xn, there are only finitely many possible atomic formulas. Consequently, there are only finitely many quantifier-free formulas, ensuring that the type spaces over the empty set are finite. Then by the Ryll-Nardzewski Theorem, T is countably categorical. QED

Uncountable Categorical Theories[edit|edit source]

Morley's Theorem: Let T be a countable theory. If T is {\displaystyle \lambda }-categorical for one uncountable cardinal, then T is {\displaystyle \lambda }-categorical for all uncountable cardinals.

Because of Morley's Theorem, one knows that (countable) theories must fall into four classes:

Proof outline: First one shows that T is stable and in fact |totally transcendental using Ehrenfeucht-Mostowski models. Next one uses the ability to stretch Vaughtian pairs in totally transcendetal theories to show that T cannot have Vaughtian pairs. From this one shows that infinity is definable in T. Using this and Cantor-Bendixson rank, one can show the existence of strongly minimal sets definable in the prime model of T. The algebraic closure operation on this strongly minimal set is a pregeometry. One associates to each model M of T the cardinality of a basis for this pregeometry. Because of no Vaughtian pairs, a model M must be constructible over such a basis. From this, one sees that M is determined up to isomorphism by the cardinality of the basis. From this, one can conclude that T is {\displaystyle \lambda }-categorical for all uncountable {\displaystyle \lambda } in roughly the same way that one proves this directly for ACFp or the theory of Q-vector spaces. (In these two examples, the resulting pregeometries are the usual pregeometries for algebraic independence and linear independence, respectively.) ∎

In fact, this argument allows one to prove the (Baldwin-Lachlan?) theorem, that if T is an uncountably categorical theory, then the number of countable models of T is either 1 or {\displaystyle \aleph _{0}}.

Much of stability theory was motivated by the problem of analyzing the structure of uncountably categorical theories.

Totally Categorical Theories[edit|edit source]

A theory if totally categorical if it is {\displaystyle \lambda }-categorical for all infinite {\displaystyle \lambda }. A great deal is known about the structure of totally categorical theories...

For example, Zilber proved that if T is totally categorical, then the underlying pregeometry is always modular. Using this, he was able to prove that T is not finitely axiomatizable. This elementary-sounding statement requires a considerable amount of stability theory to prove.