\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{mathtools}
\usepackage{float}

\setlength{\parindent}{0pt}
\setcounter{section}{-1}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[section]
\newtheorem{axiom}{Axiom}[section]

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{example}{Example}
\newtheorem*{observation}{Observation}
\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}
\newcommand{\laplace}[1]{\mathcal{L}\left\{#1\right\}}
\newcommand{\pset}[1]{\mathcal{P}\left(#1\right)}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\intemb}{int}
\DeclareMathOperator{\defequiv}{\mkern4mu :\mkern-8mu \iff}

\newcommand{\hateq}{\mathrel{\widehat{=}}}

\makeatletter
\newcommand{\axcirc}[1]{\mathbin{\mathpalette\make@circled#1}}
\newcommand{\make@circled}[2]{%
  \ooalign{$\m@th#1\largecirc{#1}$\cr\hidewidth$\m@th#1#2$\hidewidth\cr}%
}
\newcommand{\largecirc}[1]{%
  \vcenter{\hbox{\scalebox{1.5}{$\m@th#1\bigcirc$}}}%
}
\makeatother

\begin{document}

\section{Fundamentals of Mathematics}
\begin{table}[H]
    \centering
    \begin{tabular}{|c|}
        \hline
        \( (\mathbb{N}, +, \cdot), (\mathbb{Z}, \oplus, \odot), (\mathbb{Q}, \boxplus, \boxdot) \) \\
        \hline
        Algebraic structures \\
        \hline
        Maps \& relations \\
        \hline
        Set theory \\
        \hline
        Proofs \\
        \hline
        Logics \\
        \hline
    \end{tabular}
\end{table}

Instead of lots of repetition, we try to say it once, and say it right, since
\[ \text{8 years of school } \hateq \text{ 4 lectures} \]

\section{Logic}
We will be discussing \textbf{classical logic}, steps:
\begin{itemize}
    \item Propositional logic
    \item Predicate logic
\end{itemize}
\vspace{.1in}
\begin{definition}
    A \textbf{proposition} can take the values T and F (true and false), no other.
\end{definition}
\begin{remark}
    It is not in the purview of the propositional logic to study the interior structure of a proposition.
\end{remark}
One can define new propositions in terms of given ones.

\subsection{Logical operators}
\begin{itemize}
    \item Unary operators: `takes' one proposition and makes a new one.
    \begin{table}[H]
    \begin{tabular}{|c||c|c|c|c|}
         \hline
         \(p\) & \(\neg p\) & id\(\left(p\right)\) & \(T_p\) & \(\reflectbox{\rotatebox[origin=c]{180}{T}}_p\) \\
         \hline
         T & F & T & T & F \\
         F & T & F & T & F \\
         \hline
    \end{tabular}
\end{table}
    These are ALL unary operators, actually. Exhausted all cases, no other ones possible.
    \item Binary operators: `takes' two propositions and make a new one.
    A few important ones:
    \begin{table}[H]
    \begin{tabular}{|c|c||c|c|c|c|c|}
         \hline
         \(p\) & \(q\) & \( p \lor q \) & \( p \land q \) & \( p \oplus q \) & \( p \implies q \) & \( p \iff q \) \\
         \hline
         T & T & T & T & F & T & T \\
         T & F & T & F & T & F & F \\
         F & T & T & F & T & T & F \\
         F & F & F & F & F & T & T \\
         \hline
    \end{tabular}
    \end{table}
    If you had a half-decent high-school teacher, you would've known about logical implication (lol).
    For logical implication: \textbf{ex falso quod libet}.
\end{itemize}
\begin{theorem}
    \( \left( p \implies q \right) \iff \left( \neg q \right) \implies \left( \neg p \right) \)
\end{theorem}
\begin{proof}
Looking at the truth table, we can see the last two columns are equivalent for all cases, therefore the theorem holds.
    \begin{table}[H]
    \begin{tabular}{|c|c||c|c|c|c|}
         \hline
         \(p\) & \(q\) & \(\neg p\) & \(\neg q\) & \(\left( \neg q \right) \implies \left( \neg p \right)\) & \(p \implies q\) \\
         \hline
         T & T & F & F & T & T \\
         T & F & F & T & F & F \\
         F & T & T & F & T & T \\
         F & F & T & T & T & T \\
         \hline
    \end{tabular}
    \end{table}
\end{proof}
\begin{remark}
    This theorem is kind of like the `license' to perform proofs by way of contradiction. Other logic systems exist where proofs by way of contradiction do not `work' in a sense.
\end{remark}
\begin{remark}
    \(\left( \neg q \right) \implies \left( \neg p \right)\) is called the \textbf{contrapositive} of \(p \implies q\).
\end{remark}

\subsection{Notational convention}
We agree that the `binding strength' of the following operators strictly decreases:
\[ \neg \land \lor \implies \iff \]

\subsection{N-ary operators}
An \(N\)-ary operator is just a more general case of the types of operators we have seen before, they `take' \(N\) propositions and produce a single new one.
There are exactly \(2^{2^N}\) (whatever that means) \(N\)-ary operators for all \(N \in \mathbb{N}\).
\begin{theorem}
    Every N-ary operator operator can be expressed solely in terms of one particular binary operator, namely NAND, or the not-and, or the symbol `Sheffer stroke', \(p \mid q\). Its truth table:
    \begin{table}[H]
    \begin{tabular}{|c|c||c|}
         \hline
         \(p\) & \(q\) & \(p \mid q\) \\
         \hline
         T & T & F \\
         T & F & T \\
         F & T & T \\
         F & F & T \\
         \hline
    \end{tabular}
\end{table}
\end{theorem}
No proof, sadly.

\begin{example}
    \( \neg p \defequiv p \mid p \)
\end{example}
\begin{remark}
    The \(:\) symbol `defines' the left hand side of the equivalence in terms of the right hand side, for example, \(\defequiv\) and \(:=\).
\end{remark}

\subsection{Predicate Logic}
`Refines' propositional logic, \textbf{instead} of propositions, predicate logic uses the following:
\begin{itemize}
    \item objects, commonly referred to by capital letters (A, B, C), further unspecified, because again, predicate logic theory does not study the interior structure of its objects,
    \item predicates (P, Q, R), which `operate' on objects.
\end{itemize}
Each predicate is assigned a valence, e.g. the valence of a predicate \(P\) is \(\val(P)\) (technically the valence is a natural number, but those are not properly defined yet).
(continuing) objects and predicates play together such that any \textbf{evaluation} of a predicate \(P\) on \(\val(P)\) many objects \( X_1, X_1, \ldots , X_{\val(P)} \), namely \(P(X_1, X_1, \ldots , X_{\val(P)})\) is a proposition. (this is kind of the definition of a predicate but you cannot properly write it nicely as a definition in this form)
\begin{remark}
    A predicate \(P\) such that \(\val(P) = 0\) is a proposition.
\end{remark}
\subsubsection{Examples}
\begin{example}
    Let \(P\) be a predicate of valence 1 such that
    \[P(X) \defequiv X^2 = X\]
    This would be a nice, intuitive, didactically approved example, but we lack the required mathematical structures to make sense of it.
\end{example}
\begin{example}
    Let \(E\) be a predicate of valence 2 such that
    \[ E(X, Y) \defequiv X \in Y \]
    Same problem again, what is the \(\in\) operator even?
\end{example}
\begin{example}
    Let \(P\) be a predicate of valence 1 and let \(R\) be a predicate of valence 2, then define a predicate \(Q\) of valence 2 such that
    \[ Q(X, Y, Z) \defequiv P(X) \land Y(Z, Z) \]
\end{example}

\subsection{Quantification}
\begin{definition}
    Let \(P\) be a predicate such that \(\val(P) = 1\), then define the proposition (called `universal quantification')
    \[\forall X : P(X) \defequiv \begin{cases*}
        T & if \(P(X)\) is true indenpendent of \(X\), \\
        F & otherwise.
    \end{cases*} \]
\end{definition}
Read this as `For all X, P(X) (is true)'.
\begin{definition}
    Let \(P\) be a predicate such that \(\val(P) = 1\), then define the proposition (called `there exists')
    \[ \exists X : P(X) \defequiv \neg\left( \forall X : \neg P(X) \right) \]
\end{definition}
\begin{theorem}
    Let \(P\) be a predicate of valence one. Then:
    \[\forall X : P(X) \implies P(Y)\]
\end{theorem}
\begin{proof}
    Suppose the left hand side of the implication is true. Then \(P\) is true and independent of \(X\), so the theorem holds. If the left hand side of the implication is false, then the proposition still holds because of ex falso quod libet.
\end{proof}
\begin{remark}
    The following
    \[ \forall X : \exists Y : R(X, Y) \]
    is generically not equivalent to
    \[ \exists Y : \forall X : R(X, Y) \]
\end{remark}

\subsection{Proofs and axiomatic systems}
\begin{definition}
    An axiomatic system is given by a finite list of propositions, \( a_1, a_2, \ldots, a_N\), called axioms.
\end{definition}
\begin{definition}
    A proof for a proposition \(P\) under a set of assumptions \( S_1, S_2, \ldots, S_N\) (which are propositions), and withing an axiomatic system, is a finite list \( q_1, q_2, \ldots, q_{F - 1}, P\) (think `proof steps') with the following property: for every \(j\) with \(1 \leq j < F\), one of the following conditions must be true:
    \begin{itemize}
        \item \(q_j\) is an axiom,
        \item \(q_j\) is an assumption,
        \item \(q_j\) is a tautology,
        \item \(\exists m, n : q_m \land q_n \implies q_j\) and \(1 \leq m,n < j\).
    \end{itemize}
\end{definition}

\section{Set theory}
Set theory is built on predicate logic. There are 2 further stipulations we need to make:
\begin{itemize}
    \item there are \textbf{objects} that satisfy a set of additional conditions (axioms of set theory), and thus qualify as `sets';
    \item there is a particular valence two predicate \(\in\) (element of, epsilon, etc.) which is defined for objects that happen to be sets. In other words, if \(A\) and \(B\) are sets, then \(\in\!(A, B)\) is a proposition.
\end{itemize}
This is the general idea of set theory.

There are two `ways' to set theory, starting with:
\subsection{Naive set theory}
Basic idea: sets are collections (bags) of objects, where the selection of which object belongs to a particular set is made by a valence one predicate, \(S\). More precisely, we have the one and only axiom of naive set theory:
\begin{axiom}
    $\axcirc{G}$ \textbf{Axiom of General comprehension}: Let \(S\) be a predicate of valence one, then there is a naive set denoted
    \[ \left\{ X \mid S(X) \right\} \]
    which is defined by
    \[ E \in \{X \mid S(X)\} \defequiv S(E) \]
\end{axiom}
\begin{definition}
    Let $A$ and $B$ be sets. Then
    \[ A = B \defequiv \forall E : \left( E \in A \iff E \in B \right) \]
\end{definition}
\begin{definition}
    Let $A$ and $B$ be sets. Then
    \[ A \subseteq B \defequiv \forall E : \left( E \in A \implies E \in B \right) \]
\end{definition}
Thus, we have further defined two valence two predicates, \( =, \subseteq \), in terms of \(\in\).

\begin{remark}
    Notational convention:
    \[ A \in B \defequiv \in\!(A, B) \]
    \[ A \subseteq B \defequiv \subseteq\!(A, B) \]
    \[ A = B \defequiv =\!(A, B) \]
\end{remark}

The general comprehension axiom wonderfully allows to construct any set one needs in order to enact all of modern mathematics.
\begin{example}
    Consider a set \(\varnothing := \{ X \mid S(X) \} \), and let \(S(X)\) be a valence one predicate such that
    \[ S(X) \defequiv F \]
    By general comprehension, this is a (naive) set, called the `empty set'.
    
    \textbf{Justification for terminology}:
    \[ E \in \varnothing \iff S(E) \iff F \]
    Therefore, \(\varnothing\) `has no elements'.
\end{example}
\begin{example}
    Let $A$ and $B$ be naive sets. Then
    \[ A \cup B := \left\{ X \mid X \in A \lor X \in B \right\} \]
    By \(\axcirc{G} \), \( E \in A \cup B \iff X \in A \lor X \in B \). Similarly:
    \[ A \cap B := \left\{ X \mid X \in A \land X \in B \right\} \]
    \[ A \setminus B := \left\{ X \mid X \in A \land X \notin B \right\} \]
\end{example}
\begin{example}
    Let $A$ be a naive set. Then
    \[ \mathcal{P}(A) := \{ X \mid 
    X \subseteq A \} \]
\end{example}

\subsection{Trouble in (general comprehension) paradise}
Let \(u := \{ X \mid \underbrace{X \notin X}_{S(X)} \} \), then \(u\) by \(\axcirc{G}\) is a naive set. Let us consider whether \(u \in u\), by exhausting all cases.

\textbf{Case 1}: \( u \in u \underbrace{\iff}_{\text{by } S(X)} u \notin u \), contradiction.

\textbf{Case 2}: \( u \notin u \underbrace{\iff}_{\text{by } S(X)} u \in u \), contradiction.

\subsection{Zermelo-Fraenkel set theory}
Formulation of set theory on which modern mathematics is formed. Overview: we should repair $\axcirc{G}$, weakened to $\axcirc{M}$. The following axioms shall be defined at some point:
\[ \overbrace{\underbrace{\axcirc{E} \axcirc{M}}_{\text{restricted comprehension}} \axcirc{P}}^{\text{doublet sets}} \axcirc{U} \axcirc{I} \axcirc{F} (\axcirc{C}) \]

\begin{axiom}
    $\axcirc{E}$ \textbf{Axiom of empty set existence}: There is a set \(E\) such that
    \[ \forall X : X \notin E \]
\end{axiom}
\begin{remark}
    Terminology: any such set is called `an empty set'.
\end{remark}
\begin{theorem}
    Let \(E\) and $\tilde{E}$ be empty sets. Then \( E = \tilde{E} \)
\end{theorem}
\begin{proof}
    \(E\) is empty, so by definition, for all X, \( X \in E \) is false, and by ex falso quod libet, the statement `\( X \in E \implies X \in \tilde{E} \)' is true.
    Analogously, $\tilde{E}$ is empty, so by definition, \( X \in \tilde{E} \) is false, and by ex falso quod libet, the statement `\( X \in \tilde{E} \implies X \in E \)' is true. Therefore, \( \forall X : X \in \tilde{E} \iff X \in E \), and by definition of set equality, \(E = \tilde{E}\).
\end{proof}
This proves that there is only a single empty set, so we can assign it its symbol again, \(\varnothing\). In order to state \(\axcirc{M}\), we need a preceding definition:
\begin{definition}
    A valence two predicate \(F\) is called a \textbf{mapping} if and only if
    \[ \forall X : \exists! Y : F(X, Y) \]
\end{definition}
\begin{axiom}
    $\axcirc{M}$ \textbf{Axiom of mapped sets}: Let $A$ be a ZFC set, and $F$ a mapping. Then there is a set (denoted $\underbrace{\im_F(A)}_{\text{image set of } A \text{ under } F}$) defined by
    \[ Y \in \im_F(A) \defequiv \exists X : \left[ X \in A \land F(X, Y) \right] \]
\end{axiom}

Combining $\axcirc{E}$ and $\axcirc{M}$, one finds as an implication the most used theorem of mathematics\footnote{Citation needed}:
\begin{theorem}
    \textbf{Principle of restricted comprehension}: Let $A$ be a ZFC set, let $S$ be a valence one predicate. Then the set denoted by \( \left\{ X \underbrace{\in A}_{\text{new}} \mid S(X) \right\} \) and defined through
    \[ E \in \left\{ X \in A \mid S(X) \right\} \defequiv E \in A \land S(E) \]
    is a ZFC set.
\end{theorem}
\begin{proof}
    Consider the following two cases:

    \textbf{Case 1}: Suppose there exists no $E$ such that \(E \in A \land S(E)\). Then we define \( \left\{ X \in A \mid S(X) \right\} := \varnothing \).

    \textbf{Case 2}: Suppose such an $E$ does exist. Then define the following predicate of valence two:
    \[ F(X, Y) \defequiv S(X) \land (Y = X) \lor \neg S(X) \land (Y = E) \]
    $F$ is by definition a mapping. By $\axcirc{M}$, $\im_F(A)$ is a ZFC set. For notational purposes we then define \( \left\{ X \in A \mid S(X) \right\} := \im_F(A) \)
\end{proof}
\begin{axiom}
    $\axcirc{P}$ \textbf{Powerset axiom}: For every ZFC set \(A\), there exists the set denoted $\mathcal{P}(A)$, defined by
    \[ X \in \mathcal{P}(A) \defequiv X \subseteq A \]
\end{axiom}
\begin{remark}
    Recall that in naive set theory we define $\mathcal{P}(A)$ through general comprehension.
\end{remark}
\begin{example}
    \(\varnothing\) is a ZFC set due to $\axcirc{E}$. Therefore, we can ask the question whether \( \varnothing \subseteq \varnothing \). Well, by definition:
    \[ \varnothing \subseteq \varnothing \iff \forall X : X \in \varnothing \implies X \in \varnothing \]
    which, because \(X \in \varnothing\) is always false, is true, independent of X, therefore \(\varnothing \in \mathcal{P}(\varnothing)\)
\end{example}

Combining $\axcirc{E}$, $\axcirc{M}$ and $\axcirc{P}$, one finds as an implication the most used theorem of kindergarten mathematics\footnote{Again, citation needed}:
\begin{theorem}
    Let $A$ and $B$ be sets. Then there is a set denoted \(\{A, B\}\) such that
    \[ X \in \{A, B\} \iff X = A \lor X = B \]
\end{theorem}
\begin{proof}
    First, let us consider what $\pset{\varnothing}$ is. By $\axcirc{P}$,
    \[ X \in \pset{\varnothing} \iff X \subseteq \varnothing \iff \forall Y : (Y \in X \implies Y \in \varnothing) \]
    But $Y \in \varnothing$ is false, therefore $\forall Y : Y \notin X$. Only one such set by $\axcirc{E}$ exists, namely $\varnothing$. So $\varnothing \in \pset{\varnothing}$.

    Next, let us then consider $\pset{\pset{\varnothing}}$. Well,
    \[ X \in \pset{\pset{\varnothing}} \iff X \subseteq \pset{\varnothing} \iff \forall Y : (Y \in X \implies Y \in \pset{\varnothing}) \]
    We can consider the case where $Y \notin \pset{\varnothing}$, in which case $X = \varnothing$, and we can consider the case where $Y \in \pset{\varnothing}$, and there exists as shown at least one such $Y$, namely $\varnothing$. Thus $\varnothing, \pset{\varnothing} \in \pset{\pset{\varnothing}}$. Then define the following mapping $F$:
    \[ F(X, Y) \defequiv (X = \varnothing) \land (Y = A) \lor (X \neq \varnothing) \land (Y = B) \]
    Then, by $\axcirc{M}$, $\im_F(\pset{\pset{\varnothing}})$ is a ZFC set, so we define
    \[ \{A, B\} := \im_F(\pset{\pset{\varnothing}}) \]
    Again by $\axcirc{M}$, $ X \in \{A, B\} \iff \exists X : [X \in \pset{\pset{\varnothing}} \land F(X, Y)] $. There exists only two cases for which $F(X, Y)$ is true, by the definition of $F$, namely $A$ and $B$. Hence we have shown $X \in \{A, B\} \implies X = A \lor X = B$. Let us now evaluate $F$ on $A$ and $B$ in order to show that the implication in the other direction is true as well. $F(X, A) \iff X =\varnothing$, and since such an $X \in \pset{\pset{\varnothing}}$ exists, we have proven $A \in \{A, B\}$. Now check $F(X, B) \iff X \neq \varnothing$, and such an element also exists in $\pset{\pset{\varnothing}}$, hence $B \in \{A, B\}$.
\end{proof}
\begin{axiom}
    $\axcirc{U}$ \textbf{Axiom of union}: Let $C$ be a set. Then there is a set denoted by $\underbrace{\bigcup C}_{\text{union set}}$ defined by
    \[ X \in \bigcup C \defequiv \exists S : \left( S \in C \land X \in S \right) \]
\end{axiom}
\begin{definition}
    Let \( A_1, A_2, \ldots \) be sets. Then \( {A_1, A_2} \) is a set by the principle of doublet sets. Let us first define a \textbf{singleton set}:
    \[ \{ A_1 \} := \{A_1, A_1\} \]
    which is a ZFC set by doublet sets. Similarly:
    \begin{align*}
     \{ A_1, A_2, A_3 \} &:= \bigcup \left\{ \left\{A_1, A_2\right\}, \left\{A_3\right\} \right\} \\
     \{ A_1, A_2, A_3, A_4 \} &:= \bigcup \left\{ \left\{A_1, A_2, A_3\right\}, \left\{A_4\right\} \right\} \\
     \vdots \\
     \{ A_1, \ldots, A_N \} &:= \bigcup \left\{ \left\{A_1, \ldots, A_{N-1}\right\}, \left\{A_N\right\} \right\}
    \end{align*}
    This way, any finite set can now be constructed.
\end{definition}
\begin{axiom}
    $\axcirc{I}$ \textbf{Axiom of infinity}: There exists a set $\mathbb{N}$ such that \(\varnothing \in \mathbb{N}\) and
    \[ \forall X : \left( X \in \mathbb{N} \implies \left\{ X \right\} \in \mathbb{N} \right) \]
\end{axiom}
\begin{remark}
    $\varnothing \in \mathbb{N}$, $\{ \varnothing \} \in \mathbb{N}$, $\{\{ \varnothing \}\} \in \mathbb{N}$, etc. We gave them nicknames!
    \begin{align*}
        0 &:= \varnothing \\ 
        1 &:= \{\varnothing\} \\
        2 &:= \{\{\varnothing\}\}
    \end{align*}
\end{remark}

\section{Relations and maps}
\subsection{Order from disorder}
Sets have no order: \( \{ A, B \} = \{ B, A \} \). There is no order that a set imposes on its elements.
\begin{definition}
    Let A and B be sets. Define the \textbf{ordered pair}:
    \[ (a, b) = \left\{ \left\{ a \right\}, \left\{ a, b \right\} \right\} \]
\end{definition}
\begin{observation}
    \[ (b, a) = \{ \{ b \}, \{ a, b \}  \} \neq \{ \{ a \}, \{ a, b \}  \} = (a, b) \]
\end{observation}
\begin{observation}
    \[ (a, a) = \{ \{ a \}, \{ a, a \}  \} = \{ \{ a \}, \{ a\}  \} = \{ \{ a \} \} \]
    Therefore we cannot `extract' the first entry by looking which set is the singleton set.
\end{observation}
\begin{theorem}
    The first entry of \( (a, b) \) is $ \bigcup \bigcap (a, b) $, and the second entry is
    \[ \begin{cases*}
        \bigcup \bigcap (a, b) & if $ \bigcup (a, b) = \bigcap (a, b) $, \\
        \bigcup \biggr( \bigcup (a, b) \setminus \bigcap (a, b) \biggr) & otherwise.
    \end{cases*} \]
\end{theorem}
\begin{proof}
    For the first element:
    \begin{align*}
        \bigcup \bigcap (a, b) &= \bigcup \bigcap \{ \{ a \}, \{ a, b \} \} \\
        &= \bigcup \{ a \} \\
        &= a
    \end{align*}
    For the second element:
    \begin{itemize}
        \item \textbf{Case 1}: Assume $ \bigcup (a, b) = \bigcap (a, b) $. This means that \( \{ a, b \} = \{ a \} \), therefore, \( b = a \). Then, the definition is equivalent to the definition of the first element, and the first element is equal to the second element, hence proven.
        \item \textbf{Case 2}: Now assume $ \bigcup (a, b) = \bigcap (a, b) $, therefore \( b \neq a \). Then
        \begin{align*}
            \bigcup \biggr( \bigcup (a, b) \setminus \bigcap (a, b) \biggr) &= \bigcup \biggr( \{ a, b \} \setminus \{ a \} \biggr) \\
            &= \bigcup \{ b \} \\
            &= b
        \end{align*}
    \end{itemize}
\end{proof}
\begin{definition}
    Let A and B be sets. Then the \textbf{cartesian product} of A and B is denoted by \( A \times B \) and defined by
    \[ A \times B := \left\{ (a, b) \in \pset{\pset{\bigcup \{A, B\}}} \, \biggr| \,  a \in A \land b \in B \right\} \]
\end{definition}
\begin{remark}
    This definition can be extended to \( A \times B \times C := ( A \times B ) \times C\), and then by using certain notational choices, we will be able to define \(n\)-tuples \( ( a_1, \ldots, a_n ) \).
\end{remark}

\subsection{Relations}
\begin{definition}
    A \textbf{relation} R between a set A and a set B is a subset of \( A \times B \).
\end{definition}
\begin{remark}
    Notation: Having chosen a relation R, we write
    \[ a R b \defequiv (a, b) \in R \]
    Additionally, a relation `on a set A' means a relation between set A and itself.
\end{remark}
\begin{example}
    Define the following relation on $\mathbb{N}$:
    \[ < \defequiv \left\{ \begin{array}{cccc}
         (0, 1), & (0, 2), & (0, 3), & \ldots \\
         & (1, 2), & (1, 3), & \ldots \\
         & & (2, 3), & \ldots \\
         \vdots & \vdots & \vdots & \ddots
    \end{array} \right\} \]
    Now, \((1, 2) \in < \iff 1 < 2\), and \((2, 1) \notin < \iff 2 < 1\).
\end{example}
\subsection{Maps}
\begin{definition}
    A relation \(f\) between A and B for which
    \[ \forall a \in A : \exists! b \in B : (a, b) \in f \]
    is called a \textbf{map}.
\end{definition}
\begin{remark}
    Notation:
    \[ f : A \to B \]
    \[ a \mapsto f(a) = b \]
\end{remark}
means the same as `Let $F$ be a map from $A$ to $B$, then $(a, b) \in f \defequiv \ldots. $', since by definition $ f(a) = b \defequiv (a, b) \in f $.
A is the \textbf{domain}, B is the \textbf{codomain}, \( f(a) = b \) is the \textbf{function prescription}.
\begin{remark}
    \textbf{Bad talk}: `Consider the function \(f(x) = x^2\)'.
    \textbf{Correct}: `Consider the map
    \[ f : \mathbb{R}^+_0 \to \mathbb{R} \]
    '
\end{remark}
\begin{example}
    Consider the map (called the \textbf{successor map})
    \[ S : \mathbb{N} \to \underbrace{\mathbb{N}^*}_{\mathbb{N} \text{ without } 0} \]
    \[ n \mapsto S(n) = \{ n \} \]
    For example, \(S(1) = S(\{ \varnothing \}) = \{\{ \varnothing \}\} = 2\).
\end{example}
\begin{example}
    Consider the map (called the \textbf{predecessor map})
    \[ P : \mathbb{N^*} \to \mathbb{N} \]
    \[ \{n\} \mapsto n \]
    For example, \(P(7) = P(\{ 6 \}) = 6\).
\end{example}
\begin{definition}
    Let \( A \overset{f}{\to} B \) and \( B \overset{g}{\to} C \) be maps. Then, we define the \textbf{composite map} as follows:
    \[ g \circ f : A \to C \]
    \[ a \mapsto (g \circ f)(a) := g(f(a)) \]
    (read the $\circ$ symbol as `composed with' or `after')
\end{definition}
\begin{theorem}
    Composition is associative: let \( A \overset{f}{\to} B \), \( B \overset{g}{\to} C \) and \( C \overset{h}{\to} D \) be maps. Then
    \[ h \circ (g \circ f) = (h \circ g) \circ f \]
\end{theorem}
\begin{proof}
    For all $a \in A$,
    \begin{align*}
        (h \circ (g \circ f))(a) &= h((g \circ f)(a)) = h(g(f(a))) \\
        ((h \circ g) \circ f)(a) &= (h \circ g)(f(a)) = h(g(f(a)))
    \end{align*}
    Hence both sides of the identity are equal for all \(a\), therefore the maps are equal.
\end{proof}
\begin{definition}
    Let \( f : A \to A \) be a map. Then define \( f^n \) as follows:
    \begin{itemize}
        \item \( F^0 := \id_A \)
        \item \( F^n := F^{P(n)} \circ f \)
    \end{itemize}
\end{definition}
\begin{theorem}
    Let \( f : A \to B \) be a map. Then $\id_A \circ f = f$.
\end{theorem}
\begin{proof}
    For all \( a \in A \), $ (\id_A \circ f)(a) = \id_A(f(a)) = f(a) $, therefore \( \id_A \circ f = f \).
\end{proof}
\begin{example}
    \begin{align*}
        f^3 &= f^{P(3)} \circ F = F^2 \circ f \\
        &= f^{P(2)} \circ f \circ f \\
        &= f^{1} \circ f \circ f \\
        &= f^{P(1)} \circ f \circ f \circ f \\
        &= f^{0} \circ f \circ f \circ f \\
        &= \id_A \circ f \circ f \circ f \\
        &= f \circ f \circ f \\
    \end{align*}
    which shows why \(f^n\) is equivalent to composing \(f\) with itself $n$ times.
\end{example}
\begin{remark}
    Consider a map \( f : A \to B \) such that \( A = M \times N \) and $M,N$ are sets. Now, \( (m, n) \mapsto f((m, n)) =: f(m, n) \). This way, we can do multivariable functions as well.
\end{remark}
\begin{definition}
    Define
    \[ + : \mathbb{N} \times \mathbb{N} \to \mathbb{N} \]
    \[ (a, b) \mapsto S^b(a) \]
\end{definition}
\begin{remark}
    Notational shorthand: \( a + b := +((a, b)) \). Also, \( + \subseteq \mathbb{N} \times \mathbb{N} \times \mathbb{N} \). From now on, we assume we can figure out associativity, commutativity, distributivity, etc. of the plus operator, and we assume we have defined times, and its rules.

    To give an idea, you might want to define multiplication according to
    \[ \cdot : \mathbb{N} \times \mathbb{N} \to \mathbb{N} \]
    \[ (a, b) \mapsto \begin{cases*}
        0 & if \(b = 0\) \\
        \cdot((a, P(b))) + a & otherwise
    \end{cases*} \]
\end{remark}
\begin{definition}
    A map \( f : A \to B \) is
    \begin{itemize}
        \item \textbf{injective} if \( f(a) = f(a') \implies a = a' \);
        \item \textbf{surjective} if \( \forall b \in B : \exists a \in A : b = f(a) \);
        \item \textbf{bijective} if the map is injective and surjective. In this case, the map is called an \textbf{isomorphism}.
    \end{itemize}
\end{definition}
\begin{definition}
    2 sets $A, B$ are called \textbf{isomorphic} if there exists an isomorphism \( \phi : A \to B \).
\end{definition}

\subsection{Equivalence relations}
A relation \(\sim\) on a set $A$ is called an \textbf{equivalence relation} if and only if it satisfies the following conditions:
\begin{itemize}
    \item Reflexivity: for all $a\quad$, $\quad a \sim a$
    \item Symmetry: for all $a,b\quad$, $\quad a \sim b \implies b \sim a$
    \item Transitivity: for all $a,b,c\quad$, $\quad a \sim b \land b \sim c \implies a \sim c$
\end{itemize}
\begin{definition}
    Let \(\sim\) be an equivalence relation on $A$. Then for any \(a \in A\), one defines the set
    \[ [a]_\sim := \{ m \in A \mid m \sim a \} \]
    called the \textbf{equivalence class} of $a$ with respect to \(\sim\).
\end{definition}
\begin{theorem}
    Let $A$ be a set and let $\sim$ be an equivalence relation on $A$. Let $a, b\in A$. For any two equivalence classes \([a]_\sim,[b]\sim\),
    \[ [a] = [b] \lor [a] \cap [b] = \varnothing \]
\end{theorem}
\begin{proof}
    \textbf{Case 1}: $a \sim b$. Since $E \in [a] \implies E \in A \land E \sim a$, $[a] = [b]$, since by the transitivity of $\sim$, $E \sim a \iff E \sim b$ and therefore $E \in [a] \iff E \in [b]$;
    
    \textbf{Case 2}: $\neg(a \sim b)$. By the same argument as case 1, we know that $E \in [a] \iff E \notin [b]$. The predicate $E \in [a] \land E \in [b]$ is always false. Therefore by the principle of restricted comprehension and the definition of set intersection, $\forall E : E \notin [a] \cup [b]$. This set, by $\axcirc{E}$, is an/the empty set.
\end{proof}
\begin{definition}
    Define the set of all equivalence classes (called the \textbf{quotient set} of $A$ with respect to~$\sim$)
    \[ A/_\sim := \{ [a] \in \pset{A} \mid a \in A \} \]
\end{definition}
\begin{theorem}
    Let $A$ be a set, let $\sim$ be an equivalence relation on $A$. Then
    \[ \bigcup A/_\sim = A \]
\end{theorem}

\section{Ring of $\Z$ \& field of $\Q$}
To start out, we assume we already know \( (\N, +, \cdot) \).

\subsection{Construction of $\Z$}
\begin{definition}
    Define the relation
    \[ \sim \, \subseteq (\N \times \N) \times (\N \times \N) \]
    \[ \forall a,b,c,d \in \N : (a, b) \sim (c, d) \defequiv a + d = b + c \]
\end{definition}
Motivation, morally \( a - b = c - d \), therefore the ordered pair \(  (a, b) \) represents $ a - b $.
\begin{claim}
    $\sim$ is an equivalence relation.
\end{claim}
\begin{proof}
    (This will be my version of the proof, by no means this is necessarily right)
    We need to show reflexivity, symmetry and transitivity:
    \begin{itemize}
        \item $\sim$ is reflexive $\iff \forall a, b \in \N : (a, b) \sim (a, b) \iff a + b = a + b$ which is obviously true;
        \item $\sim$ is symmetric $\iff \forall a, b, c, d \in \N : (a, b) \sim (c, d) \implies (c, d) \sim (a, b) \iff a + d = b + c \implies c + b = a + d $ which is obviously true;
        \item $\sim$ is transitive $\iff \forall a, b, c, d, e, f \in \N :$
        \begin{align*}
            (a, b) \sim (c, d) \land (c, d) \sim (e, f) &\implies (a, b) \sim (e, f) \\
            \iff a + d = b + c \land c + f = d + e &\implies a + f = b + e \\
            \iff a + d + c + f = b + c + d + e &\implies a + f = b + e \\
            \iff a + f = b + e &\implies a + f = b + e
        \end{align*}
        which is a tautology. Hence proven.
    \end{itemize}
\end{proof}
Intuition: we make from the problem of not having a natural number that represents $2-3$ (for example) the solution by introducing these ordered pairs under the equivalence relation $\sim$ such that `$ 2-3 = 6-7 $'. Formally:
\[ (2, 3) \sim (6, 7) \iff 2 + 7 = 3 + 6 \]
which is provably true of course. Therefore, it makes sense to not consider these ordered pairs to be integers, but rather \textbf{all of the equivalent representations}, does that ring a bell?
\begin{definition}
    Let $\Z$ be a set (called the \textbf{integers}) such that
    $ \Z := (\N \times \N)/_\sim $.
    In other words, integers are equivalence classes of ordered pairs of natural numbers under \(\sim\).
\end{definition}
\begin{definition}
    Let
    \[ \oplus : \Z \times \Z \to \Z \]
    \[ [(a, b)] \oplus [(c, d)] := [(a + c, b + d)] \]
    be a map, called \textbf{integer addition}.
\end{definition}
Morally again, $ a - b + c - d = a + c - (b + d) $, kind of like having a positive and a negative part, so to speak.
\begin{definition}
    Let
    \[ \odot : \Z \times \Z \to \Z \]
    \[ [(a, b)] \odot [(c, d)] := [(ac + bd, ad + bc)] \]
    be a map, called \textbf{integer multiplication}.
\end{definition}
Morally, $(a - c)(b - d) = ab + cd - bc - ad$ which justifies the definition.
For these definitions, we are using quotient sets (set of all equivalence classes) in the domain and codomain of the map. In order to be of value, it would make sense that those operations produce the same result for any two equivalence classes, independent of the representative elements. If a map satisfies this property, it is called \textbf{well-defined}, and the inverse, \textbf{ill-defined}.
\begin{claim}
    The map $\oplus$ is well-defined.
\end{claim}
\begin{proof}
    Let $a, b, c, d, a', b', c', d'$ be natural numbers. Assume that
    $[(a, b)] = [(a', b')]$ and $[(c, d)] = [(c', d')]$. This implies that $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$. These statements imply $a + b' = a' + b$ and $c + d' = c' + d$, respectively. Consider $ [(a, b)] \oplus [(c, d)] = [(a + c, b + d)] $ and $ [(a', b')] \oplus [(c', d')] = [(a' + c', b' + d')] $. To show that $\oplus$ is well-defined, it would be sufficient to show that these two expressions are equal.
    \begin{align*}
        [(a' + c', b' + d')] &= [(a' + c' + b, b' + d' + b)] \\
        &= [(a + c' + b', b' + d' + b)] \\
        &= [(a + c', d' + b)] \\
        &= [(a + c' + d, d' + b + d)] \\
        &= [(a + c + d', d' + b + d)] \\
        &= [(a + c, b + d)] \\
    \end{align*}
    Therefore, $ [(a + c, b + d)] = [(a' + c', b' + d')] $. Thus for any two pairs of representatives, such that the first and second integer of each pair is equal to the other pair's first and last element, respectively, $\oplus$ maps to an equivalence class of an identical representative, and thus $\oplus$ is well-defined. 
\end{proof}
\begin{remark}
    Checking well-definedness is really important on an exam. Whenever you declare a map that incorporates quotient sets, you should always prove well-definedness.
\end{remark}

\subsection{Ring structure of $(\Z, \oplus, \odot)$}
\begin{definition}
    A set and two operations, $(A, +_A, \cdot_A)$, is a structure called a \textbf{ring} if and only if it satisfies the following laws (denoting $+_A$ and $\cdot_A$ as simply $+$ and $\cdot$ for clarity):
    \begin{itemize}
        \item $C^+$: $\forall x, y \in A : x + y = y + x$
        \item $A^+$: $\forall x, y, z \in A : (x + y) + z = x + (y + z)$
        \item $N^+$: $\exists 0_A \in A : \forall x \in A : x + 0_A = x$
        \item $I^+$: $\forall x \in A : \exists (-x) \in A : x + (-x) = 0_A$
        \item $C^\cdot$: $\forall x, y \in A : x \cdot y = y \cdot x$
        \item $A^\cdot$: $\forall x, y, z \in A : (x \cdot y) \cdot z = x \cdot (y \cdot z)$
        \item $N^\cdot$: $\exists 1_A \in A : \forall x \in A : x \cdot 1_A = x$
        \item $D^{+,\cdot}$: $\forall x, y, z \in \Z : x \cdot (y + z) = x \cdot y + x \cdot z$
    \end{itemize}
\end{definition}
Meaning of the symbols for the laws:
\begin{itemize}
    \item Commutativity
    \item Associativity
    \item Neutral element
    \item Inverse elements
    \item Distributivity
\end{itemize}
\begin{theorem}
    $(\Z, \oplus, \odot)$ is a ring, where $0_\Z = [(0, 0)]$, $1_\Z = [(1, 0)]$, $(-x) := [(0, x)]$.
\end{theorem}
\begin{proof}
    Proving all laws:
    \begin{itemize}
        \item $C^\oplus$: Let $x\in\Z$ and $y\in\Z$, $x := [(a, b)]$ and $y := [(c, d)]$. Starting with a tautology, we find
        \begin{align*}
            &\iff [(a \oplus c, b \oplus d)] = [(a \oplus c, b \oplus d)] \\
            &\iff [(a \oplus c, b \oplus d)] = [(c \oplus a, d \oplus b)] \\
            &\iff [(a, b)] \oplus [(c, d)] = [(c, d)] \oplus [(a, b)] \\
            &\iff x \oplus y = y \oplus x
        \end{align*}
        \item $A^\oplus$:
        Let $x,y,z\in\Z$, $x := [(a, b)]$, $y := [(c, d)]$ and $z := [(e, f)]$. On one hand, \[ (x \oplus y) \oplus z = [(a + c, b + d)] \oplus z = [(a + c + e, b + d + f)] \]
        On the other hand, \[ x \oplus (y \oplus z) = x \oplus [(c + e, d + f)] = [(a + c + e, b + d + f)] \]
        which are equal;
        \item $N^\oplus$: % $\exists 0_A \in A \forall x \in A : x + 0_A = x$
        For all $x \in \Z$ such that $x = [(a, b)]$, $x + 0 = [(a, b)] + [0, 0] = [(a + 0, b + 0)]$, and by definition of addition in $\N$, that is equal to $[(a, b)] = x$;
        \item $I^\oplus$:
        Let $-[(a, b)] = [(b, a)]$. Then, their sum is $[(b + a, a + b)]$ and by associativity $[(a + b, a + b)] = [(0, 0)] = 0_\Z$; 
        \item $C^\odot$:
        Let $x\in\Z$ and $y\in\Z$, $x := [(a, b)]$ and $y := [(c, d)]$. Starting with a tautology, we find
        \begin{align*}
            &\iff [(ac + bd, ad + bc)] = [(ac + bd, bc + ad)] \\
            &\iff [(ac + bd, ad + bc)] = [(ca + db, cb + da)] \\
            &\iff [(a, b)] \odot [(c, d)] = [(c, d)] \odot [(a, b)] \\
            &\iff x \odot y = y \odot x
        \end{align*}
        \item $A^\odot$:
        Let $x,y,z\in\Z$, $x := [(a, b)]$, $y := [(c, d)]$ and $z := [(e, f)]$.
        On one hand,
        \begin{align*}
            (x \odot y) \odot z &= [(ac + bd, ad + bc)] \odot z \\
            &= [((ac + bd) \cdot e + (ad + bc) \cdot f, (ac + bd) \cdot f + (ad + bc) \cdot e)] \\
            &= [(ace + bde + adf + bcf, acf + bdf + ade + bce)]
        \end{align*}
        On the other hand,
        \begin{align*}
            x \odot (y \odot z) &= x \odot [(ce + df, cf + de)] \\
            &= [(a \cdot (ce + df) + b \cdot (cf + de), a \cdot (cf + de) + b \cdot (ce + df))] \\
            &= [(ace + adf + bcf + bde, acf + ade + bce + bdf)] \\
            &= [(ace + bde + adf + bcf, acf + bdf + ade + bce)]
        \end{align*}
        Thus $(x \odot y) \odot z = x \odot (y \odot z)$;
        \item $N^\odot$:
        Let $[(a, b)] \in \Z$, then
        \begin{align*}
            [(a, b)] \cdot 1_\Z &= [(a, b)] \cdot [(1, 0)] \\
            &= [(a \cdot 1 + b \cdot 0, a \cdot 0 + b \cdot 1)] \\
            &= [(a + 0, 0 + b)] \\
            &= [(a, b)] \\
        \end{align*}
        \item $D^{+,\odot}$: % $\forall x, y, z \in \Z : x \odot (y + z) = x \cdot y + x \odot z$
        Let $x,y,z\in\Z$, $x := [(a, b)]$, $y := [(c, d)]$ and $z := [(e, f)]$.
        \begin{align*}
            x \odot (y + z) &= [(a, b)] \odot [(c + e, d + f)] \\
            &= [(a \cdot (c + e) + b \cdot (d + f), a \cdot (d + f) + b \cdot (c + e))] \\
            &= [(ac + ae + bd + bf, ad + af + bc + be))] \\
            &= [(ac + bd + ae + bf, ad + bc + af + be)] \\
            &= [(ac + bd, ad + bc)] \oplus [(ae + bf, af + be)] \\
            &= x \odot y \oplus x \odot z
        \end{align*}
    \end{itemize}
    Hence all laws hold under the imposed conditions.
\end{proof}
\begin{remark}
    You have been lied to in elementary/high school (again). Rather obviously, $\N \subseteq \Z$ is false. For example, $2 \in \N$, and $2 := \{\{\varnothing\}\}$. Similarly, $[(2, 0)] \in \Z$, and $[(2, 0)]$ is an infinite set of all natural number pairs $(a, b)$ such that $a - b = 2$. Elements of $\Z$ have no resemblance whatsoever to elements of $\N$.
\end{remark}
\subsection{Embedding of $N$ into $Z$}
\begin{definition}
    Let the following be a map:
    \[ \intemb : \N \to \Z \]
    \[ n \mapsto [(n, 0)] \]
\end{definition}
\begin{claim}
    $\intemb$ is injective.
\end{claim}
\begin{proof}
    Let $a, a' \in \N$. Suppose $\intemb(a) = \intemb(a')$. This implies that $ [(a, 0)] = [(a', 0)] $. By definition of the equivalence of integers, $a + 0 = 0 + a'$. By associativity and the definition of addition on the naturals, $a = a'$. Thus $\intemb$ is injective.
\end{proof}
\begin{theorem}
    $\intemb$ is an \textbf{embedding} of $(\N, +, \cdot)$ into $(\Z, \oplus, \odot)$. That is, the following conditions must hold:
    \begin{itemize}
        \item $\forall n,m\in\N : \intemb(n + m) = \intemb(n) \oplus \intemb(m)$
        \item $\forall n,m\in\N : \intemb(n \cdot m) = \intemb(n) \odot \intemb(m)$
        \item $\intemb(0) = 0_\Z$
        \item $\intemb(1) = 1_\Z$
    \end{itemize}
\end{theorem}
\begin{proof}
    Let $n, m\in\N$. Then:
    \begin{itemize}
        \item $\intemb(n + m) = [(n + m, 0)] = [(n, 0)] \oplus [(m, 0)] = \intemb(n) \oplus \intemb(m)$;
        \item Similarly, \begin{align*}
            \intemb(n \cdot m) &= [(nm, 0)] \\
            &= [(nm + 0 \cdot 0, n \cdot 0 + 0 \cdot m)] \\
            &= [(n, 0)] \odot [(m, 0)] \\
            &= \intemb(n) \odot \intemb(m)
        \end{align*}
        \item $\intemb(0) = [(0, 0)] = 0_\Z$;
        \item $\intemb(1) = [(1, 0)] = 1_\Z$.
    \end{itemize}
\end{proof}
For that reason, morally you can think $\N \subseteq \Z$.
\begin{example}
    Traditional notation: let $n \in \N$, then $\intemb(n) = [(n, 0)]$, $-\intemb(n) = [(0, n)]$. That way, any integer $[(a, b)]$ can be written as
    \[ \begin{cases*}
        [(n, 0)] & if $ a \geq b \iff \exists m \in \N : a = b + m$ \\
        [(0, n)] & if $ a < b \iff \exists m \in \N^*: b = a + m$
    \end{cases*} \]
    (this fact can be very trivially shown). Hence proven that any integer can be written as `$\intemb(n)$' or `$-\intemb(n)$' where $n$ is a natural number. Now, in order to arrive at the traditional notation, we leave out the $\intemb$ in order to save chalk, I suppose. Now, it `makes sense' to write $5 + (-7)$.
\end{example}

\subsection{Construction of $\Q$}
\begin{definition}
    Define the following relation:
    \[ \approx \, \subseteq (Z \times Z^*) \times (Z \times Z^*) \]
    \[ (a, b) \approx (c, d) \defequiv a \odot d = b \odot c \]
\end{definition}
Morally, $\dfrac{a}{b} = \dfrac{c}{d} \iff ad = bc$.
\begin{claim}
    $\approx$ is an equivalence relation.
\end{claim}
\begin{proof}
    We need to show all properties of an equivalence relation:
    \begin{itemize}
        \item reflexivity: $ (a, b) \approx (a, b) \iff ab = ba $ which is true;
        \item symmetry: $ (a,b) \approx (c, d) \iff ad = bc \iff cb = da \iff (c, d) \approx (a, b) $;
        \item transitivity: Given $(a, b) \approx (c, d) \land (c, d) \approx (e, f)$, we can deduce that $ad = bc$ and $cf = de$. Equivalently, $ade = bce$ and $acf = ade$, respectively. Then, $bce = acf$ and $af = be$, which is equivalent to $(a, b) \approx (e, f)$.
    \end{itemize}
\end{proof}
\begin{definition}
    $\Q = (\Z \times \Z^*)/_\approx$
\end{definition}
This relates to the traditional notation, e.g. $\dfrac{a}{b} := [(a, b)]_\approx$.

\subsection{Addition and multiplication on $\Q$}
\begin{definition}
    Define the following map:
    \[ \boxplus : \Q \times \Q \to \Q \]
    \[ [(a, b)] \boxplus [(c, d)] := [(ad \oplus bc, bd)] \]
\end{definition}
This is again morally related to fractions as we know them already:
\[ \frac{a}{b} + \frac{c}{d} = \frac{ad}{bd} + \frac{bc}{bd} = \frac{ad + bc}{bd} \]
\begin{definition}
    Define the following map:
    \[ \boxdot : \Q \times \Q \to \Q \]
    \[ [(a, b)] \boxdot [(c, d)] := [(ac, bd)] \]
\end{definition}
\begin{claim}
    $\boxplus$ and $\boxdot$ are well-defined.
\end{claim}
\begin{proof}
     Let $[(a, b)],[(c, d)],[(a', b')],[(c', d')] \in \Q$. Assume $(a, b) \approx (a', b')$ and $(c, d) \approx (c', d')$, i.e. they belong to the same equivalence classes. From these statements it clearly follows that $ a \odot b' = a' \odot b $ and $ c \odot d' = c' \odot d $ (for clarity I will now omit the $\odot$, just know that it is there).
     
     Let us first prove that $\boxplus$ is well-defined. We start with a tautology:
    \begin{align*}
        [(ad \oplus bc, bd)] &= [(ad \oplus bc, bd)] \\
        \iff [(ad \oplus bc, bd)] &= [(adb'c' \oplus b'c'bc, b'dbc')] \\
        \iff [(ad \oplus bc, bd)] &= [(a'd'bc \oplus b'c'bc, b'd'bc)] \\
        \iff [(ad \oplus bc, bd)] &= [(a'd' \oplus b'c', b'd')] \\
        \iff [(a, b)] \boxplus [(c, d)] &= [(a', b')] \boxplus [(c', d']
    \end{align*}

    Let us now prove that $\boxdot$ is well-defined. We again start with a tautology:
    \begin{align*}
        \iff acb'd' &= acb'd' \\
        \iff acb'd' &= a'c'bd \\
        \iff (ac, bd) &\approx (a'c', b'd') \\
        \iff [(ac, bd)] &= [(a'c', b'd')] \\
        \iff [(a, b)] \boxdot [(c, d)] &= [(a', b')] = [(c', d')]
    \end{align*}
\end{proof}

The following definition is not from lecture, but from the finger practice.
\begin{definition}
    Define the map
    \[ (\,)^{-1} : \Q^* \times \Q^* \]
    \[ [(a, b)]^{-1} := (b, a)^{-1} \]
\end{definition}
\begin{claim}
    $(\,)^{-1}$ is well-defined.
\end{claim}
\begin{proof}
    Take $x = [(a, b)]$ and $x' = [(a', b')]$, and assume $x = x'$. In other words, $(a, b) \approx (a', b')$. Equivalently, $ab' = a'b$. To show well-definedness we want to show that these assumptions imply that $x^{-1} = x'^{-1}$. We start with a tautology:
    \begin{align*}
        a'b &= a'b \\
        \iff ba' &= ab' \\
        \iff (b, a) &\approx (b', a') \\
        \iff [(b, a)] &= [(b', a')] \\
        \iff [(a, b)]^{-1} &= [(a', b')]^[-1] \\
        \iff x^{-1} &= x'^{-1}
    \end{align*}
\end{proof}
\begin{theorem}
    For all $x \in \Q$, $x \boxdot x{-1} = 1_\Q$ (where $1_\Q = [(1, 1)])$. 
\end{theorem}
\begin{proof}
    Let $a \in \Z$, $b \in Z^*$ and $x = [(a, b)]$. Then
    \begin{align*}
        x \boxdot x^{-1} &= [(a, b)] \boxdot [(a, b)]^{-1} \\
        &= [(a, b)] \boxdot [(b, a)] \\
        &= [(ab, ba)] \\
        &= [(1, 1)]
    \end{align*}
    The last step should probably be more justified: $(ab, ab) \approx (1, 1) \iff ab \odot 1 = ab \odot 1$ which is a tautology. This also morally shows that the map $(\,)^{-1}$ produces a multiplicative inverse, which is a property of a field.
\end{proof}

\end{document}
