\part{Naive Set Theory}

\chapter{Sets}

\section{Sets}
A \emph{set} is an unordered collection of unique objects (one cannot have two instances of the same object in the same set).

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.

Although the idea of a set is simple, extremely complicated sets with unintuitive properties can be formed. We have seen that sets can be specified by exaustively listing each of its elements, however one can use a logical statement to determine which elements lie within a set; this is known as \emph{set builder notation}.

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

\section{Examples of sets}

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

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

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






\chapter{Subsets}
\begin{definition}
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}
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\}\]
\end{definition}


\chapter{Cardinality}
\begin{definition}
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
\[Y \subseteq X \implies |Y| \leq |X|\]
\[\mathcal{P}(X)=2^{|X|}\]


- combina
- universe of discourse

\chapter{Set operations}
\section{Intersection}
\[ A \cap B = \{x : x \in A \land x \in B \} \]
\[ A \cap B = B \cap A \]


\[|A \cap B| \leq \min \{ |A|,|B| \} \]
Where 'min' refers to the smallest element of this set, see Order Theory.
\[ B \subseteq A \implies A \cap B = B \]


\section{Union}
\[ A \cup B = \{x : x \in A \lor x \in B \} \]
\[ A \cup B = B \cup A \]


\[|A \cap B| \geq \max \{ |A|,|B| \} \]
\[ B \subseteq A \implies A \cup B = A \]

\section{Complement}
\[ A^{\complement} = \{x : x \notin A \} \]
\[ (A^{\complement})^{\complement} = A\]


\section{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 \]
\[ |A \setminus B| \leq |A| \]

\section{Cartesian product}
\[ A \times B = \{ (a,b) : a \in A \land b \in B \}\]


\[|A \times B| =|A||B|\]
\[|A \times B| = |B \times A|\]

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





\chapter{Set-like objects}
- multiset; set-like object where repetition of elements is allowed
- ordered pair; set-like object of two ordered elements (which may be repetitions)

