The problem I wanted to answer is
Determine whether or not the set of irrationals, $\mathbb R \backslash \mathbb Q$, is countable.
My attempt. For nicer notation, let $\mathcal I := \mathbb R \backslash \mathbb Q$.
Definition. An irrational number is a real number that can be expressed as an infinite simple continued fraction.
An infinite simple continued fraction is an expression of the form
$$b_0+\frac{1}{b_1+\frac{1}{b_2+\frac{1}{b_3+\frac{1}{…}}}}$$ Hence a positive irrational number $\beta$ is uniquely determined by the $b_0, b_1, b_2, \ldots$. For each of these unique determinations of irrational numbers, we will construct a sequence $$s=[b_0, b_1, b_2, \ldots]$$
But a sequence is just a subset of $\mathbb{N} \times \mathbb Z$; for each $n \in \mathbb N$, take the point $(n,b_n)$ as the $n$th element of the sequence. And $\mathbb{N} \times \mathbb Z$ is countable, so the set of all such sequences is countable, so the set of all simple infinite fractions is countable, so the set of all irrationals is countable.
But since $\mathbb Q$ is countable as well, doesn't that mean that the union of $\mathbb R \backslash \mathbb Q$ and $\mathbb Q$, i.e. $\mathbb R$ is countable?
Best Answer
By analogy, the power set of $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$ is all the subsets of $\mathbb{N}$. $\mathbb{N}$ is countable. Nevertheless, $\mathcal{P}(\mathbb{N})$ has strictly greater cardinality than $\mathbb{N}$ as the power set of any set is strictly greater than the cardinality of the original set.