Why doesn't this work imply that there are countably many subsets of the naturals?

Solution 1:

Your proof shows that the finite subsets of the naturals are countable. However, consider an infinite subset, say $A = \{2,4,8, ... \}$... what is $f(A)$? It is undefined, since it is a number with an infinite number of prime factors... thus, you have not defined a function $f: P(\mathbb{N}) \rightarrow \mathbb{N}$ but a function from $F(\mathbb{N}) \rightarrow \mathbb{N}$.

Solution 2:

Artem Kaznatcheev has pointed out that your function is not defined for infinite subsets of $\mathbb N$; i.e., you have the wrong domain. From another perspective, your function is defined for every subset of $\mathbb N$, but you have the wrong codomain. As indicated in Bill Dubuque's comment, there is a formalization of numbers potentially having infinitely many prime factors, called the supernatural numbers. Your $f$ can be thought of as setting up a bijection between the power set of $\mathbb N$ and the set of supernatural numbers having at most one copy of each prime in their factorizations. (To get all supernatural numbers, you would have to consider multisets of natural numbers, allowing $\infty$ as a possible multiplicity.)

In addition to the group theoretic applications of supernatural numbers mentioned in the Wikipedia article, they are important in the theory of UHF C*-algebras, direct limits of full matrix algebras over $\mathbb C$. The associated supernatural number is the "limit" of the sizes of the matrix algebras, and corresponds uniquely to the algebra up to isomorphism.