\part{Fundamentals}

\chapter{Sets}

We will us

\begin{definition}[Set]
A \emph{set} is an unordered collection of unique objects (one cannot have two instances of the same object in the same set). Mathematical objects within a set are called \emph{elements of the set}.
\end{definition}


Typically capital case letters are used to symbolically represent sets. One may also specify a set using curly brackets around the objects, for example, $\{1,2,3,4,5\}$ is the set containing integers 1 through to 5.

\begin{example}
\[ Z= \{ 4,6502,64, \frac{\pi^2}{6} \} \]
\end{example}

\begin{example}
\[ \mathbb{N} = \{0,1,2,3,4,5, \hdots \} \]
\end{example}

\begin{example}
\[ V= \{ \mathrm{A} , \mathrm{E}  , \mathrm{I} , \mathrm{O} , \mathrm{U}\} \]
\end{example}


\begin{definition}[Empty set]
The \emph{empty set} is the set with no elements. It is denoted as $\emptyset$
\end{definition}



\begin{definition}[Subset]
Let $X$ be a set, then $Y$ is a \emph{subset} of $X$ if all the elements of $Y$ are in $X$, or in other words, the elements of $Y$ form a part of $X$.
%\[Y \subseteq X \iff \forall y \in Y [ y \in X ] \]
\end{definition}



\subsection{Set-builder notation (specification)}


Although the idea of a set is simple, extremely complicated sets with unintuitive properties can be formed. One way to construct subsets is by taking an intersection with another set, or by cherry-picking certain elements arbitrarily, however there exists another way to form subsets, one that will become very important in our future studies.
We have seen that sets can be specified by exaustively listing each of its elements, however one can use a logical statement to create a subset with elements satisfying the statement; this is known as \emph{set builder notation}.

\[ X = \{x \in Y : P(x) \} \]

We require a base set $Y$ and predicate $P$, and the elements of $X$ are therefore the elements of $Y$ satisfying $P$.


The use of a base set is important to avoid certain paradoxes, and the axiom that ensures the legality of our new set-builder notation is called \emph{the axiom schema of specification}.  Futhermore, certain hypothetical objects such as a 'set of all sets' or a 'set of all elements' cannot be sets in our theory without spoiling our work with various paradoxes; we will describe exactly what a set can be (at least according to the theory we are using right now) when we study ZFC. For now however, I implore you to have faith that the objects I describe as 'sets' are legal constructions within our theory.

\begin{example}
\[  P = \{ n \in \mathbb{N} : n \text{ is prime} \} \]
\end{example}

If the base set is obvious, or if no convenient notation for the set is known but it is clear that the object would definitely be a set, the base set may be omitted as an abuse of notation (but in secret, there would have to be some base set operating!).



\section{Set operations}



\subsection{Intersection}
Elements in both (the whole family of sets). Can also be thought of as the largest set that is a subset of both (the whole family of sets).

\[ A \cap B = \{x : x \in A \land x \in B \} \]
\[ \bigcap_{i \in I} A_i = \{x : \forall i \in I [ x \in A_i ]\}\]

Since the logical operation $\land$ is commutative, we easily get the following
\[ A \cap B = B \cap A \]


\begin{proposition}
\[  A \cap B \subseteq A \land A \cap B \subseteq B \]
\[ B \subseteq A \iff A \cap B = B \]
\end{proposition}






\subsection{Union}
\[ A \cup B = \{x : x \in A \lor x \in B \} \]
\[ \bigcup_{i \in I} A_i = \{ x : \exists i \in I [ x \in A_i ]\}\]


Since the logical operation $\lor$ is commutative, we easily get the following
\[ A \cup B = B \cup A \]


\[ A \subseteq A \cup B \land B \subseteq A \cap B \]
\[ B \subseteq A \implies A \cup B = A \]



\subsection{Set difference}
\[ A \setminus B = \{x : x \in A \land x \notin B \}\]


\[ (A \setminus B) \subseteq A \]
\subsubsection{Complement}
In some areas of mathematics we consider a universe; some set containing all the elements of the space or structure of interest. Let this universe be $X$.
\[ A^{\complement} = X \setminus A = \{x \in X : x \notin A \} \]
\[ (A^{\complement})^{\complement} = A\]
\[ A \setminus B =  A \cap B^{\complement}\]





\subsection{Disjount union}
\[ A_1 \sqcup A_2 = \{ (x,i) : x \in A_{i} \}\]
\[ \bigsqcup A_i = \{ (x,i) : x \in A_{i} \}\]


- symmetric difference
\subsection{De morgan's laws (set theory)}


\section{Cartesian product}

\[ A \times B = \{ (a,b) : a \in A \land b \in B \}\]
\[ \prod_{i \in I} A_i = \{ (x_i)_{i\in I} : x_i \in A_{i} \}\]