# An $\omega$-stable theory that is not uncountably categorical

Morley's theorem states that a countable complete theory that's $$\omega$$-stable and has no Vaughtian pair is uncountably categorical. From the statement, I guess the "no Vaughtian pair" condition is necessary. In searching for examples of theories that are $$\omega$$-stable (with Vaughtian pair) but not uncountably categorical, I stumbled upon this article. An example is given in Example 3.1.3, namely the theory in the language $$\{E\}$$ saying that $$E$$ is an equivalence relation and that for each natural number $$n$$, there is one $$E$$-class of size $$n$$. However, I don't understand the argument in the article, so I might just ask for an explanation here.

Why is this theory $$\omega$$-stable but not uncountably categorical?

• In addition to proving that this theory is $\omega$-stable and not uncountably categorical, it's also worth proving that this theory is complete (usually completeness is part of the definition of $\omega$-stability). Proving completeness is actually a bit trickier than the other two parts, in my opinion. You can do it with an EF game or by adding a unary relation symbol $P_n$ to the language to name the equivalence class of size $n$ and then proving quantifier elimination in the expanded language. – Alex Kruckman Jan 19 at 14:44
• By the way, there are many other examples of $\omega$-stable but not uncountably categorical theories. For example: (1) the theory of a single unary relation symbol picking out an infinite and coinfinite set (2) the theory of an equivalence relation with infinitely many infinite classes (3) the theory of a complete infinitely branching tree in the language of graphs (4) the theory $DCF_0$ of differentially closed fields of characteristic $0$. – Alex Kruckman Jan 19 at 14:50
• Note that $(2)$ of Alex's comment is really a simplified version of what's going on in my answer. Meanwhile, $(4)$ is great because it's a natural example, even to non-logicians, of an $\omega$-stable non-uncountably-categorical theory. – Noah Schweber Jan 19 at 20:07

Call this theory "$$T$$."

Showing that $$T$$ is not uncountably categorical is straightforward. Keep in mind that a model of $$T$$ is gotten by adjoining to the prime model (= one equivalence class of size $$n$$ for each finite $$n$$) an arbitrary number (possibly $$0$$) of equivalence classes of arbitrary infinite cardinalities. Now given $$\kappa$$ infinite, the following are some examples of non-isomorphic models of $$T$$ with cardinality $$\kappa$$:

• Exactly one class of size $$\kappa$$, no other infinite classes.

• Exactly two classes of size $$\kappa$$, no other infinite classes.

• For $$\kappa>\aleph_0$$: exactly one class of size $$\kappa$$, exactly one class of size $$\aleph_0$$, no other infinite classes.

And so on. Personally I think the last example is especially important; it's good to keep in mind that similar-looking "pieces" of the model (e.g. infinite classes) can behave very differently.

As for $$\omega$$-stability, let's start by considering the no-parameters case: can we show that there are only countably many $$1$$-types over $$\emptyset$$?

(As usual we're working in some "sufficiently saturated" monster model $$\mathfrak{M}$$ here.)

Well, intuitively the $$1$$-type over $$\emptyset$$ of some element $$a$$ is determined by a simple cardinal invariant $$size(a)$$:

Take $$size(a)$$ to be the size of the equivalence class $$a$$ lives in.

After proving that in fact $$size(a)=size(b)$$ implies $$tp_\emptyset(a)=tp_\emptyset(b)$$, we can now count the number of possible values of this invariant within the monster model $$\mathfrak{M}$$:

Either $$size(a)$$ is finite, or by saturation $$size(a)=\vert\mathfrak{M}\vert$$. So there are $$\aleph_0$$-many possible values of $$size(a)$$.

We now need to think about folding in parameter sets larger than $$\emptyset$$ and tuple lengths larger than $$1$$ - that is, counting $$n$$-types over $$A$$ for arbitrary finite $$n$$ and countable $$A\subseteq\mathfrak{M}$$. EDIT: not really, see Alex Kruckman's comment below; I'm making things harder than they need to be here. This gets a bit tedious, but the basic idea is still the same: we want to show that there are only a few different possible behaviors for a given tuple.

For example, here's how to count the $$2$$-types over a one-element parameter set $$\{c\}$$. The type of a pair $$(a_0,a_1)$$ in $$\mathfrak{M}$$ over $$\{c\}$$ is determined by the following data.

First, we have the "$$\emptyset$$-part" of each individual element of the pair $$(a_0,a_1)$$:

What are the cardinalities $$\alpha_0$$, $$\alpha_1$$ of the classes of $$a_0,a_1$$ in $$\mathfrak{M}$$? As before, there are $$\aleph_0$$-many possibilities here.

Next, we consider the structure within the tuple $$(a_0,a_1)$$:

Are $$a_0$$ and $$a_1$$ equal? Are $$a_0$$ and $$a_1$$ equivalent? There are finitely many possibilities here.

Finally, we bring the parameter into the question:

How do $$a_0$$ and $$a_1$$ compare with $$c$$, both with respect to equality and equivalence? Again, there are only finitely many possible behaviors.

Putting all this together we get as hoped for only countably many $$2$$-types over a one-element parameter set in $$\mathfrak{M}$$. And it should be reasonably clear how to continue this to get $$\omega$$-stability.

• +1, but to prove $\omega$-stability, you fortunately only need to count $1$-types (since an $n$-type over a countable set is determined by a sequence of $n$ $1$-types over countable sets). In this case, I think it's actually pretty straightforward to directly count the number of $1$-types over an arbitrary countably infinite set. – Alex Kruckman Jan 19 at 14:21
• @AlexKruckman Good point, I forgot that it's enough to just count the $1$-types here (early in the morning still). – Noah Schweber Jan 19 at 14:30
• You can also assume the countable set of parameters is a model if you want. This makes it easier because every type which "lives in" a finite class is actually isolated by $x=a$. – Alex Kruckman Jan 19 at 14:33
• @AlexKruckman can you maybe say a little bit more why it suffices to count 1-types? – ikrto Jan 19 at 20:03
• @ikrto What is your definition of $\omega$-stable? – Alex Kruckman Jan 19 at 21:01