3
$\begingroup$

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?

  • 4
    Try writing $\bf F$ as a countable union of countable sets.2012-05-29
  • 3
    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.2012-05-29
  • 2
    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.2012-05-29
  • 0
    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 union2012-05-29
  • 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 2

3

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.

1

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.