Let $T$ be a theory in a language $\mathcal L = \{E_i(x,y) \mid i \in \omega \}$ expressing the following:
(1) $E_i$ is an equivalence relation with each equivalence class infinite, for each $i \in \omega$.
(2) $E_0$ has two classes.
(3) $E_{i+1}$ refines $E_i$, and every class of $E_i$ is given by the disjoint union of two classes of $E_{i+1}$.
(a) What is the number of $1$-types that are complete over $\emptyset$? What is the number of $2$-types that are complete over $\emptyset$?
(b) What is the number of non-isomorphic countable models of $T$? Also, given an infinite cardinal $\kappa$, what is the number of models of $T$ of size $\kappa$?
I get the intuition behind the theory $T$, that we have a countably-infinitely branching of two initial equivalent classes. I have shown that $T$ is a complete theory eliminating quantifiers. I am not sure where to go about from here. We are to show the number of possibilities for complete $1$-types of the theory of any model $\mathcal M$ of $T$. I have read here for a more intuitive understanding of a type, but I am still a little lost on how to intuitively understand the following definition of a type:
An $n$-type of a theory $T$ of a language $\mathcal L$ is a set $p$ of formulas $\varphi(x_1,\dots,x_n)$ that has free variables among $x_1,\dots,x_n$ such that $T \subseteq p$ and $p$ is satisfiable, i.e. there is a structure $\mathcal A$ and elements $a_1,\dots,a_n$ in the universe of $\mathcal A$ such that $\mathcal A \models [a_1,\dots,a_n]$ for all $\varphi \in p$.
An $n$-type of a structure $\mathcal A$ over $X \subset A$ (where $A$ is the universe of $\mathcal A$ is a type $p(x_1,\dots,x_n)$ of the theory of $\mathcal A_X$, where $\mathcal A_X$ is an $\mathcal L \cup \{c_a : a \in X \}$-structure expanding $\mathcal A$ by interpreting $c_a$ as $a$.
In particular, does this mean that a $2$-type can be considered to have a $1$-type as a subset?
Also, for part (b), I get that there can be at most $2^{\aleph_0}$ possibilities for the countable case, since there are only countably many elements and each elements' equivalence class belonging is in bijective correspondence with an infinite sequence of $0$s and $1$s. The question remains to show there is at least $2^{\aleph_0}$ non-ismorphic countable models of $T$. I am given the hint that consider the case where, for example, elements $\{1,2,\dots,n\}$ remain in the same equivalence class forever, and consider the models with differing "breakage point" between $1$ and $2$ occurs, when they first become separate in equivalence classes for $E_m$ for some $m$. I kind of get the intuition behind this hint, or at least the intuition behind why there has to be at least countably infinite non-isomorphic models of $T$. However, I am grasping less of the formal proof of these two intuitions. I have also read this post but I couldn't understand what they were saying. Could someone help me out here?
A type (relative to $T$) is just a set of formulas which can be simultaneously satisfied by a tuple from a model of $T$. So it's a list of properties that you want to be able to satisfy simultaneously. I'm not sure what else you're looking for in terms of an intuitive understanding.
The definition of "type" in your question does not include completeness. Often, when people talk about types, they mean complete types - not just sets of formulas consistent with $T$, but maximal sets of formulas consistent with $T$. You can think of a complete type as a description of all the properties satisfied by a tuple from a model of $T$.
Yes. If $p(x,y)$ is a $2$-type, then $p|_x = \{\varphi(x)\mid \varphi(x)\in p\}$ (the set of formulas in $p$ with free variables from $x$) and $p|_y = \{\varphi(y)\mid \varphi(y)\in p\}$ (the set of formulas in $p$ with free variables from $y$) are both $1$-types. If $p$ is realized by $(a,b)$, then $p|_x$ is realized by $a$ and $p|_y$ is realized by $b$.
Now let's look at your particular theory of equivalence relations.
By quantifier elimination, every formula in $1$ variable is a boolean combination of atomic formulas in $1$ variable. The only such formulas (with no parameters) are $E_i(x,x)$, which are all true of every element. So there is only one complete $1$-type over $\varnothing$.
Now the atomic formulas (with no parameters) in $2$ variables $x$ and $y$ are $E_i(x,x)$, $E_i(y,y)$, $E_i(x,y)$, and $E_i(y,x)$. The first two are always true, and the third and fourth are equivalent. Further, if $i<j$, then $E_j(x,y)$ entails $E_i(x,y)$. So there are countably many complete $2$-types over $\varnothing$: For each $i$, we have a unique type containing $E_k(x,y)$ for all $k<i$ and $\lnot E_k(x,y)$ for all $k\geq i$ (this is the type of two elements which "split" at level $i$). Additionally, we have a unique type containing $E_k(x,y)$ for all $k\in \omega$ (this is the type of two elements which never split, so they live in the same class for the equivalence relation $E_\omega = \bigcap_{i\in \omega} E_i$).
You wrote "there can be at most $2^{\aleph_0}$ possibilities for the countable case, since there are only countably many elements and each elements' equivalence class belonging is in bijective correspondence with an infinite sequence of $0$s and $1$s."
This is true, but for a more basic reason that what you wrote: we don't have to understand anything about the theory to see this. For any theory $T$ in a countable language, the number of countable models of $T$ up to isomorphism is at most $2^{\aleph_0}$. This is because we can assume a model has domain $\omega$, and then to specify a model, we only need to make countably many choices: for each symbol in the language and each tuple of the appropriate length from $\omega$, we need to decide whether the relation holds, or we need to decide which element from $\omega$ is the output of the function.
I don't understand the hint you've been given toward seeing that your theory has at least $2^{\aleph_0}$-many countable models. Instead, I would think of it like this: on any countable model $M$, we have an equivalence relation $E_\omega = \bigcap_{i\in \omega} E_i$. Let's say $k\in \omega$ is represented by $M$ if there is an $E_\omega$-class with exactly $k$ elements, and let the spectrum of $M$ be the set of natural numbers represented by $M$. It is clear that if $M$ and $N$ are isomorphic, then they have the same spectrum.
It remains to show that for any infinite $X\subseteq \omega$ with $0\notin X$, there is a countable model $M$ with spectrum $X$. Since there are $2^{\aleph_0}$ infinite subsets of $\omega_{>0}$, this shows that there are at least $2^{\aleph_0}$ countable models up to isomorphism.
So fix $X$, and enumerate $X$ as $x_0<x_1<x_2<\dots$. Show that $T$ has an atomic model (e.g. this follows from the fact that $T$ is small - it has only countably many complete $k$-types over $\varnothing$ by reasoning extending the analysis of $1$-types and $2$-types above). Let $M$ be an atomic model. Since the $2$-type which says $x$ and $y$ are in the same $E_\omega$-class is not isolated, each $E_\omega$-class in $M$ has size $1$. Now enumerate $M$ as $\{m_i\mid i\in \omega\}$ and build a new model $M_X$ by adding $x_i-1$ new elements to the $E_\omega$-class of $m_i$, so this class has $x_i$ elements total. The resulting $M_X$ is countable, satisfies the axioms of $T$, and has spectrum $X$.
This is a significantly more difficult question. The answer is $\min(2^\kappa,\mu^{2^{\aleph_0}})$, where $\mu$ is the number of (finite or infinite) cardinals less than or equal to $\kappa$.
Note that if $\aleph_0\leq \kappa\leq 2^{\aleph_0}$, then $2^\kappa\leq 2^{2^{\aleph_0}} \leq \mu^{2^{\aleph_0}}$, so the count is $2^\kappa$. And if $2^{\aleph_0}\leq \kappa$, then $\mu^{2^{\aleph_0}}\leq (2^\kappa)^{2^{\aleph_0}} = 2^{\kappa\cdot 2^{\aleph_0}} = 2^\kappa$, so the count is $\mu^{2^{\aleph_0}}$.
The general reasoning above shows that any theory $T$ in a language of size at most $\kappa$ has at most $2^\kappa$-many models of cardinality $\kappa$. Additionally, given a model $M$ of size $\kappa$, if we label each $E_i$-class by a $0$ or a $1$, we get a labeling of the $E_\omega$-classes (well, the potential classes, since some of them might be empty) by elements of $2^\omega$, and $M$ determines a function from $2^\omega$ to the set of cardinals $\leq \kappa$, assigning to each class its size (which could be $0$). If two models determine the same function, they are isomorphic - but note that the implication does not go the other way, since we could have isomorphic models which determine different functions, because the isomorphism does not respect the labeling of equivalence classes by $0$s and $1$s. In any case, we get the upper bound of $\min(2^\kappa,\mu^{2^{\aleph_0}})$.
For the lower bound, we need to deal with this issue that isomorphic models can have different functions. My strategy is to "rigidify" by starting with a countable model in which every $E_\omega$-class present in the model has a different number of elements. Then these classes are distinguishable and distinguish the remaining potential classes, allowing us to use functions as above as true invariants.
Let $X$ be the set of odd natural numbers, and let $M_X$ be the countable model constructed above, so $M_X$ has exactly one $E_\omega$-class of each odd natural number size. There are $2^{\aleph_0}$-many non-realized $1$-types over $M_X$, each corresponding to a potential $E_\omega$-class. Let $P$ be the set of these types which correspond to potential $E_\omega$-classes which are not present in $M_X$, and note that $|P| = 2^{\aleph_0}$.
Now fix $\kappa>\aleph_0$. Fix a set $Q\subseteq P$ with $|Q| = \min(\kappa,2^{\aleph_0})$. When $\kappa\geq 2^{\aleph_0}$ we can take $Q = P$. Let $C$ be the set of (finite or infinite) cardinals $\leq \kappa$ which are not odd natural numbers. Note that $|C| = \mu$.
We build a model $M_{f}$ of cardinality $\kappa$ for each choice of function $f\colon Q\to C$ such that $\kappa$ is in the range of $f$. Simply modify $M_X$ by adding $f(q)$-many elements realizing the type $q$, for each $q\in Q$. We have $|M_{f}| = \kappa$ since the total number of elements is $\aleph_0+\sum_{q\in Q} f(q)$, which is at least $\kappa$ (since $\kappa = f(q)$ for some $q$) and at most $\kappa$ (since it is a sum of at most $\kappa$-many cardinals $\leq \kappa$).
Further, if $f\neq f'$, then $M_{f}\not\cong M_{f'}$. Any isomorphism between the two would have to restrict to an isomorphism between the copies of $M_X$ present in each in a way that preserves $E_\omega$-classes (by uniqueness of the sizes of these classes), and then would have to preserve complete types over $M_X$. This implies that number of realizations of each such type is the same in each model, so $f = f'$.
Now the number of choices for $f$ is $\mu^{|Q|} = \mu^{\min(\kappa,2^{\aleph_0})}$. When $\aleph_0\leq \kappa\leq 2^{\aleph_0}$, $2^{\kappa}\leq \mu^{\kappa}$, so we have constructed at least $2^\kappa$-many models up to isomorphism. When $\kappa\geq 2^{\aleph_0}$, we have constructed at least $\mu^{2^{\aleph_0}}$ models up to isomorphism. This establishes the desired lower bounds.
In the paper The uncountable spectra of countable theories, Hart, Hrushovski, and Laskowski computed all the possible spectra (in the sense of the number of non-isomorphic models in all uncountable cardinalities) for countable theories. The counting we've done for this theory puts it into case (6) of the main theorem, with $d = 1$, $\Gamma(1) = \beth_0(\mu^{\sigma(1)}+\alpha(1))$, $\sigma(1) = \beth_1$, and $\alpha(1) = 0$.