termWork

\documentclass[titlepage]{article}
\usepackage[utf8x]{inputenc}
\usepackage{amsthm, amsmath, amsfonts, amssymb, mathrsfs,mathabx}
\usepackage{chngcntr}
\usepackage{mdframed}
\usepackage{breqn}
\usepackage{tikzsymbols}

\setcounter{section}{+1}

\DeclareMathOperator*{\Pwr}{\mathscr{P}}
\DeclareMathOperator*{\Rcal}{\mathcal{R}}
\DeclareMathOperator*{\Ima}{Im}
\DeclareMathOperator*{\dom}{dom}
\DeclareMathOperator*{\card}{card}
\DeclareMathOperator*{\ord}{ord}

\newtheorem{exercise}{\underline{Exercise}}[section]
\newtheorem{proposition}{\textit{Proposition}}[section]
\renewcommand{\qedsymbol}{\Summertree[1]}
\newtheorem{lemma}{\textit{Lemma}}[section]
\newtheorem{corollary}{\textit{Corollary}}[section]
\newenvironment{Lemma}[1][Lemma]{\proof[#1]\leftskip=1cm\rightskip=1cm}{\endproof}
\usepackage[linktocpage=true]{hyperref}
\usepackage{etoolbox}
\expandafter\patchcmd\csname\string\corollary\endcsname
  {\normalparindent}{0pt }{}{}
\newcommand{\bij}{\mathrel{\hookrightarrow\hspace{-1.8ex}\to}}




\counterwithin*{equation}{section}
\counterwithin*{equation}{subsection}




\title{Set Theory Term Work}
\author{Blikas }
\date{September 2015}

\begin{document}

\maketitle
\tableofcontents

\newpage
\begin{mdframed}
\section{Misc. Exersizes}
\end{mdframed}

\bigbreak
\subsection{Logical Operators}

    \begin{exercise}We show that $\land$, $\lor$ are commutative. We do this via truth table. 
    \end{exercise}
    
    \begin{proof} Consider the logical sentences $p$, $q$ and the following truth table: 

        \begin{center}
        \begin{tabular}{c|c|c|c}
        $p$ & $q$ & $p \lor q$ & $q \lor p$\\
        T & T & T & T \\
        T & F & T & T \\
        F & T & T & T \\
         F & F & F & F 
        \end{tabular}
        \end{center}
    Thus, $p \lor q \iff q \lor p $
    \end{proof}

\begin{proof} Consider the logical sentences $p$ and $q$ and the following truth table: 
\begin{center}
\begin{tabular}{c|c|c|c}
 $p$ & $q$ & $p \land q$ & $q \land p$\\
 T & T & T & T \\
 T & F & F & F \\
 F & T & F & F \\
 F & F & F & F 
\end{tabular}
\end{center}
 Thus, $p \land q \iff q \land p$.
\end{proof}

\newpage 
\subsection{Logical Rules}
 

\begin{exercise}We show that $p \lor p \iff p$ and $p \land p \iff p$, via truth table. 
\end{exercise}

    \begin{proof}
    Consider the logical sentence $p$ and the following truth table: 
        \begin{center}
        \begin{tabular}{c|c}
        $p$ & $p \lor p$\\
        T & T \\
        F & F
        \end{tabular}
        \end{center}
    Thus, $p \lor p \iff p$
    \end{proof}


    \begin{proof} Consider the logical sentence $p$ and the following truth table: 
    \begin{center}
        \begin{tabular}{c|c}
        $p$ & $p \land p$\\
        T & T \\
        F & F
        \end{tabular}
        \end{center}
        Thus, $p \iff p \land p$.
    \end{proof}

\begin{exercise}
We show that $p \Rightarrow p \lor q$ via truth table. 
\end{exercise}
    \begin{proof} Consider the logical sentences $p$ and $q$ and the following truth table: 
        \begin{center}
        \begin{tabular}{c|c|c}
        $p$ & $q$ & $p \lor q$ \\
         T & T & T  \\
         T & F & T \\
         F & T & T \\
         F & F & F  
        \end{tabular}
        \end{center}
    Thus, if $p$ is true, $p \lor q$ is true, i.e. $p \Rightarrow p \lor q$.
    \end{proof}

\newpage
\begin{mdframed}
\section{Unordered Pairs}
\end{mdframed}

\begin{exercise} Consider the sets $ \emptyset $, $ \lbrace \emptyset \rbrace $, $ \lbrace \lbrace \emptyset \rbrace \rbrace$, etc.; Consider all  the pairs such as $ \lbrace \emptyset, \lbrace \emptyset \rbrace \rbrace$, formed by two of them; consider the pairs formed by any such two pairs, or else mixed pairs formed by a singleton and any pair; and proceed \textit{ad infinitum}. Are all the sets obtained in this way distinct from one another? 
\end{exercise}

 \bigbreak
 Yes, all sets obtained in this way are distinct. 
    \begin{proof} 
    By the axiom of pairing, we can form $A$ and $B$ as given, and by the axiom of specification, they are the only such sets which contain their elements.  Suppose, to the contrary, that $A=B$. 
    \par If $A=B$, then for all $a \in A$, $a \in B$, and for all $b \in B$, $b \in A$. Now, either $A$ and $B$ are singletons, or they are pairs.
        \begin{itemize}
        \item \textit{$A$ and $B$ are singletons:} Say, $A = \{a\}$, and $B = \{b\}$. Thus, by the \textit{Axiom of Extension}, we have $a = b$. Implying that $A$ and $B$ were formed in the same way. 
        \item \textit{$A$ and $B$ are pairs:} Let $A = \{a, a'\}$, $B = \{b,b'\}$. Without loss of generality, suppose that $a = b$, and $a' = b'$. If this is the case, then by the \textit{Axiom of Extension}, again, we have that $a,b$ were obtained in the same fashion, as well as $a',b'$. But in this case, $A$ and $B$ were constructed in the same manner. 
        \end{itemize}
    Either way, we have a contradiction. Thus, $A$ and $B$ are formed distinctly. 
    \end{proof}

\newpage
\begin{mdframed}
\section{Unions and Intersections}
\end{mdframed}
Throughout these exercises we consider a arbitrary non-empty collection $\mathcal{C}$, of sets. For simplicity we will assume that $ \mathcal{C}= \{ A, B, C\}$ for arbitrary non-empty sets (unless specified) $A$, $B$, $C$ and will make liberal use of the notation $\{x: S(x)\}$, in-place of the more precises yet cumbersome notation $\{x \in \bigcup \mathcal{C}: S(x) \}$. 

\begin{exercise} We show the following: 
    \begin{align}
    A \cup \emptyset & = A \\
    A \cup B & = B \cup A \\
    A \cup (B \cup C) & = (A \cup B) \cup C\\
    A \cup A & = A \\
    A \subset B \iff A \cup B & = B 
    \end{align}
\end{exercise}

\begin{proof} ($\iff$) 
Since $\emptyset$ has no elements, for all $a \in \bigcup \mathcal{C}$, $a \notin \emptyset$ and we have, 
    \begin{align*}
    x \in A \cup \emptyset  = \lbrace x: x \in A \lor x \in \emptyset \rbrace & \iff x \in A \lor x \in \emptyset = \lbrace \rbrace \\
    & \iff x \in A 
    \end{align*}
Thus, $A \cup \emptyset = A$
\end{proof}

\begin{proof} ($\iff$)
\bigbreak
$$A \cup B = \lbrace x : x \in A \lor x \in B \rbrace = \lbrace x : x \in B \lor x \in A \rbrace = B \cup A$$
\end{proof}

\begin{proof} ($\iff$)
\bigbreak
\begin{equation*}
\begin{split}
x \in A \cup (B \cup C)  & \iff x \in A \lor x \in B \cup C \\
&\iff x \in A \lor x \in B \lor x \in C \\
& \iff x \in \lbrace x : x \in A \lor x \in B \rbrace \lor x \in C \\
& \iff x \in A \cup B \lor x \in C \\
& \iff x \in (A \cup B) \cup C
\end{split}
\end{equation*}

\end{proof}

\begin{proof} ($\iff$)
\bigbreak
$$ A \cup A = \lbrace x: x \in A \lor x \in A\rbrace = \lbrace x: x \in A \rbrace = A$$
\end{proof}


\begin{proof}
$ $\newline
($\Rightarrow$) We note that $A \subset B$ iff for all $x \in A$, $x \in B$. Thus, we have that $$x \in A \cup B = \{ x: x \in A \lor x \in B \} \Rightarrow x \in A \lor x \in B \Rightarrow x \in B$$ by the comments above. And likewise, $$x \in B \Rightarrow x \in B \lor x \in A \Rightarrow x \in \{ x: x \in A \lor x \in B \} \Rightarrow x \in A \cup B$$ That is, $A \cup B = B$.
$ $\newline
($\Leftarrow$)
Suppose $A \cup B = B$. Then, $$x \in A \Rightarrow x \in \{ x : x \in A \cup x \in B\} = A \cup B = B$$ That is, $A \subset B$.
\end{proof}

\setcounter{equation}{0}
\begin{exercise} We show the following: 
    \begin{align}
    A \cap \emptyset & = \emptyset \\
    A \cap B & = B \cap A \\
    A \cap (B \cap C) & = (A \cap B) \cap C \\
    A \cap A & = A \\
    A \subset B \iff A \cap B & = A \\
    \end{align}
\end{exercise}

\begin{proof} (1) Suppose that $A \neq \emptyset$, then
\bigbreak
$ $\newline
($\Rightarrow$)
    \begin{align*}
    x \in A \cap \emptyset = \{ x: x\in A \land x \in \emptyset \} & \Rightarrow x \in \emptyset \land x \in A \\
    & \Rightarrow x \in \emptyset
    \end{align*}

$ $\newline
($\Leftarrow$)
    \begin{align*}
    & (\emptyset \subset A) \land (\emptyset \subset \emptyset) \\
    & \Rightarrow \emptyset \subset A \cap \emptyset \\
    \end{align*}
\end{proof}

\begin{proof}(2) ($\iff$)
\bigbreak
$$A \cap B = \{ x: x\in A \land x\in B\} = \{ x: x \in B \land x \in A \} = B \cap A$$
\end{proof}

\begin{proof}(3) ($\iff$)
$ $\newline
\begin{align*}
x \in A \cap (B \cap C) & \iff x \in A \land x \in B \cap C = \{ x: x \in B \land x \in C \} \\
& \iff x \in A \land x \in B \land x \in C  \\
& \iff x \in \{x: x \in A \land x\in B\} \land x \in C \\
& \iff x \in A \cap B \land x \in C \\ 
& \iff x \in (A \cap B) \cap C
\end{align*}
\end{proof}

\begin{proof}(4) ($\iff$)
$ $\newline
$$A \cap A = \{x: x \in A \land x \in A \} = \{x: x \in A\} = A$$
\end{proof}

\begin{proof}(5)
$ $\newline
($\Rightarrow$) Suppose that $A,B \neq \emptyset$. We note that $A \subset B$ iff for all $x \in A$, $x \in B$; then,
$$x \in A \Rightarrow x \in B \Rightarrow x \in A \land x \in B \Rightarrow x \in A \cap B$$ And likewise,
$$x \in A \cap B = \{x: x\in A \land x \in B \} \Rightarrow x \in A \land x \in B \Rightarrow x \in A$$ That is, $A \cap B = A$. 
$ $\newline
($ \Leftarrow$)Suppose that $A \cap B = A$. Then, 
$$x \in A \Rightarrow x \in A \cap B = \{ x: x \in A \land x \in B\} \Rightarrow x \in A \land x \in B \Rightarrow x \in B$$ That is, $A \subset B$.
\end{proof}

\setcounter{equation}{0}
\begin{exercise} We wish show that $(A \cap B) \cup C = A \cap (B \cup C) \iff C \subset A$: We first show (1) in the following, noting that (2) was proved in the text;
$ $\newline
From page fifteen, 
    \begin{equation}
    A \cap (B \cup B) = (A \cap B) \cup (A \cap C)
    \end{equation}
and,
    \begin{equation}
    A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
    \end{equation}
\end{exercise}

\begin{proof} ($\Rightarrow$) 
\bigbreak
$ $\newline
Suppose that not all of $A$, $B$, $C$ are the emptyset. Then,
$$x \in A \cap (B \cup C) \Rightarrow x \in A \land x \in B \cup C$$ Now, either $x \in B$ or $x \in C$: 
\begin{equation*}
x \in B \land x \in A \Rightarrow x \in A \cap B \Rightarrow (A \cap B) \cup (A \cap C)
\end{equation*}

\begin{equation*}
x \in C \land x \in A \Rightarrow x \in A \cap C \Rightarrow (A \cap B) \cup (A \cap C)
\end{equation*}
$ $\newline
Either way, $x \in (A \cap B) \cup (A \cap C)$. To prove the reverse inclusion, we note that similar logic holds; either $x \in A \cap B$ or $x \in A \cap C$.
\end{proof}
\bigbreak

$ $\newline
Now, we show that $(A \cap B) \cup C = A \cap (B \cup C) \iff C \subset A$:
\begin{proof} 
\bigbreak 
$ $\newline 
($\Leftarrow$) 
\bigbreak
$ $\newline
Suppose that $C \subset A$. Then, for all $x \in C$, $x \in A$; By \textit{Exercise 4.1.5} and the proof above, we have the following:
\begin{equation}
(A \cap B) \cup C = (A \cup C) \cap (B \cup C) = A \cap (B \cup C) 
\end{equation}

$ $\newline 
($\Rightarrow$)
$ $\newline
Suppose that $(A \cap B) \cup C = A \cap (B \cup C)$. Then, 
\begin{equation*}
\begin{split}
x \in C & \Rightarrow x \in \{x: x \in A \cap B \lor x \in C \} \\
& = (A \cap B) \cup C \\
& = A \cap (B \cup C)
\end{split}
\end{equation*} by the assumption. Thus, 
\begin{equation*}
\begin{split}
x \in C & \Rightarrow x \in A \cap (B \cup C) \\
& \Rightarrow x \in A \land x \in B \cup C \\
& \Rightarrow x \in A
\end{split}
\end{equation*}
That is, $C \subset A$.
\end{proof}

\newpage
\begin{mdframed}
\section{Complements and Powers}
\end{mdframed}

$ $\newline
Throughout these exercises we assume that "all sets are subsets of one and the same set $\mathcal{E}$, and that all complements (unless otherwise specified) are formed relative to that $\mathcal{E}$" (Halmos). Likewise, we will often use the more convenient, yet less accurate notation $\{x: S(x)\}$ in place of $\{x \in \mathcal{E}: S(x)\}$

\setcounter{equation}{0}
\begin{exercise}We prove the following: 
    \begin{align}
    A - B & = A \cap B^{c} \\ 
    A \subset B & \iff A - B  = \emptyset \\
    A - ( A - B) & = A \cap B \\
    A \cap (A - C) & = (A \cap B) - (A \cap C)\\
    A \cap B & \subset (A \cap C) \cup (B \cap C^{c}) \\
    (A \cup C) \cap (B \cup C^{c}) & \subset A \cup B \\
    \end{align}
\end{exercise}


\begin{proof} (1) ($\iff$)
\bigbreak
\begin{equation*}
\begin{split}
A - B & = \{x \in \mathcal{E}: x \in A \land x \notin B \} \\
& \iff x \in A \land x \notin B \\
& \iff x \in A \land x \in B^c \\
& \iff x \in A \cap B^c
\end{split}
\end{equation*}

\end{proof}

\begin{proof} (2)
$ $\newline
$ $\newline
($\Rightarrow$) Suppose that $A - B \neq \emptyset$, but $A \subset B$; since $A \subset B$, if $x \in A$, $x \in B$. Thus, if $x \in A - B = \{ x \in \mathcal{E}: x \in A \land x \notin B\}$, $x \notin B$. However $x \in A$, which implies $x \in B$: A contradiction.  
$ $\newline
\bigbreak
$ $\newline
($\Leftarrow$) Suppose that $A - B = \emptyset$ and that there exists some $x \in A$ which is not in $B$, i.e. $A \not\subset B$. However this is a contradiction since $$x \in A \land x \notin B \Rightarrow x \in \{x \in \mathcal{E}: x \in A \land x \notin B \} = A - B$$ and yet $A -B = \emptyset$. 

\end{proof}

\begin{proof} (3) ($\iff$) 
\bigbreak
By the proof above, 
\begin{equation*}
\begin{split}
A - (A - B) & = A - (A \cap B^c) = \{x \in \mathcal{E}: x \in A \land x \notin A \cap B^c\} \\
& \iff x \in A \land x \notin A \cap B^c \\
& \iff x \in A \land x \notin B^c \\
& \iff x \in A \land x \in B \\
& \iff x \in \{x \in \mathcal{E}: x \in A \land x \in B\} = A \cap B
\end{split}
\end{equation*}
\end{proof}

\begin{proof} (4) ($\iff$)
\bigbreak
\begin{equation*}
\begin{split}
x \in A \cap (B - C) & \iff x \in A \land x \in (B-C) \\
& \iff x \in A \land x \in \{ x \in \mathcal{E}: x \in B \land x \notin C \} \\
& \iff x \in A \land x \in B \land x \notin C \\
& \iff x \notin \{ x \in \mathcal{E}: x \in A \land x \in C \} \land x \in A \cap B \\
& \iff x \notin A \cap C \land x \in A \cap B \\
& \iff x \in \{ x \in \mathcal{E}: x \notin A \cap C \land x \in A \cap B \} \\
& \iff x \in (A \cap B) - (A \cap C) 
\end{split}
\end{equation*}
\end{proof}

\setcounter{equation}{0}
\begin{proof} (5) ($\Rightarrow$) 
\bigbreak
Consider $C \in \bigcup \mathcal{C}$, as stated above. 
\begin{equation}
\begin{split}
x \in A \cap B & \Rightarrow x \in \{ x \in \mathcal{E}: x \in A \land x \in B \} \\
& \Rightarrow x \in A \land x \in B \\
& \Rightarrow (x \in A \land x \in B) \land (x \in C \lor x \in C^c) 
\end{split}
\end{equation}

\begin{equation}
\begin{split}
x \in C \land (1) & \Rightarrow x \in A \cap C \land x \in B \cap C
\end{split}
\end{equation}

\begin{equation}
\begin{split}
x \in C^c \land (1) & \Rightarrow x \in A \cap C^c \land x \in B \cap C^c
\end{split}
\end{equation}

$ $\newline
Thus, either way, $x \in (A \cap C)$ or $x \in (B \cap C^c)$, i.e. $x \in (A \cap C) \cup (A \cap C^c)$

\end{proof}

\setcounter{equation}{0}
\begin{proof} (6) ($\Rightarrow$)
\bigbreak
\begin{equation}
\begin{split}
x \in (A \cup C) \cap (B \cup C^c) & \Rightarrow x \in A \cup C \land x \in B \cup C^c \\
&  \Rightarrow (x \in A \lor x \in C) \land (x \in B \lor x \in C^c) 
\end{split}
\end{equation}
$ $\newline
We note that either $x \in C$, or $x \in C^c$: 
\begin{equation}
\begin{split}
x \in C \land (1) & \Rightarrow x \notin C^c \land (x \in B \lor x \in A) \\
& \Rightarrow x \in A \cup B
\end{split}
\end{equation}

\begin{equation}
\begin{split}
x \in C^c \land (1) & \Rightarrow x \notin C \land (x \in A \lor x \in B) \\
&\Rightarrow x \in A \cup B
\end{split}
\end{equation}

$ $\newline
Either way, $x \in A \cup B$.
\end{proof}

\begin{exercise} We show that $\mathscr{P}(E) \cap \mathscr{P}(F)= \mathscr{P}(E \cap F)$:
\end{exercise}

    \begin{proof} 
    Let $E$, $F$ be sets such that $E$, $F \subset \mathcal{E}$ ; via \textit{Axiom of Powers}, $\mathscr{P}(E)$, $\mathscr{P}(F)$; specifically, from the discussion in Halmos\footnote{Halmos, P. "\textit{Naive Set Theory}". pg 19}, $\mathscr{P}(E) =  \{X: X \subset E\}$, and $\mathscr{P}(F) =  \{X: X \subset F\}$. Then, we have the following: 
        \setcounter{equation}{0}
        \begin{equation*}
            \begin{split}
            X \in \mathscr{P}(E) \cap \mathscr{P}(F) & \iff X \in \mathscr{P}(E) \land X \in \mathscr{P}(F) \\
            & \iff X \in \{Y: Y \subset E \land Y \subset F \} \\
            & \iff X \subset E \land X \subset F \\
            & \iff \forall x( x \in X \Rightarrow (x \in E \land x \in F) )\\
            & \iff \forall x \in X, x \in E \cap F \\
            & \iff X = \{x \in \mathcal{E}: x \in X \}  \subset E \cap F \\
            & \iff X \in \{Y: Y \subset E \cap F \} \\
            & = \mathscr{P}(E \cap F)
            \end{split}
        \end{equation*}
    \end{proof}

\begin{exercise} We show that $\mathscr{P}(E) \cup \mathscr{P}(F) \subset \mathscr{P}(E \cup F)$:
\end{exercise}

    \begin{proof}
    Let $E$, $F$ be given as in the discussion of proof \textit{5.2.0}. We first claim that if $A$, $B$ are sets, then ($x \subset A \lor x \subset B \Rightarrow x \subset A \cup B$). Indeed; if $x \subset A$, then $x \subset A \cup B$ and likewise, $x \subset B$ implies $x \subset B \cup A$. With this in mind, we have the following: 
        \begin{equation*}
            \begin{split}
            X \in \mathscr{P}(E) \cup \mathscr{P}(F) & = \{X: X \in \mathscr{P}(E) \lor X \in \mathscr{P}(F) \} \\
            & \iff X \in \mathscr{P}(E) \lor X \in \mathscr{P}(F) \\
            & \iff X \in \{Y: Y \subset E \} \lor X \in \{Y: Y \subset F \} \\
            & \iff X \in \{Y: Y \subset E \lor Y \subset F \} \\
            & \Rightarrow X \in \{Y: Y \subset E \cup F \} \\ 
            & = \mathscr{P}(E \cup F)
            \end{split}
        \end{equation*}
    \end{proof}

\begin{exercise} We show that $\bigcap_{X \in \mathcal{C}} \mathscr{P}(X) = \mathscr{P}(\bigcap_{X \in \mathcal{C}} X)$:
\end{exercise}

    \begin{proof} Let $\mathcal{C}$ be a non-empty collection of sets. 
        \bigbreak
        ($\Rightarrow$)
            \begin{equation*}
                \begin{split}
                z \in \bigcap_{X \in \mathcal{C}} \mathscr{P}(X) & \Rightarrow (\forall X \in \mathcal{C})(z \in \mathscr{P}(X)) \\
                & \Rightarrow (\forall X \in \mathcal{C})(\{z\} \subset \mathscr{P}(X)) \\
                & \Rightarrow (\forall X \in \mathcal{C})(z \in X) \\
                & \Rightarrow z \in \bigcap_{X \in \mathcal{C}} X \\
                & \Rightarrow \{z\} \subset \bigcap_{X \in \mathcal{C}} X \\
                & \Rightarrow z \in \mathscr{P} (\bigcap_{X \in \mathcal{C}} X)
                \end{split}
            \end{equation*}
    \bigbreak
    ($\Leftarrow$)
            \begin{equation*}
                \begin{split}
                z \in \mathscr{P}(\bigcap_{X \in \mathcal{C}} X) & \Rightarrow z \in \{Y: Y \subset \bigcap_{X \in \mathcal{C}} X\} \\
                & \Rightarrow z \subset \bigcap_{X \in \mathcal{C}} X \\
                & \Rightarrow (\forall X \in \mathcal{C})(z \subset X) \\
                & \Rightarrow (\forall X \in \mathcal{C})(\forall v \in z)(v \in X) \\ 
                & \Rightarrow (\forall X \in \mathcal{C})(\forall v \in z)(\{v\} \subset \mathscr{P}(X))\\
                & \Rightarrow (\forall X \in \mathcal{C})(\forall v \in z)(v \in \mathscr{P}(X))\\
                & \Rightarrow (\forall X \in \mathcal{C})(z \in \mathscr{P}(X)) \\
                & \Rightarrow z  \in \bigcap_{X \in \mathcal{C}} \mathscr{P}(X)
                \end{split}
            \end{equation*}
    And this completes the proof. 
    \end{proof}

\begin{exercise}We show that $\bigcup_{X \in \mathcal{C}} \mathscr{P}(X) \subset \mathscr{P}(\bigcup_{X \in C} X)$:
\end{exercise}

    \begin{proof}
    Let $\mathcal{C}$ be a collection of sets. A common fact used in the following proof is that if $x \in \mathscr{P}(X)$, then $x \subset X$ for any set $X$. This is indeed true, since $\mathscr{P}(X)= \{Y: Y \subset X\}$. With this in mind, we have
        \begin{equation*}
                \begin{split}
                z \in \bigcup_{X \in \mathcal{C}} \mathscr{P}(X) & \Rightarrow (\exists Y \in \mathcal{C})(z \in \mathscr{P}(Y)) \\
                & \Rightarrow z \subset Y \in \mathcal{C} \\
                & \Rightarrow z \subset \{x: x \in X (\forall X \in \mathcal{C}) \} = \bigcup_{X \in \mathcal{C}}X \\
                & \Rightarrow (\forall s \in z)(s \in \bigcup_{X \in \mathcal{C}}X) \\
                & \Rightarrow (\forall s \in z)(s \in \mathscr{P}(\bigcup_{X \in \mathcal{C}}X)) \\ 
                & \Rightarrow z \in  \mathscr{P}(\bigcup_{X \in \mathcal{C}}X)
                \end{split}
        \end{equation*} 
    Which completes the proof.
    \end{proof}

\begin{exercise}We show that $\bigcap_{X \in \mathscr{P}(E)}X = \emptyset$:
\end{exercise}

    \begin{proof}
    Let $E$ be a set and consider $\mathscr{P}(E) = \{Y: Y \subset E\}$. We note that this is non-empty because $\emptyset \in \Pwr (E)$, since $\emptyset$ is a subset of every set. We also note that the statement ($x \in \emptyset \Rightarrow x \in \bigcap_{X \in \mathscr{P}(E)}X$) is vacuously satisfied since $\emptyset$ has no elements. Thus, we only show the forward inclusion:
    \bigbreak
    ($\Rightarrow$)
        \begin{equation*}
            \begin{split}
                x \in \bigcap_{X \in \mathscr{P}(E)}X & \Rightarrow (\forall X \in \Pwr(E))(x \in X) \\
                & \Rightarrow x \in \emptyset \in \Pwr (E)
            \end{split}
        \end{equation*} And this completes the proof.
    \end{proof}


\begin{exercise}We show that ($E \subset F \Rightarrow \Pwr(E) \subset \Pwr(F)$):
\end{exercise}

    \begin{proof}
    Suppose that $E \subset F$ for sets $E$, $F$. Then, we have the following: 
        \begin{align*}
        e \in \Pwr (E) & \Rightarrow e \subset E &\\
        & \Rightarrow (\forall x \in e)(x \in E) &\\
        & \Rightarrow (\forall x \in e)(x \in F)  &(\text{by Assumption})\\ 
        & \Rightarrow e \subset F &\\
        & \Rightarrow e \in \Pwr(F) &(\text{by Definition}) \\
        \end{align*} Which completes the proof. 
    \end{proof}

\begin{exercise}We show that $E = \bigcup \Pwr(E) = \bigcup_{X \in \Pwr(E)}X$:
\end{exercise}

    \begin{proof}
    Let $E$ be a set. Then, we have the following: 
    \bigbreak
    ($\Leftarrow$)
        \begin{align*}
        x \in \bigcup \Pwr(E) & \Rightarrow (\exists Y \in \Pwr(E))(x \in Y) \\
        & \Rightarrow x \in Y \subset E \\ 
        & \Rightarrow x \in E 
        \end{align*}
    \bigbreak
    ($\Rightarrow$)
        \begin{align*}
        x \in E & \Rightarrow \{x\} \in \Pwr(E) \\
        & \Rightarrow x \in \{x\} \in \Pwr(E) \\
        & \Rightarrow x \in \bigcup \{X: X \in \Pwr(E) \} \\
        & = \bigcup \Pwr(E) \\
        \end{align*}
    Which completes the proof. 
    \end{proof}

\begin{exercise} We show that $\mathscr{P}\Big(\bigcup E\Big)$ is a set that includes $E$, typically, as a proper subset. 
\end{exercise}
    \begin{proof} Indeed, $\mathscr{P}\Big(\bigcup E\Big) = \mathscr{P}(E) = \{X \in E: X \subset E\}$. If $E$ is non-empty, then it is clear that $E \subsetneq \mathscr{P}(E)$. However, if $E = \emptyset$, then $\Pwr(E) = \emptyset$ and $E = \Pwr(E)$. 
    \end{proof}


\newpage
\begin{mdframed}
\section{Ordered Pairs}
\end{mdframed}

Throughout this section, we will consider $A$, $B$, $C$, $X$, $Y$ to be any sets, and will use the notation 
$\{x: S(x)\}$ in place of the more accurate, yet cumbersome notation $\{x \in \bigcup \mathcal{C}: S(x)\}$.
\bigbreak

\begin{exercise} We show the following: 
    \setcounter{equation}{0}
    \begin{align}
    (A \cup B) \times X & = (A \times X) \cup (B \times X) \\
    (A \cap B) \times (X \cap Y) & = (A \times X) \cap (B \times Y) \\
    (A - B) \times X & = (A \times X) - (B \times X)\\
    (A = \emptyset \lor B = \emptyset) & \iff (A \times B = \emptyset)\\
    (A \subset X) \land (B \subset Y) & \iff (A \times X \subset X \times Y) 
    \end{align}

\end{exercise}
\begin{proof} (1)
\bigbreak ($\Rightarrow$)
\begin{align*}
(x,y) \in (A \cup B) \times X & \iff (x,y) \in \{(a,b): a \in A \cup B \land b \in X \} \\
& \iff x \in A \cup B \land y \in X \\
& \iff (x \in A \lor x \in B) \land y \in X \\
(\text{by Distributivity}) \quad & \iff (x \in A \land y \in X) \lor (x\in B \land y\in X) \\
& \Rightarrow (x \in A \cup X \land y \in A \cup X) \lor (x \in B \cup X \land y \in B \cup X) \\
(\text{by Remarks in Text}) \quad & \Rightarrow  \{x, \{x,y\} \} \subset \mathscr{P}(A \cup X) 
\lor \{x, \{x,y\} \} \subset \Pwr(B \cup X) \\
& \iff (x,y) \in \Pwr(\Pwr(A \cup X)) \lor  (x,y) \in \Pwr(\Pwr(B \cup X)) \\
(\text{by Remarks in Text}) \quad & \iff (x,y) \in (A \times X) \cup (B \times X) \\
\end{align*}

\bigbreak ($\Leftarrow$)
\begin{align*}
(x,y) \in (A \times X) \cup (B \times X)  & \iff (x,y) \in (A \times X) \lor (x,y) \in (B \times X) \\
(\text{by Definition}) \quad & \Rightarrow (x \in A \land y \in X) \lor (x \in B \land y \in X) \\
& \iff (x \in A \lor x \in B) \land y \in X \\
& \iff x \in A \cup B \land y \in X \\
& \Rightarrow x \in (A \cup B) \cup X \land y \in (A \cup B) \cup X \\
& \Rightarrow \{ \{x\}, \{x,y\} \} \subset \Pwr((A \cup B) \cup X) \\
& \iff  \{ \{x\}, \{x,y\} \} \in \Pwr(\Pwr((A \cup B) \cup X)) \\
& \Rightarrow (x,y) \in (A \cup B) \times X\\
\end{align*}
Which completes the proof.
\end{proof}
\bigbreak

\begin{proof}(2)
\bigbreak
($\Rightarrow$)
\begin{align*}
(c,d) \in (A \cap B) \times (X \cap Y) & \iff c \in A \cap B \land d \in X \cap Y \\
& \iff (c \in A \land c \in B) \land (d \in X \land d \in Y) \\
(\text{by Commutativity}) \quad & \iff (c \in A \land d \in X) \land (c \in B \land d \in Y) \\
& \Rightarrow (c \in A \cup X \land d \in A \cup X) \land (c \in B \cup Y \land d \in B \cup Y)\\
& \Rightarrow \{ \{c\},\{c,d\} \} \subset \Pwr(A \cup X) \land \{ \{c\},\{c,d\} \} \subset \Pwr(B \cup Y) \\
& \iff (c,d) \in \Pwr(\Pwr(A \cup X)) \land (c,d) \in \Pwr(\Pwr(B \cup X)) \\
& \iff (c,d) \in A \times X \land (c,d) \in B \times X \\
& \iff (c,d) \in (A \times  X) \cap (B \times X) \\
\end{align*}
\bigbreak
($\Leftarrow$)
\begin{align*}
(c,d) \in (A \times X) \cap (B \times X) & \iff (c,d) \in (A \times X) \land (c,d) \in (B \times X)\\
& \iff (c \in A \land d \in X) \land (c \in B \land d \in X) \\
(\text{by Commutativity}) \quad & \iff (c \in A \land c \in B) \land d \in X  \\
& \iff (c \in (A \cap B)) \land d \in X \\
& \Rightarrow c \in (A \cap B) \cup X \land d \in (A \cap B) \cup X \\
& \Rightarrow \{ \{c\}, \{c,d\} \} \subset \Pwr((A \cap B) \cup X) \\
& \Rightarrow (c,d) \in \Pwr(\Pwr((A \cap B) \cup X)) \\
& \iff (c,d) \in (A \cap B) \times X \\
\end{align*}
Which completes the proof.
\end{proof}
\bigbreak

\begin{proof}(3)
\bigbreak ($\Rightarrow$)
\begin{align*}
(c,d) \in (A - B) \times X & \iff c \in (A-B) \land d \in X \\
& \iff (c \in A \land c \notin B) \land d \in X \\
& \iff (c \in A \land d \in X) \land (c \notin B \land d \in X) \\
(\text{since $c \notin B$} ) \quad & \Rightarrow (c,d) \in A \times X \land (c,d) \notin B \times X\\
& \iff (c,d) \in (A \times X)-(B \times X)\\
\end{align*}
\bigbreak ($\Leftarrow$)
\begin{align*}
(c,d) \in (A \times X)-(B \times X) & \iff (c,d) \in (A \times X) \land (c,d) \notin (B \times X)\\
& \Rightarrow (c \in A \land d \in X) \land (c \notin B \lor d \notin X) \\
(\text{since ($d \in X \land d \notin X$, $\rightarrow \leftarrow$)}) \quad & \Rightarrow (c \in A \land d \in X) \land (c \notin B) \\
&\iff (c \in A \land c \notin B) \land d \in X \\
& \iff c \in (A - B) \land d \in X\\
& \Rightarrow \{ \{c\}, \{c,d\} \} \subset \Pwr((A - B) \cup X) \\
& \iff \{ \{c\}, \{c,d\} \} \in \Pwr(\Pwr((A - B) \cup X)) \\
& \iff (c,d) \in (A - B) \times X \\
\end{align*}
Which completes the proof. 
\end{proof}
\bigbreak

\begin{proof}(4)
\bigbreak ($\Rightarrow$) Suppose, without loss of generality, that $A = \emptyset$. Then, $A$ contains no elements. Consider $A \times B = \{(a,b): a \in A \land b \in B\}$. Then, since there are no $a \in A$, $\{(a,b): x \in A \land x \in B\} = \emptyset$.
\bigbreak ($\Leftarrow$) Suppose to the contrary that $A\neq \emptyset$ and $B\neq \emptyset$, but $A \times X = \emptyset$. Since $A\neq \emptyset$ and $B\neq \emptyset$, there exists some $a \in A$ and $b \in B$. And so, $\{ \{a\}, \{a,b\}\} \subset \Pwr(A \cup B)$ and further we have $(a,b) \in A \times B$. However, this is a contradiction since we assumed $A \times B = \emptyset$.
\end{proof}
\bigbreak

\begin{proof} (5)
\bigbreak ($\Rightarrow$) 
We show that if $A \subset X$ and $B \subset Y$, then $A \times B \subset X \times Y$. Since $A \subset X$, for all $a \in A$, $a \in X$ and likewise for $B$.
\begin{align*}
(c,d) \in A \times B & \iff c \in A \land d \in B \\
(\text{by Assumption}) \quad & \Rightarrow c \in X \land d \in Y \\
& \Rightarrow c \in X \cup Y \land d \in X \cup Y \\
& \Rightarrow \{ \{c\}, \{c,d\}\} \subset \Pwr(X \cup Y) \\
& \Rightarrow (c,d) \in \Pwr(\Pwr(X \cup Y)) \\
& \iff (c,d) \in X \times Y \\
\end{align*}
\bigbreak ($\Leftarrow$) Suppose that $A \times X \neq \emptyset$. And that$A \times B \subset X \times Y$. We show that $A \subset X$ and $B \subset Y$.
\begin{align*}
a \in A \land b \in B & \Rightarrow \{ \{a\},\{a,b\}\} \in \Pwr(\Pwr(A \cup B)) \\
& \iff (a,b) \in A \times B \\
& \Rightarrow (a,b) \in X \times Y \\
& \Rightarrow (a,b) \in \{(x,y): x \in X \land y \in Y\} \\
& \Rightarrow a \in X \land b \in Y \\
\end{align*}
Which completes the proof.
\end{proof}


\newpage
\begin{mdframed}
\section{Relations}
\end{mdframed}


\begin{exercise} We show that for each of \textbf{symmetric}, \textbf{reflexive}, and \textbf{transitive} properties, there exists a relation that does not have that property but does have the other two. 
\end{exercise}
\begin{proof} Let $X$ be a set. We first show that if $X = \emptyset$, then any relation in $X$ is an equivalence relation: 
    \begin{Lemma} \renewcommand{\qedsymbol}{} \normalfont Let $X = \emptyset$. Then, by a previous theorem, we have $X \times X =\emptyset$. And so, if $R$ is a relation in $X$, $R = \emptyset$. However, $R$ is an equivalence relation, since all statements are vacuously satisfied. 
    \end{Lemma}
$ $\newline Likewise, suppose that $X = \{a\}$; i.e. $X$ is a singleton. We claim, also that any relation in $X$ is an equivalence relation: 
    \begin{Lemma} \renewcommand{\qedsymbol}{} \normalfont Let $X = \{a\}$. Then, by the comments of the previous section, we have $X \times X= \{(a,a)\}$. Thus, since $R$ is the set $\{(a,b): a \in X \land b \in X\}$ it follows that $R = \{(a,a)\}$ for any relation.\footnote{see Halmos pg. 27} It is easy to verify that the transitive condition is vacuously satisfied for $R$. And, it is symmetric, since $(a,a) = (a,a)$. And, clearly, $R$ is reflexive. Thus, $R$ is an equivalence relation.
    \end{Lemma}
$ $\newline We also show that for $X = \{a,b\}$ each of which is distinct, there does not exist a relation, which is symmetric, reflexive, but not transitive: 
    \begin{Lemma} \renewcommand{\qedsymbol}{} \normalfont Let $X = \{a,b\}$. Then, the relation $\mathcal{R}$ in question must contain $\{(a,a),(b,b)\} = I$. However, it is easy to verify that this is an equivalence relation.\footnote{see the above lemma} Thus, we must add an element of $X \times X$ which maintains its symmetry, yet is not transitive. However, this is not possible since either way $(a,b)$, $(b,a)$ must be in $\mathcal{R}$ and so we would have $\mathcal{R} = \{(a,a), (b,b), (a,b), (b,a)\}$.And, this is an equivalence relation since $(x,x) \in \mathcal{R}$ for all $x \in X$ and, by the comments above, $ \mathcal{R}$ is symmetric, \textit{as well as} transitive.\footnote{this is left to the reader}
    \end{Lemma}
$ $\newline Thus, let $X = \{ a, b, c ....\}$, for distinct elements. We first show the relational properties which include reflexivity: \bigbreak
Let $\mathcal{R}$ be a relation in $X$ which is reflexive. Then, we must have $I = \{(x,x): x \in X\} \subset \mathcal{R}$, by definition. Thus, we show a representation of $\mathcal{R}$ which is transitive, but not symmetric, and symmetric but not transitive:
        \begin{itemize}
        \item Consider $\mathcal{R} = I \cup \{(a,b), (b,a), (b,c), (c,b)\}$. Then, this relation is symmetric, since $(x,x) = (x,x)$ for all $x \in \mathcal{R}$ and $\{(a,b), (b,a), (b,c), (c,b)\} \subset \mathcal{R}$. However, $\mathcal{R}$ is not transitive, since $(a,b) \in \mathcal{R}$ and $(b,c) \in \mathcal{R}$ and yet $(a,c) \notin \mathcal{R}$.
        \item Consider $\mathcal{R} = I \cup \{(a,b)\}$. Then, $\mathcal{R}$ is transitive; note, we only need to check $(a,b)$, $(a,a)$, $(b,b)$ for transitivity, since they are the only ordered pairs which share a first, or second coordinate, where only $(a,a)$, or $(a,b)$ come first. Correctly, $(a,b) \in \mathcal{R}$ and $(b,b) \in \mathcal{R}$ implies $(a,b) \in \mathcal{R}$; $(a,a) \in \mathcal{R}$ and $(a,b) \in \mathcal{R}$ implies $(a,b) \in \mathcal{R}$. However, $\mathcal{R}$ is not symmetric: $(a,b) \in \mathcal{R}$, however, $(b,a) \notin \mathcal{R}$.
        \end{itemize}
$ $\newline Finally, we show the relation in $X$ which is not reflexive. Let $X$ be given as above: 
        \begin{itemize}
        \item Consider $\mathcal{R} = \{(a,b), (b,a), (a,a), (b,b)\} \subset X \times X$. This is symmetric since $(x,x) = (x,x)$ for all $x \in X$ and $\{(a,b),(b,a)\} \subset \mathcal{R}$. It is, also, reflexive since $(a,b) \in \mathcal{R}$ and $(b,a) \in \mathcal{R}$ implies $(a,a) \in \mathcal{R}$; likewise, $(b,a) \in \mathcal{R}$ and $(a,b) \in \mathcal{R}$ implies $(b,b) \in \mathcal{R}$.\footnote{the others follow} However, $\mathcal{R}$ is not reflexive since $c \in X$, yet $(c,c) \notin \mathcal{R}$. 
        \end{itemize}
\end{proof}
\bigbreak

\begin{exercise} We show that the set of all equivalence classes, $X/\mathcal{R}$, is indeed a set. 
\end{exercise}
\begin{proof} Let $\mathcal{R}$ be an equivalence relation on a set $X$. We show that $X/ \Rcal \subset \mathscr{P}(X)$: 
    \begin{align*}
    z \in X/\Rcal & \Rightarrow (\exists x \in X)(z = \{x/\Rcal \} = \{y \in X: (x,y) \in \Rcal\} \subset X) \\
    & \Rightarrow z \in \mathscr{P}(X) \\
    \end{align*}
Which completes the proof. 
\end{proof}

\newpage
\begin{mdframed}
\section{Functions}
\end{mdframed}

\begin{exercise} 
We show the special cases in which the projections are 1-1.
\end{exercise}
    \begin{proof} Without loss of generality, we only consider $g:X \times Y \rightarrow Y$, the range projection. 
        \begin{itemize}
        \item We first note that if $X$, $Y$ have a pair or more of distinct elements, then $g$ is not 1-1:
            \begin{lemma} Suppose $X$, $Y$, have more than a pair of distinct elements, then $g$ is not 1-1: To see this, let $\{a,b\} \subset X$, and $\{c,d\}\subset Y$, then $\{(a,c), (a,d), (b,c), (b,d)\} \subset X \times Y$. If we suppose $g$ is one-to-one, then $g((a,c)) = g((b,d))$ implies $(a,c) = (b,d)$. But this is a contradiction, since $a=b$ and yet $a$, $b$ are distinct. \end{lemma}
        \item Next, if $X = \{x\}$ and $Y = \{y\}$, then we claim $g$ is 1-1.
            \begin{lemma} Let $X = \{x\}$ and $Y = \{y\}$; then, $X \times Y = \{(x,y),(y,x)\}$. Upon inspection, we see that $g$ is 1-1: if $(x,y) \neq (y,x)$, then $y \neq x$ and $y = g((x,y)) \neq x = g((y,x)$. We note that this covers the case in which $x=y$.  
            \end{lemma}
        \item Next, we show that if either $X$ or $Y$ is a singleton and the other is an arbitrary set, $g$ is one-to-one. 
            \begin{lemma}
            Suppose, without loss of generality, that $X$ is the singleton. Then either $Y =\emptyset$ or $Y \neq \emptyset$. If $Y=\emptyset$, then $X \times Y = \emptyset$, by previous exercise; which is trivially 1-1. Else, we assume $Y$ has more than a pair of distinct elements. Since $X = \{x\}$ for some $x$, it follows that $\{(a,b): a\in X \land b \in Y\} = \{(x,b): b \in Y\}$, which means $g$ is 1-1. 
            \end{lemma}
        \item Lastly, if $X = Y = \emptyset$, then all conditions are vacuously satisfied, and so $g$ is 1-1. 
        \end{itemize}
    \end{proof}
\begin{exercise} We show that $Y^{\emptyset}$ has exactly one element, namely $\emptyset$, whether $Y$ is empty or not; i.e. $Y^\emptyset = \{\emptyset \}$.
\end{exercise}
    \begin{proof} Suppose that $Y$ is a set. Consider $f = Y^\emptyset$. From page thirty, and by a previous theorem, we have $f \subset \mathscr{P}(\emptyset \times Y) = \mathscr{P}(\emptyset) = \{\emptyset\}$, where $f$ is a set of elements which are ordered pairs. From the comments in section seven, $\emptyset$ is a set of ordered pairs. It follows that $f = \{\emptyset\}$. 
    \end{proof}

\begin{exercise} We show that if $X \neq \emptyset$, then $\emptyset^X$ is empty; i.e. $\emptyset^X = \emptyset$.
\end{exercise}
    \begin{proof}
    Suppose that there is some function $f \in \emptyset^X$. Then, for all $x \in X$, there exists some $b \in \emptyset$ such that $(x,b) \in f$. However, this is not true, since $\emptyset$ contains no elements. Thus, $\emptyset^X = \emptyset$.
    \end{proof}

\newpage
\begin{mdframed}
\section{Families}
\end{mdframed}

\begin{exercise} After the comments on page thirty-five, we formulate and prove a generalized version of the commutative law for unions.
\end{exercise}
    \begin{proposition} Let $K$ be an arbitrary, non-empty set, and let $p \in \normalfont\text{Aut}(K^K)$ be an element of the set of one-to-one and onto functions from $K$ to $K$. We note that in the current notation this means that $p$ is the family and $\{p_i\}$ denotes the values of $p$ evaluating some $i \in K$. Let $\{A_k\}$ be a family of functions with domain $K$. We claim that $\bigcup_{k \in K} A_k = \bigcup_{i \in K} A_{p_i}$.
    \end{proposition}
    
\begin{proof} 
\bigbreak $ $\newline  ($\Rightarrow$)
    \begin{align*}
    x \in \bigcup_{k \in K} A_k & \Rightarrow (\exists k_0 \in K)(x \in A_{k_0}) \\
    (\text{since $p$ is onto}) \quad& \Rightarrow (x \in A_{k_0}) \land (\exists s \in K)(k_0 = p_s) \\
    & \Rightarrow x \in A_{k_0} = A_{p_s} \\ 
    & \Rightarrow x \in \bigcup_{i \in K} A_{p_i} \\
    \end{align*}

\bigbreak $ $\newline ($\Leftarrow$) 
    \begin{align*}
    x \in \bigcup_{i \in K} A_{p_i} & \Rightarrow (\exists s \in K)(x \in A_{p_s})\\
    (\text{since $p_s \in K$ and onto}) \quad & \Rightarrow (x \in A_{p_s}) \land (\exists k_0 \in K)(p_s = k_0) \\
    & \Rightarrow x \in A_{p_s} = A_{k_0}\\
    & \Rightarrow x \in \bigcup_{k \in K} A_k \\
    \end{align*}
Which completes the proof.
\end{proof}

To illustrate the previous proof, consider $K = \{0,1\}$ and 
$p_i = \begin{cases}
1 & i = 0 \\
0 & i = 1 \\
\end{cases}$; it is easy to show that $p$ is 1-1 and onto. From the statement above, we have
    \begin{align}
    \bigcup_{k \in K} A_k & = A_0 \cup A_1 \\
    \bigcup_{i \in K} A_{p_i} & = A_{p_0} \cup A_{p_1} = A_1 \cup A_0
    \end{align}
    
\setcounter{equation}{0}    
\begin{exercise} We show that if both $\{A_i\}$ and $\{B_i\}$ are families of sets, with domains $I$, $J$, then 
    \begin{align}
    \Big( \bigcup_i A_i \Big) \cap \Big(\bigcup_j B_j \Big) = \bigcup_{i,j}(A_i \cap B_j) \\
    \Big( \bigcap_i A_i \Big) \cup \Big( \bigcap_j B_j \Big) = \bigcap_{i,j}(A_i \cup B_j)
    \end{align}
Where the symbols such as $\bigcap_{i,j}$ mean $\bigcap_{(i,j) \in I \times J}$
\end{exercise}

\begin{proof} (1) 
\bigbreak $ $\newline ($\iff$)
    \begin{align*}
    x \in \Big( \bigcup_i A_i \Big) \cap \Big(\bigcup_j B_j \Big) & \iff x \in \Big( \bigcup_i A_i \Big) \land x \in \Big(\bigcup_j B_j \Big) \\
    & \iff (\exists i_0 \in I)(x \in A_{i_0}) \land (\exists j_0 \in J)(x \in B_{j_0}) \\
    & \iff (\exists (i_0,j_0) \in I \times J)(x \in (A_{i_0} \cap B_{j_0}) )\\
    & \iff x \in \bigcup_{i,j}(A_i \cap B_j) \\ 
    \end{align*}
\end{proof}

\begin{proof} (2) 
\bigbreak $ $\newline ($\iff$)
    \begin{align*}
    x \in \Big( \bigcap_i A_i \Big) \cup \Big( \bigcap_j B_j \Big) & \iff x \in \Big( \bigcap_i A_i \Big) \lor x \in \Big( \bigcap_j B_j \Big) \\
    & \iff (\forall i \in I)(x \in A_i) \lor (\forall j \in J)(x \in B_j) \\
    & \iff (\forall i \in I)(\forall j \in J)(x \in A_i \lor x \in B_j) \\
    & \iff (\forall i \in I)(\forall j \in J)(x \in A_i \cup x \in B_j) \\
    & \iff (\forall (i,j) \in I\times J) (x \in (A_i \cup B_j)) \\
    & \iff x \in \bigcap_{(i,j) \in I \times J} (A_i \cup B_j)\\
    \end{align*}
\end{proof}

\setcounter{equation}{0}
\begin{exercise} Let $\{A_i\}$, $\{B_j\}$ be families of sets with domains $I \neq \emptyset$, $J \neq \emptyset$, respectively. We show that 
    \begin{align}
    \Big( \bigcup_i A_i \Big) \times \Big( \bigcup_j B_j \Big) &= \bigcup_{i,j} (A_i \times B_j) \\
    \Big( \bigcap_i A_i \Big) \times \Big( \bigcap_j B_j \Big) &= \bigcap_{i,j} (A_i \times B_j)
    \end{align}
\end{exercise}

\begin{proof} (1)
\bigbreak $ $\newline ($\iff$)
    \begin{align*}
    (a,b) \in \Big( \bigcup_i A_i \Big) \times \Big( \bigcup_j B_j \Big) & \iff a \in \bigcup_i A_i \land b \in \bigcup_j B_j \\
    & \iff (\exists i_0 \in I)(\exists j_0 \in J)(a \in A_{i_0} \land b \in B_{j_0}) \\
    & \iff (\exists (i_0,j_0) \in I \times J)((a,b) \in A_{i_0} \times B_{j_0}) \\
    & \iff (a,b) \in \bigcup_{(i,j) \in I \times J} (A_i \times B_j) \\
    \end{align*}
\end{proof}

\begin{proof} (2) Suppose that for each $i \in I$, $A_i \neq \emptyset$ and for each $j \in J$, $B_j \neq \emptyset$.
\bigbreak $ $\newline ($\iff$)
    \begin{align*}
    (a,b) \in \Big( \bigcap_i A_i \Big) \times \Big( \bigcap_j B_j \Big) & \iff a \in \bigcap_i A_i \land b \in \bigcap_j B_j \\
    & \iff (\forall i \in I)(a \in A_i) \land (\forall j \in J)(b \in B_j) \\
    & \iff (\forall i \in I)(\forall j \in J)(a \in A_i \land b \in B_j)\\
    & \iff (\forall i \in I)(\forall j \in J)( (a,b) \in A_i \times B_j ) \\
    & \iff (\forall (i,j) \in I \times J)( (a,b) \in A_i \times B_j ) \\
    & \iff (a,b) \in \bigcap_{i,j} A_i \times B_j \\
    \end{align*}
\end{proof}

\begin{exercise} Suppose that for each $i \in I$, $X_i$ is non-empty. Consider the family of sets $\{X_i\}$ with domain $I$. We show that $\bigcap_i X_i \subset X_j \subset \bigcup_i X_i$ for each index $j \in I$. 
\end{exercise}

\begin{proof} Let $\{X_i\}$ be stated as above, and let $j \in I$ be arbitrary. 
    \begin{align*}
    x \in \bigcap_i X_i & \Rightarrow (\forall i \in I)(x \in X_i) \\
    & \Rightarrow x \in X_j \quad (\text{since $j \in I$})\\
    \end{align*}
    Which proves the first inclusion. For the second, suppose $j \in I$ is arbitrary, then we have the following: 
    \begin{align*}
    x \in X_j & \Rightarrow x \in \bigcup_j X_j \\
    & \Rightarrow x \in \Big( \bigcup_j X_j \cup \bigcup_{z \in I-J} X_z \Big)\\
    & \Rightarrow x \in \bigcup_{i} X_i \\
    \end{align*}
    Which prove the second inclusion. 
\end{proof}

\begin{exercise} We show the minimality condition of intersection and unions: (1) That is, if $X_j \subset Y$ for each index $j$ and some set $Y$, then $\bigcup_i X_i \subset Y$ and that it is unique; (2) Likewise, if $Y \subset \bigcap_j X_j$ for each index $j$ and some set $Y$, then $Y \subset \bigcap_i X_i$ and it is unique.
\end{exercise}

\begin{proof} (1) 
    Suppose that $\{X_i\}$ is a family of sets with domain $I$, such that $j \in I$, and let $Y$ be a set. Then, we have the following: 
    \begin{align*}
    (\forall j)(X_j \subset Y) & \Rightarrow \bigcup_j X_j \subset Y \\
    & \Rightarrow \bigcup_i X_i \subset Y \\
    \end{align*}
\end{proof}

\begin{proof} (2)
    Suppose that $\{X_i\}$ is a family of sets with domain $I$, such that $j \in I$. And let $Y$ be a set. Then, we have the following: 
    \begin{align*}
    Y \subset \bigcap_j X_j & \Rightarrow Y \subset \bigcap_i X_i\\
    \end{align*}
\end{proof}

\newpage
\begin{mdframed}
\section{Inverses and Composites}
\end{mdframed}

\begin{exercise} Suppose that $f: X \rightarrow Y$. Let $\{A_i\}$ be a family of subsets of $X$. Define $f': \mathscr{P}(X) \rightarrow \mathscr{P}(Y)$, as the mapping from each $A_i$ to the image subset, $f'(A_i)$, as stated in the text. We claim that $$f' \Big( \bigcup_i A_i\Big) = \bigcup_i f'(A_i) $$
\end{exercise}
    \begin{proof} After the comments on page thirty-four, we note that $A: I \rightarrow \mathscr{P}(X)$, for some index set $I \neq \emptyset$. Then, we have the following: 
    \bigbreak ($\Rightarrow$)
        \begin{align*}
        x \in \bigcup_i f'(A_i) & \Rightarrow (\exists i_0 \in I)(x \in f'(A_{i_0})) \\
        (\text{since $A_{i_0} \subset \bigcup_i A_i$}) \quad & \Rightarrow x \in f'\Big(\bigcup_i A_i\Big) \\
        \end{align*}
    \bigbreak ($\Leftarrow$)
        \begin{align*}
        x \in f' \Big( \bigcup_i A_i\Big) & \Rightarrow (\exists i_0 \in I)(x \in f'(A_{i_0})) \\
        & \Rightarrow x \in \Big(\bigcup_{z \in I - \{i_0\}} f'(A_z) \Big) \cup f'(A_{i_0})  = \bigcup_i f'(A_i) \\
        \end{align*}
    And the result follows. 
    \end{proof}

\begin{exercise} We show that, in general, 
$$f' \Big( \bigcap_i A_i\Big) = \bigcap_i f'(A_i) $$ 
does not hold. 
\end{exercise}
The following proof was suggested by David. H.. 
    \begin{proof} Consider $X = \{a,b,c\}$ and $Y = \{d,e\}$ and suppose all the elements are distinct. Then define $f': \Pwr(X) \rightarrow \Pwr(Y)$ as the following: 
        \begin{align*}
        f'(\emptyset) & = \emptyset \\
        f'(\{a\}) & = \{d\} \\
        f'(\{b\}) & = \{e\} \\
        f'(\{c\}) & = \{d\} \\
        f'(\{a,b\})& = \{d,e\} \\
        f'(\{b,c\}) & = \{d\} \\
        f'(\{a,c\}) & = \{e\} \\
        f'(\{a,b,c\})& = \emptyset \\ 
        \end{align*}
    Then, let $\{A_i\}$ be a family of subsets of $X$ with domain $I = 2$, such that $A_0 = \{a\}$ and $A_1 = \{a,c\}$. Then, we have the following: 
        \begin{align*}
        f'\Big( \bigcap_i A_i\Big) & = f'(\{a\}) = \{d\} \\
        \bigcap_i f'(A_i) & = f'(A_0) \cap f'(A_1)  = \{d\} \cap \{e\} = \emptyset \\
        \end{align*}
    Which completes the proof. 
    \end{proof}
    
\begin{exercise} Let $f: X \rightarrow Y$. We show that $f$ maps $X$ onto $Y$ iff for every non-empty subset $B$ of $Y$, $f^{-1}(B) \neq \emptyset$.
\end{exercise}
    \begin{proof} 
    \bigbreak $ $\newline ($\Rightarrow$) 
    If $f$ maps $X$ onto $Y$, then for every $y \in Y$, there exists an $x \in X$ such that $f(x) = y$. Since this is the case, if $B$ is a non-empty subset of $Y$, then for any $b \in B$, $b \in Y$. And we have that there exists an $x_0 \in X$ such that $f(x_0) = b$; therefore, $f^{-1}(B) = \{x \in X: f(x) \in B\} \neq \emptyset$. 
    \bigbreak $ $\newline ($\Leftarrow$)
    Suppose that $f^{-1}(B) \neq \emptyset$ for any $B \subset Y$. In particular, for each $y \in Y$, $\{y\} \subset Y$ and $f^{-1}(\{y\}) = \{ x \in X: f(x) = y\} \neq \emptyset$. The result follows immediately. 
    \end{proof}
    
\begin{exercise} In the context of page forty-one, $R := \text{"son"}$, $S := \text{"brother"}$, what do $R^{-1}$, $S^{-1}$, $RS$ and $R^{-1}S^{-1}$ mean? 
\end{exercise}  
    \begin{proof}
    \bigbreak ($R^{-1}$): From the comments on page forty-one, $xRy$ implies that that $x$ is son-related to $y$. That is, $y$ is the father of $x$. Thus, $yR^{-1}x$ means that $y$ has the father relation to $x$.
    \bigbreak ($S^{-1}$): Likewise, $xSy$ means that $x$ bears the brother-relation to $y$. That is, $x$ is the brother of $y$. Thus, $yS^{-1}x$ implies $y$ is the brother of $x$. 
    \bigbreak ($T = R \circ S$): Also, by the previous comments, if $xTz$, then there exists $y$ such that $xSy$ and $yRz$. Thus, $x$ is the brother of $y$ and $z$ is the son to $y$. That is, $x$ is the uncle of $y$.
    \bigbreak ($T = R^{-1} \circ S^{-1}$): Likewise, if $xTz$, then there exists a $y$ such that $xS^{-1}y$ and $yR^{-1}z$. Thus, $x$ is the brother of $y$ and $y$ is the father to $z$. Thus, $x$ is the uncle of $z$. 
    \end{proof}
    
\begin{exercise} Assume that for each of the following $f: X \rightarrow Y$. We show the following: 
    \begin{enumerate}
    \item If $g: Y \rightarrow Z$ such that $g \circ f$ is the identity on $X$, then $f$ is 1-1 and $g$ maps $Y$ onto $X$.  
    \item $f(A \cap B) = f(A) \cap f(B)$ for all $A,B \subset X$ iff $f$ is 1-1.  
    \item $f(X - A)  \subset Y - f(A)$ for all subsets $A$ of $X$ iff $f$ is 1-1.
    \item $Y - f(A) \subset f(X-A)$ for all subsets $A$ of $X$ iff $f$ maps $X$ onto $Y$. 
    \end{enumerate}
\end{exercise}

\begin{proof} (1): 
    Suppose that $g: Y \rightarrow Z$ such that $g \circ f$ is the identity on $X$. Since $g \circ f$ is the identity on $X$, for all $x \in X$, $g(f(x)) = x$. Thus, if $f(x_0) = f(x_1)$, then $x_0 = g(f(x_0)) = g(f(x_1) ) = x_1$ and $f$ is 1-1. To show that $g$ maps $Y$ onto $X$ let $x \in X$, then $x = g(f(x))$ where $f(x) \in Y$. Thus, $g$ maps $Y$ onto $X$. 
\end{proof}

\bigbreak
\begin{proof}(2):
    \bigbreak ($\Rightarrow$)
    By assumption, we have that $f(A \cap B) = f(A) \cap f(B)$ for all $A,B \subset X$. Suppose that $f(x) = f(y)$ for some $x,y \in X$. If $x = y$, then we are done. So, suppose that $x \neq y$. Letting $A = \{x\}, B= \{y\}$, we have that $f(A \cap B) = \emptyset \neq \{f(x) = f(y)\} = f(A) \cap f(B)$, a contradiction.  
    \bigbreak ($\Leftarrow$)
    Suppose that $f$ is 1-1. If $y \in f(A \cap B)$, then $y = f(x)$ for some $x \in A \cap B$. Thus,  $x \in A$ and $x \in B$. This implies that $f(x) = y \in f(A)$ and $f(x) = y \in f(B)$. Thus, $y \in f(A) \cap f(B)$.
    \par Now take $y \in f(A) \cap f(B)$. Then $y \in f(A)$ so there is some $a \in A$ with $f(a) = y$. Also, $y \in f(B)$, so there is some $b \in B$ such that $y = f(b)$. Now $f(a) = y = f(b)$, so $f$ being 1-1 now implies $a = b$. Thus, $a \in A \cap B$ and $f(a) = y \in f(A \cap B)$.
\end{proof}

\bigbreak
\begin{proof}(3):
    \bigbreak ($\Rightarrow$)
    Suppose that $f(x)=f(y)$ for some $x,y \in X$. Let $A = \{x,y\}$. Then, $f(X - \{x,y\}) \subset Y - f(\{x,y\}) = Y - \{f(x)=f(y)\} = Y - \{f(x)\}$.By the comments on page thirty-nine, we have that 
        \begin{align*}
        & f^{-1}f((X - A)) \subset f^{-1}(Y - \{f(x)\}) \\
        & \Rightarrow X - A = X - f^{-1}(\{f(x)\}) \\
        & \Rightarrow X - \{x,y\} = X - \{x\} \\
        \end{align*}
    It follows that $\{x,y\} = \{x\}$ i.e. $y=x$. 
    \bigbreak ($\Leftarrow$)
    Suppose that $f$ is 1-1. And let $y \in f(X - A)$ for any non-empty subset $A \subset X$. Then, there exists an $x_0 \in X - A$ such that $f(x_0) = y$. Suppose to the contrary that $y \notin Y - f(A)$. Then, $f(x_0) = y \in (Y -f(A))^c = f(A)$. This implies that there exists some $a \in A$ such that $f(x_0) = y = f(a)$. However, this is a contradiction since $f$ being 1-1 implies $a = x_0 \in A $.
\end{proof}

\bigbreak
\begin{proof}(4): 
    \bigbreak ($\Rightarrow$)
    Let $y \in Y$ and consider an arbitrary subset $A$ of $X$. Now, either $y \in f(A)$ or it is not. If it is, we are done. So suppose that it is not. Then, $y \in Y - f(A) \subset f(X-A)$ and so, there exists some $x_0 \in X -A$ such that $y = f(x_0)$; and the result follows.
    \bigbreak ($\Leftarrow$)
    Let $A \subset X$ and suppose that $y \in Y - f(A)$. Since $f$ maps $X$ onto $Y$, there exists some $x \in X$ such that $y = f(x) \in Y - f(A)$. Thus, $x \notin A$ and so $x \in A^c = X - A$. It follows from he definition that $y=f(x) \in f(X-A)$ and the result follows.   
\end{proof}


\newpage 
\begin{mdframed}
\section{Numbers}
\end{mdframed}


\begin{exercise} Let $\{A_i\}$ be a family of non-empty successor sets for some non-empty domain $I$. We show that $$\bigcap_i A_i$$ is a successor set. 
\end{exercise}
    \begin{proof} For all $i \in I$, $A_i$ is a successor set, and so $0 \in A_i$. This implies that $0 \in \bigcap_i A_i$. Likewise, suppose that $n \in \bigcap_i A_i$; then $n \in A_i$ for all $i \in I$ and so $n^+ \in A_i$ for each $i \in I$; from the definition of intersection $n^+ \in \bigcap_i A_i$. This completes the proof. 
    \end{proof}

\newpage
\begin{mdframed}
\section{Peano Axioms}
\end{mdframed}

\begin{exercise} We prove that if $n \in \omega$ then $n \neq n^+$. 
\end{exercise}
    \begin{proof} Suppose, to the contarary, that $n = n^+$ for some $n \in \omega$. Then, from the axiom of extension we have that $n^+ \subset n$. However, then we would have that $n^+ = n \cup \{n\} \subset n$ implying that $n \in n$ which is a contradiction. 
    \end{proof}
    
\begin{exercise} Let $n \in \omega$. We show that if $n \neq 0$, then $n = m^+$ for some $m \in \omega$ --- We note that this show any element $n \in \omega$ has a predecessor.  
\end{exercise}
    \begin{proof} We proceed by mathematical induction: Let $S$ be that subset of $\omega$ for which if $n \neq 0$, then $n = m^+$ for some $m \in \omega$. We note that $1 \in S$, since $1 = 0^+$ and $0 \in \omega
    $. Suppose that for some $n \in \omega$, $n = m^+$ for some $m \in \omega$; indeed, if $n^+ = m$ for some $m \in \omega$ we have $(n^+)^+ = m^+ = z$ for some $z \in \omega$ by the induction hypothesis.  This completes the proof.
    \end{proof}
    
\begin{exercise} We prove that $\omega$ is transitive. That is, if $x \in y$ and $y \in \omega$, then $x \in \omega$.
\end{exercise}
    \begin{proof} We proceed by mathematical induction. Let $S$ be the set of all $z \in \omega$ such that if $x \in z$, then $x \in \omega$. We note that $\{\} = 0 \in S$, vacuously. Thus, let $y \in S$. We show that $y^+ \in S$. That is, let $x$ be any element in $y^+$: $x \in y^+ = y \cup \{y\}$ . Then, either $x \in y$ or $x = y$. In the former cases, we that $x \in \omega$, by assumption; in the later case we have that $y = x \in S$. Thus, $\omega = S$ and so $\omega$ is transitive. 
    \end{proof}
    
\begin{exercise} We show the following: if $E$ is non-empty subset of some natural number, then there exists an element $k\in E$ such that $k \in m$ whenever $m$ is an element of $E$ and distinct from $k$ --- This says that any finite set has a lower bound, namely a greatest lower bound. 
\end{exercise}
    \begin{proof} We proceed by mathematical induction. Let $S$ be the set of $z \in \omega$ such that the above holds. We note that $\{\} = 0 \in S$, vacuously. Suppose that $n \in S$ for some $n \in \omega$; we show that $n^+ \in S$. Suppose that $E$ is a non-empty subset of $n^+ = n \cup \{n\}$. If $E$ is a singleton, then we are done; the above is vacuously satisfied. We note that if $E = n$, then we are done, by the induction hypothesis. Thus, there exists some $k \in E$, as specified above. We claim that this $k$, so specified, will work even if $n \in E$; Indeed from a previous proof, we know that no element is equal to its successor and so it follows that for any $a \in E$, $a \in n$. In particular, this is true for $k$. Therefore, $S = \omega$. 
    \end{proof}
    
    
\newpage
\begin{mdframed}
\section{Arithmetic}
\end{mdframed}
In many of these exercises, we use induction. As pointed out in the \textit{Axiom of Substitution}, and the conversation I had with S. Bleiler, and later sections, it is still valid to start induction at some $x \in \omega$; we have used this fact a couple times. 

\begin{exercise} Prove that if $m < n$ for some natural numbers $m$, $n$, then $m + k < n + k$ for any $k \in \omega$. 
\end{exercise}
    \begin{proof} 
        We proceed by mathematical induction. Suppose that for some natural numbers $m$, $n$, $m < n$. Let $S$ be the set of all $z \in \omega$ such that $m + z < n + z$. We show that $S = \omega$. Indeed; we note that since $m+0 = m$ and $n+0 = n$, it follows that $m = m+0 < n+0 = n$, and so, $0 \in S$. Now, suppose that $k \in S$ for some $k \in \omega$. We show that $k^+ \in S$. 
        \par Note, $s_n(k^+) = (s_n(k))^+ = s_n(k) \cup \{s_n(k)\}$, and by the definition of $<$, and the induction hypothesis, we have that $\{s_n(k)\} \subset s_m(k) \subset (s_m(k) \cup \{s_m(k)\}) = s_m(k^+)$. This implies that $s_n(k^+) = s_n(k) \cup \{s_n(k)\} \subset s_m(k) \cup \{s_m(k)\} = s_m(k^+)$. That is, $S = \omega$
    \end{proof}
    
\begin{exercise} Prove that if $m < n$ for some $m,n \in \omega$, and $k \neq 0$, then $m\cdot k < n \cdot k$.
\end{exercise}
    \begin{proof}
        We proceed by mathematical induction. Suppose that $m < n$ for some $m,n \in \omega$. Let $S$ be the set of $z \in \omega$, which satisfy the following statement: if $z \neq 0$, then $m \cdot z < n \cdot z$. We note that $1 \in S$. Suppose that $k \in S$ for some $k \in \omega$; we show that $k^+ \in S$. Indeed: by definition of product, we have the following: 
            \begin{align}
            p_m(k^+) & = p_m (k) + m \nonumber\\
            & = s_m(p_m(k)) \\
            & < s_m(p_n(k)) \\
            & = p_n(k) + m  \nonumber\\
            & < p_n(k) + n \\
            & = p_n(k^+) \nonumber
            \end{align}
        We only note that (1),(2), and (3) follow from the inductive hypothesis and the previous exercise. Therefore, $S = \omega$.
    \end{proof}
    
\begin{lemma} For any $n \in \omega$, $n$ is transitive. 
\end{lemma}
    \begin{proof} Suppose that $E = n \in \omega$ and $y \in E$. Since $y \in E$, $y$ is a proper subset of $E$. Now, if $x \in y$, then $x$ is a proper subset of $y$  and it follows directly that $x \subset y \subset E$. That is, $x$ is a proper subset of $E$. That is $x \in E$.
    \end{proof}
    
\begin{lemma} If $m, n \in \omega$ such that $m \neq n$, then $m \in n$ iff $ m \subset n$
\end{lemma}
    \begin{proof} Let $m$, $n$ be stated as above. 
        \bigbreak ($\Rightarrow$) \par
        Suppose that $m \in n$. We show that $m \subset n$: let $x \in m$, then by the lemma above, $x \in n$. Thus, $m \subset n$.
        \bigbreak ($\Leftarrow$) \par
        Suppose that $m \subset n$. If $m = n$, then we are done. Otherwise, $m \neq n$. If this is the case, then $n \in m$ cannot happen (for them $m$ would be a subset of one of its elements), and therefor $m \in n$; this is by the comparability of  and $x,y \in \omega$.
    \end{proof}
        
\begin{exercise} We prove that if $E$ is a non-empty set of natural numbers, then there exists an element $k \in E$ such that $k \leq m$ for all $m \in E$. --- This statement says that any non-empty subset in $\omega$ has a minimum. 
\end{exercise}
    \begin{proof} Let $E \subset \omega$ such that $E \neq \emptyset$. Since $E$ is non-empty, we can form the intersection of elements in $E$. Consider $$z = \bigcap_{x \in E} x$$ It follows directly from the formulation of $z$ that $z \subset x$, for all $x \in E$: $z \leq x$. Thus, it is only necessary to prove that $z \in E$. From the previous lemma we see that since $z \in x$ for all $x \in E$, and $x \in E$, that $z \in E$. The result follows. 
    \end{proof}
 
\begin{exercise} A set E is called finite if it is equivalent to some natural number; otherwise E is infinite. We use this definition to prove that $\omega$ is infinite. 
\end{exercise}
    \begin{proof} Suppose, to the contrary that $\omega$ is finite. Then, there exists a 1-1 and onto function, $f$, from $\omega$ to $n$ for some $n \in \omega$: $f \subset \omega \times n$. Since $f$ is 1-1 and onto, for ever $y \in n$, there exists a unique $x \in \omega$ such that $(x,y) \in f$. Let $g$ be the union of all such $x$, which is an element of $\omega$. Then, $g^+ = g \cup \{g\}$ is in $\omega$ but not in $g$. Since $f$ is a function, we must have $(g^+, y_1) \in f$ for some $y_1 \in n$; likewise since $f$ is onto, there exists some $x \in g$ such that $(x, y_1) \in f$. From here we see that we must have $(g^+, y_1) = (x, y_1)$, implying $g^+ = x$; which is  a contradiction since $g^+ \notin g$, whereas $x \in g$.
    \end{proof}
    
\begin{exercise} If $A$ is a finite set, then $A$ is not equivalent to a proper subset of $A$. The contrastive of this statement is that if $A$ is equivalent to a proper subset of $A$, then $A$ is not finite (infinite). We use this definition to show that $\omega$ is infinite. 
\end{exercise}
    \begin{proof} We show that $\omega \sim A$, where $A = \omega - \{0\}$. First, it is clear that $A$ is a non-empty proper subset of $\omega$. Consider the map $f \subset \omega \times \omega$, given by $f(n) = n^+$. First, we show that $f$ is indeed a function, and then that it is 1-1 and onto:
        \begin{itemize}
        \item \textit{Well-Defined}: Suppose that $x = y$ for some $x, y \in \omega$. From a previous theorem, we have $x^+ = y^+$. This shows that $f$ is well-defined. 
        \item \textit{Everywhere-Defined}: This follows directly from the definition of $\omega$ as being a successor set. This shows that $f$ is everywhere defined. 
        \item \textit{1-1}: Suppose that $n^+=m^+$. Again, from a previous exercise (page 46), we have $n=m$. This shows that $f$ is 1-1.
        \item \textit{Onto}: Suppose that $n \in A = \omega - \{0\}$. Then no $n \in A$ is $0$. Thus, by a previous theorem, we have that $n = m^+ = f(m)$ for some $m \in \omega$. This implies that $f$ is onto. 
        \end{itemize}
    \end{proof}
    
\begin{exercise} We prove that union of a finite set of finite sets is finite. 
\end{exercise}
    \begin{proof} We proceed by mathematical induction. Let $S$ be a finite set, such that $\#(S) = n$, for some $n \in \omega$. Let $B$ be the set of all $N \in \omega$ such that $\bigcup S$ is finite. 
    \par Note $0 \in B$ since, if $\#(S) = 0$, then $S = \{\}$ and $\bigcup \{\} = \{\}$ (which is finite). Next, suppose that $k \in B$: that is, if $S$ is a finite set such that $\#(S) = k$, then $\bigcup S$ is finite. We show that $k^+ \in B$. Suppose that $\#(S) = k^+$. Then, there exists some 1-1 and onto function $f$ i.e. $f: k^+ \leftrightarrow S$. And we have the following: 
        \begin{align*}
        \bigcup S = \bigcup_{i \in k^+} f(i)  = \Big(\bigcup_{i \in k} f(i)\Big) \cup f(k)
        \end{align*}
    From the comments on page 53, and the induction hypothesis, we see that $k^+ \in B$. Thus, $B= \omega$. 
    \end{proof}
    
\begin{exercise} We prove the following: If $E$ is finite, then $\Pwr(E)$ is finite and, moreover, $\#(\Pwr(E)) = 2^{\#(E)}$.
\end{exercise}
    \begin{proof} It is only necessary to show that if $\#(E) = n$ for some $n \in \omega$, then $\#\Pwr(E) = 2^{\#(E)}$; we conclude that $2^{\#(E)} \in \omega$ by a previous exercise. We proceed by mathematical induction.
    \par Let $S$ be the set of all $N \in \omega$ such that $\#(E) = N$ and $\#\Pwr(E) = 2^{\#(E)}$. Note that $0 \in S$, since $\#(E) = 0$ implies $E = \{\}$ and $\#(\Pwr(E)) = \#(\{\emptyset, \{\emptyset\}\}) = 2 = 2^0$. Next, assuming that $k \in S$, we show that $k^+ \in S$: 
    \par Suppose that $\#(E) = k^+ = k + 1$, and consider the set $E^* = E - \{0\}$. Note, $\#(E^*) = k$. We note that either $0$ is in a subset of $E$, or it is not. If it is not, then we are forming subsets of $E^*$. From the inductive hypothesis, there are $2^{\#(E^*)} = 2^k$ subsets of $E^*$. By similar logic, there are $2^k$ subsets which include $0$. It follows that there are $2^k + 2^k = 2\cdot 2^k = 2^{k+1} = 2^{\#(E)}$ subsets of $E$. Thus, $k+1 = k^+ \in S$. That is, $S = \omega$.
    \end{proof}
    
\begin{exercise} If $E$ is a non-empty finite set of natural numbers, then there exists and element $k \in E$ such that $m \leq k$ for all $m \in E$ --- This statement says that for any finite set $E$, non-empty, of natural numbers, there is an upper bound, actually a maximum. 
\end{exercise}
    \begin{proof} Let $E$ be a finite, non-empty, subset of natural numbers. We proceed by mathematical induction. Let $S$ be the set of all $N \in \omega$ such that $\#(E) = N$ and there exists a $k \in E$ such that the above holds.
    \par Note that $1 \in S$; $1 = \#(E)$ implies $E = \{n\}$ for some $n \in \omega$, and clearly $n \leq n$. Next, assuming that $k \in S$, for some $k \geq 1$, we show that $k^+ \in S$: 
    \par Suppose that $\#(E) = k^+ = k+1$. Fix some $x \in E$, and consider $E^* = E - \{x\}$. We note that $\#(E^*) = k$, and so, it follows from the induction hypothesis that there exists some $g \in E^*$ such that $m \leq g$, for all $m \in E^*$. By the comparability of elements in $\omega$, we must have that either $x \in g$, or $g \in x$; we only note that $x \neq g$, since otherwise we would have $\#(E) = k$. In the former case, if $x \in g$, then $x < g$, and in particular $x \leq g$. In the later case, supposing that $g \in x$, we have $g < x$; and, again, in particular $g \leq x$. But then $m \leq g$ and $g \leq x$ for all $m \in E = E^* \cup \{x\}$, implying $m \leq x$ for all $m \in E$ by the transitivity of $\leq$. This shows that $k^+ \in S$, and so $S = \omega$. 
    \end{proof}
    
\newpage
\begin{mdframed}
\section{Order}
\end{mdframed}
 
 \begin{exercise} We express the conditions of antisymmetry and totality for a relation $R$ by means of equations involving $R$ and its inverse --- This exercise illustrates that we can determine a partial, or total order, by looking the the co(domains), of a relation.  
 \end{exercise}
    \begin{proof} From the comments on page 54 and the notation in section 10, we adopt the usual assumptions and notation. That is, assume that $R$ is a relation in $X$. And, we have the following: 
    $ $\newline Antisymmetry: 
        \begin{align*}
        xRy \land yRx & \Rightarrow x = y \\
        \text{iff} \quad (R(x) = y \land R^{-1}(x) = y) & \Rightarrow R(x) = R^{-1}(y) 
        \end{align*}
    $ $\newline Totality: 
        \begin{align*}
        (\forall x,y \in X)(xRy \lor yRx) & \iff (\forall x,y \in X)(R(x) = y \lor R^{-1}(x) = y) \\ 
        \end{align*}
    \end{proof}


\newpage
\begin{mdframed}
\section{Axiom of Choice}
\end{mdframed}

\begin{exercise} We prove that every relation includes a function with the same domain. 
\end{exercise}
    \begin{proof} Suppose that $X$ and $Y$ are sets and let $R$ be a relation from $X$ into $Y$. By definition, $R \subset X \times Y$, and so if $X$ or $Y$ is empty, the $X \times Y$ is empty and we are done. Otherwise, there exists at least an element in each of $X$, $Y$. Let $X_R$ be the subset of $X$ given by the first coordinates of $R$. Claim: there exists some function $f:X_R \rightarrow Y$. 
    \par Let $y \in Y$ be arbitrary and consider $T_y = \{x \in X_R: xRy\}$. Let $I$ be the set of $z \in Y$ such that $T_z \neq \emptyset$. Then, define $T = \bigcup_{y \in I} \{T_y\} = \{T_i\}$. Assuming the axiom of choice, and by the comments on page sixty, $\{T_i\}$ is a family of non-empty sets indexed by $I$ and so, there exists a family $\{t_i\}$, $i \in I$ such that $t_i \in T_i$ for each $i \in I$. Since $R$ is a relation on $X_R$, so defined, it follows that $f = \{(t_i,b): i \in I \land b=R(t_i)\}$ is a candidate function. 
    \par Indeed; we verify that $f$ is well-defined and everywhere defined: 
        \begin{itemize}
        \item \textit{Well-Defined}: Suppose that $t_i = t_j$ for some $i,j \in I$. By construction, and the previous supposition, we have that $T_{t_i} = \{x \in X_R: x R t_i\} = \{x \in X_R: x R t_j\} = T_{t_j}$. Thus, $(t_i, R(t_i)) = (t_j, R(t_j)) = f(t_i) = f(t_j)$. 
        \item \textit{Every-Where Defined}: This is clear by construction. 
        \end{itemize}
    Thus, $f$ is a function. 
    \end{proof}

\newpage
\begin{mdframed}
\section{Zorn's Lemma}
\end{mdframed}
    
\begin{exercise} We show that Zorn's Lemma is equivalent to the axiom of choice. 
\end{exercise}
    \begin{proof} Let $X$ be a set and define $\mathcal{F}$ to be the following set of functions: 
        \begin{align*}
        f \in \mathcal{F} \iff 
        \begin{cases} 
        \dom f \subset \Pwr(X) \\
        \Ima f \subset X \\
        (\forall A \in \dom f)(f(A) \in A)  
        \end{cases}
        \end{align*}
    Next, consider the relation $\leq$, in $X$, given by the following: for all $f_1, f_2 \in \mathcal{F}$, $f_1 \leq f_2$ iff $f_2$ is an extension of $f_1$ i.e. $f_1 \subset f_2$. As the comments on page 65 point out, $\leq$ is a partial ordering. We note that $(F, \leq)$ is a partially ordered set. Assuming \textit{Zorn's Lemma}, we show that there exists some maximal element $f \in \mathcal{F}$: 
    \par $\mathcal{F}$ is already partially ordered. So, let $\mathscr{X}$ be a chain in $\mathcal{F}$. Note that $\mathscr{X}$ is a collection of ordered pairs, satisfying the above criterion. We claim that $\bigcup \mathscr{X}$ is the upper bound for $\mathscr{X}$; we only need to show that $\bigcup \mathscr{X}$ is a function: 
        \begin{itemize}
        \item \textit{Function}: Suppose that $(a,x), (a,y) \in \bigcup \mathscr{X}$, then $(a,x) \in f$ for some $f \in \mathscr{X}$ and, likewise, $(a,y) \in g$ for some $g \in \mathscr{X}$. Then, since $\mathscr{X}$ is a chain, either $f \leq g$, $f = g$, $g \leq f$. Without loss of generality, we have $(a,x), (a,y) \in g$. Since $g$ is a function, we have $x = y$. The fact that $\bigcup \mathscr{X}$ is every-where defined is obvious. 
        \item The rest of the properties follow by definition. 
        \end{itemize}
    By \textit{Zorn's Lemma}, there exists a maximal element in $\mathcal{F}$, call it $f$. To complete the proof, we show that $\dom f = \Pwr(X) - \{\emptyset\}$: 
        \begin{itemize}
        \item Suppose that $\dom f \neq \Pwr(X) - \{\emptyset\}$. Then, there exists some $a \in P(X)$ such that $a \notin \dom f$. Let $g = f \cup \{(a, b)\}$, for any $b \in X$. It is clear that $g \in \mathcal{F}$ and that $g \geq f$. However, this contradicts the minimality of $f$. 
        \end{itemize}
    We note that using the \textit{Axiom of Choice} to prove \textit{Zorn's Lemma} was shown in text. This completes the proof.  
    \end{proof}
    
%\begin{lemma} We prove that if $(X, \leq)$ is a partially ordered set, and $A$ is a maximal chain (i.e. a chain that is not a proper subset of any other chain) in $X$, then $A$ has an upper-bound $x \in X$, moreover, $x \in A$.
%\end{lemma}
 %   \begin{proof} Let $X$, $A$, be stated as above. I claim that $x = \bigcup A$ is an upper bound. Indeed, for all $a \in A$, $a \leq x$. Now, if $x \notin A$, then we can form $F = A \cup \{x\}$, in which case, $A \subset F$, contradicting the maximality of $A$.  
  %  \end{proof}
    
\begin{exercise} We prove that the following is equivalent to the axiom of choice: Every partially ordered set has a maximal chain --- This is the Hausdorff Maximality Principal (HMP). 
\end{exercise}
    \begin{proof} We show that \textit{HMP} is equivalent to \textit{Zorn's Lemma} and use the fact that \textit{Zorn's Lemma} is equivalent to the \textit{Axiom of Choice} to conclude. 
        \begin{itemize}
        \item ($\Rightarrow$) Suppose the \textit{HMP}. Let $(X,\leq)$ be the partially ordered set, and $A$ the maximal chain. By the assumptions of \textit{Zorn's Lemma}, $A$ has an upper-bound, call it $a$. Now, $a \in A$, since otherwise, we could form $B = A \cup \{a\}$, which is again a totally ordered set, containing $A$; for all $s \in B$, the elements of $A$ are comparably, likewise, $s \leq a$. To complete the proof in this direction, we note that if $z \in X$ is any element such that $z \geq a$, then $z$ is an upper-bound and must be in $A$, by the previous discussion. This implies that $a \geq z$ for all $z \in X$. Specifically, since $A$ is partially ordered, we have $a \leq z$ and $z \leq a$ implying $a = z$. Thus, $a$ is maximal.  
        \item ($\Leftarrow$) Suppose \textit{Zorn's Lemma}. Let $(X, \leq)$ be a partially ordered set. Consider $\mathcal{F}$ be the set of all totally ordered subsets of $X$. The inclusion order on $\mathcal{F}$ is a partial order. Note that if $S$ is a maximal element in $\mathcal{F}$, then it will be a maximal chain in $X$. We show that any chain $A$ in $\mathcal{F}$ has an upper-bound:
            \begin{itemize}
            \item (The following was \href{http://www.auburn.edu/~harriga/mh7200/hints/hw2.pdf}{suggested by this example}): Indeed, consider $A' = \bigcup_{E \in A} E$. By definition, $A'$ contains all elements of $A$. We only show that $A' \in \mathcal{F}$: To show this take $x$ and $y$, elements of $A'$. Then there are sets $E_x$ and $E_y$, members of $A$, with $x \in E_x$ and $y \in E_y$. Since $A$ is partially ordered by inclusion, $E_x \subset E_y$ or $E_y \subset E_x$, that is, either $x, y \in E_y$ or $x, y \in E_x$. Since both $E_x$ and $E_y$ are linearly ordered in $X$ then either $x \leq y$ or $y \leq x$. This shows that $A'$ is a totally ordered set, and so a chain in $X$ i.e. $A' \in \mathcal{F}$.
            \end{itemize}
        \end{itemize}
    This completes the proof.
    \end{proof}
    
\begin{exercise} We show that the following statements are equivalent to the axiom of choice: (i) Every partially ordered set has a maximal chain --- This is the Hausdorff Maximality Principal (ii) Every chain in a partially ordered set is included in some maximal chain. (iii) Every partially ordered set in which each chain has a least upper bound has a maximal element. 
\end{exercise}
    \begin{proof} To do so, we show that $i \Rightarrow ii \Rightarrow iii \Rightarrow \textit{ZL} \Rightarrow i$, noting that \textit{Zorn's Lemma} is equivalent to the axiom of choice. Throughout these exercises, we assume that $(X, \leq)$ is the partially ordered set in discussion. 
        \begin{itemize}
        \item (i $\Rightarrow$ ii) Suppose that every partially ordered set has a maximal chain. Since $(X, \leq)$ is partially ordered, there exists some maximal chain $A \subset X$. We note that for chains, inclusion is the partial order. Thus, by definition, for all other chains $A' \subset X$, we must have $A' \subset A$, since otherwise, $A \subsetneq A'$, contradicting the maximality of $A$. 
        \item (ii $\Rightarrow$ iii) Suppose that every chain in a partially ordered set is included in some maximal chain. Let $(X, \leq)$ be such a partially ordered set. Then, there exists some maximal chain $A$ such that $A' \subset A$ for all other chains $A' \subset X$. We show that each chain $A'$ of $X$ has a least upper bound:  
            \begin{itemize}
            \item Let $G$ be the set of all upper-bounds of some chain $A'$. Then, we have have $A' \leq g$ for all $g \in G$. Likewise $G \cap A' =  A'$ implying $A'$ is the least upper-bound of $A'$.
            \end{itemize}
        From the antecedent in (iii), we see that $A$ has a maximal element in $A$, call it $a$. We also note that $a$ is maximal in $X$: If not, then we can define $T = A \cup \{a\}$, which is a totally ordered set in which $A \subset T$; contradicting the maximality of $A$. 
        \item (iii $\Rightarrow$ \textit{Zorn's Lemma}) Suppose that every partially ordered set in which each chain has a least upper bound has a maximal element. Let $X$ be such a set. Then for any chain $A \subset X$, $A$ has a l.u.b. call it $\delta_A$. In particular, $\delta_A$ is an upper-bound. By assumption $X$ has a maximal element.
        \item (\textit{Zorn's Lemma} $\Rightarrow$ i) This was proved in the previous exercise. 
        \end{itemize} 
    \end{proof}
    
\newpage
\begin{mdframed}
\section{Well Ordering}
\end{mdframed}

\begin{exercise} A subset $A$ of a partially ordered set $X$ is \textit{cofinal} in $X$ in case for each element $x \in X$, there exists an element $a \in A$ such that $x \leq a$. We prove that every totally ordered set has a cofinal well ordered subset.
\end{exercise}
    \begin{proof} Let $(X, \leq)$ be a non-empty totally ordered set. If $X$ has a maximum element, then we are done. Thus, suppose that $X$ has no maximum. Let $\mathcal{F}$ be the set of all well ordered subsets of $X$ with the following order: for all $f,g \in \mathcal{F}$, $f\preceq g$ iff $f$ is an initial segment of $g$. We seek to apply \textit{Zorn's Lemma}.
        \begin{itemize}
        \item From the previous result, $\preceq$ is a partial order on $\mathcal{F}$.
        \item Suppose that $Z$ is chain in $\mathcal{F}$. We show that $Z$ has an upper bound in $\mathcal{F}$. Consider $\bigcup Z$. It is clear that $Z \preceq \bigcup Z$. We show that $\bigcup Z$ is well ordered; Indeed, these are the comments on page 67. 
        \end{itemize} 
    We have satisfied the assumptions in \textit{Zorn's Lemma}, and so it follows that there exists some maximal element $M \in \mathcal{F}$. We claim that $M$ is a well ordered cofinal subset of $X$. 
    \par First, it is a subset. Second, it is well ordered by the definition of $\mathcal{F}$. Next, if $x \in X$, then for any $m \in M$, either $m \leq x$, $x \leq m$ or $x = m$. But, since $M$ is maximal, if $m \leq x$, then $x \in M$; otherwise, we could form $N = M \cup \{x\}$ which is a contradiction to the maximality of $M$. Thus, $M$ is the well ordered cofinal subset of $X$. 
    \end{proof}

\begin{exercise} We prove that a totally ordered set is well ordered iff the set of strict predecessor of each element is well ordered. 
\end{exercise}
    \begin{proof}
        $ $\newline 
        ($\Rightarrow$) Suppose that we have a well ordered set $(X, \leq)$. Note that the set of strict predecessors of some $x \in X$ forms a subset. The rest follows from the definition.
        $ $\newline
        ($\Leftarrow$) Suppose that $(X, \leq)$ is a totally ordered set and that for any $x \in X$ the strict initial segment $s(x)$ is well ordered. Let $J$ be a subset of $X$. Pick some $j_0 \in J$ and consider $s(j_0) = \{x \in X: x < j_0\}$. If $s(j_0) = \emptyset$, $j_0$ is the least element, and we are done. Otherwise, $s(j_0) \neq \emptyset$. But since $s(j_0)$ is well ordered, we have $J \cap s(j_0) \subset s(j_0)$ and $J \cap s(j_0) \subset J$. Implying that $J \cap s(j_0)$ has a least element in $J$, call it $z$. We note that $z$ is the least element for $J$; Otherwise, there is some $x \in J$, $x \neq z$ such that $x < z < j$ for all $j \in J$ and in particular for $j_0$. This implies that $x \in s(j_0)$. However, then we must have $x \in J \cap s(j_0)$ and so $x = z$; a contradiction. 
    \end{proof}
    
\begin{exercise} Does any such condition apply to partially ordered sets? 
\end{exercise}
\begin{proof} It does not. Imagine a poset consisting of two disjoint chains. Any subset that bridges the chains will have no least element, even though set of strict predecessors will be well ordered.\end{proof}

\begin{exercise} We prove that the well ordering theorem implies the \textit{Axiom of Choice}.
\end{exercise}
    \begin{proof} The following proof was adapted from \href{http://planetmath.org/wellorderingprincipleimpliesaxiomofchoice}{this website}: 
    \par Let $C$ be a collection of nonempty sets. Then $\bigcup_{S \in C} S$ is a set. By the well-ordering principle, $\bigcup_{S \in C} S$ is well-ordered under some relation $<$. Since each $S$ is a nonempty subset of $\bigcup_{S \in C} S$, each $S$ has a least member $m_S$ with respect to the relation $<$. Define $f:C \rightarrow \bigcup_{S \in C} S$ by $f(S)=m_S$. We show that $f$ is a choice function:
        \begin{itemize}
        \item \textit{Well-Defined}: Suppose that $(a,x),(a,y) \in f$. Then, there exists some $S_1 \in C$ such that $x \in S_1$. Likewise, there exists some $S_2 \in C$ such that $y \in S_2$. Without loss of generality, it follows that $x,y \in S_2$, and so $x = y =m_{S_2}$.
        \item \textit{Everywhere Defined}: This follows fromt he discussion above. 
        \end{itemize}
    Therefore, $f$ is a choice function. Hence, the axiom of choice holds. 
    \end{proof}

\begin{exercise} We prove that if $R$ is a partial order in a set $X$, then there exists a total order $S$ in $X$ such that $R \subset S$; in other words, every partial order can be extended to a total order without enlarging the domain. 
\end{exercise}
    \begin{proof}
    Let $(R, \leq)$ be a partially ordered subset of $X$. Let $C$ be the set of all $A$ in $R$ of partial orders, with respect to $\leq$. Let $(C, \subset)$ be the partial ordered set\footnote{This has been shown other exercises.}. Let $\mathscr{X}$ be the collection of all chains in $C$. Note that for all $y \in \mathscr{X}$ $y \leq \bigcup_{y \in \mathscr{X}} y$. Thus, every chain has an upper-bound. By \textit{Zorn's Lemma}, $C$ has a maximal element. Denote this by $c$. Claim: $c$ is a total order in $X$:
        \begin{itemize}
        \item Since $c \in C$, $c$ is a partial order in $X$. Since it is maximal, for all $c' \in C$, we have $c' \subset c$. Thus, for all $x,y \in X$, either $(x,y), (y,x) \in c$. Either way, we must have $x \leq y$, $y \leq x$ or $x = y$. 
        \end{itemize}
    \end{proof}

\newpage
\begin{mdframed}
\section{Transfinite Recursion}
\end{mdframed}

\begin{exercise} We prove that a similarity preserves $\prec$ (in the same sense in which the definition demands the preservation of $\leq$).
\end{exercise}
    \begin{proof} Let $(X, \preceq)$, $(Y, \leq)$ be two partially ordered sets and that there exists some function $f:X \rightarrow Y$, 1-1 and onto. $f$  has the property that for all $a,b \in X$ with $a \preceq b$ iff $f(a) \leq f(b)$, for all $f(a), f(b) \in Y$. 
    \par Suppose, to the contrary, that $a \prec b$ and $f(a) \geq f(b)$. However, this is a contradiction, since, by definition, we must have $b \preceq a$. Thus $f$ preserves strict order. 
    \end{proof}

\begin{exercise} We prove the following statement: A 1-1 function, $f$ that maps one partially ordered set onto another is a similarity iff $f$ preserves $<$ (strict order). 
\end{exercise}
    \begin{proof} Throughout this exercise, we assume that $(X, \preceq)$ and $(Y, \leq)$ are partially ordered sets and $f: X \rightarrow Y$ is 1-1 and onto. 
        \begin{itemize}
        \item ($\Rightarrow$): Suppose that $f$ is a similarity, then the previous exercise prove this conclusion. 
        \item ($\Leftarrow$): Suppose that $f$ is as stated above, such that for any $a,b \in X$ we have $a \prec b$ iff $f(a) < f(b)$. To show that $f$ is a similarity, we show that $a = b$ iff $f(a) = f(b)$:
            \begin{itemize}
            \item ($\Leftarrow$): Since $f$ is 1-1, then $f(a) = f(b)$ implies $a = b$.
            \item ($\Rightarrow$): Suppose, to the contrary, that $a = b$ and, (without loss generality) $f(a) < f(b)$. Since $f$ preserves strict order, we must have $a \prec b$. However, this is a contradiction. 
            \end{itemize}
        \end{itemize}
    This completes the proof. 
    \end{proof}

\begin{exercise} We show that a subset $Y$ of a well ordered set $X$ is, again, well ordered. 
\end{exercise}
    \begin{proof} Let $(X, \leq)$ be a well-ordered set, and $Y \subset X$. If $Y=X$ or $Y =\emptyset$, then $Y$ is clearly a well-order. Thus, suppose that $Y$ is proper subset of $X$. Suppose that $Y$ was \textit{not} well-ordered. Then, some subset, $Z$ of $Y$ does not have a least element. However, $Z \subset X$, and so by definition of a well-ordered set, it has a least element. A contradiction. 
    \end{proof}

\begin{exercise} We prove that each subset of a well-ordered set $X$ is similar either to $X$, or an initial segment of $X$. 
\end{exercise}
    \begin{proof} Suppose that $(X, \preceq)$ is a well-ordered set. If $X = \emptyset$, then every subset of $X$ is equivalent to $X$. So, suppose $X \neq \emptyset$, and let $S$ be a non-empty subset of $X$. Since $X \subset X$, $X$ has a least element, call it $x$. Likewise, $S$ has a least element, $s$. Consider the map $f$ given by $f(s) = x$. And then, since $X - \{x\} \subset X$ it has a least element, call it $x'$. Likewise, $S - \{s\}$ has a least element, call it $s'$ and define $f(s') = x'$, and so on. We show that $f$ is a sequence of type $S$ in $X$. Now, either this process terminates, or it does not. If it does, then it terminates at some $x^*$, $s^*$ i.e. $f(s^*) = x^*$. Claim: $S \cong s(x^*)$. 
        \begin{itemize}
        \item The fact that $f$ is a function is clear by previous definition. It only need to be shown that $f$ is 1-1, onto and preserves $\prec$. The fact that $f$ is 1-1 is clear. Thus, if $\bar{x} \prec x^*$, then by construction, $s(\bar{x}) = f(t)$ for some $t \in S$. 
        \item $f$ preserves $\prec$: This follows from the definition of initial segments give on page 65, 78. 
        \end{itemize}
    \par Otherwise, the process does not terminate. In this case, the claim is that $S \cong X$. The fact that $f$ is a 1-1 and onto function is shown similarly as before. Likewise for $\prec$. 
    \end{proof}

\begin{exercise} We prove that if $(X, \prec)$, $(Y, \leq)$ are well ordered sets, and $X \cong Y$, then the similarity maps the least upper bound (if any) of each subset of $X$ onto the least upper bound of the image of that subset. 
\end{exercise}
    \begin{proof} Let $X, Y$ be stated as above. And suppose that $S \subset X$ has a least upper bound, $s^*$. This implies that for all $s \in S$, $s \leq s^*$ and for any other upper bound $x \in X$, $x \leq s^*$ implies $x = s^*$. Suppose, to the contrary, that $f(s^*)$ was not the least upper-bound of $f(S)$. Since $f$ is order preserving, we have that $f(s^*)$ is an upper-bound for $f(S)$. Let $\alpha \neq f(s^*)$ be the l.u.b. of $f(S)$ (since $f$ is onto there exists some $x \in X$ such that $\alpha = f(x)$. Thus from here, $\alpha = f(x)$); for all $f(s) \in f(S)$, we have $f(s) \leq f(x)$, and that for any other upper-bound $z$ of $f(S)$, $z \leq f(x)$ implies $z = f(x)$, in particular, this implies that $s^* \geq x$. But then, since $f$ is order-preserving, we have that $f(s) \leq f(x)$ implies that $s \leq x$ for all $s \in S$. But since $s^*$ is the l.u.b. for $S$, we must have  $s^* \leq x$. Since $X$, and consequently $S$ is well-ordered, it is partially ordered, and so $s^* = x$, a contradiciton.
    \end{proof}
    
\newpage
\begin{mdframed}
\section{Ordinal Numbers}
\end{mdframed}
This page was intentionally left blank; there were not specified exercises for this section. 

\newpage
\begin{mdframed}
\section{Sets Of Ordinal Numbers}
\end{mdframed}
This page was intentionally left blank; there were not specified exercises for this section. 

\newpage
\begin{mdframed}
\section{Ordinal Arithmetic}
\end{mdframed}
This page was intentionally left blank; there were not specified exercises for this section. 

\newpage
\begin{mdframed}
\section{The Schr\"oder-Bernstein Theorem}
\end{mdframed}

\begin{exercise} Let $X$, and $Y$ be sets. Suppose that $f: X \rightarrow Y$, is a function, and $g: Y \rightarrow X$, is a function. We prove that there exist subsets $A \subset X$, $B \subset Y$ such that $f(A) = B$, and $g(Y-B) = X - A$. (This statement is used to prove the Schr\"oder-Bernstein theorem.)
\end{exercise}
    \begin{proof} Let $X$, $Y$, $f$ and $g$ be stated as above. Throughout this exercise, we will use $f[A]$ instead of the more common, yet less accurate, $f(A)$. We look at four cases: 
        \begin{itemize}
        \item $f$ onto, and $g$ is not: In this case, we have $f[X] = Y$, and $g[Y-f(X)]= g[Y - Y] = g[\emptyset] = \{\} = X - X$. Thus, choosing $A = X \subset X$ and $B = \{\} \subset Y$, the result follows. 
        \item $g$ onto, and $f$ is not: In this case, we have $f[\emptyset] = \emptyset$, and $g[Y - \emptyset] = g(Y) = X = X- \{\}$. Thus, choosing $A = \{\} \subset X$, and $B = \{\} \subset Y$, the result follows. 
        \item $f$ onto, $g$ onto: Again, in this case, letting $A = \emptyset \subset X$ we have $f[\emptyset] = \emptyset$, and $g[Y- \emptyset] = g[Y] = X = X -\emptyset$; the result follows. 
        \item $f$ not onto, $g$ not onto: We point out that since neither $f$ nor $g$ is onto, there exists some $\bar{x} \in X$ such that the fiber of $\bar{x}$ under $g$ is empty. Likewise, there exists some $\bar{y} \in Y$ such that the fiber of $\bar{y}$ under $f$ is empty. Let $F_{\{\}}$ be the set of all such $\bar{x} \in X$. 
        \par For any $x \in X$ such that the fiber of $x$ under $g$ is not empty, either $g^{-1}[x] = \{f(x)\}$ or $f(x) \in g^{-1}[x]$, and $g^{-1}[x] \neq \{f(x)\}$. In the first case, let $F_{\{f(x)\}}$ be the set of all $x \in X$ such that $g^{-1}[x] = \{f(x)\}$ and then let $F_x$ be the set of all $x \in X$ for which $f(x) \in g^{-1}[x]$, and $g^{-1}[x] \neq \{f(x)\}$. From the section on relations, we have that $X$ is partitioned by $F_{\{\}}$, $F_x$ and $F_{\{f(x)\}}$. That is, these sets are pairwise disjoint, and their union is $X$. 
        \par These sets have some interesting properties. Namely $g[ Y- f[F_{\{\}}]]= g [f[F_x] \cup f[F_{\{f(x)\}}]]$. This is from the fact that $F_{\{\}}$, $F_x$, and $F_{\{f(x)\}}$ partition $X$ and that if $g$ is not mapping from to the set $F_{\{\}}$, then it must map to the other two.  Likewise, $g[ Y- f[F_{\{f(x)\}}]] = g [f[F_x] \cup f[F_{\{ \}}]]$.
        \par The claim is that the subset $A$ of $X$, so desired is, $F_{\{\}} \cup F_{\{f(x)\}}$. We compute: 
            \begin{align}
            g \Big[ Y - \big( f[F_{\{\}}] \cup f[F_{\{f(x)\}}] \big) \Big] & = g \Big[ Y- f[F_{\{\}}]\Big] \cup g\Big[Y - f[F_{\{f(x)\}}] \Big] \nonumber \\
            & = g\Big[ f[F_{x}] \cup f[F_{\{f(x)\}}]\Big] \cup g\Big[ f[F_{x}] \cup f[F_{\{\}}]\Big] \nonumber \\
            & = g\Big[f[F_x]\Big] \cup g\Big[f[F_{\{\}}]\Big] \nonumber \\ 
            & = g\Big[f[F_x]\Big] \cup \emptyset \\
            & = g\Big[f[F_x]\Big] \nonumber \\
            & = F_x \nonumber
            \end{align}
        Where the second line follows form the comments above, and (1) is from the construction of $F_{}$. Indeed, from the comments above, $X - (F_{\{\}} \cup F_{\{f(x)\}}) = F_x$. 
        \end{itemize}
    \end{proof}

\begin{exercise} We prove the Schr\"oder-Bernstein theorem using the above exercise. 
\end{exercise}
    \begin{proof} Suppose that $X \precsim Y$, and $Y \precsim X$. Then, there exist some $f:X \rightarrow Y$ such that $f$ is 1-1 and onto a subset $Y'$ of $Y$. Likewise, there exists some $g: Y \rightarrow X$ which is 1-1 and onto a subset $X'$ of $X$. We note that if either $X' = X$ or $Y' = Y$, then we are done. So, suppose that $X' \neq X$ and $Y' \neq Y$. Likewise, if either $X'$ or $Y'$ was the empty set, then we are done, since it is trivially true that $X \sim Y$.So, suppose that $X' \subsetneq X$, such that $X' \neq \emptyset$, and $Y' \subsetneq Y$ and $Y' \neq Y$.
    \par So, consider $f|_{X - X'}$ and $g|_{Y - Y'}$. From the previous theorem, there exists a subset $X'' \subset X - X'$ and some $Y'' \subset Y - Y'$ such that $f|_{X -X'}[X''] = Y''$ and $g|_{Y - Y'}[(Y - Y') - Y''] = (X -X') - X''$.  We claim that $\emptyset = (X - X') - X''$ i.e. $X '' = X - X'$; if not, then $g|_{Y - Y'}[(Y - Y') - Y''] \neq \emptyset$ and so there is some $g(y) \in X'$ such that $y \in (Y - Y') - Y''$. But then, we have $f(g(y)) \in Y' \not\subset (Y - Y') - Y''$; this implies that $y \in Y'$, a contradiction. Thus, $X'' = X - X'$.
    \par Since this is the case, $f|_{X -X'}[X''] \subset Y'$. But then, $g|_{Y - Y'}[(Y-Y') - f|_{X -X'}[X''] ] = g|_{Y - Y'}[Y-Y'] = (X - X') - X'' = \emptyset$. This implies that $Y - Y' = \emptyset$, or in other words, $Y = Y'$. A contradiction. 
    \end{proof}

\newpage
\begin{mdframed}
\section{Countable Sets}
\end{mdframed}

\begin{exercise} We prove that the set of all finite subsets of a countable set is countable. 
\end{exercise}
    \begin{proof} The following proof was suggested  \href{https://proofwiki.org/wiki/Set_of_Finite_Subsets_of_Countable_Set_is_Countable}{ by this website:} 
    \par Let $A(n)$ be the set of subsets of $A$ with no more than $n$ elements. Thus, $A(0)= \{a\}$, $A(1)=A(0) \cup \{\{a\}: a \in A\}$ and for all $n \geq 0$:
    $$A(n+1) = \{a(n) \cup a(1): a(n) \in A(n) \land a(1) \in A(1)\}$$ We verify, by induction, that each $A(n)$ is countable. Let $A$ be countable. Then, $A(1)$ is countable, by construction. Suppose $A(n)$ is countable. Then by since the union of countable sets is countable, $A(n+1)$ is also countable.
    \par Denote with $A_f$ as the set of finite subsets of $A$. It is apparent that every finite subset is in some $A(n)$, and so:
    $$A_f = \bigcup_{n \in \mathbb{N}}A(n)$$
    And since the union of countable subsets is countable, $A_f$ is countable. 
    \end{proof}
    
\begin{exercise} We prove that if every countable subset of a totally ordered set $X$ is well ordered, then $X$ itself is well ordered. 
\end{exercise}
    \begin{proof} Let $A \subset X$ be an arbitrary countable subset. Then, $A$ is well-ordered, and every subset $a$ of $A$ is well-ordered, so they have least elements. Let $\bigcup_n A_n$ be the union of all countable subsets of $X$. Since $\bigcup_n A_n$ is the union of well-ordered sets, it is well-ordered. The claim is that $\bigcup_n A_n = X$: 
    \par Suppose otherwise; Since $\bigcup_n A_n \subset X$, it follows that $X = \bigcup_n A_n \cup (X - \bigcup_n A_n) = \bigcup_n A_n \cup Y$. Since $\bigcup_n A_n$ is the union of all countable subsets of $X$, $Y$ must be finite; otherwise, we have missed a countable subset. But, since $Y$ is finite, $Y$ is included in some countable subset of $X$. Thus, 
    $$X = \bigcup_n A_n \cup Y = \bigcup_n A_n$$
    This contradiction concludes the proof. 
    \end{proof}
    
\newpage
\begin{mdframed}
\section{Cardinal Arithmetic} 
\end{mdframed}

\begin{exercise} We prove that if $a,b,c$ and $d$ are cardinal numbers such that $a \leq b$ and $c \leq d$, then $a + c \leq b + d$. 
\end{exercise}
    \begin{proof} Let $a,b,c,d$ be stated as given. By definition, there exists sets $A,B,C,D$ (without loss of generality, pairwise disjoint) with cardinality $a,b,c,d$, respectively. Using the stated conditions, we have $A \precsim B$, $C \precsim D$. Thus, there exists $B' \subset B$, and $D' \subset D$ such that $A \sim B'$ and $C \sim D'$ i.e. $\card A = \card B'$ and $\card C = \card D'$. Then, $a + b = b' + d' \leq b + d$. 
    \end{proof}
    
\begin{exercise} We prove that if $a,b,c$ and $d$ are cardinal numbers such that $a \leq b$ and $c \leq d$, then $ac \leq bd$. 
\end{exercise}
    \begin{proof} We proceed in a fashion similar to exercise $24.1$. Let $a,b,c,d$ be stated as given. By definition, there exists sets $A,B,C,D$ (without loss of generality, pairwise disjoint) with cardinality $a,b,c,d$, respectively. Using the stated conditions, we have $A \precsim B$, $C \precsim D$. Thus, there exists $B' \subset B$, and $D' \subset D$ such that $A \sim B'$ and $C \sim D'$ i.e. $\card A = \card B'$ and $\card C = \card D'$. Thus, $ab = \card (A \times B) = \card(B' \times D')$. From a previous exercise and the comments on page 94, we have $B' \times D' \precsim B \times D$, and so it follows that $\card(B' \times D') \leq \card(B \times D)$.  
    \end{proof}
    
\begin{exercise} We prove that if $\{a_i\}$ $(i \in I)$ and $\{b_i\}$ $(i \in I)$ are families of cardinal numbers such that $a_i < b_i$ for each $i \in I$, then $\sum_i a_i \leq \prod_i b_i$.
\end{exercise}
    \begin{proof} The following proof was suggested to me by Sophie C.. 
    \par Note, 
    $$\sum_i a_i = a_0 + a_1 + \dots \leq a_0 \times a_1 \times \dots = \prod_i a_i $$
    We proceed by mathematical induction. 
        \begin{itemize}
        \item \textit{Initial Case}: $a_0 < b_0$ --- By assumption.
        \item \textit{Hypothesis}: Suppose that $\prod_{0 \leq i \leq n} a_i < \prod_{0 \leq i \leq n}b_i$
        \item \textit{Step}: $\prod_{0 \leq i \leq n} a_i + a_{n+1} < \prod_{0 \leq i \leq n}b_i \times b_{n+1}$ for $a_{n+1} < b_{n+1}$. Therefore, $\prod_{0 \leq i \leq n+1} a_i < \prod_{0 \leq i \leq n+1}b_i$
        \end{itemize}
    From the above, we have $\sum_{i} a_i \leq \prod_i a_i < \prod_{i}b_i$. Which completes the proof. 
    \end{proof}

\begin{exercise} We prove that if $a,b$ and $c$ are cardinal numbers such that $a \leq b$, then $a^c \leq b^c$.
\end{exercise}
    \begin{proof} The following proof was suggested by Sophie C.. We take the definition of $a^c$ as multiply $a$ by itself $c$ times. And likewise for $b^c$. We proceed by mathematical induction: 
        \begin{itemize}
        \item \textit{Initial Case}: $a^1 \leq b^1$.
        \item \textit{Inductive Hypothesis}: Suppose that $\prod_{i \in I} a_i \leq \prod_{i \in I} b_i$ such that $\card I = C$. 
        \item \textit{Step}: If $\prod_{i \in I} a_i \leq \prod_{i \in I} b_i$, then $\prod_{i \in I} a_i \times a \leq \prod_{i \in I} b_i \times b$, since $a \leq b$.
        \end{itemize}
    Thus, $\prod_{i \in I} a_i \leq \prod_{i \in I} b_i$ where $\card I = C + 1$. And so, $a^c \leq b^c$
    \end{proof}

\begin{exercise}Prove that if $a$ and $b$ are finite, greater than $1$, and if $c$ is infinite, then $a^c = b^c$. 
\end{exercise}
    \begin{proof} The following proof was suggested by Sophie C..  We take the definition of $a^c$ as multiply $a$ by itself $c$ times. And likewise for $b^c$. If $c$ is countable then, $a^c, b^c$ are countable, and if $c$ is uncountable, then $a^c, b^c$ are uncountable. Thus, $a^c = b^c$
    \end{proof}

\begin{exercise} We prove that if $a$ and $b$ are cardinal numbers at least one of which is infinite, then $a+b = ab$. 
\end{exercise}
    \begin{proof} The following proof was suggest by Sophie C.. Suppose that $a,b$ are given as stated. Without loss of generality, there exists sets $A,B$ such that $\card A = a, \card B = b$, and $A \sim B'$, for some $B' \subset B$. Thus, $a + b = \card A \sim \card B' \cup \card B = \card (A \cup B) \sim \card (B' \cup B) = \card B = b = ab$. Therefore, $a+b=ab$.
    \par Suppose that $a$ and $b$ are both infinite, then as above, we have $a + b = a + a = a$ and $ab = aa = a$. Therefore, $a+b = ab$. 
    \par Suppose, without loss of generality, that $a$, and $b$ are both infinite such that $\card A < \card B$. Then, $a + b = b$ and $ab = b$, thus, $a + b = ab$.
    \end{proof}

\begin{exercise} We prove that if $a$ and $b$ are cardinal numbers such that $a$ is infinite and $b$ is finite, then $a^b = a$. 
\end{exercise}
    \begin{proof} The following proof was suggested by Sophie C.. Suppose that $a,b$ are given, as above. Then, $a^b = \prod_{i \in I} a_i$ where $\card I = b$ and where $a_i = a$, for all $ i \in I$. Then, we have the following: 
        \begin{align*}
        a^b & = \card (A \times A \times \dots \times A) \quad \text{where $\card A = a$} \\
        & = a \times a \times \dots \times a \quad \text{$b$ times} \\
        & = a \times a \times \dots \times a \quad \text{$b/2$ times, since $a \times a = a$} \\
        & = a \times a \times \dots \times a \quad \text{$b/4$ times, since $a \times a = a$} \\
        & \vdots \\
        & = a
        \end{align*}
    This completes the proof. 
    \end{proof}

\newpage 
\begin{mdframed}
\section{Cardinal Numbers}
\end{mdframed}

\begin{exercise} We prove that each infinite cardinal number is a limit number. 
\end{exercise} 
    \begin{proof} This proof was inspired from \href{http://euclid.colorado.edu/~monkd/m6730/gradsets06.pdf}{this website.}
    \par Suppose to the contrary that $k$ is an infinite cardinal which was not a limit number. Then, $k = a^+$ for some ordinal $a^+$. If $a$ is finite, we are done. Otherwise, we proceed to show that $k = a$. 
    \par Not that since $k$ is infinite, $\omega \precsim k$, and in particular, $\omega \precsim a$. Thus, consider $\phi: a \rightarrow k$ given by $\phi(0) = a$, and $\phi(m^+) = m$ (if $m \in \omega$), and $\phi(x) = x$ (if $x \in a - \omega$). We show that $\phi$ is a 1-1 and onto function:
        \begin{itemize}
        \item \textit{Well-Defined}: Since no ordinal is equivalent to its successor, it follows that $\phi$ is well-defined. 
        \item \textit{Everywhere Defined}: By construction, this is clear. 
        \item \textit{1-1}: If $\phi(x) = \phi(y)$, then in any of the cases, we have $x = y$. 
        \item \textit{Onto}: Let $k_1 \in k$. Then, either $k_1 \in a$, or $k_1 = a$. In either case, there exists a $\ell \in a$ for which $\phi ( \ell) = a$.
        \end{itemize}
    Thus $k = a$, a contradiction. 
    \end{proof}

\begin{exercise} We answer a few questions: If $\card A = a$, what is the cardinal number of the set of all 1-1 and onto in $A$? What is the cardinal number of the set of all countably infinite subsets of $A$? 
\end{exercise}
    \begin{proof} If $A$ is infinite, then $\omega \precsim A$ and we can consider the infinitely manly maps $f_i$, such that $i \in \omega$, given by $f_i(x) = x + 1$ (if $x \in \omega$), and $f_i(x) = x$ (if $x \in A - \omega$). However, if $A$ is finite, then a simple counting argument show that the number is the multiplication of all predecessors of $a$, except zero. 
    \par This answer was suggested by \href{http://math.stackexchange.com/questions/184746/the-cardinality-of-the-set-of-countably-infinite-subsets-of-an-infinite-set}{this website}: "$A$ has $a^{\omega}$ countably infinite subsets, and there’s not much more that you can say unless you know something about the cardinal $a$. For example, $2 \leq a \leq 2^{\omega}$, then $a^{\omega} = 2^{\omega}$. If cf $a ={\omega}$, i.e., if $a$ has cofinality $\omega$, then $a^{\omega} > a$."
    \end{proof}
    
\begin{exercise} We prove that if $\alpha, \beta$ are ordinal numbers, then $\card (\alpha + \beta) = \card \alpha + \card \beta$ and $\card \alpha \beta = \card \alpha \card \beta$. We use the ordinal interpretation of the operations on the left side and the cardinal interpretation on the right. 
\end{exercise}
    \begin{proof}The following proof was suggested by Sophie C.. We compute: 
        \begin{itemize}
        \item $\card \alpha \beta = \card (\ord A \ord B) = \card( \ord (A \times B)) = \card (A \times B)$
        \item $(\card \alpha)( \card \beta) = (\card(\ord A))(\card(\ord B)) = \newline
        \card(A) \card(B) = \card(A \times B)$
        \end{itemize}
    Thus, $\card \alpha \beta = (\card \alpha)( \card \beta)$
    \end{proof}
    
    \begin{proof} The following proof was suggest by Sophie C.. We compute: 
        \begin{itemize}
        \item $\card(\alpha + \beta) = \card (\ord A + \ord B) = \card( \ord(A \cup B)) = \ord (A \cup B) = \ord(A) + \ord(B) = \card(\ord(A)) + \card(\ord(B)) = \card \alpha + \card \beta$.
        \end{itemize}
    Thus, $\card(\alpha + \beta) = \card \alpha + \card \beta$.
    \end{proof}

\newpage
\begin{mdframed} 
\section{Extra Exercises}
\end{mdframed}

Many of these exercises were collaborations with other student. They are not marked exercises in the text, however, they are useful.

\subsection{Arithmetic}

\begin{exercise} We show that addition for elements of $\omega$ is associative. The following proof was suggested by Aidan H. and David H., and I attribute all credit to them.  
\end{exercise}
    \begin{proof} We proceed by mathematical induction: By the recursion theorem there exists a function $s_m:\omega\to\omega$ such that $s_m(0)=m$ and $s_m(n^{+})=(s_m(n))^{+}$ where $m,n\in\omega$ and $s_m(n)=m+n$.First note $s_{k+m}(n)=(k+m)+n$, and similarly $s_k(m+n)=k+(m+n)$. Consider the set $T=\{n\in\omega\mid s_{k+m}(n)=s_k(m+n)\}$.
\newline

Initial case: See that $0\in T$ since $s_{k+m}(0)=k+m=s_k(m+0)=k+(m+0)=k+m$.
\newline

Inductive hypothesis: Let $n\in T$ hold. Then $s_{k+m}(n)=s_k(m+n)$.

This implies $(k+m)+n=k+(m+n)$.

Now $s_{k+m}(n^{+})=(k+m)+n^{+}=(s_{k+m}(n))^{+}=((k+m)+n)^{+}$.

Similarly, $s_k((m+n)^{+})=k+(m+n)^{+}=(s_k(m+n))^{+}=(k+(m+n))^{+}$.
\newline

Since $s_{k+m}(n)=s_k(m+n)$ by the inductive hypothesis. We obtain
$$(k+m)+n^{+}=((k+m)+n)^{+}=(k+(m+n))^{+}=k+(m+n)^{+}$$

Note that $s_m(n)=m+n$, so $(s_m(n))^{+}=(m+n)^{+}=m+n^{+}=s_m(n^{+})$. 

Thus, $(k+m)+n^{+}=k+(m+n^{+})$
\newline

Conclusion: Therefore, $n^{+}\in T$, and thus $T=\omega$, and thus addition is associative.
    \end{proof}

\begin{exercise} We prove that addition is commutative. 
\end{exercise}
    \begin{proof}The following proof was suggested by Aidan H. and David H., and I attribute all credit to them.
    \par Let $B=\{m\in\omega\mid s_m(n)=s_n(m)\}$.
    \newline 
    Initial case: $0\in B$, since $s_0(n)=s_n(0)=n$.
    \newline
    Inductive hypothesis: Let $b\in B$ hold. That is, $s_b(n)=b+n=n+b=s_n(b)$. Then $s_n(b^{+})=(s_n(b))^{+}=(n+b)^{+}$, by definition. Similarly, $s_{b^{+}}(n)=(s_b(n))^{+}=(b+n)^{+}$. Then, by the inductive hypothesis, $s_{b^{+}}(n)=(s_b(n))^{+}=(s_n(b))^{+}=s_n(b^{+})$. 
    \newline
    Inductive conclusion: $b^{+}\in B$. Thus, by the induction principle, $B=\omega$. This implies $s_m(n)=s_n(m)$ $\forall m,n\in\omega$, and thus $m+n=n+m$ $\forall m,n\in\omega$, and thus addition is commutative.
    \end{proof}

\begin{exercise} We prove the properties of exponentiation. 
\end{exercise}
    \begin{proof} The following proof was suggested by Aidan H. and David H., and I attribute all credit to them.
    \par First note $e_m:\omega\to\omega$ is a function defined as
    $$e_m(0)=1$$
    $$e_m(n^{+})=e_m(n)\cdot m\textnormal{\hspace{20px}where }e_m(n)=m^n\textnormal{ for }m,n\in\omega$$ 
    I want to show $m^{(n+l)}=m^n\cdot m^l$, that is $e_m(n+l)=e_m(n)\cdot e_m(l)$ for $m,n,l\in\omega$.
    \newline
    Define $P_m:\omega\to\omega$ such that $P_m(0)=0$ and $P_m(n^{+})=P_m(n)+m$, and $P_m(n)=m\cdot n$ for $m,n\in\omega$.
    First I will show $P_1(n)=n$ $\forall n\in\omega$ by induction.
    Consider the set $B=\{n\in\omega\mid P_1(n)=n\}$.
    Initial case: Note $0\in B$ since $P_1(0)=0$ by definition.
    \newline
    Inductive hypothesis: Let $n\in B$ hold, then $P_1(n)=n$.
    Then $P_1(n^{+})=P_1(n)+1=n+1=n^{+}$.
    \newline
    Inductive conclusion:  Thus $n^{+}\in B$ and by principle of mathematical induction, $B=\omega$. Thus, $P_1(n)=n$ $\forall n\in\omega$.
    \newline
    Now to show $m^{(n+l)}=m^n\cdot m^l$.
    Let $F=\{n\in\omega\mid e_m(n+l)=e_m(n)\cdot e_m(l)\}$.
    \newline
    Initial case: Note $0\in F$ since $e_m(0+l)=e_m(l)$ and
    $e_m(0)\cdot e_m(l)=1\cdot e_m(l)=P_1(e_m(l))=e_m(l)$.
    \newline
    Inductive hypothesis: Let $n\in F$ hold, then $e_m(n+l)=e_m(n)\cdot e_m(l)$.
    Then
        \begin{align*}
        e_m(n^{+}+l) & =e_m((n+l)^{+}) \\
        & =e_m(n+l)\cdot m \\ 
        & =e_m(n)\cdot e_m(l)\cdot m \\
        & =e_m(n)\cdot m\cdot e_m(l) \\
        & =e_m(n^{+})\cdot e_m(l)
        \end{align*}
    Inductive conclusion: Thus, $n^{+}\in F$, and by the principle of mathematical induction, $F=\omega$. Thus, $m^{(n+l)}=m^n\cdot m^l$ $\forall m,n,l\in\omega$.
    \end{proof}
    
\begin{exercise} We prove the left distributive law. 
\end{exercise} 
    \begin{proof} The following proof was suggested by Aidan H. and David H., and I attribute all credit to them. 
    \par We proceed by mathematical induction:
    \par Initial case:
    $$k\cdot(m+0)=k\cdot m+k\cdot0$$
    $$k\cdot m=k\cdot m+0=k\cdot m$$
    Inductive hypothesis: $k\cdot(mn)=k\cdot m+k\cdot n$
    Then 
    $$k\cdot(m+n^{+})=(k\cdot(m+n))^{+}\textnormal{ by definition of addition}$$
    $$=(k\cdot m+k\cdot n)^{+}=k\cdot m+(k\cdot n)^{+}\textnormal{ by hypothesis and addition}$$ 
    $$=k\cdot m+k\cdot n^{+}\textnormal{ by definition of addition}$$
    $$\textnormal{Conclusion: }k\cdot(m+n^{+})=k\cdot m+k\cdot n^{+}$$
    \end{proof}
    
    
    
\end{document}