I am trying to prove the following
Prove that the set of all finite subsets of $\omega$ is denumerable
where $\omega$ is the set of natural numbers.
How would I approach this proof? I need some help to get started. Would it suffice to show that the set of all finite subsets of $\omega$, if we call is $S$, that $S$ be countable? since if $S$ is countable and infinite, it means that it is denumerable.
Yes, you indeed have to show that $S$ is infinite and countable.
Infinite is obvious. For example, take all singletons $\{ n \}$, for $n \in \mathbb{N}$. These are all in $S$, and there are infinitely many of them.
Countable is more tricky. There are several methods, but one method is to first list all subsets whose elements add up to 0, then do all the ones that add up to 1, etc. So you get:
$\emptyset , \{ 0 \}, \{ 1 \}, \{ 0,1 \}, \{ 2 \} , \{0,2 \}, \{3\}, \{0,3\}, \{1,2\}, \{0,1,2\}, ...$
Since for any $n$ there are only finitely many subsets whose elements add up to $n$, you will only add finitely many entries at each step, meaning that for any $n$, you will get to listing all subsets with sum $n$, and since each finite subset has a finite sum, you will eventually hit all finite subsets using this list, meaning that the set of all finite subsets is countable.
List the subsets of (for example) $\{0,1,2,3,4,5,6,7,8,9\}.$ You have only finitesly many. Then make a second copy of that list and for each set $S$ in the list add $S\cup\{10\}$. That's another finitely many that you can append to the list you already had. Then make a second copy of this new longer finite list and for each set $S$ in that list, add the set $S\cup\{11\}.$ That's another finitely many that you can append to the list you already had. And so on. You get a list of all finite subsets of $\omega$, and each member of your list has only finitely many others before it.
Let's try this starting with the empty set $\varnothing$ rather than with $\{0,1,2,3,4,5,6,7,8,9\}:$
$$ \begin{array}{lrl} & 1 & \varnothing \\ \hline \text{Copy the list above and add the next member:} & 2 & \{0\} \\ \hline \text{Copy the list of 2 sets above and add the next member:} & 3 & \{1\} \\ & 4 & \{0,1\} \\ \hline \text{Copy the list of 4 sets above and add the next member:} & 5 & \{2\} \\ & 6 & \{0,2\} \\ & 7 & \{1,2\} \\ & 8 & \{0,1,2\} \\ \hline \text{Copy the list of 8 sets above and add the next member:} & 9 & \{3\} \\ & 10 & \{0,3\} \\ & 11 & \{1,3\} \\ & 12 & \{0,1,3\} \\ & 13 & \{2,3\} \\ & 14 & \{0,2,3\} \\ & 15 & \{1,2,3\} \\ & 16 & \{0,1,2,3\} \\ \hline \text{Copy the list of 16 sets above and add the next member:} & & \cdots \cdots \cdots \end{array} $$
One way is use the numbers in any such finite subset to generate a unique positive integer in the manner illustrated by the following example. Let $\{5, 12, 8, 4\}$ be the finite set of natural numbers. The associated positive integer will be $(p_{5})^{5}\cdot (p_{12})^{12} \cdot (p_{8})^{8} \cdot (p_{4})^{4},$ where $p_1, \, p_2, \, p_3,\, \ldots $ is the sequence of primes in numerical order. After defining what happens in general a little more explicitly, show that this defines an injection (i.e. a one-to-one) function from the set of finite subsets of the natural numbers into the positive integers. Then explain why this implies the result you want.
