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

• May 16th 2009, 02:42 AM
armeros
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.

• May 16th 2009, 03:02 AM
Swlabr
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.
• May 16th 2009, 03:17 AM
armeros
Thanks, but could you give more formal proof?
• May 16th 2009, 03:32 AM
Plato
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.
• May 16th 2009, 07:50 AM
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.
• May 16th 2009, 08:25 AM
Swlabr
Quote:

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|$.)
• May 18th 2009, 03:27 AM
armeros
Thanks a lot.