Consider$\mathbf F=\{F\subset \mathbb Q\colon F\text{ is finite}\}\quad\text{and}\quad\mathbf I=\{I\subset\mathbb Q\colon I\text{ is infinite}\}.$ How can I prove that $\mathbf F$ is countable and $\mathbf I$ is uncountable?
How many finite rational subset are there?
-
0...of counted sets is countable requires no appeal to any form of choice, so it can be done in ZF. – 2012-05-29
2 Answers
I'll use $\mathbb{N}$ instead of $\mathbb{Q}$, which doesn't matter since $\mathbb{Q}$ is countable. An enumeration of $\mathbf{F}$ is obtained by writing the numbers $0, 1, 2, \dotsc$ in binary and then interpret the digits as an indicator function. For example, $9 = 2^3 + 2^0$ represents $\{0, 3\}$.
Now $\mathbf{F} \cup \mathbf{I} = \wp(\mathbb{N})$, the set of all subsets, which is not countable (see below). Since $\mathbf{F}$ is countable it follows that $\mathbf{I}$ is not countable.
For $\wp(\mathbb{N})$ you can use a diagonal argument: if $S_k$ is a sequence of subsets of $\mathbb{N}$ then $S \subseteq \mathbb{N}$ defined by $S = \{k \in \mathbb{N} \mid k \not \in S_k\}$ does not occur in this sequence. Therefore $\wp(\mathbb{N})$ is not countable.
Following the same idea by sos440, but without enumerating the rationals. Define $F_n:=\{F\in \textbf{F}\,\,/\,\,|F|=n\}\Longrightarrow \textbf{F}=\bigcup_{n\in\mathbb{N}}F_n$ and this last is a countable union of countable sets...
For the other set just take into account that there are $\,\,2^{\aleph_0}\,\,$ subsets of rational numbers.