is the set of integers as big as P(prime numbers)? I have a function $f:\mathbb{N}\to P(\mathbb{P})$ where $f(x) = \{prime\ factors\ of\ x\}$
$f$ is not $1:1$ (easy)
I proved that $f$ is on $P(\mathbb{P})$ which is probably wrong since it means $|\mathbb{N}|\geq |P(\mathbb{P})|$ but $|\mathbb{N}|=|\mathbb{P}|$.
Every subset of primes has a source in $\mathbb{N}$ (the multiplication of all the primes)
What's wrong with this?
 A: Every finite set of primes is in the range of $f$.
However, what about any infinite set of primes? Say, the set of all primes, itself?
No number has infinitely many prime factors, so no infinite set of primes is in the range of $f$. Indeed, the set of finite sets of primes is countable, while the set of infinite sets of primes is uncountable - "most" sets of primes are infinite!
A: You already saw your mistake: the cardinality of the power set of an infinite set is strictly greater than the cardinality of the set itself.
Since $\mathbb{P}$ and $\mathbb{N}$ have the same cardinality, then $f$ cannot be onto (as mentioned before, indeed, every integer $\ge 2$ has a finite number of distinct prime factors).
A: As someone pointed out in the comments, $\mathbb{N}$ has the same cardinality as $\mathbb{P}$ because they are both infinite subsets of the countably infinite set $\mathbb{Z}$, hence they are both countably infinite sets. If you want to see this explicitly, just define $f : \mathbb{N} \to \mathbb{P}$ letting $f(n)$ be the $n$th prime, i.e. $f(1) = 2, f(2) = 3, f(3) = 5,\ldots$.
