Let $$\mathsf{Sq} = \{ n^2 \mid n \in \mathbb{N} \}$$ and $$\mathsf{Cu} = \{ n^3 \mid n \in \mathbb{N} \}$$.
Prove that $$|\mathsf{Cu}| = |\mathsf{Sq}|$$ by:
* using the Cantor-Schröder-Bernstein Theorem, and
* by giving an explicit bijection between the two sets.

---

### CSB Proof

#### Scratchwork

We need to show that $$|\mathsf{Cu}| \le |\mathsf{Sq}|$$, and $$|\mathsf{Sq}| \le |\mathsf{Cu}|$$.

Cantor's definition says that to prove $$|\mathsf{Cu}| \le |\mathsf{Sq}|$$, we need to show that there exists a surjective function from $$\mathsf{Sq}$$ to $$\mathsf{Cu}$$.

Proposition 11 of the Notes on Cardinality (aka Problem 3 on WS4) if we show there exists an injective function from $$\mathsf{Cu}$$ to $$\mathsf{Sq}$$, then there there is a surjective function from $$\mathsf{Sq}$$ to $$\mathsf{Cu}$$, which means that $$|\mathsf{Cu}| \le |\mathsf{Sq}|$$.

We already know that squaring a natural number gives an element of $$\mathsf{Sq}$$. So let's just square all of the elements on $$\mathsf{Cu}$$. And this will probably be injective. Hopefully.

The same logic says that if we give an injective function from $$\mathsf{Sq}$$ to $$\mathsf{Cu}$$ then $$|\mathsf{Sq}| \le |\mathsf{Cu}|$$. So before we were squaring, so here let's try cubing.

#### Proof

To prove $$|\mathsf{Cu}| = |\mathsf{Sq}|$$, we will show $$|\mathsf{Cu}| \le |\mathsf{Sq}|$$, and $$|\mathsf{Sq}| \le |\mathsf{Cu}|$$, and then the result will follow from the Cantor-Schröder-Bernstein theorem.

First we will show that $$|\mathsf{Cu}| \le |\mathsf{Sq}|$$ by giving an injective function from $$\mathsf{Cu}$$ to $$\mathsf{Sq}$$. So consider the function $$f : \mathsf{Cu} \to \mathsf{Sq}$$, given by $$f(n) = n^2$$. We will prove that $$f$$ is injective. Let $$x,y \in \mathsf{Cu}$$ such that $$f(x) = f(y)$$, i.e., $$x^2 = y^2$$. Since $$x,y \ge 0$$, $$\sqrt{x^2} = x$$ and $$\sqrt{y^2} = y$$. So taking square roots of both sides of the equation $$x^2 = y^2$$ gives $$x = y$$. So $$f$$ is injective.

Similarly, we will show that $$|\mathsf{Sq}| \le |\mathsf{Cu}|$$ by giving an injective function from $$\mathsf{Sq}$$ to $$\mathsf{Cu}$$. Let $$g : \mathsf{Sq} \to \mathsf{Cu}$$ be defined by $$g(n) = n^3$$. To show that $$g$$ is injective, let $$x,y \in \mathsf{Sq}$$ such that $$g(x) = g(y)$$, i.e., $$x^3 = y^3$$. But for all real numbers $$z$$, $$\sqrt[3]{z} = z$$. So in fact $$x = y$$, and $$g$$ is injective.

So this completes the proof.

---

### Explicit bijection

#### Scratchwork

So some of you maybe noticed that we can do the following: given $$n^2 \in \mathsf{Sq}$$, we can send it to $$n^3 \in \mathsf{Cu}$$. We can write this as $$h : \mathsf{Sq} \to \mathsf{Cu}$$, $$h(x) = x^{3/2}$$. We can try proving this is a bijective function.

We've already talked about injectiveness of squaring and cubing, so let's focus on surjectiveness.

Recall that for $$y \in \mathsf{Cu}$$ we need to show that there exists $$x \in \mathsf{Sq}$$ such that $$h(x) = y$$. We're going to solve for $$x$$ (in terms of $$y$$) and hope that the thing we get is actually in $$\mathsf{Sq}$$. $$h(x) = y$$ means that $$x^{3/2} = y$$, so rearranging, we get $$x = y^{2/3}$$.

#### Proof

Consider the function $$h : \mathsf{Sq} \to \mathsf{Cu}$$, $$h(x) = x^{3/2}$$. We will prove that this function is bijective.

(Injective): Let $$x,y \in \mathsf{Sq}$$ such that $$h(x) = h(y)$$, i.e, $$x^{3/2} = y^{3/2}$$. Squaring both sides gives $$x^3 = y^3$$, then since for any real number $$z$$, $$\sqrt[3]{z} = z$$, $$x = y$$.

(Surjective): Let $$y \in \mathsf{Cu}$$. We need to show there exists $$x \in \mathsf{Sq}$$ such that $$h(x) = y$$. So consider $$x = y^{2/3}$$. Since $$y \in \mathsf{Cu}$$, there exists a $$k \in \mathbb{N}$$ such that $$y = k^3$$. Then $$x = (k^3)^{2/3} = k^2$$. So $$x \in \mathsf{Sq}$$, and $$f(x) = f(y^{2/3}) = (y^{2/3})^{3/2} = y$$.

This completes the proof.

---
---
---
---
---
---