1. ## Countability

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

What I have so far:

Let $\displaystyle A_i$ be the set of all subsets of $\displaystyle \mathbb{N}$ consisting of $\displaystyle i$ elements, $\displaystyle A$ be the set of all finite subsets of $\displaystyle \mathbb{N}$. Then $\displaystyle A$ is a union of $\displaystyle 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 $\displaystyle \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 $\displaystyle A_i$ be the set of all subsets of $\displaystyle \mathbb{N}$ consisting of $\displaystyle i$ elements, $\displaystyle A$ be the set of all finite subsets of $\displaystyle \mathbb{N}$. Then $\displaystyle A$ is a union of $\displaystyle 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: $\displaystyle \mathbb{N}^m$ is countable for all $\displaystyle m\in\mathbb{N}$

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

Now, let $\displaystyle \eta:\mathbb{N}^m\mapsto\mathbb{N}$ be given by $\displaystyle (n_1,\cdots,n_m)\mapsto p_1^{n_1}\cdots p_m^{n_m}$ where $\displaystyle p_k$ is the $\displaystyle 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. $\displaystyle \blacksquare$

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

And then since $\displaystyle A=\bigcup_{j=1}^{\infty}A_j$ it follows that $\displaystyle 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 $\displaystyle \mathbb{N} = \mathbb{Z}^ +$
Let $\displaystyle \mathbb{P}=\left\{ {p_1 ,p_2 ,p_3 , \cdots } \right\}$ be a listing of the primes. Let $\displaystyle \mathbb{A} = \left\{ {X \subseteq \mathbb{N}:\left| X \right| < \infty } \right\}$, the finite subsets.
If $\displaystyle X\in \mathbb{A}$ define a mapping $\displaystyle \Theta :\mathbb{A} \mapsto \mathbb{N}$ as $\displaystyle \Theta (X) = \prod\limits_{k \in X} {p_k }$.
Show that $\displaystyle \Theta$ is an injection.

5. Drexel, I assume that instead of $\displaystyle \eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\displaystyle \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 $\displaystyle \eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\displaystyle \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 $\displaystyle \eta:\mathbb{N}\mapsto\mathbb{N}$ you meant $\displaystyle \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 $\displaystyle \mathbb{N}^m$ be as normal and define on it the relation $\displaystyle \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 $\displaystyle \pi_m$ of $\displaystyle \mathbb{N}^m$. Define $\displaystyle \alpha:\pi_m\mapsto\mathbb{N}^m$ by $\displaystyle \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 $\displaystyle \gamma:A_m\mapsto\pi_m$ by $\displaystyle \{n_1,\cdots,n_m\}\mapsto\left[(n_1,\cdots,n_m)\right]$. This is readily verified to be a bijection. It follows that $\displaystyle \alpha\gamma:A_m\mapsto\mathbb{N}^m$ is an injection and so $\displaystyle A_m$ is countable by the lemma. And since $\displaystyle A=\bigcup_{j=1}^{\infty}A_j$ and the countable union of countable sets is countable it follows that $\displaystyle A$ is countable.

9. thanks a lot!