2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bbw Nov 5 '18 at 4:05
  • $\begingroup$ 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? $\endgroup$ – bbw Nov 5 '18 at 4:10
  • $\begingroup$ 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\}\}$. $\endgroup$ – Alex Kruckman Nov 5 '18 at 4:10
  • $\begingroup$ (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$. $\endgroup$ – Alex Kruckman Nov 5 '18 at 4:12
  • $\begingroup$ 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$. $\endgroup$ – bbw Nov 5 '18 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.