# Thread: Show that P={X \in P(Z+)|X finite} is countably infinite.

1. ## Show that P={X \in P(Z+)|X finite} is countably infinite.

I have no idea where to start.

Let $\displaystyle P= \{X \in \wp(Z^+)|X finite \}$. Prove that $\displaystyle P$ is denumerable (countably infinite), where $\displaystyle \wp(Z^+)$ is the power set of $\displaystyle Z^+$

I tried to find $\displaystyle f:Z^+ \longrightarrow P$ that is one-to-one and onto. But that attemt was failed. I also tried to find something that might be equivalent to $\displaystyle Z^+$ and $\displaystyle P$ and show that they are equivalent, but failed as well.

2. There are countably infinite sets with cardinality i for i a natural number (as is aleph null times i). There are countably infinite choices for i. So, the set has cardinality equal to countably infinite times countably infinite, which is countably infinite. Basically.

The same logic gives us that every finitely generated group is countably infinite.

3. Thanks, but could you give more formal proof?

4. We know that there is an injection $\displaystyle \Phi :\mathbb{Z}^ + \mapsto \{ 2,3,5, \cdots \}$ to the set of prime numbers.
Define a function $\displaystyle f:P \mapsto \mathbb{Z}^ + ,\,f\left( X \right) = \prod\limits_{y \in X} {\Phi (y)}$.
Noting that each $\displaystyle X \in P$ is finite, prove that $\displaystyle f$ is an injection.
That means that $\displaystyle P$ is countable.

5. The question asked show that P is countably infinite, not just countable. I wonder if showing injection is enough. Shouldn't it be to show that there is a bijection?

Thanks a lot.

6. Originally Posted by armeros
The question asked show that P is countably infinite, not just countable. I wonder if showing injection is enough. Shouldn't it be to show that there is a bijection?

Thanks a lot.

If you show there is a injection both ways then that is sufficient. For the injection $\displaystyle \phi: \mathbb{N} \rightarrow S$ meerly take $\displaystyle i \mapsto \{i\}$. Simples!

(If there exists an injection from $\displaystyle A$ to $\displaystyle B$ then $\displaystyle |A| \leq |B|$.)

7. Thanks a lot.