Intereting Posts

The topology defined by the family of pseudo-distances.
Continuous $f\colon \to \mathbb{R}$ all of whose nonempty fibers are countably infinite?
Taking stalk of a product of sheaves
One-point compactification of manifold
Quadratic Polynomial factorization
Is a pathwise-continuous function continuous?
Embedding torsion-free abelian groups into $\mathbb Q^n$?
Differentiation under the integral sign for Lebesgue integrable derivative
Any Set of Ordinals is Well-Ordered
Help me solve this olympiad challenge?
heat equation with inhomogenous BC and IC
For $k<n/2$ construct a bijection $f$ from $k$-subsets of $$ to $(n-k)$-subsets s.t. $x\subseteq f(x)$
Solve $x^2+2=y^3$ using infinite descent?
Solve in integers $x,y$ the equation $\left\lfloor\frac{xy-xy^2}{x+y^2} \right\rfloor=a$
extending a vector field defined on a closed submanifold

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

- Alternatives to show that $|\mathbb{R}|>|\mathbb{Z}|$
- Why can't a set have two elements of the same value?
- Number of different partitions of N
- Cardinality of a basis of an infinite-dimensional vector space
- Rigorous proof that countable union of countable sets is countable
- Suppose $A,B,C$ are sets. Prove that $A\mathbin\triangle B\subseteq C \iff A\cup C=B\cup C$.

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

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

- Cardinality of the infinite sets
- How do I write $\{3,6,11,18,27,38,…\}$ in set-builder notation?
- countable group, uncountably many distinct subgroup?
- Number of $\sigma$ -Algebra on the finite set
- The way into set theory
- Is $\mathbb{Z}= \{\dots -3, -2, -1, 0 ,1 ,2 , 3, \dots \}$ countable?
- Cardinality of the Cartesian Product of Two Equinumerous Infinite Sets
- Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$

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.

- Discrete logarithm tables for the fields $\Bbb{F}_8$ and $\Bbb{F}_{16}$.
- Evaluate $\int \frac{1}{(x^2+1)^2}dx$
- What exactly are fractals
- $S_n = x_1^3+x_2^3+ \cdots +x_n^3$ squares perfect
- Why am I under-counting when calculating the probability of a full house?
- How does adding big O notations works
- Mapping random points on a sphere onto a uniform grid
- Generators of the multiplicative group modulo $2^k$
- How can I use Bessel's equation to solve the Lengthening Pendulum differential equation?
- Is there a unique finitely-additive extension of the length function to all real subsets?
- Number of ways to split a list into consecutive parts
- $-1$ is a quadratic residue modulo $p$ if and only if $p\equiv 1\pmod{4}$
- Sorgenfrey line is hereditarily separable
- About the Legendre differential equation
- Exact sequence and torsion