# Do Cantor's Theorem and the Schroder-Bernstein Theorem Contradict?

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?

• 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$. Nov 20, 2014 at 19:04
• This has been asked literally uncountably many times on the site. Nov 20, 2014 at 19:07
• 'Literally uncountably many times'...Wow! Nov 20, 2014 at 19:33
• @Hurkyl Belonging to both Math.SE and English.SE gives me a massive headache. Literally! :) Nov 21, 2014 at 4:00
• @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. Nov 21, 2014 at 7:30

$$\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.
• 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) Nov 20, 2014 at 23:36
• 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$. Nov 21, 2014 at 0:15