Countability

**sfspitfire23** · February 12th 2010, 12:07 PM

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

**mabruka** · February 12th 2010, 12:14 PM

Wait! You want to prove that A is countable so

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

**Drexel28** · February 12th 2010, 12:22 PM

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.

**Plato** · February 12th 2010, 12:33 PM

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.

**sfspitfire23** · February 13th 2010, 11:18 AM

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?

**sfspitfire23** · February 13th 2010, 11:43 AM

.

**Sampras** · February 15th 2010, 06:20 PM

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.

**Drexel28** · February 15th 2010, 06:25 PM

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.

**sfspitfire23** · February 15th 2010, 08:36 PM

thanks a lot!

Thread: Countability

LinkBack

Thread Tools

Display

Countability

Similar Math Help Forum Discussions

countability of a set

Countability

Bijection - Countability

Countability

Countability

Search Tags