Here’s a problem I’m struggling with:
Let M and N be two denumerable models for the theory of equivalence relations such that:
(i) Every equivalence class in M and N has infinitely many members
(ii) There are infinitely many distinct equivalence classes in both M and N
Show that M and N are isomorphic
I’m frankly not even sure how to start. My guess is that we must show that the set of equivalence relations is denumerably categorical, but I’m not sure how to do that
On
Please note: Alex Kruckman has posted a much nicer answer. I considered deleting the following, but it was suggested that I leave it up. Alex, thanks for your help!
Let's let $E$ be the symbol for the equivalence relation.
One way to show the two models are isomorphic is to use what's called a back and forth argument. We want to build a sequence $M_0\subseteq M_1\subseteq M_2\subseteq\ldots$ of finite subsets of $M$, a sequence $N_0\subseteq N_1\subseteq N_2\subseteq\ldots$ of finite subsets of $N$, and a sequence $f_0,f_1,f_2,\ldots$ of functions such that for each $n\in\Bbb{N}$, $f_n:M_n\to N_n$ is an isomorphism. If we do this in a clever way, then $\underset{n\in\Bbb{N}}{\bigcup}f_n:M\to N$ will be an isomorphism.
Here's how to do it: we'll use the fact that $M=\{m_0,m_1,m_2,\ldots\}$ and $N=\{n_0,n_1,n_2,\ldots\}$, since $M$ and $N$ are countable. To start out, let $M_0=\{m_0\}$, let $N_0=\{n_0\}$, and let $f_0=\{(m_o,n_0)\}$.
Next we need to check to see if $n_1 E\,n_0$. If $n_1E\,n_0$, then let $a_1$ be the earliest element of $m_1,m_2,m_3,\ldots$ with $a_1E\,m_0$. If $\,\lnot(n_1E\,n_0)$, then let $a_1$ be the earliest element of $m_1,m_2,m_3,\ldots$ with $\lnot(a_1E\,m_0)$. Then let $M_1=\{m_0,a_1\}$, let $N_1=\{n_0,n_1\}$, and let $f_1=\{(m_o,n_0),(a_1,n_1)\}$.
At this point, we've constructed $M_0\subseteq M_1$, $N_0\subseteq N_1$, and isomorphisms $f_0:M_0\to N_o$ and $f_1:M_1\to N_1$. Also, note that $f_0\subseteq f_1$.
Suppose that for some $n\in\Bbb{N}$, we've already constructed $M_0\subseteq\ldots\subseteq M_{2n+1}$, $N_0\subseteq\ldots\subseteq N_{2n+1}$, and isomorphisms $f_i:M_i\to N_i$ for $0\le i\le2n+1$, such that $f_0\subseteq\ldots\subseteq f_{2n+1}$. We'll use these to construct $f_{2n+2}$ and $f_{2n+3}$ as follows:
First, let $a_{2n+2}$ be the earliest element of the $x_0,x_1,x_2,\ldots\,$ such that $a_{2n+2}$ is not an element of $M_{2n+1}$. Let $M_{2n+2}=M_{2n+1}\cup\{a_{2n+2}\}$. Next, let $b_{2n+2}$ be the earliest element of $y_0,y_1,y_2\ldots$ such that $f_{2n+1}\cup\{(a_{2n+2},b_{2n+2})\}$ is an isomorphism. Note: the fact that we can find $b_{2n+2}$ follows from the fact that $M$ and $N$ have infinitely many equivalence classes, all of which are infinite. Let $N_{2n+2}=N_{2n+1}\cup\{b_{2n+2}\}$, and let $f_{2n+2}=f_{2n+1}\cup\{(a_{2n+2},b_{2n+2})\}$.
Now let $b_{2n+3}$ be the earliest element of the $y_0,y_1,y_2,\ldots\,$ such that $b_{2n+3}$ is not an element of $N_{2n+2}$. Let $N_{2n+3}=N_{2n+2}\cup\{b_{2n+3}\}$. Next, let $a_{2n+3}$ be the earliest element of $x_0,x_1,x_2\ldots$ such that $f_{2n+2}\cup\{(a_{2n+3},b_{2n+3})\}$ is an isomorphism. Note: the fact that we can find $a_{2n+3}$ follows from the fact that $M$ and $N$ have infinitely many equivalence classes, all of which are infinite. Let $M_{2n+3}=M_{2n+2}\cup\{a_{2n+3}\}$, and let $f_{2n+3}=f_{2n+2}\cup\{(a_{2n+3},b_{2n+3})\}$.
Notice, that at odd stages, we're picking the first available element of $M$, and then picking an element of $N$ so that $f_{2k}$ is an isomorphism. At even stages, we're picking the first available element of $N$, and then picking an element of $M$ so that $f_{2k+1}$ is an isomorphism. This is how we know that $\underset{n\in\Bbb{N}}{\bigcup}M_i=M$ and $\underset{n\in\Bbb{N}}{\bigcup}N_i=N$. The fact that each $f_i:M_i\to N_i$ is an isomorphism and that $f_0\subseteq f_1\subseteq f_2\subseteq\ldots\,$ gives us that $\underset{n\in\Bbb{N}}{\bigcup}f_i:M\to N$ is an isomorphism.
Suppose $M$ and $N$ are two countable models with the properties (i) and (ii). (I will write countable instead of denumerable throughout this answer).
By (2), $M$ has infinitely many classes, and since $M$ is countable, it has countably infinitely many classes. So we can enumerate the classes $C_1, C_2, \dots$.
Similarly, $N$ has countably infinitely many classes, which we can enumerate $D_1, D_2, \dots$.
Each class $C_i$ in $M$ is infinite, and since $M$ is countable, it is countably infinite. So we can enumerate the elements of $C_i$ as $a^i_1, a^i_2,\dots$.
Similarly, we can enumerate the elements of each class $D_i$ as $b^i_1, b^i_2, \dots$.
Now let $f\colon M\to N$ be defined by $a^i_j\mapsto b^i_j$ for all $i,j\in \mathbb{N}$. I'll leave it to you to verify that this is an isomorphism $M\cong N$.