# proving a set is countable

• November 5th 2013, 06:22 AM
Tweety
proving a set is countable
Hello,

Can anyone please help me with this question, I am finding it very hard. I am not sure where to begin
• November 5th 2013, 06:52 AM
SlipEternal
Re: proving a set is countable
Let's write $S(E)$ a slightly different way:

$S(E) = \left\{A \subseteq E \mid \text{card}(A) = n, n\in \mathbb{N}\right\}$

Note that this is similar to the power set, but the power set includes subsets with infinite cardinality and the empty set.

Let $P$ be the set of primes (as suggested in the hint). Define $f:E \to P$ to be any injection. Such an injection exists since both $E$ and $P$ are countable. Then, define $g:S(E) \to \mathbb{N}$ by $g(A) = \prod_{e \in A}f(e)$. Prove that $g$ is an injection.

Another proof of this: If $E$ is finite, then $S(E) = \mathcal{P}(E) \setminus \{\emptyset\}$. Hence, $\text{card}(S(E)) = 2^{\text{card}(E)}-1$ where $\mathcal{P}(E)$ is the power set of $E$, so $S(E)$ is finite and therefore countable. Suppose $E$ is infinite and let $E = \{e_0,e_1,\ldots\}$ be an enumeration of the elements of $E$. Then, define $h: S(E) \to \mathbb{N}$ by $h(A) = \sum_{e_k \in A}2^k$. Show that $h$ is a bijection.