2
$\begingroup$

Let $B := \{ (x_n) \mid x_n \in \{0, 1\}, n \in \mathbb N \}$ then prove that $|B| = 2^{\aleph_0}$.

I know that the given set $B$ is uncountable. This can be deduced by proving that any countable subset of sequences of $B$ will be a proper subset. $B$ being countable would then give a contradiction.

To explicitly find out the cardinality of $B$, however, is what the problem demands. Will it be correct to say that since there are exactly $2$ choices ($0$ or $1$) for each term of any infinite binary sequence, whose cardinality is ${\aleph_0}$, so, the cardinality of $B$ is $2^{\aleph_0}$?

$\endgroup$
  • 6
    $\begingroup$ This is correct because almost by definition the symbol $2^{|X|}$ denotes the cardinality of the set of functions from $X$ to $\{0,1\}$. $\endgroup$ – Michal Adamaszek May 26 '18 at 10:25
  • $\begingroup$ I was going to say that a roundabout way to show this would be to make a bijection from B to the half open interval of reals from 0 to 1, and then make a bijection from that to the reals, and then show that the cardinality of the reals is $2^{\aleph_0}$. But that proof requires that you already know precisely what you're trying to prove, so that doesn't work! $\endgroup$ – Eric Lippert May 26 '18 at 17:45
7
$\begingroup$

A binary sequence $(x_n)$ is just a function $x: \mathbb{N} \to \{0,1\}$. The $x_n$ is an alternative notation for $x(n)$.

In cardinal arithmetic $\kappa^\lambda$, for two cardinals $\kappa,\lambda$, is defined as the cardinal number of the set of all functions from a set of size $\lambda$ to a set of size $\kappa$.

So the size of your $B$ (all binary sequences) is, by this definition, $|\{0,1\}|^{|\mathbb{N}|} = 2^{\aleph_0}$

$\endgroup$
2
$\begingroup$

You're correct, but an even easier way to see so is that for each such binary sequence, one can construct a unique subset $S$ of $\mathbb{N}$ by including the number $n$ in $S$ iff the $n$th term of the sequence is 1. Then, the set of binary sequences is in bijection with the set of subsets of $\mathbb{N}$, which is the definition of $2^{\aleph_0}$.

$\endgroup$
  • 4
    $\begingroup$ That is a bit of a roundabout way of doing the argument. The direct, plain meaning of the notation $2^{\aleph_0}$ is the cardinality of the set of maps from a countably infinite set to $\{0,1\}$. It is true that this also happens to be the cardinality of the power set of $\mathbb N$, but if you want to use that fact in an argument at the level of detail we're working at here, you need to prove it first. $\endgroup$ – Henning Makholm May 26 '18 at 10:37
  • 1
    $\begingroup$ Agreed. Point taken. $\endgroup$ – Isky Mathews May 26 '18 at 10:38

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.