Title: Numbers and Sets

Q: Negating quantifiers
A: \[
  \neg (\forall x) P(x) \Leftrightarrow (\exists x)(\neg P(x));
\]
\[
  \neg (\exists x) P(x) \Leftrightarrow (\forall x)(\neg P(x)).
\]

Q: Division
A: Given $a, b\in \mathbb{Z}$, we say $a$ \emph{divides} $b$, $a$ is a \emph{factor} of $b$ or $a\mid b$ if \[
\exists c\in \mathbb{Z}:b = ac.\]

Q: Proper factor
A: For any $b$, $\pm 1$ and $\pm b$ are always factors of $b$. The other factors are called \emph{proper factors}.

Q: Division Algorithm
A: Given $a, b\in \mathbb{Z}$, there are unique $q, r\in \mathbb{Z}$ with $a = qb + r$ and $0\leqslant r < b$.
\begin{proof}
  Choose $q = \max\{q : qb \leqslant a\}$. This maximum exists because the set of all $q$ such that $qb\leqslant n$ is finite. Now write $r = a - qb$. We have $0\leqslant r < b$ and thus $q$ and $r$ are found.
  To show that they are unique, suppose that $a = qb + r = q'b + r'$. We have $(q - q')b = (r' - r)$. Since both $r$ and $r'$ are between $0$ and $b$, we have $-b < r - r' < b$. However, $r' - r$ is a multiple of $b$. Thus $q - q' = r' - r = 0$. Consequently, $q = q'$ and $r = r'$.
\end{proof}

Q: Common factor
A: A \emph{common factor} of $a$ and $b$ is a number $c\in\mathbb{Z}$ such that $c\mid a$ and $c\mid b$.

Q: Highest common factor/greatest common divisor
A: The \emph{highest common factor} or \emph{greatest common divisor} of two numbers $a, b\in \mathbb{N}$ is a number $d\in \mathbb{N}$ such that $d$ is a common factor of $a$ and $b$, and if $c$ is also a common factor, $c\mid d$. \\
We write $d = \mathrm{hcf}(a, b) = \mathrm{gcd}(a, b) = (a, b)$. \\
We must show it exists.
\begin{proof}
  Let $S=\{ua + vb \ | \ u, v\in\mathbb{Z}\}$ be the set of all linear combinations of $a, b$. Let $d$ be the smallest positive member of $S$. Say $d = xa + yb$. Hence if $c\mid a, c\mid b$, then $c\mid d$. So we need to show that $d\mid a$ and $d\mid b$, and thus $d=(a, b)$.
  By the division algorithm, there exists numbers $q, r\in\mathbb{Z}$ with $a = qd + r$ with $0\leq r < d$. Then $r = a - qd = a(1 - qx) - qyb\in S$. Since $d$ is the smallest positive member of $S$ and $0\leq r < d$, we have $r = 0$ and thus $d\mid a$. By symmetry, $d\mid b$.
\end{proof}
This is clearly unique.
\begin{proof}
Let $d$ and $d'$ be highest common factors of $a,b$. Therefore \[
d|d', d'|d \implies d=d'
\]
\end{proof}
Finally, it is also the largest common factor.
\begin{proof}
Let $d=(a,b)$ and $c|a,c|b$. Therefore \[
c|d \implies c\leqslant d
\]
\end{proof}

Q: Show that common factors divide all linear combinations.
A: If $c\mid a$ and $c\mid b$, then $c\mid (ua + vb)$ for all $u, v\in \mathbb{Z}$.
\begin{proof}
  By definition, we have $a = kc$ and $b = lc$. Then $ua + vb = ukc + vlc = (uk + vl)c$. So $c\mid (ua + vb)$.
\end{proof}

Q: B\'ezout's Theorem
A: Let $a, b\in\mathbb{N}$ and $c\in \mathbb{Z}$. Then there exists $u, v\in \mathbb{Z}$ with $c=ua + vb$ iff $(a, b)\mid c$.
\begin{proof}
  ($\Rightarrow$) Let $d=(a, b)$. If $c$ is a linear combination of $a$ and $b$, then $d\mid c$ because $d\mid a$ and $d\mid b$.
  ($\Leftarrow$) Suppose that $d\mid c$. Let $d = xa + yb$ and $c = kd$. Then $c = (kx)a + (ky)b$. Thus $c$ is a linear combination of $a$ and $b$.
\end{proof}

Q: Euclid's Algorithm
A: If we continuously break down $a$ and $b$ by the following procedure:
  \begin{align*}
    a &= q_1b + r_1\\
    b &= q_2r_1 + r_2\\
    r_1 &= q_3r_2 + r_3\\
    &\vdots\\
    r_{n-2} &= q_nr_{n-1}
  \end{align*}
  then the highest common factor is $r_{n-1}$.
\begin{proof}
  We have $($common factors of $a, b)=($common factors of $b, r_1)=($common factors of $r_1, r_2 )= \ldots = ($factors of $r_{n-1})$.
\end{proof}
This gives an alternative proof that hcfs exist. \\
This can be reversed to write the hcf as a linear combination of $a$ and $b$.

Q: Efficiency of Euclid's Algorithm
A: Consider the $i$th step \[
r_i=q_{i+2}r_{i+1}+r_{i+2}.
\]
As $q_{i+2}\geqslant 1, r_{i+1}>r_{i+2}$, we have \[
r_i\geq r_{i+1} + r_{i+2} > 2r_{i+2} \]
So every two steps, the number on the left goes down by at least half. Hence the number of digits goes down every 8 steps. Thus the time needed is $\leq 8\times$ number of digits and has time complexity $O(\log b)$.

Q: Memory efficient method of writing the hcf as a linear combination
A: We attempt to find a recurrence relations for the coefficients $A_j, B_j$ such that $a B_j - b A_j = (-1)^{j - 1}r_j$. Suppose that this is satisfied for all indices less than $j$. Then we have
\begin{align*}
  (-1)^{j-1}r_{j} &= (-1)^{j-1}(r_{j - 2} - q_jr_{j - 1})\\
  &= (-1)^{j - 3} r_{j - 2} + q_j (-1)^{j - 2} r_{j - 1}\\
  &= a (B_{j - 2} + q_j B_{j - 1}) - b (A_{j - 2} + q_j A_{j - 1}).
\end{align*}
Hence we can obtain the following recurrence relation:
\begin{align*}
\begin{pmatrix}A_j\\B_j\end{pmatrix}=q_j\begin{pmatrix}A_{j-1}\\B_{j-1}\end{pmatrix}+\begin{pmatrix}A_{j-2}\\B_{j-2}\end{pmatrix}
\end{align*}
To satisfy the original equation for $j=0$ and $j=-1$ (remembering that $r_{-1}=a,r_0=b$) we have \[
\begin{pmatrix}A_{-1}\\B_{-1}\end{pmatrix}=\begin{pmatrix} 0\\1\end{pmatrix}, \begin{pmatrix}A_{0}\\B_{0}\end{pmatrix}=\begin{pmatrix} 1\\0\end{pmatrix}
\]
Note that $a B_{n-1} - bA_{n-1} = (-1)^{n-1}r_{n - 1} =\pm (a, b)$ and $aB_n-bA_n=\pm r_n=0$ so $\frac{a}{b}=\frac{A_n}{B_n}$.
More generally,
\begin{align*}
A_jB_{j - 1} - B_jA_{j-1} &=(q_jA_{j-1}+A_{j-2})B_{j-1}-(q_jB_{j-1}+B_{j-2})A_{j-1} \\
&=-(A_{j-1}B_{j-2}-B_{j-1}A_{j-2}) \\
&\ldots  \\
&=(-1)^j(A_0B_{-1}-B_0A_{-1}) \\
&= (-1)^j
\end{align*}
So $(A_j, B_j) = 1$.

Q: Convergents
A: Consider the $i$th step of Euclid's algorithm
\begin{align*}
r_i&=q_{i+2}r_{i+1}+r_{i+2} \\
\implies \frac{r_i}{r_{i+1}}&=q_{i+2}+\frac{r_{i+2}}{r_{i+1}} \\
\implies  \frac{r_i}{r_{i+1}}&=q_{i+2}+\frac{1}{r_{i+1}/r_{i+2}} \\
\implies  \frac{r_i}{r_{i+1}}&=q_{i+2}+\frac{1}{q_{i+3}+r_{i+3} / r_{i+2} } \\
\ldots & \\
\implies \frac{a}{b}&=q_0+\cfrac{1}{q_1+\cfrac{1}{q_2+\cfrac{1}{q_3+\ldots}}}
\end{align*}
If we apply this process to $\frac{A_j}{B_j}$ we would get the same continued fraction up to $q_j$.

Q: Prime number
A: $p\in \mathbb{N}$ is a \emph{prime} if $p > 1$ and the only factors of $p$ are $\pm 1$ and $\pm p$.

Q: Infinitude of the prime numbers
A: There are infinitely many primes.
\begin{proof}
  (Euclid 300BC) Suppose there are finitely many primes, say $p_1, p_2 \ldots p_n$. Then $N = p_1p_2\ldots p_n + 1$ is divisible by none of the primes. Otherwise, $p_j\mid (N - p_1p_2\ldots p_n)$, ie. $p_j\mid 1$, which is impossible. However, $N$ is a product of primes, so there must be primes not amongst $p_1, p_2\ldots p_n$.
\end{proof}
\begin{proof}
  (Erd\"{o}s 1930) Suppose that there are finitely many primes, $p_1, p_2\ldots p_k$. Consider all numbers that are the products of these primes, ie. $p_1^{j_1}p_2^{j_2}\ldots p_k^{j_k}$, where $j_i \geq 0$. Factor out all squares to obtain the form $m^2p_1^{i_1}p_2^{i_2}\ldots p_k^{i_k}$, where $m\in \mathbb{N}$ and $i_j = 0$ or $1$.
  Let $N\in\mathbb{N}$. Given any number $x \leq N$, when put in the above form, we have $m \leq \sqrt{N}$. So there are at most $\sqrt{N}$ possible values of $m$. For each $m$, there are $2^k$ numbers of the form $m^2p_1^{i_1}p_2^{i_2}\ldots p_k^{i_k}$. So there are only $\sqrt{N}\times 2^k$ possible values of $x$ of this kind.
  Now pick $N\geq 4^k$. Then $N > \sqrt{N}\times 2^k$. So there must be a number $\leq N$ not of this form, i.e. it has a prime factor not in this list.
\end{proof}

Q: Fundamental Theorem of Arithmetic
A: Every natural number is expressible as a product of primes in exactly one way.
\begin{proof}
\textbf{Existence} Let $\varphi(k)$ be the statement that $\forall k\leq n\in\mathbb{N}$, $k$ can be written as a product of primes. We have $\varphi(1)$ as we think of $1$ as the empty product of primes. If $n\geq 2 \in\mathbb{N}$ is prime, then it is already a product of primes. Otherwise $n=ab$ where $a,b<n$. So $\varphi(n-1)\implies\varphi(n)$. The result follows by the SPI. \\
\textbf{Uniqueness}  Let $p_1\ldots p_k = q_1\ldots q_l$. We know that $p_1 \mid q_1\ldots q_l$. Then $p_1 \mid q_1q_2q_3\ldots q_l$. Thus $p_1 \mid q_i$ for some $i$. wlog assume $i = 1$. Then $p_1 = q_1$ since both are primes. Thus $p_2p_3 \ldots p_k = q_2q_3\ldots q_l$. Likewise, we have $p_2 = q_2$. This process stops when one side equals one such that $k=l$ and $p_1=q_1,p_2=q_2\ldots p_k=q_k$.
\end{proof}

Q: Modulo
A: If $a, b\in \mathbb{Z}$ have the same remainder after division by $m$, then $a$ and $b$ are \emph{congruent modulo} $m$ i.e.
  \[
    m \mid (a - b) \iff a\equiv b\pmod m
  \]

Q: Addition and multiplication in modular arithmetic
A: If $a\equiv b\pmod m$ and $u\equiv v \pmod m$, then $a + u\equiv b + v\pmod m$ and $au \equiv bv \pmod m$.
\begin{proof}
  Since $a\equiv b\pmod m$ and $u\equiv v \pmod m$, we have $m \mid (a - b) + (u - v) = (a + u) - (b + v)$. So $a + u\equiv b + v\pmod m$.
  Since $a\equiv b\pmod m$ and $u\equiv v \pmod m$, we have $m \mid (a - b)u + b(u - v) = au - bv$. So $au \equiv bv \pmod m$.
\end{proof}

Q: There are infinitely many primes that are $\equiv -1 \pmod 4$.
A: \begin{proof}
  Suppose not. So let $p_1, \cdots p_k$ be all primes $\equiv -1 \pmod 4$. Let $N = 4p_1p_2\cdots p_k - 1$. Then $N\equiv -1\pmod 4$. Now $N$ is a product of primes, say $N= q_1q_2\cdots q_\ell$. But $2\nmid N$ and $p_i\nmid N$ for all $i$. So $q_i \equiv 1\pmod 4$ for all $i$. But then that implies $N = q_1q_2\cdots q_\ell \equiv 1\pmod 4$, which is a contradiction.
\end{proof}

Q: Unit (modular arithmetic)
A: $u$ is a \emph{unit} if $\exists v$ such that $uv \equiv 1\pmod m$, i.e. $u$ is invertible

Q: Determining units
A: $u$ is a unit modulo $m$ if and only if $(u, m) = 1$
\begin{proof}
  $(\Rightarrow)$ Suppose $u$ is a unit. Then $\exists v$ such that $uv \equiv 1\pmod m$. Then $uv = 1 + mn$ for some $n$, or $uv - mn = 1$. So $1$ can be written as a linear combination of $u$ and $m$. So $(u, m) = 1$.
  $(\Leftarrow)$ Suppose that $(u, m) = 1$. Then there exists $a, b$ with $ua + mb = 1$. Thus $ua \equiv 1\pmod m$.
\end{proof}
So Euclid's algorithm allows us to determine $a\equiv u^{-1}\pmod m$ quickly.

Q: Solving congruences
A: If $(a, m) = 1$, then the congruence $ax \equiv b\pmod m$ has a unique solution (mod $m$).
\begin{proof}
  If $ax\equiv b\pmod m$, and $(a, m) = 1$, then $\exists a^{-1}$ such that $a^{-1}a\equiv 1\pmod m$. So $a^{-1}ax\equiv a^{-1}b\pmod m$ and thus $x\equiv a^{-1}b\pmod m$. Finally we check that $x \equiv a^{-1}b \pmod m$ is indeed a solution: $ax \equiv aa^{-1}b \equiv b \pmod m$.
\end{proof}
  There is a solution to $ax \equiv b\pmod m$ if and only if $(a, m) \mid b$.
  If $d = (a, m) \mid b$, then the solution is the unique solution to $\frac{a}{d}x \equiv \frac{b}{d} x\pmod {\frac{m}{d}}$
\begin{proof}
  Let $d = (a, m)$ (so in particular $d|a$). If there is a solution to $ax \equiv b\pmod m$, then $m \mid ax - b$. So $d \mid ax - b$ and $d \mid b$.
  On the contrary, if $d= (a, m)\mid b$, letting $a = da'$, $b = db'$ and $m = dm'$ we have
\begin{align*}
ax \equiv b\pmod m &\Leftrightarrow ax - b = km \\
&\Leftrightarrow da'x - db' = dkm' \\
&\Leftrightarrow a'x - b' = km' \\
&\Leftrightarrow a'x \equiv b'\pmod {m'}
\end{align*}
Note that $(a', m') = 1$ since we divided by their greatest common factor. Then this has a unique solution modulo $m'$.
\end{proof}

Q: Decreasing base in modular arithmetic
A: If $a\equiv b\pmod m$, and $d \mid m$, then $a \equiv b\pmod d$.
\begin{proof}
  \begin{align*}
a\equiv b\pmod m &\Rightarrow m \mid a - b \\
& \Rightarrow d \mid a - b \\
&\Rightarrow a \equiv b\pmod d
\end{align*}
\end{proof}
So if $m=n_1n_2\ldots n_k$, then
\begin{align*}
&a\equiv b\pmod {n_1} \\
&a\equiv b\pmod {n_2}  \\
& \ \vdots \\
&a\equiv b\pmod {n_k}
\end{align*}

Q: Chinese Remainder Theorem
A: Let $(m, n) = 1$ and $a, b\in \mathbb{Z}$. Then there is a unique solution (modulo $mn$) to the simultaneous congruences
  \[
    \begin{cases}x\equiv a\pmod m \\ x\equiv b\pmod n \end{cases},
  \]
\begin{proof}
\textbf{Existence}  Since $(m, n) = 1$, $\exists u, v\in \mathbb{Z}$ with $um + vn = 1$. Then $vn \equiv 1\pmod m$ and $um \equiv 1 \pmod n$. So $x = umb + vna$ satisfies $x\equiv a\pmod m$ and $x\equiv b\pmod n$.
\textbf{Uniqueness} Suppose both $y$ and $x$ are solutions to the equation. Then
  \begin{align*}
    &\; y \equiv a\pmod m \text{ and } y \equiv b\pmod n\\
    \Leftrightarrow &\; y \equiv x\pmod m \text{ and } y\equiv x\pmod n\\
    \Leftrightarrow &\; m \mid y - x\text{ and } n \mid y - x\\
    \Leftrightarrow &\; n| y - x=km,\\
    \Leftrightarrow &\; y-x= (ln)m \\
    \Leftrightarrow &\; y \equiv x\pmod {mn}
  \end{align*}
The same applies to more than two moduli by repetition/induction. \\
The reverse is obviously true so we have a bijection between pairs $a\in \{0,1,\dots m-1\},b\in \{0,1,\dots n-1\}$ and $c\in \{0,1,\ldots mn-1\}$ by $c\equiv a \pmod m$ and $c\equiv b \pmod n$.
\end{proof}

Q: Units in different moduli
A: Given any $(m,n) = 1$, $c$ is a unit mod $mn$ iff $c$ is a unit both mod $m$ and mod $n$.
\begin{proof}
  $(\Rightarrow)$ If $\exists u$ such that $cu \equiv 1 \pmod {mn}$, then $cu \equiv 1\pmod m$ and $cu\equiv 1\pmod n$. So $c$ is a unit mod $m$ and $n$.
  $(\Leftarrow)$ Suppose there exists $u, v$ such that $cu\equiv 1\pmod m$ and $cv \equiv 1\pmod n$. Then by CRT, $\exists w$ with $w\equiv u \pmod m$ and $w\equiv v\pmod n$. Then $cw\equiv cu\equiv 1\pmod m$ and $cw\equiv cv\equiv 1\pmod n$. We can easily see that $cw \equiv 1\pmod{mn}$ is a solution to these simultaneous congruences. By CRT, this solution is unique.
\end{proof}

Q: Euler's totient function
A: \[
\phi(m)=\left| \{ a\in\mathbb{N} \ | \ 0\leq a\leq m, (a, m) = 1\} \right|
\]
i.e. the number of units (mod $m$) up to $m$.
  \begin{enumerate}
    \item $\phi(mn) = \phi(m)\phi(n)$ if $(m, n) = 1$, ie. $\phi$ is multiplicative.
    \item If $p$ is a prime, $\phi(p) = p - 1$
    \item If $p$ is a prime, $\phi(p^k) = p^k - p^{k - 1} = p^k(1 - 1/p)$
    \item $\phi(m) = m\prod_{p \mid m}(1 - 1/p)$.
  \end{enumerate}
\begin{proof}
(1) Follows from the relationship between units in different moduli. \\
(2) $\left| \{ 1,2,\dots p-1\} \right|=p-1$ \\
(3) There are $p^k$ natural numbers up to $p^k$ of which only the $p^{k-1}$ multiples of $p$ are not units. \\
(4) Suppose $m = p_1^{k_1}p_2^{k_2}\cdots p_\ell^{k_\ell}$. Then
      \begin{align*}
        \phi(m) &= \phi(p_1^{k_1})\phi(p_2^{k_2})\cdots \phi(p_\ell^{k_\ell})\\
        &= p_1^{k_1}(1-1/p_1)p_2^{k_2}(1 - 1/p_2)\cdots p_\ell^{k_\ell}(1 - 1/p_\ell)\\
        &= m\prod_{p \mid m}(1 - 1/p)
      \end{align*}
Alternative for (4): let $m = p_1^{k_1}p_2^{k_2}\cdots p_\ell^{k_\ell}$. Let $X = \{0, \cdots m - 1\}$. Let $A_j = \{x\in X: p_j\mid x\}$. Then $|X| = m$, $|A_j| = m/p_j$, $|A_i\cap A_j| = m/(p_ip_j)$ etc. So $\phi(m) = |\bar A_1\cap \bar A_2\cap \cdots \bar A_\ell| = m\prod_{p \mid m}(1 - 1/p)$
\end{proof}

Q: Wilson's Theorem
A: $(p - 1)! \equiv -1\pmod p$ if $p$ is a prime.
\begin{proof}
  If $p$ is a prime, then $1, 2, \cdots, p - 1$ are units which form a group under multiplication. By closure under inverses, each element is self-inverse or comes in an inverse pair with another element of the group. The self-inverse elements are exactly $1$ and $-1$:
  \begin{align*}
    &\;x \equiv x^{-1}\pmod p\\
    \Leftrightarrow&\;x^2 \equiv 1\pmod p\\
    \Leftrightarrow&\; p \mid (x^2 - 1)\\
    \Leftrightarrow&\; p \mid (x - 1)(x + 1)\\
    \Leftrightarrow&\; p \mid x - 1 \text{ or } p \mid x + 1\\
    \Leftrightarrow&\; x \equiv \pm 1\pmod p
  \end{align*}
If $p=2$, then we can see the congruence holds. Otherwise $(p - 1)!$ is a product of $(p - 3)/2$ inverse pairs together with 1 and -1. So the product is $-1$.
\end{proof}

Q: Fermat's little theorem
A: Let $p$ be a prime. Then $a^p \equiv a\pmod p$ for all $a\in \mathbb{Z}$. Equivalently, $a^{p - 1}\equiv 1\pmod p$ if $a\not\equiv 0 \pmod p$.
\begin{proof}[Proof 1]
The numbers $\{1, 2, \dots p - 1\}$ are units modulo $p$ and form a group of order $p - 1$. So $a^{p - 1} \equiv 1$ (for $a\not\equiv 0$) by Lagrange's theorem.
\end{proof}
\begin{proof}[Proof 2]
    If $a\not\equiv 0$, then $a$ is a unit. So $ax \equiv ay$ iff $x\equiv y$. Then $a, 2a, 3a, \dots (p - 1)a$ are distinct mod $p$. So they are congruent to $1, 2, \dots p -1$ in some order. Hence
\begin{align*}
a\cdot 2a\cdot 3a\dots (p - 1)a&\equiv 1\cdot 2\cdot 3 \cdots (p - 1)  \pmod p\\
&\equiv a^{p - 1}[1\cdot 2\cdot 3 \cdots (p - 1) ] \pmod p  \\
\implies a^{p-1}&\equiv 1\pmod p
\end{align*}
\end{proof}
\begin{proof}[Proof 3]
For $0<k<p: {p\choose k}\equiv 0 \pmod p$. So for $a,b\in\mathbb{Z}$:
\begin{align*}
(a+b)^p&\equiv a^p +  {p\choose 1}a^{p-1}b +\ldots + {p\choose p-1}ab^{p-1}+b^p \pmod p \\
&\equiv a^p+b^p \pmod p
\end{align*}
Fermat's little theorem is clearly true for $a\equiv 0\pmod p$. For $a\in\mathbb{Z}$:
\begin{align*}
(a+1)^p\equiv a+1\pmod p &\iff  a^p+1^p\equiv a+1\pmod p\\
&\iff a^p\equiv a\pmod p
\end{align*}
The result follows by induction.
\end{proof}

Q: Fermat-Euler Theorem
A: Let $a, m$ be coprime. Then
  \[
    a^{\phi(m)} \equiv 1\pmod m.
  \]
\begin{proof}
  Lagrange's theorem: The units mod $m$ form a group of size $\phi(m)$.
  Alternatively, let $U = \{x\in \mathbb{N}: 0 < x < m, (x, m) = 1\}$. These are the $\phi(m)$ units. Since $a$ is a unit, \[
ax\equiv ay \pmod m \iff x\equiv y\pmod m \]
So if $U = \{u_1, u_2, \cdots , u_{\phi(m)}\}$, then $\{au_1, au_2, \cdots au_{\phi(m)}\}$ are distinct and are units. So they must be $u_1, \cdots u_{\phi(m)}$ in some order. Then
\begin{align*}
au_1au_2\cdots au_{\phi(m)} &\equiv u_1u_2\cdots u_{\phi(m)} \pmod m \\
&\equiv a^{\phi(m)} u_1u_2\cdots u_{\phi(m)} \pmod m \\
\implies a^{\phi(m)}&\equiv 1\pmod m
\end{align*}
\end{proof}

Q: Quadratic residues
A: The non-zero ``squares'' mod $p$
\begin{align*}
a^2 \equiv b^2\pmod p &\iff p \mid a^2 - b^2 \\
&\iff p | (a - b)(a + b) \\
&\iff p \mid a - b\textrm{ or }p \mid a + b \\
&\iff a\equiv\pm b \pmod p
\end{align*}
So every quadratic residue is the square of two numbers. \\
Therefore, there are $\frac{p-1}{2}$ quadratic residues $\mod p$ (and $\frac{p-1}{2}$ numbers which are not quadratic residues $\mod p$).

Q: If $p$ is an odd prime, then $-1$ is a quadratic residue if and only if $p\equiv 1\pmod 4$.
A: If $p$ is an odd prime, then $-1$ is a quadratic residue if and only if $p\equiv 1\pmod 4$.
\begin{proof}
  If $p \equiv 1 \pmod 4$, so $p=4k+1$, then by Wilson's theorem
\begin{align*}
-1 &\equiv (p - 1)! \pmod p \\
&\equiv 1\cdot 2\cdots \left(\frac{p - 1}{2}\right)\left(-\frac{p - 1}{2}\right)\cdots (-2)(-1) \pmod p \\
&\equiv (-1)^{\frac{p - 1}{2}}\left(\frac{p - 1}{2}\right)!^2 \pmod p\\
&\equiv (-1)^{2k}[(2k)!]^2  \pmod p\\
&\equiv (2k)!^2 \pmod p
\end{align*}
So $-1$ is a quadratic residue. \\
Otherwise, $p \equiv -1\pmod 4$, i.e. $p = 4k + 3$. Now suppose $-1$ is a square such that $-1 \equiv z^2 \pmod p$, then by Fermat's little theorem
\begin{align*}
1&\equiv z^{p - 1} \pmod p \\
&\equiv z^{4k+ 2} \pmod p \\
&\equiv (z^2)^{2k + 1} \pmod p \\
&\equiv (-1)^{2k + 1} \pmod p \\
&\equiv -1 \pmod p
\end{align*}
Contradiction.
\end{proof}

Q: Infinitude of primes $\equiv 1\pmod 4$.
A: \begin{proof}
  Suppose not, and $p_1, \dots p_k$ are all the primes $\equiv 1\pmod 4$. Let $N = (2p_1\cdots p_k)^2 + 1$. Then $N$ is not divisible by $2$ or $p_1,\cdots, p_k$ (as these all give remainder 1). This leaves only prime factors of $N$ of the form $ -1\pmod 4$. Let $q| N$ with $q$ prime so $q\equiv -1\pmod 4$. Then
\begin{align*}
N&\equiv 0 \pmod q \\
\implies (2p_1\cdots p_k)^2 + 1&\equiv 0\pmod q \\
\implies (2p_1\cdots p_k)^2 &\equiv -1\pmod q.
\end{align*}
So $-1$ is a quadratic residue mod $q$, which is a contradiction since $q \equiv -1\pmod 4$.
\end{proof}

Q: Computing square roots mod $p$
A: Let $p = 4k + 3$ be a prime. Then if $a$ is a quadratic residue, ie. $a \equiv z^2 \pmod p$ for some $z$, then $z = \pm a^{k + 1}$.
\begin{proof}
  By Fermat's little theorem
\begin{align*}
1 &\equiv  z^{p - 1} \pmod p \\
&\equiv z^{4k + 2}\pmod p \\
&\equiv a^{2k + 1} \pmod p\\
\implies a& \equiv a^{2k+2} \pmod p \\
\implies a&\equiv (\pm a^{k + 1})^2 \pmod p
\end{align*}
We know that quadratic residues have at most two square roots in mod $p$ so we are done. \\
This can be calculated efficiently through repeated squaring.
\end{proof}

Q: Number of square roots in modular arithmetic
A: First consider
\begin{align*}
a^2 \equiv b^2\pmod p &\iff p \mid a^2 - b^2 \\
&\iff p | (a - b)(a + b) \\
&\iff p \mid a - b\textrm{ or }p \mid a + b \\
&\iff a\equiv\pm b \pmod p
\end{align*}
so every quadratic residue has exactly 2 square roots. So for $N=p_1p_2\dots p_n$ where the $p_i$ are distinct
\begin{align*}
&z\equiv x^2 \pmod N \\
\implies &z\equiv x^2 \pmod {p_1}, z\equiv x^2 \pmod {p_2}, \dots  z\equiv x^2 \pmod {p_n} \\
\implies &z\equiv \pm k_1 \pmod {p_1}, z\equiv \pm k_2\pmod {p_2}, \dots  z\equiv \pm k_n \pmod {p_n}
\end{align*}
\textbf{Case 1} $x=0$. There is 1 solution mod $N$. \\
\textbf{Case 2} A non-zero square root exists, so there must be a quadratic residue for each prime. Then there are exactly $2^n$ square roots mod $N$ by CRT. \\
\textbf{Case 3} No square root exists.

Q: Tossing a coin over a phone
A: Alice chooses two 100 digit primes $p, q\equiv 3\pmod 4$ (found with near certainty by Fermat testing). Then she tells Bob the product $n = pq$. Bob picks a number $u$ (in all probability coprime to $n$), computes $a\equiv u^2\pmod n$ and tells Alice the value of $a$.
Alice can compute the square roots of $a$: $\pm u, \pm v$ and tells Bob one of these pairs.
Now if Alice picks $\pm u$, Bob says ``you win''. Otherwise, Bob says ``you lose'' and must produce $\pm v$.
Suppose Bob cheated, so knew $\pm v$ without Alice telling him. Then
\begin{align*}
&u^2 \equiv v^2\pmod n \\
\implies &n \mid (u - v)(u + v)
\end{align*}
But $n\mid (u \pm v)$ would mean $u\equiv \pm v \pmod n$, which is false as we define $\pm u,\pm v$ to be the two distinct square roots which we are guaranteed. So wlog
\begin{align*}
&p \mid (u - v), q \mid (u + v) \\
\implies &p = (n, u - v), q = (n, u + v)
\end{align*}
Bob can thus calculate $p,q$ efficiently by Euclid's algorithm. Conversely, he could calculate $\pm v$ the same way that Alice did if he knew $p,q$. Thus cheating is exactly as hard as prime factorisation \dots which is hard \dots as far as we know.

Q: RSA encryption
A: Alice thinks of two large primes $p, q$. Let $n = pq$ and pick $e$ coprime to $\phi(n) = (p - 1)(q - 1)$. Then work out $d$ with $de \equiv 1\pmod {\phi(n)}$ (ie. find $d,k$ such that $de - k\phi(n) = 1$) which is solvable by Euclid's Algorithm as we chose $e$ such that $(e,\phi(n))=1$. Alice then publishes $(n, e)$.
  For Bob to encrypt a message, Bob splits the message into numbers $0<M < n$. Bob sends $M^e \pmod n$ to Alice.
 Alice then decrypts by computing $(M^e)^d = M^{k\phi(n) + 1} \equiv M\pmod n$ by Fermat-Euler.

Q: Pigeonhole Principle
A: If we put $mn + 1$ pigeons into $n$ pigeonholes, then some pigeonhole has at least $m + 1$ pigeons.

Q: Indicator function/characteristic function
A: Let $X$ be a set. For each $A\subseteq X$, the \emph{indicator function} or \emph{characteristic function} of $A$ is the function $i_A: X\to \{0, 1\}$ with $i_A(x) = 1$ if $x\in A$, $0$ otherwise. It is sometimes written as $\chi_A$.

Q: Arithmetic of indicator functions
A: \begin{enumerate}
    \item $i_A = i_B \Leftrightarrow A = B$
    \item $i_A = i_A^2$
    \item $i_{A\cap B} = i_A i_B$
    \item $i_{\bar{A}} = 1 - i_A$
    \item $i_{A\cup B} = 1 - i_{\overline{A\cup B}} = 1 - i_{\bar A\cap \bar B} = 1 - i_{\bar{A}}i_{\bar{B}} = 1 - (1 - i_A)(1 - i_b) = i_A + i_B - i_{A\cap B}$.
    \item $i_{A\setminus B} = i_{A\cap \bar B} = i_Ai_{\bar B} = i_A(1 - i_B) = i_A - i_{A\cap B}$
  \end{enumerate}

Q: Prove that $A\cap(B\cup C) = (A\cap B)\cup (A\cap C)$
A: \begin{align*}
        i_{A\cap (B\cup C)} &= i_Ai_{B\cup C}\\
        &= i_A(i_B + i_C - i_Bi_C)\\
        &= i_Ai_B + i_Ai_C - i_Ai_Bi_C\\
        i_{(A\cap B)\cup (A\cap C)} &= i_{A\cap B} + i_{A\cap C} - i_{A\cap C}i_{A\cap B}\\
        &= i_Ai_B + i_Ai_C - i_Ai_Ci_Ai_B\\
        &= i_Ai_B + i_Ai_C - i_Ai_Bi_C
      \end{align*}
      Therefore $i_{A\cap (B\cup C)} = i_{(A\cap B)\cup (A\cap C)}$ and thus $A\cap(B\cup C) = (A\cap B)\cup (A\cap C)$. \qed

Q: Prove that the symmetric difference is associative
A: Observe that $i_{A\Delta B} \equiv i_A + i_B \pmod 2$. Thus $i_{(A\Delta B)\Delta C} = i_{A\Delta(B\Delta C)} \equiv i_A + i_B + i_C \pmod2$.

Q: Prove that $|A\cup B| = |A| + |B| - |A\cap B|$
A: \begin{proof}
  \begin{align*}
    |A\cup B| &= \sum_{x\in X} i_{A(x)\cup B(x)}\\
    &= \sum (i_A(x) + i_B(x) - i_{A\cap B}(x))\\
    &= \sum i_A(x) + \sum i_B(x) - \sum i_{A\cap B}(x)\\
    &= |A| + |B| - |A\cap B|
  \end{align*}
\end{proof}

Q: Inclusion-Exclusion Principle by indicator functions
A: Let $A_i$ be subsets of a finite set $X$, for $1 \leq i\leq n$. Then
\[
    |A_1\cup \dots \cup A_n| = \sum_i|A_i| - \sum_{i < j}|A_i\cap A_j| + \dots +(-1)^{n-1}|A_1\cap \dots \cap A_n|.
  \]
  Or equivalently
\[
    |\bar A_1\cap \dots \cap \bar A_n| = |X| - \sum_i |A_i| + \sum_{i < j}|A_i\cap A_j| - \dots + (-1)^n|A_1\cap \dots A_n|.
  \]
  The two forms are equivalent since $|A_1\cup\dots\cup A_n| = |X| - |\bar A_1\cap \dots \cap \bar A_n|$.
\begin{proof}
  \begin{align*}
    i_{\bar A_1\cap \bar A_2\cap \dots \cap \bar A_n} &= \prod_j i_{\bar A_j}\\
    &= \prod_j (1 - i_{A_j})\\
    &= 1 - \sum_i i_{A_i} + \sum _{i < j}i_{A_i}i_{A_j} - \dots + (-1)^ni_{A_1}i_{A_2}\dots i_{A_n}\\
    &= 1 - \sum_i i_{A_i} + \sum_{i < j}i_{A_i\cap A_j} - \dots + (-1)^ni_{A_1\cap A_2\cap A_3\cap \dots \cap A_n}
    \intertext{Thus}
    |\bar A_1\cap \dots \cap \bar A_n| &= \sum_{x\in X} i_{\bar A_1\cap \bar A_2\cap \dots \cap \bar A_n}(x)\\
    &= \sum_x 1 - \sum_i\sum_x i_{A_i}(x) + \sum_{i < j}\sum_x i_{A_i\cap A_j}(x) - \dots\\
    & + \sum_x (-1)^ni_{A_1\cap A_2\cap A_3\cap \dots \cap A_n}(x)\\
    &= |X| - \sum_i |A_i| + \sum_{i < j}|A_i\cap A_j|\\
    & - \sum_{i < j < k}|A_i\cap A_j\cap A_k| + \dots + (-1)^n|A_1\cap A_2\cap \dots A_n|
  \end{align*}
\end{proof}

Q: Relationship between binomial coefficients and powers of $2$
A: How many subsets of $\{1, 2, \cdots n\}$ are there? There are $2\times 2\times \cdots \times 2 = 2^n$. Since for each subset, every element is either in or out of the subset, and there are two choices for each element. (Equivalently, there are $2^n$ possible indicator functions, ie. functions $\{1, 2, 3, \cdots, n\} \to \{0, 1\}$.) \\
There are $\binom{n}{r}$ subsets of $\{1, 2, 3, \cdots, n\}$ of size $r$. So
\begin{align*}
2^n&=\sum_r \binom{n}{r} \\
&= \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n}
\end{align*}

Q: Binomial theorem
A: For $n\in \mathbb{N}$ with $a, b\in \mathbb{R}$, we have
  \[
    (a + b)^n = \binom{n}{0}a^n b^0 + \binom{n}{1}a^{n-1}b^1 + \dots + \binom{n}{r}a^{n - r}b^r + \dots + \binom{n}{n}a^0b^n
  \]
\begin{proof}
  We have $(a + b)^n = (a + b)(a + b)\cdots (a + b)$. When we expand the product, we get all terms attained by choosing $b$ from some brackets, $a$ from the rest. The term $a^{n - r}b^r$ comes from choosing $b$ from $r$ brackets $a$ from the rest, and there are $\binom{n}{r}$ ways to make such a choice.
\end{proof}

Q: Symmetry of binomial coefficients
A: $\displaystyle\binom{n}{r} = \binom{n}{n - r}$. This is because choosing $r$ things to keep is the same as choosing $n - r$ things to throw away.

Q: Pascal's Identity
A: \[ \binom{n }{r - 1} + \binom{n}{r} = \binom{n + 1}{r} \]
The RHS counts the number of ways to choose a team of $r$ players from $n + 1$ available players, one of whom is Pietersen. If Pietersen is chosen, there are $\binom{n}{r - 1}$ ways to choose the remaining players. Otherwise, there are $\binom{n}{r}$ ways. The total number of ways is thus $\binom{n}{r - 1} + \binom{n}{r}$.

Q: Pascal's Triangle
A: Pascal's Identity and $\binom{n}{0} =\binom{n}{n}= 1$ allows us to construct
\begin{center}
        \begin{tabular}{lllllllll}
          & & & & 1 & & & & \\
          & & & 1 & & 1 & & & \\
          & & 1 & & 2 & & 1 & & \\
          & 1 & & 3 & & 3 & & 1 & \\
          1 & & 4 & & 6 & & 4 & & 1 \\
        \end{tabular}
      \end{center}
      where each number is the sum of the two numbers above it, and the $r$th item of the $n$th row is $\binom{n}{r}$ (first row is row $0$). Note that using symmetry saves time.

Q: Choosing a set within a set
A: \[\binom{n }{k}\binom{k }{r} = \binom{n}{r}\binom{n - r}{k - r}\]
Given a set $X$, we are counting the number of pairs of sets $(Y, Z)$ with $Z\subseteq Y \subseteq X$, $|X|=n$, $|Y| = k$ and $|Z| = r$.
In the LHS, we first choose $Y$ then choose $Z\subseteq Y$. The RHS chooses $Z$ first and then choose the remaining $Y\setminus Z$ from $X\setminus Z$.

Q: Vandermonde's convolution
A: \[\displaystyle \binom{a}{r}\binom{b}{0} + \binom{a}{r - 1}\binom{b}{1} + \cdots + \binom{a }{r - k}\binom{b}{k} + \cdots \binom{a}{0}\binom{b}{r} = \binom{a + b}{r}\]
Suppose we have $a$ men and $b$ women, and we need to choose a committee of $r$ people. The right hand side is the total number of choices. The left hand side breaks the choices up according to the number of men vs women.

Q: Choosing from a partitioned set
A: Let $X_1,X_2\dots X_n$ be equivalence classes which partition $X$. The number of ways to choose $r$ elements from $X$ is $\binom{n + r - 1}{r}$.
\begin{proof}
Imagine the $X_i$ are $n$ stalls each selling a different type of fruit which cost one coin each. The choice of what to buy is equivalent to placing your $r$ coins in a line with a gap to separate the different stalls where you will spend them. There are $n$ stalls so $n$ piles so $n-1$ gaps needed. This gives $n+r-1$ coins/gaps to order so $\binom{n + r - 1}{r}$ possible choices.
\end{proof}

Q: Numerical value of binomial coefficients
A: \[ \binom{n}{r} = \frac{n!}{(n - r)!r!} \]
\begin{proof}
  There are $n(n - 1)(n - 2)\cdots (n - r + 1) = \frac{n!}{(n - r)!}$ ways to choose $r$ elements from $n$ elements in order. Each choice of subsets is chosen this way in $r!$ orders, so the number of subsets is $\frac{n!}{(n - r)!r!}$.
\end{proof}

Q: Falling binomial theorem
A: We might write $x^{\underline{r}}$ for the polynomial $x(x - 1)\cdots (x - r + 1)$. We call this ``$x$ to the $r$ falling''. We can write $\displaystyle \binom{n}{r} = \frac{n^{\underline{r}}}{r!}$. Multiplying Vandermonde by $r!$
\begin{align*}
(a + b)^{\underline{r}} &= r!\frac{a^{\underline{r}}}{r!}\frac{b^{\underline{0}}}{0!} + r!\frac{a^{\underline{r-1}}}{(r-1)!}\frac{b^{\underline{1}}}{1!}+\dots +  r!\frac{a^{\underline{0}}}{0!}\frac{b^{\underline{r}}}{r!} \\
 &= \binom{r}{0}a^{\underline{r}}b^{\underline{0}} + \binom{r}{1}a^{\underline{r - 1}}b^{\underline{1}} + \dots + \binom{r}{r}a^{\underline{0}}b^{\underline{r}}
\end{align*}

Q: Number of permutations with no fixed point
A: Let $X$ be the set of all permutations of $\{1,2,\dots n\}$ so $|X|=n!$. Let $A_i = \{x\in X: \text{$x$ sends $i$ to $i$}\}$. We want to know $|\bigcap_i \bar A_i|$. We know that $|A_i| = (n - 1)!$ since $x\in A_i$ sends $i$ to $i$ and permutes the other $n-1$ elements freely. Similarly, $|A_i\cap A_j| = (n - 2)!$, $|A_i\cap A_j \cap A_k| = (n - 3)!$ etc.
  By the inclusion-exclusion formula, we have
  \begin{align*}
    \left|\bigcap_i \bar A_i\right| &= |X| - \sum |A_i| + \sum | A_i\cap A_j| + \dots +(-1)^n \left|\bigcap_i A_i\right| \\
    &= n! - \binom{n}{1}(n - 1)! + \binom{n}{2}(n - 2)! - \dots +(-1)^n\binom{n}{n}0!\\
    &= n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!}\right)\\
    &\approx n! e^{-1}
  \end{align*}
for large $n$.

Q: Weak Principle of Induction
A: Let $\varphi(n)$ be a statement about the natural number $n$. Suppose that
  \begin{enumerate}
    \item $\varphi(1)$
    \item $\forall n\in\mathbb{N}: \varphi(n)\Rightarrow \varphi(n + 1)$
  \end{enumerate}
  Then $\varphi(n)$ is true for all $n\in\mathbb{N}$.

Q: Minimal moves to solve the Tower of Hanoi puzzle
A: Let $\varphi(n)$ be ``$n$ rings needs exactly $2^n - 1$ moves''.
  First consider $\varphi(1)$. We simply have to move the ring across which takes exactly one move.
  Suppose we have $n + 1$ rings. We can move the top $n$ rings to peg C, then move the bottom ring to peg B, then move the $n$ rings from $C$ back to $B$. Assuming $\varphi(n)$ is true, this needs at most $2\times (2^n - 1) + 1 = 2^{n + 1} -1 $ moves.
  Can we do it in fewer moves? To succeed, we must free the bottom ring, so we must shift the top $n$ rings to another peg. This needs $\geq 2^n - 1$ moves by $\varphi(n)$. Then we need to shift the bottom ring. Then we need to shift the $n$ smaller rings to the big one. This needs $\geq 2^n - 1$ moves by $\varphi(n)$. So this needs $\geq 2^{n + 1} - 1$ moves altogether.
  So we showed that $\varphi(n)\Rightarrow \varphi(n + 1)$. By the WPI, $\varphi(n)$ is true for all $n$.

Q: Inclusion-Exclusion Principle by WPI
A: Let $A_i$ be finite sets, for $1 \leq i\leq n$. Then
\[
    |A_1\cup \dots \cup A_n| = \sum_i|A_i| - \sum_{i < j}|A_i\cap A_j| + \dots +(-1)^{n+1}|A_1\cap \dots \cap A_n|.
  \]
\begin{proof}
  Let $\varphi(n)$ be the statement ``for any sets $A_1\dots A_n$, we have $|A_1\cup \dots \cup A_n| = \sum_i|A_i| - \sum_{i < j} |A_i\cap A_j| + \dots +(-1)^{n+1} |A_1\cap A_2\cap \dots \cap A_n|$''.
  $\varphi(1)$ is trivially true. $\varphi(2)$ is also true (considering the Venn diagram). Now given $A_1 \dots A_{n + 1}$ for $n\geq 2$, we show $\varphi(n)\Rightarrow \varphi(n + 1)$
\begin{align*}
    |A_1\cup A_2\cup \dots \cup A_{n + 1}| &= |A_1\cup \dots \cup A_n| + |A_{n + 1}| - |(A_1\cup\dots\cup A_n)\cap A_{n + 1}|\\
    &=  |A_{n + 1}|+|A_1\cup \dots \cup A_n| - |(A_1\cap A_{n+1})\cup \dots \cup (A_n\cap A_{n+1})|\\
    &= |A_{n + 1}| +\sum_{i\leq n}|A_i|- \sum_{i < j\leq n}|A_i\cap A_j| + \dots +  \\
    &-\sum_{i \leq n}|A_i\cap A_{n+1}| + \sum_{i < j\leq n}|A_i\cap A_j\cap A_{n+1}| - \dots \\
    &= \sum_{i \leq n + 1}|A_i| - \sum_{i< j \leq n + 1}|A_i \cap A_j| + \dots
  \end{align*}
 By WPI, $\varphi(n)$ is true for all $n$.
\end{proof}

Q: Strong principle of induction
A: Let $\varphi(n)$ be a statement about $n\in \mathbb{N}$. Suppose that
  \begin{enumerate}
    \item $\varphi(1)$ is true
    \item $\forall n\in \mathbb{N}$, if $\varphi(k)$ is true $\forall k < n$ then $\varphi(n)$ is true.
  \end{enumerate}
  Then $\varphi(n)$ is true for all $n\in \mathbb{N}$.

Q: SPI$=$WPI
A: \begin{proof}
  Clearly SPI$\implies$WPI since if $\varphi(n)\Rightarrow \varphi(n + 1)$, then $(\varphi(1)\wedge \varphi(2)\wedge \dots \wedge \varphi(n))\Rightarrow \varphi(n + 1)$.
  Now show WPI$\implies$ SPI. Suppose that $\varphi(1)$ is true and $\left[ \forall k\leq n:\varphi(k) \right]\Rightarrow \varphi(n+1)$. Let $\psi(n) = $ ``$\forall k\leq n:\varphi(k)$''. Then $\psi(1)$ is true and $\psi(n)\implies \psi(n+1)$. By WPI, $\psi(n)$ is true for all $n$. So $\varphi(n)$ is true for all $n$.
\end{proof}

Q: Well-ordering principle
A: Every non-empty subset of $\mathbb{N}$ has a minimal element. In practice, this is used by supposing a minimal counter-example for the purpose of deriving a contradiction.

Q: WOP$=$SPI
A: \begin{proof}
  WOP$\implies$SPI: let $\varphi(n)$ be a proposition such that $[\forall k<n: \varphi(k)]\implies \varphi(n)$. Now suppose $\varphi(n)$ is not true for all $n$. Then the set $S = \{n\in \mathbb{N} : \neg \varphi(n)\}$ is a non-empty subset of the naturals so WOP$\implies S$ has a minimal element $m$. Since $m$ is the minimal counterexample to $\varphi$, $\varphi(k)$ is true for all $k < m$. However, this implies that $\varphi(m)$ is true, which is a contradiction. Therefore $\varphi(n)$ must be true for all $n$.
  To show SPI$\implies$WOP, let $S\subseteq \mathbb{N}$ have no minimal element. We need to show that $S$ is empty. Let $\varphi(n)$ be the statement $n\not\in S$.
  Certainly $1\not\in S$, or else it will be the minimal element. So $\varphi(1)$ is true. Suppose we know that $\varphi(k)$ is true for all $k < n$, ie. $k\not\in S$ for all $k < n$. Now $n\not\in S$, or else $n$ will be the minimal element. So $\varphi(n)$ is true. By SPI, $\varphi(n)$ is true for all $n$, i.e. $S$ is empty.
\end{proof}

Q: A diagram can be drawn with one stroke of a pen iff. the diagram is connected and every junction has even order
A: If the graph was not connected, you couldn't reach the other part of the diagram. If a junction had odd order, you would get stuck. \\
Conversely, we show that all even, connected diagrams can be drawn with one stroke. Suppose otherwise. Then there is a counterexample with a minimal number of lines by WOP. Consider wandering around this diagram (starting at a junction) until you get stuck. Then, by evenness, there is always a way forward so you must be back at the start (too soon). \\
The lines that remain form a diagram which, by minimality, can be drawn. \\
Therefore, you can draw the whole diagram by wandering around your original path, then each time you meet a missed piece, take time to go round it before carrying on. \\
So the minimal counterexample is not a counterexample.

Q: Peano Arithmetic
A: We call a set $\mathbb{N}$ ``natural numbers'' if it has a special element $0$ and a map $S: \mathbb{N} \to \mathbb{N}$ that maps $n$ to its ``successor'' (intuitively, it is $+1$) such that:
  \begin{enumerate}
    \item $(\forall n)\,S(n) \not= 0$
    \item $(\forall n, m)\,n \not= m\Rightarrow S(n)\not= S(m)$
    \item $(\forall A\subseteq \mathbb{N})\,[(1\in A)\wedge (\forall n\in\mathbb{N}: n\in A\Rightarrow S(n)\in A)]\Rightarrow (A = \mathbb{N})$ (Equivalent to weak induction)
\end{enumerate}
We write $1 = S(0), 2 = S(1)$, $3 = S(2)$ etc. We can define addition and multiplication recursively by
\begin{align*}
a+0=a \\
a+S(b)=S(a+b) \\
a\times 0=0 \\
a\times S(b)=ab+a
\end{align*}

Q: Totally ordered field
A: $F$ is a field if
\begin{enumerate}
    \item $F$ is an additive abelian group with identity $0$.
    \item $F\setminus \{0\}$ is a multiplicative abelian group with identity $1$.
    \item Multiplication is distributive over addition: $a(b + c) = ab + ac$.
\end{enumerate}
$F$ is also totally ordered if
\begin{enumerate}
    \item There is an order relation $\leq$ on $F$ which is total i.e. has trichotomy
    \item The order respects the field i.e. \[ \forall p, q, r\in F, p \leq q\Rightarrow p + r \leq q+ r \]
\[\forall p, q, r\in F, p \leq q, 0 \leq r\Rightarrow pr \leq qr\]
\end{enumerate}

Q: Show that $(-1)^2=1$ in a field
A: \begin{align*}
0&=-1[1+(-1)] \\
&=-1+(-1)^2  \\
\implies (-1)^2&=1
\end{align*}

Q: Show that $0<1$ in an ordered field
A: Suppose otherwise, so by trichotomy
\begin{align*}
1&<0  \\
\implies 1+(-1)&<0+(-1) \\
\implies 0&<-1 \\
 \implies 0&<(-1)^2 \\
\implies 0&<1
\end{align*}
Contradiction. \qed

Q: Show $\mathbb{Q}$ is densely ordered
A: \[
    (\forall p, q\in \mathbb{Q})\,p < q\Rightarrow ((\exists r \in \mathbb{Q})\, p < r < q),
  \]
\begin{proof}
eg. $r = \frac{p + q}{2}$.
\end{proof}

Q: Show there is no rational $q\in \mathbb{Q}$ with $q^2 = 2$.
A: \begin{proof}
  Suppose not, and $(\frac{a}{b})^2 = 2$, where $b$ is chosen as small a positive integer as possible, in particular $(a,b)=1$.
  \begin{enumerate}
    \item $a^2 = 2b^2$. So $a$ is even. Let $a = 2a'$. Then $b^2 = 2a'^2$. Then $b$ is even as well, and $b = 2b'$. But then $(a,b)\geq 2$. Contradiction.
    \item We know that $b$ is a product of primes as clearly $b \not= 1$. Let $p \mid b$. Then $a^2 = 2b^2$. So $p \mid a^2$. So $p \mid a$. So $(a,b)\geq p\geq 2$. Contradiction.
    \item (Dirichlet) For any $u,v$
\begin{align*}
a^2 &= 2b^2 \\
\implies a^2v &= 2b^2v \\
\implies uab + a^2v &= uab + 2b^2v \\
\implies a(bu + av) &= b(ua + 2bv) \\
\implies\frac{a}{b} &= \frac{au + 2bv}{bu + av} \\
\implies \frac{a}{b} = \frac{2b - a}{a - b}
\end{align*} Since $a < 2b, a - b < b$. So we have found a rational with smaller denominator. Contradiction.
    \item Same as 3, but pick $u, v$ so $bu + av = 1$ since $a$ and $b$ are coprime.. So $\frac{a}{b}$ is an integer. Contradiction.
  \end{enumerate}
\end{proof}

Q: Least upper bound/supremum and greatest lower bound/infimum
A: $s\in X$ is a \emph{least upper bound} (or \emph{supremum}) for the set $S\subseteq X$, denoted by $s = \sup X$, if
  \begin{enumerate}
    \item $s$ is an upper bound for $S$, ie. $(\forall x\in S) x \leq s$.
    \item if $t$ is any upper bound for $S$, then $s \leq t$.
  \end{enumerate}
  Similarly, $s\in X$ is a \emph{greatest lower bound} (or \emph{infimum}), written $s=\inf X$ if
\begin{enumerate}
    \item $s$ is a lower bound for $S$, ie. $(\forall x\in S) x \geq s$.
    \item if $t$ is any lower bound for $S$, then $s \geq t$.
  \end{enumerate}
It immediately follows that $\sup X$ and $\inf X$ are unique.

Q: Real numbers
A: A totally ordered field which satisfies the LUB axiom: \\
Every non-empty subset of the real numbers that has an upper bound has a LUB.\\
Note that this implies that every non-empty subset $S\subseteq\mathbb{R}$ which is bounded below has an infimum as $\sup T=\inf S$ where $T=\{ -x \ | \ x\in S\}$.

Q: Axiom of Archimedes
A: Given $r\in \mathbb{R}$, there exists $n\in \mathbb{N}$ with $n > r$.
\begin{proof}
  Assume the contrary. Then $r$ is an upper bound for $\mathbb{N}$. $\mathbb{N}$ is not empty since $1\in \mathbb{N}$. By the least upper bound axiom, $s = \sup \mathbb{N}$ exists. Since $s$ is the least upper bound for $\mathbb{N}$, $s - 1$ is not an upper bound for $\mathbb{N}$. So $\exists m\in \mathbb{N}$ with $m > s - 1$. Then $m + 1\in \mathbb{N}$ but $m + 1 > s$, which contradicts the statement that $s$ is an upper bound.
\end{proof}

Q: $\inf\{\frac{1}{n}: n\in \mathbb{N}\}$
A: $\inf\{\frac{1}{n}: n\in \mathbb{N}\} = 0$
\begin{proof}
Certainly $0$ is a lower bound for $S$. Gven $t > 0$, there exists $n \in \mathbb{N}$ such that $n \geq 1/t$ by the (Axiom of Archimedes). So $t \geq 1/n\in S$. So $t$ is not a lower bound for $S$.
\end{proof}

Q: Prove that $\mathbb{Q}$ is dense in $\mathbb{R}$.
A: Given $r, s\in \mathbb{R}$, with $r < s$, $\exists q\in \mathbb{Q}$ with $r < q < s$.
\begin{proof}
  wlog assume first $r \geq 0$ (just multiply everything by $-1$ if $r < 0$). Since $s - r > 0$, $\exists n\in \mathbb{N}$, $\frac{1}{n} < s - r$. By the Axiom of Archimedes, $\exists N\in \mathbb{N}$ such that $N > sn$.
  Let $T = \{k\in \mathbb{N} \ | \ \frac{k}{n}\geq s\}$. $T$ is not empty, since $N\in T$. Then by WOP, $T$ has a minimum element $m$. [Note $m\not= 1$ since $\frac{1}{n} < s - r \leq s$.]  Since $m - 1\not\in T$, $\frac{m - 1}{n} < s$. So try $q=\frac{m - 1}{n}\in\mathbb{Q}$.
If $q < r$, then
\begin{align*}
&\frac{m - 1}{n}<r \\
\implies &\frac{m}{n} < r + \frac{1}{n} < r+ (s-r) \\
\implies &\frac{m}{n} <s \\
\implies &m\not\in T \\
 &\textrm{contradiction!}
\end{align*}
So $r < q < s$.
\end{proof}

Q: Show that $\sqrt{2}\in\mathbb{R}$
A: There exists $x\in\mathbb{R}$ with $x^2 = 2$.
\begin{proof}
  Let $S = \{r\in \mathbb{R}: r^2 \leq 2\}$. Then $0\in S$ so $S\not= \emptyset$. Also $\forall r\in S: r \leq 3$. So $S$ is bounded above. So $x = \sup S\in\mathbb{R}$  and $0\leq x \leq 3$.
\textbf{Case 1} $x^2 < 2$. Let $0 < \delta< 1$. Then
\begin{align*}
(x + \delta)^2 &= x^2 + 2x\delta + \delta^2 \\
&< x^2 + 6\delta + \delta \\
&\leq x^2 + 7\delta
\end{align*}
Picking $\delta < \frac{2 - x^2}{7}$ then $(x + \delta)^2 < 2$. So $x + \delta \in S$. This contradicts the fact that $x$ is an upper bound of $S$.
\textbf{Case 2} $x^2 > 2$. Let $0 < \delta < 1$. Then
\begin{align*}
(x - \delta)^2 &= x^2 - 2x\delta + \delta^2 \\
&\geq x^2 - 6\delta
\end{align*}
Pick $\delta < \frac{x^2 - 2}{6}$. Then $(x - \delta)^2 > 2$, so $x -\delta$ is an upper bound for $S$ smaller than $x=\sup S$. Contradiction. \\
  So by trichotomy, $x^2 = 2$.
\end{proof}

Q: Sequence
A: A \emph{sequence} is a function $\mathbb{N}\to \mathbb{R}$. If $a$ is a sequence, instead of $a(1), a(2), \dots$, we usually write $a_1, a_2, \dots$. To emphasize it is a sequence, we write the sequence as $(a_n)$.

Q: Limit of sequence
A: $a_n \to l$ as $n\to \infty$ if
  \[
    \forall \varepsilon > 0: \exists N \in \mathbb{N}: \forall n \geq N: |a_n - l| < \varepsilon.
  \]
\begin{proof}
 Given $\varepsilon > 0$, we ensure $|a_n - l| < \varepsilon$ by choosing a large $N$ i.e. a clever $f$ such that $n\geq N\geq f(\varepsilon)$.
\end{proof}
$a_n \not\to l$ as $n\to \infty$ if
 \[\exists \varepsilon > 0: \forall N\in\mathbb{N}:\exists n>N : |a_n - l| \geq \varepsilon.
  \]
\begin{proof}
 Given $N\in\mathbb{N}$, we ensure $|a_n - l| \geq \varepsilon$ by choosing a small $\varepsilon$ i.e. clever $f,g$ such that $0\leq\varepsilon\leq f(\varepsilon)$ and $N<n\leq g(N)$.
\end{proof}
To prove convergence, you find $l$, then use the first type of proof. To prove divergence, you must use the second type of proof for a general $l$ (probably need to consider cases though).

Q: Prove that every bounded monotonic sequence converges.
A: \begin{proof}
  wlog assume $(a_n)$ is increasing. The set $\{a_n: n\geq 1\}$ is bounded and non-empty. So it has a supremum $l$ (least upper bound axiom). Now we show $(a_n)\to l$. \\
  Given $\varepsilon >0$, $l - \varepsilon$ is not an upper bound of $a_n$. So $\exists N$ such that $a_N > l - \varepsilon$. As $(a_n)$ is increasing,  for all $n \geq N$
\begin{align*}
l \geq a_n \geq a_N > l - \varepsilon \\
\implies |a_n - l| < \varepsilon
\end{align*}
\end{proof}

Q: Subsequence
A: A \emph{subsequence} of $(a_n)$ is $(a_{g(n)})$ where $g: \mathbb{N}\to\mathbb{N}$ is strictly increasing.

Q: Every sequence has a monotonic subsequence.
A: \begin{proof}
  Call a point $a_k$ a ``peak'' if $\forall m \geq k: a_m \leq a_k$. If there are infinitely many peaks, then they form a decreasing subsequence. If there are only finitely many peaks, $\exists N$ such that no $a_n$ with $n > N$ is a peak. Pick $a_{N_1}$ with $N_1 > N$. Then pick $a_{N_2}$ with $N_2 > N_1$ and $a_{N_2} > a_{N_1}$. This is possible because $a_{N_1}$ is not a peak. The pick $a_{N_3}$ with $N_3 > N_2$ and $a_{N_3}> a_{N_2}$, \emph{ad infinitum}. Then we have a monotonic subsequence.
\end{proof}

Q: Uniqueness of limits
A: If $a_n\to a$ and $a_n\to b$, then $a = b$.
\begin{proof}
Suppose otherwise, so wlog $a < b$. So for all $\varepsilon>0$
\begin{align*}
&\exists N_1: \forall n\geq N_1: |a_n - a| < \varepsilon \\
&\exists N_2: \forall n\geq N_2: |a_n - b| < \varepsilon.
\end{align*}
Let $N = \max\{N_1, N_2\}$. Then for $n\geq \max\{N_1, N_2\}$
\begin{align*}
|a - b| &=|(a-a_n)+(a_n-b)| \\
&\leq |a - a_n| + |a_n - b| \\
&< 2\varepsilon
\end{align*}
Picking $\varepsilon = \frac{b - a}{2}$, then $|a-b|=b-a<b-a$. Contradiction.
\end{proof}

Q: What happens to the limit of a sequence if you change a finite number of terms?
A: If $a_n \to a$ and $b_n = a_n$ for all but finitely many $n$, then $b_n \to a$.
\begin{proof}
Given $\varepsilon > 0$, there $\exists N_1$ such that \[
\forall n\geq N_1:|a_n - a| < \varepsilon.\]
Since $b_n = a_n$ for all but finitely many $n$, there exists $N_2$ such that \[
\forall n\geq N_2: a_n = b_n.\]
Let $N = \max\{N_1, N_2\}$. Then $\forall n\geq N$: \[
|b_n - a| = |a_n - a| < \varepsilon. \]
So $b_n\to a$.
\end{proof}

Q: Limit of a constant sequence
A: If $a_n = a$ for all $n$, then $a_n \to a$.
\begin{proof}
$\forall \varepsilon>0$ \[
|a_n - a| = 0 < \varepsilon \]
for all $n \geq N=1$.
\end{proof}

Q: Multiplying sequences
A: If $a_n\to a$ and $b_n \to b$, then $a_nb_n\to ab$
\begin{proof}
 \begin{align*}
        |a_nb_n - ab| &= |b_n(a_n - a) + a(b_n - b)|\\
        &\leq |b_n| |a_n - a| + |a||b_n - b|\\
        &< (|b| + 1) |a_n - a| + |a||b_n - b|\\
        &< \frac{\varepsilon}{2} + \frac{\varepsilon}{2}\\
        &= \varepsilon
      \end{align*}
for $n\geq N$ where $N = \max\{N_1, N_2, N_3\}$ and
      \begin{align*}
        &\forall n\geq N_1: |a_n - a| < \frac{\varepsilon}{2(|b| + 1)}\\
        &\forall n\geq N_2: |b_n - b| < \frac{\varepsilon}{2|a|}\\
        &\forall n\geq N_3: |b_n - b| < 1 \Rightarrow |b_n| < |b| +1
      \end{align*}
\end{proof}

Q: Summing sequences
A: If $a_n\to a$ and $b_n\to b$, then $a_n + b_n \to a+ b$
\begin{proof}
\begin{align*}
|(a_n + b_n) - (a + b)| &=|(a_n-a)+(b_n-b)| \\
&\leq |a_n - a| + |b_n - b| \\
&<\frac{\varepsilon}{2}+\frac{\varepsilon}{2} \\
&=\varepsilon
\end{align*}
for $n \geq N$ where $N = \max\{N_1, N_2\}$ and
\begin{align*}
&\forall n\geq N_1: |a_n - a| < \varepsilon/2 \\
&\forall n\geq N_2: |b_n - b| < \varepsilon/2
\end{align*}
\end{proof}

Q: Dividing sequences
A: If $a_n\to a\not= 0$, and $\forall n: a_n \not= 0$. Then $1/a_n \to 1/a$.
\begin{proof}
   \begin{align*}
        \left|\frac{1}{a_n} - \frac{1}{a}\right| &= \frac{|a_n - a|}{|a_n||a|}\\
        &< \frac{2}{|a|^2}|a_n - a|\\
        &< \varepsilon
      \end{align*}
for $n \geq N$ where $N = \max\{N_1, N_2\}$,
\[ \forall n>N_1: |a_n - a|  < \frac{|a|^2}{2}\varepsilon \]
and
\begin{align*}
        \forall n>N_2:  |a_n - a|  &< \frac{|a|}{2} \\
\implies |a|-|a_n|&<\frac{|a|}{2} \\
 \implies |a_n|&>\frac{|a|}{2} \\
\implies \frac{1}{|a_n|}&<\frac{2}{|a|}.
      \end{align*}
\end{proof}

Q: Sandwich theorem
A: If $a_n \to a$ and $b_n \to a$, and $\forall n: a_n\leq c_n\leq b_n$, then $c_n \to a$.
\begin{proof}
\begin{align*}
a_n\to a, b_n\to a \implies a_n-b_n&\to 0 \\
\therefore (\forall\varepsilon >0: \exists N:  \forall n>N) |b_n - a_n| &< \varepsilon \\
\therefore (\forall\varepsilon >0:\forall n>N) |c_n-a_n|\leq |b_n-a_n|&< \varepsilon\\
\therefore c_n-a_n&\to 0 \\
\therefore c_n=(c_n-a_n)+a_n&\to a
\end{align*}
\end{proof}

Q: Series
A: Let $(a_n)$ be a sequence. Then $s_m = \sum_{n = 1}^m a_n$ is the \emph{$m$th partial sum} of $(a_n)$. We write
  \[
    \sum_{n = 1}^\infty a_n = \lim_{m\to \infty} s_m
  \]
  If the limit exists.

Q: Geometric series
A: Suppose $a_n = r^n$, where $|r| < 1$. Then $s_m = r\cdot \frac{1 - r^m}{1 - r} \to \frac{r}{1- r}$ since $r^n \to 0$. So
  \[
    \sum_{n = 1}^\infty r^n = \frac{r}{1 - r}.
  \]

Q: Harmonic series
A: Let $a_n = \frac{1}{n}$. Consider
  \begin{align*}
    S_{2^k} &= 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + \cdots + \frac{1}{2^k}\\
    & \geq 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{16} + \cdots + \frac{1}{2^k}\\
    &\geq 1 + \frac{k}{2}.
  \end{align*}
  So $\displaystyle \sum_{n = 1}^\infty\frac{1}{n}$ diverges.

Q: Decimal expansion
A: Let $(d_n)$ be a sequence with $d_n\in \{0, 1, \cdots 9\}$. Then $\displaystyle \sum_{n = 1}^\infty \frac{d}{10^n}$ converges to a limit $r$ with $0 \leq r \leq 1$ since the partial sums $s_m$ are increasing and bounded by $\sum \frac{9}{10^n}\to 1$ (geometric series). We say $r = 0.d_1d_2d_3\cdots$, the \emph{decimal expansion} of $r$.

Q: Show that every number has a unique decimal expansion
A: \textbf{Existence} Pick $d_1$ maximal such that $\frac{d_1}{10} \leq x < 1$. Then $0 \leq x - \frac{d_1}{10} < \frac{1}{10}$ since $d_1$ is maximal. Then pick $d_2$ maximal such that $\frac{d_2}{100} \leq x - \frac{d_1}{10}$. By maximality, $0 \leq x - \frac{d_1}{10} - \frac{d_2}{100} < \frac{1}{100}$. Repeat inductively, pick maximal
\[
  \frac{d_n}{10^n} \leq x- \sum_{j = 1}^{n - 1} \frac{d_j}{10^j}
\]
so
\[
  0 \leq x - \sum_{j = 1}^n \frac{d_j}{10^j} < \frac{1}{10^n}.
\]
Since both LHS and RHS $\to 0$, by sandwich, $x - \sum_{j = 1}^\infty \frac{d_j}{10^j} = 0$, ie. $x = 0.d_1d_2\cdots$.
\textbf{Uniqueness} Now suppose that the $a_j$ and $b_j$ are equal until $k$, ie. $a_j = b_j$ for $j < k$. wlog assume $a_k < b_k$. Then
\[
  \sum_{j = k + 1}^\infty \frac{a_j}{10^j} \leq \sum_{j = k+1}^\infty \frac{9}{10^j} = \frac{9}{10^{k+1}}\cdot \frac{1}{1 - 1/10} = \frac{1}{10^k}.
\]
So we must have $b_k = a_k + 1$, $a_j = 9$ for $j > k$ and $b_j = 0$ for $j > k$.

Q: Periodic number
A: A decimal is \emph{periodic} if after a finite number $\ell$ of digits, it repeats in blocks of $k$ for some $k$, i.e. $d_{n + k} = d_n$ for $n > \ell$.

Q: A number is periodic iff it is rational.
A: \textsc{Periodic $\implies$ rational \\} Say $x = a_0.a_1\ldots a_nb_1b_2\ldots b_\ell\ldots$ where $b_i=b_{i+\ell}$. Then
  \begin{align*}
    x &= a_0.a_1\ldots a_n+10^{-n}\cdot 0.b_1b_2\ldots b_\ell\ldots \\
    \implies 10^\ell x &=10^\ell a_0.a_1\ldots a_n+10^{-n}\cdot b_1b_2\ldots b_\ell+ 10^{-n}\cdot 0.b_1b_2\ldots b_\ell\ldots \\
\implies x(10^\ell -1) &= (10^\ell -1) a_0.a_1\ldots a_n+ 10^{-n}\cdot b_1b_2\ldots b_\ell \\
\implies x&= \frac{(10^\ell -1) a_0a_1\ldots a_n+ 10^{-\ell}b_1b_2\ldots b_\ell}{10^n(10^\ell -1)} \\
&\in\mathbb{Q}
  \end{align*}
\textsc{Rational $\implies$ periodic\\}
Let $x\in \mathbb{Q}$. Suppose $x = \frac{p}{2^c5^dq}$ with $(q, 10) = 1$. Then $10^{\max(c, d)}x = \frac{a}{q} = n + \frac{b}{q}$ for some $a, b, n\in \mathbb{Z}$ and $0\leq b < q$. So it suffices to show that $\frac{b}{q}$ is periodic with $0\leq b < q$ and $(q, 10) = 1$.
Since $(q, 10) = 1$, by Fermat-Euler, $10^{\phi(q)}\equiv 1\pmod q$, ie. $10^{\phi(q)} - 1 = kq$. Then
  \[
    \frac{b}{q} = \frac{kb}{kq} = \frac{kb}{999\dots 9} = kb\left(\frac{1}{10^{\phi(q)}} + \frac{1}{10^{2\phi(q)}} + \dots \right).
  \]
  Since $kb < kq < 10^{\phi(q)}$, we can write $kb = d_1d_2\dots d_{\phi(q)}$. So $\frac{b}{q} = 0.d_1d_2\dots d_{\phi(q)}d_1d_2\dots$ is periodic. \qed

Q: Prove that $e$ is irrational.
A: \begin{proof}
  Suppose $e= 1+\frac{1}{1!}+\frac{1}{2!}\ldots= \frac{p}{q}$ where $p,q\in\mathbb{Z}$. Clearly $q\geq 2$ because $2<e<3$. Then $q!e \in \mathbb{Z}$ where
  \[
    q!e = \underbrace{q! + q! + \frac{q!}{2!} + \frac{q!}{3!} + \dots + \frac{q!}{q!}}_{n} + \underbrace{\frac{q!}{(q + 1)!} + \frac{q!}{(q + 2)!} + \cdots}_{x},
  \]
  and $n \in \mathbb{N}$. We also have
  \[
    x = \frac{1}{q + 1} + \frac{1}{(q + 1)(q + 2)} + \cdots.
  \]
  where $x$ is a difference of integers, so $x\in\mathbb{Z}$. We can bound $x$ by
  \[
    0 < x < \frac{1}{q+1} +\frac{1}{(q + 1)^2} + \frac{1}{(q + 1)^3} = \frac{1}{q + 1}\cdot \frac{1}{1 - 1/(q + 1)} = \frac{1}{q} < 1.
  \]
  This contradicts the fact that $x\in\mathbb{Z}$.
\end{proof}

Q: algebraic number
A: An \emph{algebraic number} is a root of a polynomial with integer coefficients (or rational coefficients). A number is \emph{transcendental} if it is not algebraic.

Q: Show that all rational numbers are algebraic.
A: \begin{proof}
  Let $x = \frac{p}{q}$, then $x$ is a root of $qx - p = 0$.
\end{proof}

Q: Partial order
A: A \emph{partial order} on a set is a relation $\sim$ which is
reflexive: $ x\sim x$, \\
antisymmetric: ($(a\sim b) \wedge (b\sim a) \Leftrightarrow a = b$), \\
transitive: $a \sim b, b\sim c \implies a\sim c$. \\
e.g. `divides'

Q: Well-founded order
A: Every non-empty subset has a minimal element, ie. if $S\not= \emptyset$, then $\exists m\in S$ such that $x < m \Rightarrow x\not\in S$.
e.g. $\mathbb{N}$

Q: Show that $\mathbb{N}\times \mathbb{N}$ is well-ordered
A: If $S\subseteq\mathbb{N}\times \mathbb{N}$ is non-empty, let $S_x$ be the set of $\{x\in\mathbb{N}: (\exists y)\,(x, y)\in S\}$, ie. the set of all $x$-coordinates of $S$. By the well-ordering principle, $S_x$ has a minimal element $m$. Then let $S_y = \{y\in \mathbb{N}: (m, y)\in S\}$. Then $S_y$ has a minimal element $n$. Then $(m, n)$ is the minimal element of $S$. \qed

Q: Lexicographic order
A: \begin{align*}
(u,v)\leq (x,y) \iff
\begin{cases}
u<x \\
\textrm{or }u=x \textrm{ and }v\leq y
\end{cases}
\end{align*}

Q: Construction of rationals
A: Define $\mathbb{Q}$ to be the equivalence classes of $\mathbb{Z} \times \mathbb{N}$ with $(a, b) \sim (c, d)$ iff $ad = bc$.
  We write $\frac{a}{b}$ for $(a, b)$. We can define $(a, b) + (c, d) = (ad + bc, bd)$ and $(a, b)\times (c, d) = (ac, bd)$.

Q: Same size sets: injective $\implies $ bijective
A: Let $[n] = \{1, 2, 3, \dots, n\}$.  If $f:[n] \to [n]$ is injective, then $f$ is bijective.
\begin{proof}
Let $\varphi(n)$ be `if $f:[n] \to [n]$ is injective, then $f$ is bijective'. Clearly $\varphi(1)$ is true.
Suppose $\varphi(n-1)$ for $n\geq 2$. Let $j = f(n)$. Define $g: [n]\to [n]$ by
  \[
    g(j) = n,\quad g(n) = j, \quad g(i) = i \text{ otherwise}.
  \]
  Then $g$ is a bijection. So the map $g\circ f$ is injective. It fixes $n$, ie. $g\circ f(n) = n$. So the map $h:[n - 1]\to [n - 1]$ by $h(i) = g\circ f(i)$ is well-defined and injective. So $h$ is bijective by $\varphi(n-1)$. So $g\circ f$ is bijective. So $f$ is bijective. Therefore $\varphi(n-1)\implies \varphi(n)$.
\end{proof}

Q: Uniqueness of bijections from a finite set
A: If $A$ is a set and $f: A\to [n]$ and $g: A\to [m]$ are both bijections, then $m = n$.
\begin{proof}
wlog let $m\geq n$. Define $h:[n]\to[m]$ by $i\mapsto i$. So $h$ is an injection.
\begin{align*}
\therefore &[m]\overset{g^{-1}}{\to}A\overset{f}{\to}[n]\overset{h}{\to}[m] \textrm{ is injective so bijective}
\end{align*}
So $m=n$.
\end{proof}

Q: Show that subsets of the naturals are countable
A: Let $S\subseteq \mathbb{N}$. Then either $S$ is finite or there is a bijection $g:\mathbb{N} \to S$.
\begin{proof}
  If $S\not= \emptyset$, by the well-ordering principle, there is a least element $s_1\in S$. If $S\setminus \{s_1\} \not= \emptyset$, it has a least element $s_2$. If $S\setminus \{s_1, s_2\}$ is not empty, there is a least element $s_3$. If at some point the process stops, then $S = \{s_1, s_2,\cdots, s_n\}$, which is finite. Otherwise, if it goes on forever, the map $g:\mathbb{N} \to S$ given by $g(i) = s_i$ is well-defined and is an injection. It is also a surjection because if $k\in S$, then $k$ is a natural number and there are at most $k$ elements of $S$ less than $k$. So $k$ will be mapped to for some $i\leq k$.
\end{proof}

Q: Finite set
A: The set $A$ is \emph{finite} if there exists a bijection $A\to [n]$ for some $n\in\mathbb{N}_0$. The \emph{cardinality} or \emph{size} of $A$, written as $|A|$, is $n$. This is well-defined i.e.  if $f: A\to [n]$ and $g: A\to [m]$ are both bijections, then $m = n$.
\begin{proof}
  wlog assume $m \geq n$. Let $h: [n]\to [m]$ with $h(i) = i$, which is injective. Then the map $h\circ f\circ g^{-1}: [m]\to [m]$ is injective so bijective. Thus $h$ is bijective. Hence $n = m$.
\end{proof}

Q: Countable set
A: $A$ is countable if
\begin{enumerate}
    \item $A$ is finite or there is a bijection between $A$ and $\mathbb{N}$
    \item There is an injection from $A\to \mathbb{N}$
    \item $A = \emptyset$ or there is a surjection from $\mathbb{N} \to A$
  \end{enumerate}
\begin{proof}
  (i) $\Rightarrow$ (iii): If $A$ is finite, there is a bijection $f: A \to S$ for some $S\subseteq \mathbb{N}$. For all $x\in \mathbb{N}$, if $x\in S$, then map $x\mapsto f^{-1}(x)$. Otherwise, map $x$ to any element of $A$. This is a surjection since $\forall a\in A$, we have $f(a)\mapsto a$.
  (iii) $\Rightarrow$ (ii): If $A\not= \emptyset$ and $f: \mathbb{N}\to A$ is a surjection. Define a map $g: A\to \mathbb{N}$ by $g(a) = \min \{ i \ | \ f(i)=a\}=\min f^{-1}(a)$, which exists by WOP. So $g$ is an injection.
  (ii) $\Rightarrow$ (i): If there is an injection $f: A\to \mathbb{N}$, then $f$ gives a bijection between $A$ and $S = f(A)\subseteq\mathbb{N}$. If $S$ is finite, so is $A$. If $S$ is infinite, there is a bijection $g$ between $S$ and $\mathbb{N}$. So there is a bijection $g\circ f$ between $A$ and $\mathbb{N}$.
\end{proof}

Q: Show $\mathbb{Z}^k$ is countable for all $k\in \mathbb{N}$
A: \begin{proof}
 \textbf{Basis} $\mathbb{Z}$ is countable. The map $f: \mathbb{Z}\to \mathbb{N}$ given by
  \[
    f(n) =
    \begin{cases}
      2n & n > 0\\
      2(-n) + 1 & n \leq 0
    \end{cases}
  \]
  is a bijection.
\textbf{Induction} If $\mathbb{Z}^k$ is countable, $\mathbb{Z}^{k + 1} = \mathbb{Z}\times \mathbb{Z}^k$. Since we can map $\mathbb{Z}^k \to \mathbb{N}$ injectively by the induction hypothesis, we can map injectively $\mathbb{Z}^{k + 1}\to \mathbb{Z}\times \mathbb{N}$, and we can map that to $\mathbb{N}\times\mathbb{N}$ injectively.
We can map $(a, b)\in\mathbb{N}\times\mathbb{N}\mapsto 2^a3^b$ injectively by FTA.
\end{proof}
 Note - we can also construct a bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by counting diagonally: $(a, b) \mapsto \binom{a + b}{2} - a + 1$:

Q: Are the algebraic numbers countable?
A: The set of algebraic numbers is countable.
\begin{proof}
  Let $\mathcal{P}_k$ be the set of polynomials of degree $k$ with integer coefficients. Then $a_kx^k + a_{k - 1}x^{k - 1} + \cdots + a_0 \mapsto (a_k, a_{k - 1}, \dots, a_0)$ is an injection $\mathcal{P}_k \to \mathbb{Z}^{k + 1}$. Since $\mathbb{Z}^{k + 1}$ is countable, so is $\mathcal{P}_k$.
Then $\mathcal{P} = \bigcup \mathcal{P}_k$ is a countable union of countable sets, so is countable. Finally $\bigcup_{p\in \mathcal{P}} \{ \textrm{roots of }p\}$ is a countable union of countable sets, so countable.
\end{proof}

Q: Countability of $\mathbb{R}$
A: The set of real numbers $\mathbb{R}$ is uncountable.
\begin{proof}
  (Cantor's diagonal argument) Assume $\mathbb{R}$ is countable. Then we can list all the reals in decimal form
  \begin{align*}
    r_1 &= n_1\,.\,d_{11}\,d_{12}\,d_{13}\,d_{14}\cdots\\
    r_2 &= n_2\,.\,d_{21}\,d_{22}\,d_{23}\,d_{24}\cdots\\
    r_3 &= n_3\,.\,d_{31}\,d_{32}\,d_{33}\,d_{34}\cdots\\
    r_4 &= n_4\,.\,d_{41}\,d_{42}\,d_{43}\,d_{44}\cdots \\
    \vdots
  \end{align*}
  Define $r = 0\,.\,d_1\,d_2\,d_3\,d_4\cdots$ by $d_n =
  \begin{cases}
    1 & d_{nn}\not= 1\\
    2 & d_{nn}=1
  \end{cases}$. $r\neq r_i$ as they differ in the $n$th digit so $r$ is a real number but not in the list. Contradiction.
\end{proof}
Note that we are legitimate in concluding $r\neq r_n$ as decimal expansions are unique except in the case of repeating $9$s which is excluded here by the fact that the next digit of $r$ is $1$ or $2$.

Q: Countability of transcendentals
A: The transcendentals are uncountable.
\begin{proof}
  If not, then the reals, being the union of the transcendentals and algebraic numbers, must be countable. But the reals are uncountable.
\end{proof}

Q: Countability of the set of subsets of $\mathbb{N}$
A: $\mathcal{P}\mathbb{N}$ is uncountable.
\begin{proof}
Suppose $\mathcal{P}\mathbb{N}$ is countable. Let $S_1,S_2,S_3, \dots$ be the list of all subsets of $\mathbb{N}$. Let $S = \{n\in\mathbb{N} \ | \ n\not\in S_n\}$. But then $S$ is not in the list. Contradiction.
\end{proof}
The set $\mathcal{F}$ of all finite subsets of $\mathbb{N}$ is countable.
\begin{proof}
$\mathcal{F}_k = \{Y\subseteq\mathbb{N} \ | \ |Y| = k\} \overset{\mathrm{inj}}{\to} \mathbb{Z}^k$. So $\mathcal{F} = \bigcup_{k\geq 0}\mathcal{F}_k$ is a countable union of countable sets so countable.
\end{proof}
Thus the set of infinite subsets of $\mathbb{N}$ is uncountable.

Q: Countability of $\Sigma=\mathbb{Z}^\infty$
A: Let $\Sigma$ be the set of all functions $\mathbb{N}\to \mathbb{N}$ (ie. the set of all integer sequences). $\Sigma$ is uncountable.
\begin{proof}
 If $\Sigma$ were countable, we could list it as $f_1, f_2, f_3\cdots$. But then $f$ given by \[f(n) =
  \begin{cases}
    1 & f_n(n) \not= 1\\
    2 & f_n(n) = 1
  \end{cases}\]
is missing from the list. Contradiction.
\end{proof}
\begin{proof}
If $\Sigma$ were countable, then there would be an injection $\Sigma\to\mathbb{N}$. We can also inject $\mathcal{P}(\mathbb{N})\to\Sigma$ by $S\mapsto 1+i_S$. Therefore, $\mathcal{P}(\mathbb{N})\to\Sigma\to\mathbb{N}$ is an injection. So $\mathcal{P}(\mathbb{N})$ is countable. Contradiction.
\end{proof}

Q: Show that power sets are larger than their parents
A: Let $A$ be a set. Then there is no surjection from $A\to \mathcal{P}A$.
\begin{proof}
  Suppose $f: A\to \mathcal{P}(A)$ surjectively, so there is an $s\in A$ such that \[
f(s) = \{a\in A \ | \ a\not\in f(a)\}.\]
Then $s\in f(s) \iff s\not\in f(s)$. Contradiction.
\end{proof}

Q: Show that $|(0,1)|=|(0,\infty)|$
A: $(0,1)\leftrightarrow (0,\infty)$ by $x\mapsto \frac{1}{x}-1$ which has inverse $y\mapsto\frac{1}{y+1}$.

Q: Show that $|\mathcal{P}(\mathbb{N})|=|\mathbb{R}|$
A: $\mathcal{P}(\mathbb{N})\to\mathbb{R}$ by $S\mapsto 0.i_S(1)i_S(2)\cdots$ is injective.
$\mathbb{R}\to\mathcal{P}(\mathbb{Q})\leftrightarrow\mathcal{P}(\mathbb{N})$ by $r\mapsto \{ q\in\mathbb{Q} \ | \ q\leq r \}$ is injective by the fact that the rationals are dense in the reals.
So by the Cantor-Schr\"oder-Bernstein theorem, $\mathcal{P}(\mathbb{N})\leftrightarrow\mathbb{R}$.