The function $f : \mathbb N\to \mathbb S$ defined as $f(n) = n^2$ is a bijection. It is an injection since if $n^2 = m^2$, then $n = m$. And it is surjective since for every $s \in \mathbb S$, by the definition of $\mathbb S$, there exists an $n$ such that $n^2 = s$.

Since $\mathbb N\subseteq \mathbb Z$, we have $|\mathbb N| \leq |\mathbb Z|$. So we just need to argue $|\mathbb Z| \leq |\mathbb N|$, i.e. there is a surjective function $f$ from $\mathbb N$ to $\mathbb Z$. For this, our strategy is to argue that we can list the elements of $\mathbb Z$ such that every element eventually appears in the list. If we can do this, then we have the surjection $f$ that we want: we let $f(n)$ be the $n$’th element in the list. Creating such a listing of $\mathbb Z$ is relatively straightforward: $$0, \; 1, \; -1, \; 2, \; -2, \; 3, \; -3, \; \ldots$$ With this listing, the mapping $f$ is such that odd numbers are mapped to positive integers and even numbers are mapped to non-positive integers. The formula for $f$ is $$f(n) = \begin{cases} -n/2 & \text{ if $n$ is even,} \\ (n+1)/2 & \text{ if $n$ is odd.} \end{cases}$$

We will show $|\mathbb Z\times \mathbb Z| = |\mathbb N|$ by arguing $|\mathbb N| \leq |\mathbb Z\times \mathbb Z|$ and $|\mathbb Z\times \mathbb Z| \leq |\mathbb N|.$

The former doesn’t really require much of an argument. The map $n \mapsto (n,0)$ is an injection and so $|\mathbb N| \leq |\mathbb Z\times \mathbb Z|.$

For the latter, we will show that there is a surjective function $f$ from $\mathbb N$ to $\mathbb Z\times \mathbb Z$, and we will do so by arguing that we can list the elements of $\mathbb Z\times \mathbb Z$ such that every element eventually appears in the list. If we can do this, then we have the surjection $f$ that we want: we let $f(n)$ be the $n$’th element in the list.

We now describe how to list the elements of $\mathbb Z\times \mathbb Z$. Consider the plot of $\mathbb Z\times \mathbb Z$ on a 2-dimensional grid. Starting at $(0,0)$ we list the elements of $\mathbb Z\times \mathbb Z$ using a spiral shape, as shown below.

(The picture shows only a small part of the spiral.) Since we have a way to list all the elements such that every element eventually appears in the list, we are done.

(Side node: It is not a requirement that we give an explicit formula for $f(i)$. In fact, sometimes in such proofs, an explicit formula may not exist. This does not make the proof any less rigorous! The above proof is perfectly acceptable.)

We want to show $|\mathbb Q| = |\mathbb N|$, and it is clear that $|\mathbb N| \leq |\mathbb Q|$ (since $\mathbb N\subseteq \mathbb Q$), so we just need to show $|\mathbb Q| \leq |\mathbb N|$. We will make use of the previous proposition to establish this.

Note that every element of $\mathbb Q$ can be written as a fraction $a/b$ where $a, b \in \mathbb Z$. In other words, there is a surjection from $\mathbb Z\times \mathbb Z$ to $\mathbb Q$ that maps $(a,b)$ to $a/b$ (if $b = 0$, map $(a,b)$ to say $0$). This shows that $|\mathbb Q| \leq |\mathbb Z\times \mathbb Z|$. From the previous proposition, $|\mathbb Z\times \mathbb Z| = |\mathbb N|$. Putting things together, $|\mathbb Q| \leq |\mathbb N|$.

Recall that $\Sigma^*$ denotes the set of all words/strings over the alphabet $\Sigma$ with finitely many symbols. We want to show $|\mathbb N| \leq |\Sigma^*|$ and $|\Sigma^*| \leq |\mathbb N|$.

To show $|\mathbb N| \leq |\Sigma^*|$, note that the function that maps a string to its length, $s \mapsto |s|$, is a surjection from $\Sigma^*$ to $\mathbb N$. (Remark: When $|\Sigma| = 1$, this function is a bijection.)

We will now show $|\Sigma^*| \leq |\mathbb N|$ by presenting a way to list all the elements of $\Sigma^*$ such that eventually all the elements appear in the list. (As before, if we can present this listing, then we have a surjection $f : \mathbb N\to \Sigma^*$: we let $f(n)$ be the $n$’th element in the list.)

For each $k = 0,1,2,\ldots$, let $\Sigma^k$ denote the set of words in $\Sigma^*$ that have length exactly $k$. Note that $\Sigma^k$ is a finite set for each $k$, and $\Sigma^*$ is a union of these sets: $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots$. This gives us a way to list the elements of $\Sigma^*$ so that any element of $\Sigma^*$ eventually appears in the list. First list the elements of $\Sigma^0$, then list the elements of $\Sigma^1$, then list the elements of $\Sigma^2$, and so on.

Since $\mathbb{P} \subseteq \mathbb N$, we know $|\mathbb{P}| \leq |\mathbb N|$. We also know that there are infinitely many primes. Then by Theorem (No cardinality strictly between finite and $|\mathbb N|$), $|\mathbb{P}| = |\mathbb N|$.

(One can also prove this proposition without invoking the theorem. The function that maps $n$ to the $n$’th prime number is a bijection.)

Let $\mathbb Q[x]$ denote the set of all polynomials in one variable with rational coefficients. We want to show that $\mathbb Q[x]$ is countable. We will do so using the CS method. Let $$\Sigma = \{{\texttt{0}},{\texttt{1}},{\texttt{2}},{\texttt{3}},{\texttt{4}},{\texttt{5}},{\texttt{6}},{\texttt{7}},{\texttt{8}},{\texttt{9}},{\texttt{+}},{\texttt{-}},{\texttt{/}},{\texttt{x}}\}.$$ Then observe that every element of $\mathbb Q[x]$ can be written as a finite string over this alphabet. For example, $${\texttt{2x3-1/34x2+99/100x1+22/7}}$$ represents the polynomial $$2x^3 - 1/34x^2 + 99/100x + 22/7.$$ This implies that there is a surjective map from $\Sigma^*$ to $\mathbb Q[x]$. And therefore $|\mathbb Q[x]| \leq |\Sigma^*|$. Since $\Sigma^*$ is countable, i.e. $|\Sigma^*| \leq |\mathbb N|$, $\mathbb Q[x]$ is also countable.

Given a set $\mathcal{F}$ of functions $f: X \to Y$, we want to construct a function $f_D : X \to Y$ that is different from every $f \in \mathcal{F}$. The main idea is the following. For each $f \in \mathcal{F}$, pick a unique input $x \in X$ and define $f_D(x)$ in a way such that it is different from $f(x)$. Since by construction $f_D$ and $f$ disagree on input $x$, $f_D$ is different from $f$. And since we do this for every $f \in \mathcal{F}$, $f_D$ is different from all $f \in \mathcal{F}$.

Above, it is important that we pick a unique $x$ for each $f \in \mathcal{F}$ so that $f_D$ can be defined in a consistent way. The ability to pick a unique $x$ for each $f \in \mathcal{F}$ is equivalent to $|X| \geq |\mathcal{F}|$.

A bit more formally, since $|X| \geq |\mathcal{F}|$, there is an injection $\phi : \mathcal{F}\to X$. Let $x_f = \phi(f)$. So $f \neq f'$ implies $x_f \neq x_{f'}$. Define $f_D$ such that for all $f \in \mathcal{F}$, $f_D(x_f) \neq f(x_f)$ (this is where the assumption $|Y| \geq 2$ is used). This ensures that $f_D$ is different from every $f \in \mathcal{F}$, and therefore $f_D \not \in \mathcal{F}$. (Note that our description of $f_D$ leaves it underspecified, but see the remark below.)

Diagonalization tells us that whenever $|X| \geq |\mathcal{F}|$, we can construct a function $f_D$ not in $\mathcal{F}$. But if $\mathcal{F}$ denotes the set of all functions $f: X \to Y$, the construction of $f_D$ is not possible. Therefore it must be the case that $|X| < |\mathcal{F}|$.

Let $\mathcal{F}$ be the set of all functions $f : X \to \{0,1\}$, which are the characteristic functions of the subsets of $X$ (so $f(x) = 1$ if and only if $x \in X$). Then by Note (Functions in disguise), $|\mathcal{F}| = |\wp(X)|$ and the result follows from the above Corollary.

Let’s break this up into two cases: (i) $S$ is countably infinite and (ii) $S$ is uncountable.

If $S$ is countably infinite, $|S| = |\mathbb N|$. And by Cantor’s Theorem, $|\mathbb N| = |S| < |\wp(S)|$, which by definition means $\wp(S)$ is uncountable.

If $S$ is uncountable, then $|\mathbb N| < |S| < |\wp(S)|$, and so once again, $\wp(S)$ is uncountable.

We will prove the existence of a number in $\mathbb R\setminus \mathbb Q$ (i.e. the existence of an irrational number) by constructing such a number using diagonalization. In order to simplify the proof, we will restrict our attention to numbers in the interval $[0,1]$, so we will construct an irrational number in $[0,1]$. The restriction to $[0,1]$ allows us to represent a number just by considering the fractional part.

As mentioned in Note (Functions in disguise), numbers can be viewed as functions: Every function $f : \mathbb N^+ \to \{0,1\}$ represents a real number in $[0,1]$ in binary, namely $0.f(1)f(2)f(3)\ldots$. Two different functions $f$ and $f'$ may represent the same real number, e.g. $0.10000\ldots$ and $0.01111\ldots$ represent the same real number. But we don’t have more than two different functions representing the same number.

Now consider the set $\mathcal{F}$ of all functions $f : \mathbb N^+ \to \{0,1\}$ representing a rational number. We will diagonalize against $\mathcal{F}$ to construct $f_D$ not in $\mathcal{F}$. This $f_D$ then represents a real number that is not rational, and we are done.

In order to diagonalize against $\mathcal{F}$, all we need is that $|\mathbb N^+| \geq |\mathcal{F}|$ holds. And this is indeed the case. $\mathcal{F}$ is countably infinite because $\mathbb Q$ is countably infinite. And obviously $\mathbb N^+$ is countably infinite. This means we are in the situation outlined in Note (Diagonalization with countable sets), and $|\mathbb N^+| = |\mathcal{F}|$.

Using the observation in Note (Functions in disguise), an infinite-length string $s \in \{{\texttt{0}},{\texttt{1}}\}^\infty$ corresponds to a function $f_s : \mathbb N^+ \to \{{\texttt{0}}, {\texttt{1}}\}$, which is the characteristic function of a set $S \subseteq \mathbb N^+$ (where $n \in S$ if and only if $f_s(n) = {\texttt{1}}$). Therefore the set of all infinite-length strings, $\{{\texttt{0}},{\texttt{1}}\}^\infty$, corresponds to the set of all subsets of $\mathbb N^+$, $\wp(\mathbb N^+)$. That is, $\{{\texttt{0}},{\texttt{1}}\}^\infty \leftrightarrow\wp(\mathbb N^+)$. Using Corollary (The power set of an infinite set is uncountable) we can conclude $\{{\texttt{0}},{\texttt{1}}\}^\infty$ is uncountable.