\chapter{Relation}

\section{Relation}
Sometimes we wish to describe that 2 objects are 'related' in some way; maybe they share a specific property, and we want a set to keep track of all pairs of 'similar elements'. This leads to the idea of a relation.

\begin{definition}
A \emph{relation} is a set $R$ of ordered pairs from two sets. We use the notation $xRy$ to say that $(x,y)$ is in $R$, meaning that $x$ is $R$-related to $y$.
\[ R \text{ is a relation of } X \times Y \iff R \subseteq X \times Y \]
	\[ xRy \iff (x,y) \in R\]
\end{definition}


Relations are extremely powerful notions and there exist many special types, such as equivalence relations, orders, and functions.




\subsection{Examples of relations}

We are familiar with a few relations already.

\begin{example}
The following is a relation that relates real numbers that are equal to eachother.
\[ E = \{ (x,y) \in \mathbb{R}\times\mathbb{R} :  x = y \} \]
In this relation, each $x$ is related only to the $y$ equal to it; it's kind of a trivial relation.
\end{example}


\begin{example}
The following is a relation that relates real numbers with real number less that or equal to it.
\[ L = \{ (x,y) \in \mathbb{R}\times\mathbb{R} :  x \leq y \} \]
In this relation, each $x$ is related to an infinite amount of $y$.
\end{example}


\begin{example}
The following is a relation that characterizes cartesian coordinates on the unit circle
\[ L = \{ (x,y) \in \mathbb{R}\times\mathbb{R} :  x^2+y^2=1 \} \]
In this relation, each $x$ is related to at most 2 $y$.
\end{example}

Relations don't even need to have deep mathematical properties; they simply need to be subsets of the cartesian product of two sets!

\begin{example}
The following is an example relating my sister an I to our favourite numbers.
\[ F= \{ (\mathbf{Zac},64), (\mathbf{Zac},6502), (\mathbf{Zac},4), (\mathbf{Alyssa},6), (\mathbf{9})  \}\]
This is a subset of $\{\mathbf{Zac}, \mathbf{Alyssa}\} \times \mathbb{N}$, hence it is a relation.
\end{example}

\section{Properties of relations}


\begin{definition}[Total relation on $x$]
\[R \text{ is total on } X \iff \forall x,y \in X [x \neq y \implies xRy \lor yRx]\]
\end{definition}

\section{Function}


We now look to study a special type of relation that is still quite general, but as we will later see is particularly interesting regarding the things we can say about them.

These kind of relations give every element in the first set strictly 1 mapping, and are called \emph{functions}.


\begin{definition}[Function]
A \emph{function} is a relation $f$ where no two ordered pairs have the same first element. Since functions relate every element from the first entry of the ordered pair only once, we can denote the $y$ such tht $xfy$ as $f(x)$.
\[ f \text{ is a function } \iff f \text{ is a relation } \land \forall (x,y),(x,z) \in f [ y=z ] \]
\[ f(x) = y \iff xfy\]
\end{definition}

Functions are perhaps the most interesting objects in mathematics; just ask Thomas Garrity \url{https://youtu.be/zHU1xH6Ogs4?si=i3G81IifMUrq8sP9}. Because of their special status and properties, they are often described using different notations to relations; more on this later.

\section{Equivalence relation}

Readers familiar with some number theory know that $7 = 2 ( \mod 5 )$, although obviously $7 \neq 2$. Readers familiar with Star Wars know that Anakin Skywalker is Darth Vader, but Darth Vader often exclaims that he isn't Anakin and that "Anakin Skywalker is dead".

The point is that in certain contexts, distinct (unequal) objects may exhibit identical behaviour. $7,2$ are 'equivalent' in $\mathbb{Z} \setminus 5 \mathbb{Z}$, and 'from a certain point of view' Darth Vader is Anakin.

Relations that seek to relate entities that are 'the same from a certain point of view' are called \emph{equivalence relations}, and are defined as relations that obey the 3 properties of reflexivity, symmetry, and transitivity.


\begin{definition}[Equivalence relation]
An \emph{equivalence relation} $\sim$ is a relation that is reflexive, symmetric, and transitive. It generalizes the properties that equality has.
\[ \sim \text{ is an equivalence relation } \iff \sim \text{ is symmetric, reflexive and transitive} \]
\[ \sim \text{ is an equivalence relation }\iff \forall x \in X [x\sim x] \land \forall x,y \in X [x \sim y \implies \sim x ] \land forall x,y,z \in X [ x\sim y \land y \sim z \implies x \sim z ]  \]
\end{definition}

\[ R \text{ is reflexive } \iff \forall x \in X, xRx \]
\[ R \text{ is symmetric } \iff (\forall x,y \in X, xRy \implies yRx) \]
\[ R \text{ is antisymmetric } \iff (\forall x,y \in X, xRy \land xRy \implies x=y) \]
\[ R \text{ is transitive } \iff (\forall x,y,z \in X, xRy \land yRz \implies xRz) \]

\begin{definition}
An \emph{equivalence class} of an element $a$ is the set of all elements that an equivalence relation deems 'equal' to $a$.
\[ [a] = \{ x \in X : a \sim x \} \]
\end{definition}

\begin{proposition}
\[ b \in [a] \implies [b]=[a] \]
\end{proposition}


\begin{proposition}
Equivalence classes form partitions.
\end{proposition}