\part{Fundamentals}

\chapter{Sets}

At the beggining of the 19th century, mathematicians sought to create a robust mathematical framework that ensured consistent proofs, propositions and algorithms. To do this, they had to create general, unambiguous, and well-formed definitions and axioms throughout mathematics. Formalizing mathematical logic would be the first step, however there would need to be some 'intermediate' field of mathematics that defines objects on which mathematical logic can state propositions on.

Georg Cantor has created a paradise which connects almost all the rest of mathematics between eachother and to mathematical logic (the notable exception being type theory; an alternative to set theory). Philosophically, set theory is extremely fundamental and powerful, so having a strong command of it is an essential tool for every mathematician.

Indeed, there are many ways to go about establishing set theory depending on one's philosophy on how mathematics 'should' be (this is a topic in its own), however the earlierst step forward was the development of \emph{naive set theory}.

Georg Cantor's development of set theory contained some paradoxes, leading it to be called naive set theory. Axiomatic set theories such as \emph{ZFC} (Zermelo's Fried Chicken?!?) fix these paradoxes, however naive set theory gives a mostly correct intuition as well as the proper language to make branches of mathematics rigorous. As we study naive set theory, we'll allude to its limitations due to some noteworthy paradoxes.

We now commence our journey through Cantor's paradise.

\section{Sets}

A mathematical object is anything that can be well defined in mathematics. They include numbers, functions, geometric objects, spaces (linear spaces, topological spaces, measure spaces etc.), algebraic strucutres (groups, rings etc.) and even (or perhaps especially) sets themselves.



Then Cantor said, "Let there be sets," and there were sets. And Cantor saw that the sets were good.

\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}[Disjoint pair of sets]
A \emph{disjoint pair of sets} are a pair of sets $A,B$ that share no elements in common. We say that $A$ and $B$ are \emph{disjoint}.
\end{definition}

\begin{definition}[Disjoint family of sets]
\end{definition}


\section{Examples of sets}

The most basic set is the emptyset; a set which contains nothing.

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

\begin{definition}[Singleton]
A \emph{singleton} is a set containing 1 element. If this element is $x$, the singleton is often denoted as $\{x\}$.
\end{definition}






\section{Subsets}
\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}

\begin{definition}[Powerset]
The \emph{powerset} of a set $X$ is the set of all subsets of $X$. It is denoted as $\mathcal{P}(X)$.
%\[ \mathcal{P}(X) = \{Y : Y \subseteq X\}\]
\[ Y \in \mathcal{P}(X) \iff Y \subseteq 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{Cardinality}


 

\begin{definition}[Cardinality of a finite set]
The \emph{cardinality of a set $X$} is the number of elements within $X$. It is denoted as $|X|$.
\end{definition}

One interesting question to ask is what cardinality sets of infinite elements have. The truth is that there are different types of 'infinities', and therefore to do proper analysis on these sets we require more theory; this will be covered in part 3.

Some observations can be made  using all this theory that we have developed


- combina
- universe of discourse

\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}



Intersections allow us to formally define the disjoint property between sets.

\begin{definition}
A \emph{disjoint pair of sets} are a pair of sets $A,B$ that satisfy $A \cap B = \emptyset$. In other words, they share no elements in common.
\end{definition}



\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 =  A \cap B^{\complement}\]


\[ (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\]



\subsection{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} \}\]


\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{Closure operators}
\[X \subseteq \mathrm{cl}(X)\]
\[\mathrm{cl}( \mathrm{cl}(X) ) = \mathrm{cl}(X)\]
\[X \subseteq Y \implies \mathrm{cl}( X ) \subseteq \mathrm{cl}(Y)\]

Related to topological closure of a set. Also have use in universal algebra.






\section{Covers}

\begin{definition}[Cover]
A \emph{cover of $X$} is a family of sets $\mathcal{C} = (S_i)_{i\in I}$ whose union is a superset of $X$.
\[ X \subseteq \bigcup_{i \in I}S_i \]
\end{definition}

Covers appear in branches of mathematics such as topology and measure theory.

\section{Partitions}
\begin{definition}[Partition]
	A \emph{partition on $X$} is a family of sets $\mathcal{P}$ of subsets of $X$ such that all the following hold.
\item $\emptyset \notin \mathcal{P}$
\item $\bigcup_{P \in \mathcal{P}} P  = X$
\item Any two distinct sets in the partition are disjoint.
\end{definition}

\begin{definition}
A partition $A$ is a \emph{refinement of $B$} iff every $a \in$ A is a subset of some $b \in B$. We say that A is finer than B and B is coarser than A.
\end{definition}



\subsection{Russel's paradox}

\chapter{Other collection objects}

\section{Multiset}

Here is a useful set-like object which is crucial to combinatorics.

\begin{definition}
A \emph{multiset} is an unordered collection of objects, where the same object may have multiple instances. Unique objects within the multiset are called \emph{elements of the multiset} The amount of instances of an element is called its \emph{multiplicity}.
\end{definition}