# Thread: proving a set is countable

1. ## 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

2. ## Re: proving a set is countable

Let's write $\displaystyle S(E)$ a slightly different way:

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

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