4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Concatenate every infinite subset into a numerical string and attach a decimal to the front. It looks like it might be the interval $[0,1]$ or something close to it. $\endgroup$ – jdods May 8 '16 at 21:55
  • $\begingroup$ Perhaps there is a nice, quick diagonal argument to be made, getting a contradiction if the infinite subsets of $\mathbb{N}$ are countable. $\endgroup$ – hardmath May 8 '16 at 21:57
  • $\begingroup$ a standard old-fashioned mapping goes via continued fractions $\endgroup$ – Mirko May 8 '16 at 22:04
  • $\begingroup$ Um, how would proving that the set of all finite sets being countable help you conclude the that the set of infinite subsets is uncountable? $\endgroup$ – fleablood May 8 '16 at 22:06
  • 1
    $\begingroup$ Why is the title "prove the set of infinite subsets is uncountable" when your post is trying to prove the set of finite subsets is countable. Those are completely different statements? $\endgroup$ – fleablood May 8 '16 at 22:12
4
$\begingroup$

Hint: Show that the set of finite subsets is countable, to see this, consider $S(n)$ the set of subsets of length $n$, it is countable, thus $\cup_{n\in N}S(n)$ is countable. this implies its complementary as the same cardinality than $P(N)$ the set of subsets of $N$ which is uncountable.

$\endgroup$
2
$\begingroup$

Let $F:=\{ A\subseteq \mathbb{N} : \vert A \vert < \infty \}$. For $a\in \mathbb{N}$ denote by $\pi(a)$ the nth prime number. Then consider the following map

$$ \phi: F \rightarrow \mathbb{N}, \ \phi(A):= \prod_{a\in A} \pi(a).$$

One easily checks that $\phi$ is injective and hence $F$ is countable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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