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$ – dav11 Jul 25 '17 at 10:42
  • $\begingroup$ @LevonHaykazyan: Do you have any thoughts on my proposed example? $\endgroup$ – dav11 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$ – dav11 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$ – dav11 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

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