What are some examples of complete theories in a finite relational language that are

1) $\omega$-stable

2) Has continuum many countable models up to isomorphism

I tried reverse engineering the example in If a theory has a countable $\omega$-saturated model does it need to have only countable many countable models? but couldn't find a way around the "naming the elements" trick to obtain sufficiently many types used there.

Edit 1: Does the following work? I'm having some trouble establishing completeness, $\omega$-stability:

Let $L=\{U,E,R\}$, $U$ is unary, $E,R$ are binary:

The theory $T$ says that:

1) The universe splits in to $U$ and $\neg U$ both infinite.

2) E is an equivalence relation and on $\neg U$. it has precisely one equi. class $\neg U$ itself.

3) Each element of $U$ is in some $E$ class

4) No two elements of $\neg U$ are $R$ related.

5) The allowed $R$ related structures are $n$ cycles for each $n$

6) $U$ has infinitely many $n$ cycles for each $n$ (using $R$)

7) If the equi. class on $U$ contains an $n$-cycle for some $n$ then it contains all $n$ cycles in $U$ and for $n\neq m$, no other $n$ cycle is allowed in the equivalence class.

8) Each point, say $x$, in $\neg U$ is $R$ related to some point in $U$, and the points that $x$ is $R$ related are in the same $E$ class of $U$.

9) For each $k,n$ there are infinitely many points that connect to precisely $kn$ points with $n$ cycles.

10) If $x$ is in $\neg U$ $R$ connects to an $n$ cycle, then it $R$ connects to the rest of the points in the cycle.

The idea is to look at the types where $x$ is in $\neg U$ and have they are related to infinitely many $n$ elements in the $U$. We can tell these types apart by saying what sort of $n$ cycle they connect to (eliminating the need for the infinitely many constants in the linked answer) and the number of $n$-cycles they connect to. But this should still keep the #-of types over a finite set countable....

  • 2
    $\begingroup$ In your list 1) implies 2). $\endgroup$ – Levon Haykazyan Jul 25 '17 at 2:14
  • $\begingroup$ @LevonHaykazyan: Thank you for pointing that out! $\endgroup$ – user185596 Jul 25 '17 at 10:42
  • $\begingroup$ @LevonHaykazyan: Do you have any thoughts on my proposed example? $\endgroup$ – user185596 Jul 25 '17 at 14:49
  • 2
    $\begingroup$ I am not sure I completely understand your example. However $DCF_0$ has continuum many countable models, see e.g. Corollary 2.6 of Chapter 3 of "Model Theory of Fields" by Marker, Messmer and Pillay. $\endgroup$ – Levon Haykazyan Jul 26 '17 at 1:36
  • $\begingroup$ @LevonHaykazyan Thanks! $\endgroup$ – user185596 Jul 26 '17 at 4:59

The theory $DCF_0$ of differentially closed fields of characteristic $0$ is such an example. Its $\omega$-stability is well known, and it has $2^{\aleph_0}$ countable models by Corollary 2.6 of Chapter 3 of Model Theory of Fields by Marker, Messmer and Pillay.


I think your example is more complicated than it needs to be. Here's a simple way to adjust the main idea of my example from the other thread down to a finite relational language.

$L = \{E_1,E_2\}$. $T$ says:

  • $E_1$ is an equivalence relation, and $E_2$ is an equivalence relation refining $E_1$.
  • If $xE_1y$ and the $E_2$-class of $x$ is finite, then the $E_2$-class of $y$ is finite of the same size.
  • For every $n$, $m$ in $\mathbb{N}_+$, there is exactly one $E_1$-class which contains $n$ $E_2$-classes, each of size $m$.

You should be able to show that $T$ is complete and $\omega$-stable. The type of an element is determined by the number of $E_2$-classes in its $E_1$ class, and their size, among $\mathbb{N}_+\cup \{\infty\}$. The types $(\infty,n)$ [corresponding to an $E_1$-class containing infinitely many $E_2$-classes, each of size $n$] and $(m,\infty)$ [corresponding to an $E_1$-class containing $m$ $E_2$-classes, each infinite] are non-isolated and independent, in the sense that they can be realized and omitted independently, giving continuum-many countable models.

  • $\begingroup$ Nice, very clean! $\endgroup$ – Noah Schweber Jul 27 '17 at 19:33
  • 1
    $\begingroup$ I should say, though, that Levon's example of DCF$_0$ is much less contrived and should really be the accepted answer! $\endgroup$ – Alex Kruckman Jul 27 '17 at 19:34
  • $\begingroup$ Thanks Alex. I will wait to see what Levon does :) $\endgroup$ – user185596 Jul 27 '17 at 20:58

Your Answer

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