Intereting Posts

Calculate distance in 3D space
difficulty of accepting $i^2 = -1$ for first timers
Product of Riemannian manifolds?
Proving a set is Lebesgue Measurable
How do we check if a polynomial is a perfect square?
A generalization of the connected sum of links
Link between the negative pell equation $x^2-dy^2=-1$ and a certain continued fraction
calculating nested exponents modulo n
Show $\sum_{k=1}^\infty \frac{k^2}{k!} = 2\mathrm{e}$
Expected value of a minimum?
Is there an integral for $\pi^4-\frac{2143}{22}$?
$\sum_{k=0}^n (-1)^k \binom{n}{k}^2$ and $\sum_{k=0}^n k \binom{n}{k}^2$
Why I am getting different answer?
Intuition behind proof of bounded convergence theorem in Stein-Shakarchi
Are the natural numbers implicit in the construction of first-order logic? If so, why is this acceptable?

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

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

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

- Help with a recurrence with even and odd terms
- Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive
- What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?
- Combinatorial proofs of the following identities
- Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$
- Prove that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?

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?

- Mutually exclusive countable subsets of a countable set
- How to prove $ A \cup \{a\} \approx B \cup \{ b \} \Rightarrow A \approx B $
- What's the meaning of a set to the power of another set?
- Use mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.
- Indexed Family of Sets
- Powers of Adjacency Matrix (Determination of connection in Graph)
- Is symmetric group on natural numbers countable?
- Bob starts with \$20. Bob flips a coin. Heads = Win +\$1 Tails = Lose -\$1. Stops if he has \$0 or \$100. Probability he ends up with \$0?
- Proof: no fractions that can't be written in lowest term with Well Ordering Principle
- Power Set of $X$ is a Ring with Symmetric Difference, and Intersection

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.

- Why is $(3,x^3-x^2+2x-1)$ not principal in $\mathbb{Z}$?
- Solving quadratic Diophantine equations: $5n^2+2n+1=y^2$
- $|G|>2$ implies $G$ has non trivial automorphism
- To prove $ \tan(A) + 2 \tan(2A) +4\tan4A + 8 \cot8A =\cot(A) $
- Integral identity related with cubic analogue of arithmetic-geometric mean
- Pointwise a.e. convergence and weak convergence in Lp
- Show uniform convergence of function series
- Prove a square is homeomorphic to a circle
- Convergence testing of the improper integral $\int_{0}^{\infty}\frac{\ln x}{\sqrt{x}(x^2-1)}\ dx$
- In proof by induction, what does it mean when condition for inductive step is lesser than the propsition itself?
- Homology groups of a tetrahedron
- Is there a multiple function composition operator?
- How many ways to arrange people on a bench so that no woman sits next to another woman?
- what is the$ \int \sin (x^2) \, dx$?
- What is the difference between topological and metric spaces?