Let's write a slightly different way:

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

Let be the set of primes (as suggested in the hint). Define to be any injection. Such an injection exists since both and are countable. Then, define by . Prove that is an injection.

Another proof of this: If is finite, then . Hence, where is the power set of , so is finite and therefore countable. Suppose is infinite and let be an enumeration of the elements of . Then, define by . Show that is a bijection.