Tuesday, 4 August 2015

elementary set theory - Prove that the set of all infinite subsets of $mathbb{N}$ is uncountable.

For this problem, my proof was:
If we want to express out the set of all the finite subsets, $F$.

$F = \{\{n_{1}\},\{n_{1},n_{2}\},\{n_{1},n_{2},n_{3}\},\cdots\}$ with $n_{1} \in \mathbb{N}$, $n_{2} \in \mathbb{N} - \{n_{1}\}$, $n_{3} \in \mathbb{N} - \{n_{1},n_{2}\}$.
Notice that the first element of the $F$ above comes with the only one element $\in \mathbb{N}$, the second element of $F$ comes with only two elements $\in \mathbb{N} \cdots$.
There are countably infinite number of the first element of $F$, and countably infinite number of the second element of $F$(since countably infinite $\times$ countably infinite gives countably infinite). Then the cardinality of $F$ is the sum of finite number of countably infinite, which is countably infinite.
Therefore, we can conclude that set of all finite subsets of $\mathbb{N}$ is a countably finite set.



However, I realized that the proof above although got the rough idea but is very informal and actually made use of P&C.
Now I think it is possible to do a proof with mapping: For example:
$\{n_{1},n_{2}\} \hookrightarrow (n_{1},n_{2}) \in \mathbb{N} \times \mathbb{N}$.
However, I found it difficult to phrase it in this approach.
Hope some one can help me to improve my proof. Thank you!

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...