I am confused as to how Cantor's Theorem and the Schroder-Bernstein Theorem interact. I think I understand the proofs for both theorems, and I agree with both of them. My problem is that I think you can use the Schroder-Bernstein Theorem to disprove Cantor's Theorem. I think I must be doing something wrong, but I can't figure out what. Can someone tell me where I am going wrong? Here's how I think I can prove that the set of all natural numbers has the same cardinality as its power set. Cantor's Theorem says that the power set of any set A has greater cardinality than A. Specifically, the set of all natural numbers, $\mathbb{N}$, is countably infinite, while its power set $P(\mathbb{N})$ is uncountably infinite. The Schroder-Bernstein Theorem says that, for two sets $A$ and $B$, if there exist one-to-one functions $f:A\mapsto B$ and $g:B \mapsto A$, then sets $A$ and $B$ have the same cardinality. I will try to use this to prove that the set of all natural numbers N has the same cardinality as its power set $P(\mathbb{N})$.

I need to prove that there exist one-to-one functions $f:\mathbb{N}\mapsto P(\mathbb{N})$ and $g:P(\mathbb{N})\mapsto \mathbb{N} $

  1. $f:\mathbb{N}\mapsto P(\mathbb{N})$

Define $f:\mathbb{N}\mapsto P(\mathbb{N})$, $n\mapsto f(n)=\{n\}$

For each output $f(n)$, there can only be one n corresponding to $f(n)$, so $f$ is a one-to-one function.

  1. $g:P(\mathbb{N})\mapsto \mathbb{N} $

Define $g:P(\mathbb{N})\mapsto \mathbb{N} $ as follows

Each element of $P(\mathbb{N})$ is a subset of $\mathbb{N}$, as represented by $\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$ where ${a}_{1},{a}_{2},\dots ,{a}_{k}$ are elements of $\mathbb{N}$

For each element $s=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$ of $P(\mathbb{N})$, the elements of $s=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$ are ordered from lowest to highest, so that ${a}_{1}<{a}_{2}<\dots <{a}_{k}$. The order of a set does not matter, so this can be done without creating a new set.

For each element $s=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$ of $P(\mathbb{N})$, $g(s)={{p}_{1}}^{{a}_{1}} *{{p}_{2}}^{{a}_{2}} * ... * {{p}_{k}}^{{a}_{k}}$, where ${p}_{1},{p}_{2},...,{p}_{k}$ are each the $k$th prime number. Ex. ${p}_{1}=2, {p}_{2}=3, {p}_{3}=5,\dots$

$P(\mathbb{N})$ contains the empty set, so $g(\emptyset)=0.$

The set of all prime numbers is countably infinite, so it has the same cardinality as the largest element of $P(\mathbb{N})$, which is $\mathbb{N}$.

Each output $g(s)$ is the prime factorization of some number n. Each number n has a unique prime factorization, so there is only one s in $P(\mathbb{N})$ whose $g(s)$ is the prime factorization of n.

Since the elements of $s=\{{a}_{1},{a}_{2},\dots ,{a}_{k}\}$ are ordered from lowest to highest, ${a}_{1}$ is the only element of $s$ that can be $0$. Thus, ${p}_{1}=2$ is the only prime number that can have an exponent of 0 in the output. Thus, it is impossible for any set $s$ in $P(\mathbb{N})$ to have the same output $g(s)$ as a set of different length in $P(\mathbb{N})$ . In other words, it is impossible to add or remove an element of s to create a new set ${s}_{2}$ so that $g(s)=g({s}_{2})$.

Every element $s$ of $P(\mathbb{N})$ has a unique output $g(s)$, so $g:P(\mathbb{N})\mapsto \mathbb{N} $ is a one-to-one function.

So $f:\mathbb{N}\mapsto P(\mathbb{N})$ and $g:P(\mathbb{N})\mapsto \mathbb{N} $ are both one-to-one functions.

So $\mathbb{N}$ and $P(\mathbb{N})$ have the same cardinality.

I'm fairly certain that both Cantor's Theorem and the Schroder-Bernstein Theorem are correct, so where does my proof go wrong?

  • 14
    $\begingroup$ Your $g$ isn't defined for all elements of $\mathcal P(\mathbb N)$, it's only defined for the finite ones. This set is indeed equinumerous with $\mathbb N$. $\endgroup$
    – Git Gud
    Nov 20, 2014 at 19:04
  • 15
    $\begingroup$ This has been asked literally uncountably many times on the site. $\endgroup$
    – Asaf Karagila
    Nov 20, 2014 at 19:07
  • 1
    $\begingroup$ 'Literally uncountably many times'...Wow! $\endgroup$
    – paw88789
    Nov 20, 2014 at 19:33
  • 1
    $\begingroup$ @Hurkyl Belonging to both Math.SE and English.SE gives me a massive headache. Literally! :) $\endgroup$
    – Deepak
    Nov 21, 2014 at 4:00
  • 1
    $\begingroup$ @Hurkyl: I did mean literally, though. Literally literally. Whenever I try to make a list of the questions which can be essentially reduced to the classic "What about infinite subsets of $\Bbb N$?" rebuttal, there is one that is not on that list. Cantor's diagonal argument comes to life. $\endgroup$
    – Asaf Karagila
    Nov 21, 2014 at 7:30

1 Answer 1


Your argument does not work when you say

$$\mbox{For each element $s=\{a_1,a_2,...,a_k\}$ of $P(\mathbb{N})$}$$ since you are not considering infinite subsets of $\mathbb{N}$. However you just proved that finite subsets of $\mathbb{N}$ form a countable set.

  • $\begingroup$ Thanks for the response. Could you elaborate a bit more on why the function isn't defined for infinite subsets? The infinite subsets of the natural numbers are countably infinite, and the set of the prime numbers is also countably infinite, so you could form a one-to-one correspondence from an infinite subset of the natural numbers to the infinite set of prime numbers. Why isn't the function defined, then, when it links each element of an infinite subset of the natural numbers to an element of the set of primes? $\endgroup$ Nov 20, 2014 at 22:02
  • $\begingroup$ @The it is only defined for finite subsets because not every subset of N has that specific form. Specifically infinite subsets of N don't have that form. Your prime number multiplication construction that follows relies on k being finite, so it couldn't be modified to allow infinite subsets. $\endgroup$ Nov 20, 2014 at 22:07
  • 7
    $\begingroup$ Hint: $\mathbb{N}\in P(\mathbb{N})$. What is $g(\mathbb{N})$ under your definition? Well, it seems to be: $$\prod_{n=1}^{\infty}p_n^{n}$$ - but hey, wait, that doesn't converge (at least not in the natural numbers!). In fact your function is undefined for every infinite subset of $\mathbb{N}$ (like even numbers, prime numbers, square numbers, etc. which are all subsets of the naturals) $\endgroup$ Nov 20, 2014 at 23:36
  • 1
    $\begingroup$ Another reasonable way to see this would be to say: For an infinite subset $~K$, it must be that $g(K)=\infty$, but then $g$ isn't 1:1 at $\infty$. $\endgroup$ Nov 21, 2014 at 0:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .