# How many finite rational subset are there?

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?

-
Try writing $\bf F$ as a countable union of countable sets. –  David Mitra May 29 '12 at 19:41
Remember that $\mathbb{Q}$ is countable, so in this problem you can replace $\mathbb{Q}$ with $\mathbb{N}$. It gets a little easier that way. –  Qiaochu Yuan May 29 '12 at 19:42
We know that $\mathbb{Q}$ is countable. Let $\mathbb{Q} = \{ r_1, r_2, r_3, \cdots \}$ be an enumeration of $\mathbb{Q}$. Then $F \in \mathbf{F}$ implies that $F \subset \{ r_1, \cdots, r_n \} =: A_n$ for some $n$, since every element of $F$ is one of $r_k$ for some $k$ and $F$ is finite. Of course, every subset of $A_n$ is in $F$. Therefore $$\mathbf{F} = \bigcup_{n=1}^{\infty} \mathcal{P}(A_n),$$ which proves that $\mathbb{F}$ is countable. –  Sangchul Lee May 29 '12 at 19:44
This is enormously nitpicky, but it might be interesting to someone else reading this question. The statement that a countable union of countable sets is countable actually requires a use of the axiom of countable choice, since one needs to choose a counting of each of the sets for the standard proof to go through. Of course, in practice one can write down all of the countings one needs explicitly. This shows that if we're being really careful we should distinguish between countable sets and counted sets (namely, sets equipped with a bijection to $\mathbb{N}$). Showing that a countable union –  Qiaochu Yuan May 29 '12 at 20:03
...of counted sets is countable requires no appeal to any form of choice, so it can be done in ZF. –  Qiaochu Yuan May 29 '12 at 20:04

## 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.

-