1
$\begingroup$

Q. Let $X$ be a countable, infinite set. Prove that the set of all finite subsets of $X$ is countable.

So I say;

Let $X$ countable be given.

Let $F$ be the set of all finite subsets of $X$.

Let $F_i$ be the subsets of $X$ containing $i$ elements where $i$ a natural number.

Then $F$ is the union of all the $F_i$.

This union is countable as the natural numbers are countable.

A countable union of finite sets is countable, hence $F$ is countable.

(I have already proved a countable union of finite sets is countable in an earlier stage of the question, that is why I am stating this as fact)

Does this proof hold? I have seen a few other proofs that seem to be more complicated than mine and so I worry that I am missing something simple.

$\endgroup$
  • 2
    $\begingroup$ The countable union of countable sets is countable. You need this and to show that $F_i$ is countable (indeed, it is infinite) for each $i$. $\endgroup$ – Tom Oct 27 '14 at 12:01
  • $\begingroup$ This question has been bumped so that the answers can be reviewed. The question asked is "is my proof correct?" The correct answer is "no, the proof is not correct", because of the reason given in 5xum's answer: The set of subsets containing i elements is not necessarily finite. The answer of WierdFishes [sic] gives some helpful hints for solving the problem, but does not answer the question that was asked, which is "is this proof correct". $\endgroup$ – Eric Lippert Apr 8 at 23:28
  • $\begingroup$ There are many ways to show that the set of all finite subsets of (WOLOG) the naturals is countable: for example, map the empty set onto 1 and any set {1, 2, 4} say, onto the product of the 1st, 2nd and 4th prime. Every subset will map onto a unique integer, and that's good enough to know that they are countable. Or map it onto the rational number 0.1101, where the 1st, 2nd and 4th digits are set; now we have a map from subsets to unique rationals, which again is sufficient to show countability. But the question is not about clever solutions; it's about where the flaw in the proof is. $\endgroup$ – Eric Lippert Apr 8 at 23:35
1
$\begingroup$

You say that $F$ is countable because it is a countable union of finite sets, which is false. $F_1$ is not a finite set if $X$ is infinite, and neither is $F_i$ for any other $i$!

$\endgroup$
-1
$\begingroup$

There are numerous method for this kind of question.

This is a nice one. In my opinion at least.

The first step; Consider the empty set. We won't want to ruin our proof by considering everything except the empty set. This is easy, however, as if we can show all non-empty finite subsets are countable, we can show adding the empty set is.

Step 2; We consider $ n > 0$ t be fixed. Let X be a subset of the natural numbers (for the sake of simplicity) that is of size $n$ - that is, is of the form {$x_1 , x_2 , ... , x_{n-1} , x_n$}. Can you associate this to n-tuple of real numbers?

Hint; that is $(x_1 , x_2 , ... , x_{n-1} , x_n)$

Now, we have an injection of finite subsets of size $n$ to the set of n-tuples of natural numbers, i.e. $\mathbb{N}^n$.

Now, can you prove that the (countable) union of countable sets is countable? Hint; Arrange the naturals in some kind of grid, where every row is infinite and not equal to any rows above or below it.

Now, prove via induction that for a countable set $\mathbb{B}$ we also have $\mathbb{B}^k$ is countable for any natural number k. Hint; consider your notes of proving the rational numbers are countable.

Now, we finally see that there is an injection from the set of all finite subsets of the natural numbers to the set $U_{n \in \mathbb{N}} \mathbb{N}^n$.

Thus, the set of all subsets of $\mathbb{N}$ is countable (*).

(*) assuming the following; that any subset of a countable set is countable, and if there is an injection from an infinite subset to a countable set, that set must be countable - can you prove these and state at which points they should be used (try to explicitly construct a bijection)?

$\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.