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

$$\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?

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.

• Now I see. So the set on the right hand side should actually be $\{(\omega,F):F=\omega \vee F=n\}$ which has cardinality $\aleph_0$, right? – bbw Nov 5 '18 at 4:05
• And according to this reasoning, for the second question, the set of all uncountable $L$-structure is $\{(\aleph_1,F): |F|=\aleph_1,\aleph_0,n\}$ which is again countable? – bbw Nov 5 '18 at 4:10
• I guess you're trying to write down an explicit set of representatives for the countably infinite structures up to isomorphism? One such set is $\{(\omega,F)\mid F = n,n\in \omega\}\cup \{(\omega,F)\mid F = \omega\setminus n,n\in \omega\} \cup \{(\omega,F)\mid F = \{2n\mid n\in \omega\}\}$. – Alex Kruckman Nov 5 '18 at 4:10
• (That is, the set you wrote down is missing the cases when $F$ is infinite but not all of $\omega$). The set of structures of size $\aleph_1$ (this is not the same as the set of all uncountable structures!) is indeed countable. But again, you need to account not just for the size of $F$, but also for the size of $\aleph_1\setminus F$ when $|F| = \aleph_1$. – Alex Kruckman Nov 5 '18 at 4:12
• Yes. As you have pointed out, two countably infinite subsets of $\omega$ are isomorphic to each other. So to count the set $\{(\omega,F)\}$ we are actually counting the number of finite subsets of $\omega$ (which is $\aleph_0$) plus the number of countably infinite subset of $\omega$ up to isomorphism (which is one). So the set $\{(\omega,F)\}$ has cardinality $\aleph_0$. – bbw Nov 5 '18 at 4:15