Cantor's theorem shows us that the power set of the natural numbers is uncountably infinite. But today (and before remembering Cantor's proof) I was trying to prove the incorrect version: that the power set of the natural numbers is actually countably infinite. My work obviously has to be wrong, so I'm hoping that someone can spot a false implication.

So, to prove that the set of natural numbers is of the same cardinality as the power set of the natural numbers, I intend to show that a bijection $f: \mathcal{P}(\mathbb{N}) \to \mathbb{N}$ exists.

Now, it suffices for $f$ to be injective; Afterwards, we can just sort the image of $f$ and number the results starting from 1 to make it surjective as well.

So here is my $f$: For any set $A$ consisting of natural numbers, $$f(A) = p_1^{\delta(1)}p_2^{\delta(2)}p_3^{\delta(3)}\cdots$$ where $p_i$ is the $i$-th prime number and $$ \delta(x) = \begin{cases} 1, & x\in A\\ 0, & x\not \in A \end{cases} $$

So, as an example, if $A = \{1,3,4\}$, then $f(A) = 2^1\cdot5^1\cdot7^1 = 70$. This function should be one-to-one, since each integer has a unique prime factorization. Therefore, any set in $\mathcal{P}(\mathbb{N})$ will be associated with a unique natural number. We sort these natural numbers are re-number them starting with 1, producing a bijection between the power set of naturals and the naturals, meaning that the power set of the naturals is actually countably infinite.

But this is wrong. Where is the weakness in my proof?

  • 15
    $\begingroup$ $f$ is not well-defined for infinite subsets. (The set of $finite$ subsets of $\Bbb N$ is countable...) $\endgroup$ – David Mitra Jan 9 '12 at 1:43
  • 3
    $\begingroup$ Look up supernatural numbers. $\endgroup$ – Bill Dubuque Jan 9 '12 at 1:50
  • $\begingroup$ Given $A=\mathbb N$ what is $f(A)$? $\endgroup$ – Asaf Karagila Jan 9 '12 at 6:51

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}$.

  • 6
    $\begingroup$ In the first sentence, the first "countable" should be "finite". $\endgroup$ – Arturo Magidin Jan 9 '12 at 1:52

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.