1. ## Countability

Q- Prove that the collection of all finite subsets of N are countable

What I have so far:

Let $A_i$ be the set of all subsets of $\mathbb{N}$ consisting of $i$ elements, $A$ be the set of all finite subsets of $\mathbb{N}$. Then $A$ is a union of $A_i$....

Now I need to find a bijective function of this union to the real numbers? How should I proceed from where I am?

Thanks

2. Wait! You want to prove that A is countable so

you need a bijective function from $\mathbb{N}$ to A right?

3. Originally Posted by sfspitfire23
Q- Prove that the collection of all finite subsets of N are countable

What I have so far:

Let $A_i$ be the set of all subsets of $\mathbb{N}$ consisting of $i$ elements, $A$ be the set of all finite subsets of $\mathbb{N}$. Then $A$ is a union of $A_i$....

Now I need to find a bijective function of this union to the real numbers? How should I proceed from where I am?

Thanks
Lemma: $\mathbb{N}^m$ is countable for all $m\in\mathbb{N}$

Proof: Let $\tau:\mathbb{N}\mapsto\mathbb{N}^m$ be given by $n\mapsto(n\underbrace{1,\cdots,1}_{m-1\text{ times}})$. This is clearly an injection.

Now, let $\eta:\mathbb{N}^m\mapsto\mathbb{N}$ be given by $(n_1,\cdots,n_m)\mapsto p_1^{n_1}\cdots p_m^{n_m}$ where $p_k$ is the $k$th prime. It is clear that this is an injection since the representation of a number by a prime decomposition is unique (fundamental theorem of arithmetic)

So, the conclusion follows by virtue of the Schroder-Bernstein theorem. $\blacksquare$

Now, let $A_m$ be set of all finite subsets of $\mathbb{N}$ with cardinality $m$. Define $\gamma:A_m\mapsto\mathbb{N}_m$ by $\{n_1,\cdots,n_m\}\mapsto (n_1,\cdots,n_m)$ where $n_1\leqslant\cdots\leqslant n_m$ (this is possible because of finiteness). This is clearly an injection, for to suppose that $(n_1,\cdots,n_m)=(n'_1,\cdots,n'_m)$ would mean that $n_1=n'_1,\cdots,n_m=n'_m$ and so $\{n_1,\cdots,n_m\}=\{n'_1,\cdots,n'_m\}$. It follows that each $A_m$ is countable.

And then since $A=\bigcup_{j=1}^{\infty}A_j$ it follows that $A$ is the countable union of countable sets, and thus countable.

4. Originally Posted by sfspitfire23
Prove that the collection of all finite subsets of N are countable.
Here are my suggestions. Lets agree that $\mathbb{N} = \mathbb{Z}^ +$
Let $\mathbb{P}=\left\{ {p_1 ,p_2 ,p_3 , \cdots } \right\}$ be a listing of the primes. Let $\mathbb{A} = \left\{ {X \subseteq \mathbb{N}:\left| X \right| < \infty } \right\}$, the finite subsets.
If $X\in \mathbb{A}$ define a mapping $\Theta :\mathbb{A} \mapsto \mathbb{N}$ as $\Theta (X) = \prod\limits_{k \in X} {p_k }$.
Show that $\Theta$ is an injection.

5. Drexel, I assume that instead of $\eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\eta:\mathbb{N}^m\mapsto\mathbb{N}$? I think that is the only way the Bernstein-Schroeder theorem works?

6. .

7. Originally Posted by sfspitfire23
Drexel, I assume that instead of $\eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\eta:\mathbb{N}^m\mapsto\mathbb{N}$? I think that is the only way the Bernstein-Schroeder theorem works?
yes..typo.

8. Originally Posted by sfspitfire23
Drexel, I assume that instead of $\eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\eta:\mathbb{N}^m\mapsto\mathbb{N}$? I think that is the only way the Bernstein-Schroeder theorem works?
Obviously. In retrospect, here is a better way to do this problem.

Let $\mathbb{N}^m$ be as normal and define on it the relation $\left(n_1,\cdots,n_m\right)\overset{\pi_m}{\sim}\l eft(n'_1,\cdots,n'_m\right)\Leftrightarrow \{n_1,\cdots,n_m\}=\{n'_1,\cdots,n'_m\}$ which (as can be readily proved) is an equivalence relation, and thus forms a partition $\pi_m$ of $\mathbb{N}^m$. Define $\alpha:\pi_m\mapsto\mathbb{N}^m$ by $\left[(n_1,\cdots,n_m)\right]\mapsto(n_1,\cdots,n_m)$ (make the proper addendum so that mapping is well-defined). Clearly this is an injection. Now, form a mapping $\gamma:A_m\mapsto\pi_m$ by $\{n_1,\cdots,n_m\}\mapsto\left[(n_1,\cdots,n_m)\right]$. This is readily verified to be a bijection. It follows that $\alpha\gamma:A_m\mapsto\mathbb{N}^m$ is an injection and so $A_m$ is countable by the lemma. And since $A=\bigcup_{j=1}^{\infty}A_j$ and the countable union of countable sets is countable it follows that $A$ is countable.

9. thanks a lot!