# Formally prove some results for countable and uncountable sets

Prove that:

$a)$ the set of all rational numbers is countable;

$b)$ the set of all real numbers is uncountable;

$c)$ any subset of a countable set is countable;

$d)$ the union of countably many countable sets is countable.

I have no idea how to formally prove this.

For $a)$, I think, the idea would be to notice that any rational number can be expressed like fraction. Taking the number of the denominator $n$ for establishing a relation to set of integers there would be $n-1$ numbers for each integer. So it would be a union of countably many countable sets. But then I would need to prove $d)$ first.

Could anyone show me an example of this type of proofs or give any advice.

• Depends how formal. Here is an argument with a subtle gap. List the sets as an infinite matrix, first row is first set, second row is second set, and so on. Now start at Northwest corner, go South 1, go Northeast, then go East $1$, go Southwest, go South $1$, go Northeast until hit the top, then East $1$, and so on. – André Nicolas Oct 3 '12 at 17:46

## 1 Answer

Hints:

For (d) you need (a fragment of) the axiom of choice to choose for each of the countable sets a function witnessing its countability. Then use the fact that $\mathbb{N} \times \mathbb{N}$ is countable.

For (a) you don't need the full strength of (d). Just write the rational numbers out in a two-dimensional array and find a linear path that covers them all. Then work out an equation that describes the path.

For (b), for any set $X$ there is no surjection from $X$ onto the power set of $X$. (If $f$ were such a surjection, considering $\{x \in X : x \notin f(x)\}$ leads to a contradiction.) Then let $X = \mathbb{N}$ and consider binary expansions of real numbers.

For (c), if there is a surjection from $X$ to $Y$ and $Y'$ is a nonempty subset of $Y$ then there is a surjection from $X$ to $Y'$. (You can modify the given surjection somehow using the fact that $Y'$ is nonempty.)

• For (c) I am assuming that countability is defined in terms of surjections from $\mathbb{N}$. If it is defined in terms of injections into $\mathbb{N}$ or bijections with subsets of $\mathbb{N}$ you will have to do something slightly different. – Trevor Wilson Oct 3 '12 at 20:20
• Thankyou @Trevor Wilson. So for c) you mean X is N, right? – Mykolas Oct 4 '12 at 6:44
• @Mykolas Yes (although it occurred to me after I wrote the answer that I was assuming a definition of "countable" that might not be the most common one.) – Trevor Wilson Oct 4 '12 at 20:20