We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific symbols) is countable and contains a two-place predicate symbol, then there are $2^{2^{\aleph_0}}$ classes of structures for $L$ closed under $\equiv$ but only $2^{\aleph_0}$ such $EC_\Delta$ classes?

Here is what I think. Every $EC_\Delta$ class is obtained via a set of first-order sentences. If $L$ is countable, there are $2^{\aleph_0}$ such sets because $card(Sent(L)) = \aleph_0$ and $\wp(Sent(L)) = 2^{card(Sent(L))}$. And every $EC_\Delta$ class is closed under $\equiv$.

But how to show that there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$? Why the assumption that $L$ contains a two-place predicate symbol is relevant?

Thanks for help!

  • $\begingroup$ What is $EC_\Delta$? $\endgroup$ – tomasz Jun 30 '14 at 12:55
  • $\begingroup$ EC_{\delta}, or EC, is the class of models of some $L$-theory, not necessarily complete $\endgroup$ – user115940 Jun 30 '14 at 13:15
  • $\begingroup$ @user115940 $EC_\Delta$ and $EC$ classes are not identical. A class of $L$-structures $K$ is $EC_\Delta$ if there is a (possibly infinite) set of $L$-sentences $X$ such that $K = Mod(X)$, whereas $K$ is $EC$ if there is a finite set of such sentences or equivalently there is a $L$-sentence $\phi$ such that $K = Mod(\phi)$ (such $\phi$ is merely a conjunction of all elements of $X$ which of course is a first-order sentence; in case of infinite $X$ it wouldn’t be). Every $EC$ class is $EC_\Delta$ and every $EC_\Delta$ class is an intersection of some $EC$ classes. $\endgroup$ – Roy Jun 30 '14 at 15:07

I will write "many" for the cardinal of the power set of the reals.

Note that a class of structures which is closed with respect to elementary equivalence is the same as a collection of complete theories (exactly those theories which are the theory of some structure in your collection).

If you want many classes, it is enough to have continuum many complete theories: for each subset of these theories, look at the class of those structures $M$ with the property that the theory of $M$ is in the subset. Different subsets give different collections. So let us show how to construct continuum many complete theories (and explain why you need to assume something about the language)

If $L$ has a binary predicate $E$, you can say that $E$ is an equivalence relation, and then for every infinite subset $A$ of the natural numbers you can say that there is precisely one equivalence classes of size $k$, for each $k$ in $A$. This gives you continuum many distinct theories, since there are continuum many infinite susets of the natural numbers.

If $L$ has a single unary predicate $P$ then you cannot say much. You can only specify the number of elements satisfying $P$ (finite for some fixed natural number, or infinite) and similarly for the complement. So there are only countably many complete theories in this language.

EC classes are those classes of structures which satisfy some given $L$-theory, not necessarily complete. These are in bijective correspondence with $L$-theories, again not necessarily complete, as before. Since an $L$-theory is just a collection of sentences and there are only countably many sentences, there can only be continuum many theories, and hence only continuum many EC classes. Conversely, there are continuum many complete theories, and the class of models of each of these complete theory is an EC class. These classes are all distinct, so there are continuum many classes.

  • 1
    $\begingroup$ Sorry but I don't get the idea. Why the existence of continuum such theories implies the fact that there are $2^{2^{\aleph_0}}$ classes closed under $\equiv$? $\endgroup$ – Roy Jun 29 '14 at 16:24
  • 1
    $\begingroup$ For each set $A$ of complete $L$-theories, look at the family of structures $M$ with the propety that the theory of $M$ is in $A$. $\endgroup$ – user115940 Jun 29 '14 at 16:33
  • $\begingroup$ @user115940: but OP asked about far more than just continuum theories. $\endgroup$ – tomasz Jun 30 '14 at 12:54
  • $\begingroup$ For each collection $A$ of complete theories, look at the class of structures that are models of some theory in $A$. This is a class of structures closed with respect to elementary equivalence. Furthermore distinct collections of complete theories give different classes. There are continuum theories, so many collection of theories $\endgroup$ – user115940 Jun 30 '14 at 13:00
  • 1
    $\begingroup$ @user115940: Oh. I see what you mean now. Thanks for clearing that up. :) Of course there can't be more than continuum many complete $L$-theories (because there are only that many countable models). That said, you might want to add that the theory says that $E$ has infinitely many infinite classes (so that it is complete whether or not $A$ is finite). $\endgroup$ – tomasz Jun 30 '14 at 13:11

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.