3
$\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$
2
  • 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$ May 26, 2018 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$ May 26, 2018 at 17:45

2 Answers 2

8
$\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$
2
  • 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$ May 26, 2018 at 10:37
  • 1
    $\begingroup$ Agreed. Point taken. $\endgroup$ May 26, 2018 at 10:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .