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

Question

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.

2. $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?

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.