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