Show that there are exactly $\aleph_0$-many countable $L$-structure if $L$ consists of one unary relation symbol.

Question

$\textbf{First question:}$ Let $L=\{R\}$ be a language consisting of one unary relation symbol. Show that there are exactly $\aleph_0$-many countable $L$-structures up to isomorphism.

My (attempted) solution is as follows: Let $\mathcal{M}=(M,R^{\mathcal{M}})$ be an $L$-structure. Since $R$ is a unary relation symbol, the basic relation $R^{\mathcal{M}}$ is also unary. But a unary relation is just a subset of $M$. Any countable $L$-structure is isomorphic to $\omega$ or some $n \in \omega$. So the set of all countable $L$-structures up to isomorphism is $$\{(n,E):n \in \omega,E \subseteq n\} \cup \{(\omega,F):F \subseteq \omega\}$$

We first look at the set one the left hand side. It is of cardinality $\aleph_0$. If I can show the set on the right hand side is also of cardinality $\aleph_0$ then we are done. But how?

$|\mathcal{P}(\omega)|=\aleph_1$ hence the cardinality of the set on the right is $\aleph_1$. $\textbf{What did I do wrong?}$

$\textbf{Second question:}$ Let $L=\{R\}$ be a language consisting of one unary relation symbol. How many $L$-structure of size $\aleph_1$ are there?

I was trying to use the similar argument as in my first question, but in the first question, we consider countable structures and we know every countable set is isomorphic to $\omega$ or some $n \in \omega$. But if we consider structures of cardinality $\aleph_1$, I don't know the particular set they are isomorphic to, so I can't use the argument as before. What should I do?

Answer 1

To start, $|\mathcal{P}(\omega)| = \aleph_1$ is the statement of the continuum hypothesis, which is not provable in ZFC. The correct statement is $|\mathcal{P}(\omega)| = 2^{\aleph_0}$.

As to what you're doing wrong, note that if $E$ is the set of even numbers, and $O$ is the set of odd numbers, then $(\omega,E)\cong (\omega,O)$, even though these structures are not equal. So when you look at $\{(\omega,F)\mid F\subseteq \omega\}$, you're vastly overcounting.

Instead, prove that up to isomorphism, a countable structure in the language with a single unary relation symbol $R$ is totally determined by the cardinality of the set of elements $R$ and the cardinality of the set of elements not in $R$. These two cardinalities can be $0$, $1$, $2$,$\dots$ or $\aleph_0$.

The same sort of reasoning works for structures of size $\aleph_1$.

Aside: For structures of size $\aleph_1$, you write "I don't know the particular set they are isomorphic to..." Any set of size $\aleph_1$ is isomorphic to the set $\aleph_1$, namely the first uncountable ordinal.