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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Alex Kruckman Jan 19 at 14:44
  • 2
    $\begingroup$ 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$. $\endgroup$ – Alex Kruckman Jan 19 at 14:50
  • $\begingroup$ 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. $\endgroup$ – 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.

  • 2
    $\begingroup$ +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. $\endgroup$ – Alex Kruckman Jan 19 at 14:21
  • $\begingroup$ @AlexKruckman Good point, I forgot that it's enough to just count the $1$-types here (early in the morning still). $\endgroup$ – Noah Schweber Jan 19 at 14:30
  • $\begingroup$ 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$. $\endgroup$ – Alex Kruckman Jan 19 at 14:33
  • $\begingroup$ @AlexKruckman can you maybe say a little bit more why it suffices to count 1-types? $\endgroup$ – ikrto Jan 19 at 20:03
  • $\begingroup$ @ikrto What is your definition of $\omega$-stable? $\endgroup$ – Alex Kruckman Jan 19 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.