Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

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?

share|improve this question
4  
Try writing $\bf F$ as a countable union of countable sets. – David Mitra May 29 '12 at 19:41
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. – Qiaochu Yuan May 29 '12 at 19:42
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. – sos440 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

up vote 3 down vote

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.

share|improve this answer
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.