Show this set of axioms is $\aleph_0$-categorical.

Question

Let $\mathcal{L}=\{\sim\}$ be a FOL and $\Sigma$ the set formed by the following axioms:

• $\left(Ref\right) \;\; \forall x_1 \;\; x_1 \backsim x_1$
• $\left(Sym\right) \;\; \forall x_1 \forall x_2\;\; \left(x_1\backsim x_2\right) \rightarrow \left(x_2\backsim x_1\right)$
• $\left(Trans\right) \;\; \forall x_1\forall x_2\forall x_3 \;\; \left( x_1\backsim x_2 \wedge x_2\backsim x_3 \right) \rightarrow \left( x_1\backsim x_3\right) $
• $\left(EC_n\right)\;\; \exists x_1 \; ... \;\exists x_n \;\; \bigwedge_{1\leq i<j\leq n} \neg \left(x_i \backsim x_j \right)$ for $n=1,2,...$
• $\left(IE_n\right)\;\; \forall x_1\exists x_2 \; ... \;\exists x_{n} \;\; \bigwedge_{1\leq i<j\leq n} x_i \neq x_j \wedge \bigwedge_{i=2}^{n} \left(x_1 \backsim x_i \right)$ para $n=1,2,...$

These axioms are for the sets with an equivalence relation, infinite equivalence classes, each one with infinite elements.

I want to show $\Sigma$ is complete. I already showed it has quantifier elimination and now I want to use Vaught's test for completeness. It is obvious that $\Sigma$ has no finite models and that it does indeed have a model, but I still have to show $\kappa$-categoricity.

I'm kind of wrapped up in this part. I know what I need to prove any two models of cardinal $\aleph_0$ are isomorphic but I'm having trouble defining what that isomorphism should be. I've tried to use representatives of equivalence classes to define it but then I can't prove it is well defined. Any help with that would be appreciated.

Answer 1

Consider two countable models $M, N$. Then both $M / \sim_M$ and $N / \sim_N$ are countably infinite, so we have a bijection $f : M / \sim_M \to N / \sim_N$.

Now for each equivalence class $c \in M / \sim_M$, we know that both $c$ and $f(c)$ are countably infinite equivalence classes. So we may pick a bijection $g_c : c \to f(c)$.

Combining all these data, we have a bijection $h : M \to N$ given by $h(x) = g_{[x]}(x)$. In fact, $h$ is an isomorphism.

Answer 2

I recommend stepping back a bit and thinking about classifying all models of the theory in question. The key result is the following (the notation I'm using is nonstandard):

Given a model $M$ of your theory, let $\mathsf{Spec}_M$ be the function sending an infinite cardinal $\kappa$ to the number of classes in $M$ of size $\kappa$. For example, if $M$ consists of countably many equivalence classes each of which has cardinality $\aleph_{17}$, then $$\mathsf{Spec}_M(\kappa)=\begin{cases} 0 & \mbox{ if } \kappa\not=\aleph_{17},\\ \aleph_0 & \mbox{ if }\kappa=\aleph_{17}. \end{cases}$$ Show that if $\mathsf{Spec}_M=\mathsf{Spec}_N$ as functions then $M\cong N$.

HINT: first whip up a bijection between the classes of $M$ and the classes of $N$ which preserves cardinality, then turn that bijection into an isomorphism. Admittedly this is going to involve a lot of arbitrary choices, so "show that there exists" might be more intuitive than "whip up."

Once you have this result, you'll be done immediately: if $A$ is a countable model of your theory, then each of its classes must have cardinality exactly $\aleph_0$ and there must be exactly $\aleph_0$-many such classes, so we get $$\mathsf{Spec}_A(\kappa)=\begin{cases} 0 & \mbox{ if } \kappa\not=\aleph_{0},\\ \aleph_0 & \mbox{ if }\kappa=\aleph_{0}. \end{cases}$$