%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%

% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Winter 2020 by Cynthia Bailey Lee

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage{hyperref}
\usepackage{minted}
\usepackage{cancel}
\usepackage{tabularx}
\usepackage{makecell}
\usepackage{changepage}
\usepackage{xcolor}
\usepackage{colortbl}
\usepackage{array}
\usepackage{fourier}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set 3}
\author{Your Name(s) Here}
\date{\today}

% Running author based on https://tex.stackexchange.com/a/68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 3}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2020}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}
\newcommand{\nb}[1]{\multicolumn{1}{c}{\textit{#1}}}
\newcommand{\homog}{\,E\,}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parskip}{6pt}
\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\definecolor{incorrect}{RGB}{182,0,12}
\usetikzlibrary{arrows}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
% end MZ

\tikzset{
  relates/.style={very thick, arrows={-triangle 60}},
  toploop/.style={out=135, in=45, loop, looseness=5},
  bottomloop/.style={out=225, in=-45, loop, looseness=5},
  leftloop/.style={out=135, in=225, loop, looseness=5},
  rightloop/.style={out=45, in=-45, loop, looseness=5},
  trloop/.style={out=90, in=0, loop, looseness=5},
  tlloop/.style={out=180, in=90, loop, looseness=5},
  blloop/.style={out=-90, in=180, loop, looseness=5},
  brloop/.style={out=0, in=-90, loop, looseness=5},
  toparrowright/.style={out=45, in=135, looseness=0},
  bottomarrowleft/.style={out=225, in=-45, looseness=0},
  toparrowleft/.style={out=135, in=45, looseness=0},
  bottomarrowright/.style={out=-45, in=225, looseness=0},
  leftarrowdown/.style={out=225, in=135, looseness=0},
  rightarrowup/.style={out=45, in=-45, looseness=0},
  leftarrowup/.style={out=135, in=225, looseness=0},
  rightarrowdown/.style={out=-45, in=45, looseness=0}
}

\begin{document}

\maketitle

\begin{center}
    \textit{This checkpoint problem is due on Monday at 2:30PM.}
\end{center}

\section*{Checkpoint Problem One: Binary Relations}

The first part of this problem revolves around a mathematical construct called \emph{homogeneous coordinates} that shows up in computer graphics. If you take CS148, you'll get to see how they're used to quickly determine where to display three-dimensional objects on screen. \\

Let $\R^2$ denote the set of all ordered pairs of real numbers. For example $(137, 42) \in \R^2$, $(\pi, e) \in \R^2$, and $(-2.71, 103) \in \R^2$. Two ordered pairs are equal if and only if each of their components are equal. That is, we have $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$. \\

Consider the relation $E$ defined over $\R^2$ as follows:
$$(x_1, y_1) E (x_2, y_2) \text{ if } \exists k \in \R.(k \neq 0 \land (kx_1, ky_1) = (x_2, y_2)).$$
For example, $(3, 4) E (6, 8)$ because $(2 \cdot 3, 2 \cdot 4) = (6, 8)$. \\

For this problem, we want to see how you would structure a proof that $E$ is an equivalence relation over $\R^2$. The structure has 6 important parts, an ``assume'' and a ``want to show'' for each of the three properties: reflexive, symmetric, and transitive. We want you to separately state what these six parts of the proof would be. It would also be a good idea for you to just go ahead and complete the proof from there, but \emph{you will not turn that in}. (If you want feedback on the fully-written proof, you are welcome to compare it to the solutions, which will include that, or come to office hours for consultation.)

\begin{enumerate}[label=\roman*.]
    \item On its own line, clearly marked ASSUME, write down the assumption for the \textbf{reflexive} part of the proof. As we learned in class, this includes properly introducing any variables you need to state the assumption.
        
    \begin{shaded}
    \textbf{ASSUME:} Write your assumption here.
    \end{shaded}
    
     \item On its own line, clearly marked WANT TO SHOW (or W.T.S.), write down the ``want to show'' for the \textbf{reflexive} part of the proof. 
        
    \begin{shaded}
    \textbf{W.T.S:} Write your want to show statement here.
    \end{shaded}
    
     \item On its own line, clearly marked ASSUME, write down the assumption for the \textbf{symmetric} part of the proof. As we learned in class, this includes properly introducing any variables you need to state the assumption.
        
    \begin{shaded}
    \textbf{ASSUME:} Write your assumption here.
    \end{shaded}
    
     \item On its own line, clearly marked WANT TO SHOW (or W.T.S.), write down the ``want to show'' for the \textbf{symmetric} part of the proof. 
        
    \begin{shaded}
    \textbf{W.T.S:} Write your want to show statement here.
    \end{shaded}
    
    \item On its own line, clearly marked ASSUME, write down the assumption for the \textbf{transitive} part of the proof. As we learned in class, this includes properly introducing any variables you need to state the assumption.
        
    \begin{shaded}
    \textbf{ASSUME:} Write your assumption here.
    \end{shaded}
    
     \item On its own line, clearly marked WANT TO SHOW (or W.T.S.), write down the ``want to show'' for the \textbf{transitive} part of the proof. 
        
    \begin{shaded}
    \textbf{W.T.S:} Write your want to show statement here.
    \end{shaded}
    
    
    
    \annotate{Remember that the ``if'' in the definition of the relation $E$ means ``is defined as'' and isn't an implication. Follow the advice of the Guide to Proofs on Discrete Structures and the Discrete Structures Proofwriting Checklist: don't use quantifiers or connectives in your written proof. The in-class questions have you predict the first sentences of proofs, so those would be a great guide for what this means. You may want to start or by taking the  first-order statement in the definition here, and the first-order logic definitions of reflexive, symmetric, and transitive, to help guide your determination of what the assumption and want to show are. Here is an (unrelated) example to remind you. For theorem ``If $n$ is even, then $n^2$ is even," we would write: }
    \begin{shaded}
    \emph{delete this example} \\
    \textbf{ASSUME:} Pick an arbitrary even integer $n$. \\
    \textbf{W.T.S:} We want to show that $n^2$ is even. 
    \end{shaded}

    
\end{enumerate}

\pagebreak

\begin{center}
    \emph{These problems are due on Friday at 2:30PM.}
\end{center}

\section{Computational Equivalence Relations}
\begin{shaded}
  Submit your edited \textsf{BinaryRelations.cpp} file through Gradescope.
\end{shaded}

\pagebreak

\section{Building Binary Relations}
Let's begin with a new definition. A \emph{preorder} is a binary relation that's
both reflexive and transitive.
\begin{enumerate}[label=\roman*.]
  \item Below is a drawing of a relation that is not a preorder. Add the
    smallest number of arrows possible to this diagram to make it a preorder.
    No justification is required. \\
\end{enumerate}
\begin{tabularx}{\textwidth}{|X|X|}
  \hline
  \makecell[c]{\emph{Original Relation}} &
  \makecell[c]{\emph{That Relation, Expanded to a Preorder}} \\
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (0,0) {$c$};
      \node[state] (d) at (2,0) {$d$};
      \draw[relates] (a) -> (b);
      \draw[relates] (a) to [rightarrowdown] (c);
      \draw[relates] (c) to [leftarrowup] (a);
      \draw[relates] (c) -> (d);
    \end{tikzpicture}\\~} &
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (0,0) {$c$};
      \node[state] (d) at (2,0) {$d$};
      \draw[relates] (a) -> (b);
      \draw[relates] (a) to [rightarrowdown] (c);
      \draw[relates] (c) to [leftarrowup] (a);
      \draw[relates] (c) -> (d);
      % TODO: Add arrows here for 3i
    \end{tikzpicture}\\~}\\\hline
\end{tabularx}

This problem is about building new relations from old ones. Heres one way to do
this. If $R$ is a binary relation over $A$, the \emph{symmetric component of
$\boldsymbol{R}$}, denoted $\boldsymbol{E_R}$, is a binary relation over $A$
defined as follows:
\[
  aE_Rb \quad \textrm{if} \quad aRb \land bRa
\]

\begin{enumerate}[resume*]
  \item Draw the symmetric component of the relation on the left by adding
    arrows on the right
\end{enumerate}
\begin{tabularx}{\textwidth}{|X|X|}
  \hline
  \makecell[c]{\emph{Original Relation}} &
  \makecell[c]{\emph{Its Symmetric Component}} \\
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (4,2) {$c$};
      \node[state] (d) at (0,0) {$d$};
      \node[state] (e) at (2,0) {$e$};
      \node[state] (f) at (4,0) {$f$};
      \draw[relates] (a) -> (b);
      \draw[relates] (a) -> (d);
      \draw[relates] (d) to [rightarrowup] (a);
      \draw[relates] (b) -> (c);
      \draw[relates] (b) -> (e);
      \draw[relates] (c) to [rightloop] (c);
      \draw[relates] (d) to [leftloop] (d);
      \draw[relates] (d) -> (e);
      \draw[relates] (e) to [rightarrowup] (b);
      \draw[relates] (e) -> (f);
      \draw[relates] (f) -> (c);
      \draw[relates] (f) to [bottomarrowleft] (e);
    \end{tikzpicture}\\~} &
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (4,2) {$c$};
      \node[state] (d) at (0,0) {$d$};
      \node[state] (e) at (2,0) {$e$};
      \node[state] (f) at (4,0) {$f$};
      % TODO: Add arrows here for 3ii
    \end{tikzpicture}\\~}\\\hline
\end{tabularx}

\begin{enumerate}[resume*]
  \item Prove that if $R$ is a preorder over a set $A$, then $E_R$ is an
    equivalence relation.
\end{enumerate}

\annotate{$E_R$ is defined in terms of $R$, but you can't assume $E_R$
  reflexive and transitive just because $R$ is. You need to prove that. Go
  slowly. To prove $E_R$ is transitive, what would you assume, and what do you
  need to show?}

\begin{shaded}
  Provide a proof here.
\end{shaded}

Here's another way to form new relations from old ones. If $R$ is a binary
relation over $A$, the \emph{asymmetric component of $\boldsymbol{R}$}, denoted
$\boldsymbol{S_R}$, is a binary relation over $R$ over $A$ defined as follows:
\[
  a S_R b \quad \textrm{if} \quad a R b \land b \cancel{R} a
\]

\begin{enumerate}[resume*]
  \item Draw the asymmetric component of the relation on the left by adding
    arrows on the right.
\end{enumerate}
\begin{tabularx}{\textwidth}{|X|X|}
  \hline
  \makecell[c]{\emph{Original Relation}} &
  \makecell[c]{\emph{Its Asymmetric Component}} \\
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (4,2) {$c$};
      \node[state] (d) at (0,0) {$d$};
      \node[state] (e) at (2,0) {$e$};
      \node[state] (f) at (4,0) {$f$};
      \draw[relates] (a) -> (b);
      \draw[relates] (a) -> (d);
      \draw[relates] (d) to [rightarrowup] (a);
      \draw[relates] (b) -> (c);
      \draw[relates] (b) -> (e);
      \draw[relates] (c) to [rightloop] (c);
      \draw[relates] (d) to [leftloop] (d);
      \draw[relates] (d) -> (e);
      \draw[relates] (e) to [rightarrowup] (b);
      \draw[relates] (e) -> (f);
      \draw[relates] (f) -> (c);
      \draw[relates] (f) to [bottomarrowleft] (e);
    \end{tikzpicture}\\~} &
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (4,2) {$c$};
      \node[state] (d) at (0,0) {$d$};
      \node[state] (e) at (2,0) {$e$};
      \node[state] (f) at (4,0) {$f$};
      % TODO: Add arrows here for 3iv
    \end{tikzpicture}\\~}\\\hline
\end{tabularx}

\begin{enumerate}[resume*]
  \item \textbf{UPDATE: You may skip the problem that was here as 2.v} 
\end{enumerate}




\section{Composition, Identity, Existence, and Uniqueness}

Although we often speak about how relations are applied (for example, that $1 <
4$ or that $\varnothing \subseteq \mathbb{N}$), binary relations are
mathematical objects in their own right, and we can talk about manipulating
relations algebraically. This question explores how.

Given two relations $R_1$ and $R_2$ over the same set $A$, we say that
$\boldsymbol{R_1 \subseteq R_2}$ if the following statement is true:
\[
  \forall a \in A.~\forall b \in A.~(a R_1 b \rightarrow a R_2 b).
\]

Just as we say that two sets are equal if they're each subsets of the other, if
$R_1$ and $R_2$ are binary relations over the same set $A$, we say that
$\boldsymbol{R_1 \mathbf{=} R_2}$ if $R_1 \subseteq R_2$ and $R_2 \subseteq
R_1$.

\begin{enumerate}[label=\roman*.]
  \item Consider the following relations over the set $\mathbb{Z}$. First,
    there's the $\equiv_2$ relation that you saw on Problem Set One. Second,
    there's the $\sim$ relation where $x \sim y$ holds when $x + y$ is even.
    Prove that $\equiv_2 = \sim$.
\end{enumerate}
\annotate{This is a great spot to write out two columns, one for what to assume
  and one for what you need to show.}
\begin{shaded}
  Provide a proof here.
\end{shaded}

Next, let's introduce a way of combining relations together. Given two binary
relations $R_1$ and $R_2$ over some set $A$, the \emph{composition} of $R_1$
and $R_2$, denoted $R_1 \circ R_2$, is the binary relation over $A$ defined as
\[
  x(R_1 \circ R_2)y \qquad \textrm{if} \qquad \exists z \in A. (x R_1 z \land z
  R_2 y)
\]
Let's do a quick check-in to make sure these definitions make sense.
\begin{enumerate}[resume*]
  \item Below are pictures of binary relations $R_1$ and $R_2$ over some set
    $A$. Add arrows to the diagrams on the bottom to show the relation $R_1
    \circ R_2$ and the relation $R_2 \circ R_1$, respectively.
\end{enumerate}
\begin{tabularx}{\textwidth}{|X|X|}
  \hline
  \makecell[c]{\emph{Relation $\boldsymbol{R_1}$}} &
  \makecell[c]{\emph{Relation $\boldsymbol{R_2}$}} \\
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (0,0) {$c$};
      \node[state] (d) at (2,0) {$d$};
      \draw[relates] (a) -> (b);
      \draw[relates] (a) -> (c);
      \draw[relates] (d) to [rightloop] (d);
    \end{tikzpicture}\\~} &
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (0,0) {$c$};
      \node[state] (d) at (2,0) {$d$};
      \draw[relates] (a) -> (c);
      \draw[relates] (b) -> (a);
      \draw[relates] (b) -> (c);
      \draw[relates] (b) -> (d);
      \draw[relates] (d) -> (c);
    \end{tikzpicture}\\~}\\\hline
  \makecell[c]{\emph{Arrows to Show $\boldsymbol{R_1 \circ R_2}$}} &
  \makecell[c]{\emph{Arrows to Show $\boldsymbol{R_2 \circ R_1}$}} \\
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (0,0) {$c$};
      \node[state] (d) at (2,0) {$d$};
      % TODO: Add arrows here for 4ii
    \end{tikzpicture}\\~} &
  \makecell{
    \tikzset{every state/.style={scale=1, fill=black!8, very thick,
      circle,inner sep=0pt, minimum size=.2in}}
    \begin{tikzpicture}[on grid, auto,
        baseline={(current bounding box.north)}, scale=.7]
      \node[state] (a) at (0,2) {$a$};
      \node[state] (b) at (2,2) {$b$};
      \node[state] (c) at (0,0) {$c$};
      \node[state] (d) at (2,0) {$d$};
      % TODO: Add arrows here for 4ii
    \end{tikzpicture}\\~}\\\hline
\end{tabularx}

Now, a new definition. Given a set $A$, a binary relation $I_A$ is called an
\emph{identity relation over $\boldsymbol{A}$} if the following statement is
true for \textit{every} binary relation $R$ over $A$:
\[
  I_A \circ R = R \qquad \land \qquad R \circ I_A = R
\]
In other words, composing \textit{any} binary relation $R$ over $A$ with $I_A$,
either on the left or the right, has the same effect as not doing any
composition at all.
\begin{enumerate}[resume*]
  \item Let $A$ be an arbitrary set. Fill in the following blank in the simplest
    way possible to define an identity relation over $A$. No justification is
    necessary.
\end{enumerate}
\annotate{While you don't need to prove this, you should definitely triple-check
  your answer. You'll need to know what this relation is for another problem on
  this problem set.}
\begin{shaded}\[
    x I_A y \qquad \textrm{if} \qquad \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\]\end{shaded}

In the above problem we spoke of an identity relation over a set $A$, but we
just as easily could have spoken of the identity relation over $A$ because, for
each set $A$, there's exactly one identity relation.

The question, then, is how you show that there's only one object with some
property. From your answer to part (iii) of this problem, you know that there
is at least one identity relation. Your answer to part (iii) is therefore
sometimes called an \emph{existence proof}, since it shows that something
exists. (We didn't ask you to formally prove that your answer was correct, but
if you were to do so, that would be an existence proof.)

You now need to prove that there is \textit{at most one} identity relation,
which is often called a \emph{uniqueness proof}. To prove that there is only
one object of some type, the standard technique is to assume you have two
different objects that each have the given property, then to prove that they're
actually the same object. In pseudo-first-order logic notation you'd want to
prove this:
\[
  \forall I_1.~\forall I_2.~(IdentityRelation(I_1) \land IdentityRelation(I_2)
  \rightarrow I_1 = I_2).
\]
In other words, if you think you've found two different identity relations,
you've really just found two different names for the same thing.
\begin{enumerate}[resume*]
  \item Based off the discussion in the above paragraphs, prove that there is
    exactly one identity relation $I_A$ for each set $A$.
\end{enumerate}
\annotate{As a hint, you can write a fully rigorous proof of this result
  without referencing what it means for one relation to be a subset of another.
  Look at the definition of an identity relation, which gives a series of
  equalities involving an identity relation. Can you make use of those
  equalities here?}
\begin{shaded}
  Provide a proof here.
\end{shaded}




\section{Preorders, Composition, and Identities}
There's an surprising connection between the concepts from Problem Three and
Problem Four:
\begin{center}
  \begin{minipage}{.5\textwidth}
    \emph{Theorem:} If $R$ is a binary relation over a set $A$, then $R$ is a
    preorder if and only if $I_A \subseteq R$ and $R \circ R \subseteq R$.
  \end{minipage}
\end{center}
This might look like a lot of symbols, so let's back up a bit and talk about
what this means. Intuitively, you can think of this result as letting us switch
back and forth between two different views of binary relations. The left-hand
side of this biconditional talks about binary relations in the way we've mostly
seen them discussed so far: we have some rules (reflexivity, transitivity) that
talk about how binary relations behave with regards to individual elements.
The right-hand side talks about binary relations more as whole objects in their
own right, exploring more ``algebraic'' properties of those relations. And the
biconditional linking them means that we can switch between these
representations whenever we find it useful to do so!

The rest of this problem asks you to prove this.
\begin{enumerate}[label=\roman*.]
  \item Prove the reverse direction: if $R$ is a binary relation over $A$ where
    $I_A \subseteq R$ and $R \circ R \subseteq R$, then $R$ is a preorder.
\end{enumerate}
\annotate{This one is all about setting things up properly and working through
  the definitions slowly and methodically. Use the strategy we discussed in
  class when working with cyclic relations: write out two columns, one
  containing everything you're going to assume and one containing everything
  that you're going to prove. Specifically think about the following: you will
  be assuming that $I_A \subseteq R$; what exactly does that mean? Plug $I_A$
  into the definition of what it means for one relation to be a subset of
  another and see what that tells you. Similarly, if you're assuming $R \circ R
  \subseteq R$, what exactly does that tell you? Then think about what you need
  to prove. What do you have to show to prove that $R$ is a preorder? As
  always, drawing pictures never hurts!}
\begin{shaded}
  Provide a proof here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove the forward direction: if $R$ is a binary relation over $A$ and
    $R$ is a preorder, then $I_A \subseteq R$ and $R \circ R \subseteq R$.
\end{enumerate}
\annotate{The same advice from part (i) applies here. Go slowly and
  methodically, writing out what it is that you’re assuming and what you need to
  prove in two separate columns and drawing pictures as needed.}
\begin{shaded}
  Provide a proof here.
\end{shaded}

\section{Properties of Functions}
\begin{shaded}
  Submit your edited \textsf{FunctionsVennDiagram.h} file through Gradescope.
\end{shaded}

\pagebreak

\section{Permutation Dances}

There's a dance in which each dancer has an assigned position. In the first
dance, the dancers begin in the positions indicated on the left (it's a
top-down view, and we've numbered the dancers 0, 1, \dots, 9). In the second
dance, some dancers have moved to new starting positions, and the overall
arrangement is what's shown on the right.

\begin{center}
\begin{minipage}{0.35\textwidth}
\begin{flushright}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (90:3) {0};
  \node[state] (1) at (162:2) {1};
  \node[state] (2) at (234:3) {2};
  \node[state] (3) at (90:2) {3};
  \node[state] (4) at (18:3) {4};
  \node[state] (5) at (306:2) {5};
  \node[state] (6) at (162:3) {6};
  \node[state] (7) at (306:3) {7};
  \node[state] (8) at (18:2) {8};
  \node[state] (9) at (234:2) {9};
\end{tikzpicture}
\end{flushright}
\end{minipage}
\hfill\vline\hfill
\begin{minipage}{0.35\textwidth}
\tikzset{every state/.style={inner sep=1pt,minimum size=0pt}}
\begin{tikzpicture}[scale=.7,on grid,auto,baseline={(current bounding box.north)}]
  \node[state] (0) at (306:2) {0};
  \node[state] (1) at (90:3) {1};
  \node[state] (2) at (162:3) {2};
  \node[state] (3) at (90:2) {3};
  \node[state] (4) at (18:3) {4};
  \node[state] (5) at (234:2) {5};
  \node[state] (6) at (162:2) {6};
  \node[state] (7) at (18:2) {7};
  \node[state] (8) at (306:3) {8};
  \node[state] (9) at (234:3) {9};
\end{tikzpicture}
\end{minipage}
\end{center}

How can we model how the dancers' positions changed from the first dance to the
second? For now, focus on Dancer 0. Notice that, in the second dance, Dancer 0
has moved to the inner position in the bottom-right pair. That's the spot that
was occupied by Dancer 5 in the first dance. In that sense, from Dancer 0's
perspective, she starts off the second dance at ``the spot that Dancer 5 used
to occupy.''

We can do this for other people as well. Look at Dancer 8, for example. Dancer
8 ended up in the outer position in the bottom-right pair, which is where
Dancer 7 used to be. So we could instruct Dancer 8 to get to his new location
by saying ``go to where Dancer 7 was in the previous dance.''

How about Dancer 3? Notice that Dancer 3 started in the inner pair of the
top-center pair, and that's where she ended up as well. If we wanted to
instruct Dancer 3 how to prepare for the second dance, we could tell her ``go
to the spot that Dancer 3 was in in the first dance.'' It's a little verbose,
but it works!

More generally, we can move from the first dance to the second by telling each
dancer whose spot they should take. This method of rearranging a group of
things (here, people, but in principle they could be anything) by indicating
how each item takes on a position previously held by some item is called a
\emph{permutation}, which is at the heart of this problem.

To make this rigorous, let's introduce some notation. First, for any natural
number $k$, let's have
$$\llbracket k \rrbracket = \{ n \in \N \mid n < k \}$$
In other words, $\llbracket k \rrbracket$ is the set of all natural numbers
less than $k$. The people in our dance can be represented as $\llbracket 10
\rrbracket$. Next, let's think of how everyone swaps around. This is something
we can model as a function that takes as input a person, then outputs which
person's position they should move to. In our case, we could represent this as
a function $f : \llbracket 10 \rrbracket \rightarrow \llbracket 10 \rrbracket$.
For example, we'd have $f(0) = 5$.

\begin{enumerate}[label=\roman*.]
    \item Just to make sure everything makes sense at this point, what is $f(6)$?
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

Formally speaking, a \emph{permutation} of a collection of items $A$ is a
bijection $\sigma : A \rightarrow A$ from $A$ to itself. (That's a lower-case
Greek letter sigma, by the way, in case you haven't encountered it before.)
There's a good reason this definition says a permutation is a
\textit{bijection}, rather than just a plain old \textit{function}.

\begin{enumerate}[resume*]
  \item Let's go back to our example of dancers changing places. Imagine that
    there's a dance where the dancers start off in some initial configuration.
    To set up for the next dance, each dancer moves to the spot previously
    occupied by one of the dancers, and after everyone has set up all positions
    are filled. If we model that change as a function as we did here, explain
    why that function must be a bijection. No formal proof is necessary, but
    you should address the rigorous definition of a bijection in your answer.
\end{enumerate}
\annotate{It might help to think of things this way: what happens if that
  function \emph{isn't} a bijection?}
\begin{shaded}
  Write your answer here.
\end{shaded}

There's a nice notation that's often used to describe permutations called
\emph{two-line notation}. In the top line, we list the objects being permuted
in some nice, human-readable order. Then, below each object, we write the
object whose position it ends up in after the objects move. For example, the
two-line notation
$$
  \begin{pmatrix}
    0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
    1 & 3 & 5 & 7 & 9 & 2 & 4 & 6 & 8 & 0
  \end{pmatrix}
$$
could be read as ``Dancer 0 moves to the position previously held by Dancer 1,
Dancer 1 moves to the position previously held by Dancer 3, Dancer 2 moves to
the position previously held by Dancer 5, etc.'' This isn't the permutation
described in the previous picture; it's just an example of the notation.

\begin{enumerate}[resume*]
  \item Look back at the dances from the previous page. The function $f$ we
    described earlier tells each dancer whose position to take when setting up
    for the second dance. Express the function $f$ using two-line notation by
    filling in the following blanks:
\end{enumerate}
\begin{shaded}
$$
  \begin{pmatrix}
    0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
    \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_
  \end{pmatrix}
$$
\end{shaded}

Now, let's imagine that there's a third dance scheduled and the dancers yet
again need to change places. At the end of the first dance, Dancer 0 moved to
the spot that Dancer 5 started off in. To make things easier for Dancer 0,
imagine that she adopts the following strategy: starting with the second dance,
she \textit{always} lines up for the next dance in by moving to the position
Dancer 5 held in the prior dance.

\begin{enumerate}[resume*]
  \item Where will Dancer 0 be at the start of the third dance? Provide your
    answer in the following way: determine which position Dancer 0 will be in,
    then look back at the original configuration of the dancers and tell us
    whose position Dancer 0 would be standing in. For example, if Dancer 0
    would end up in the outer position in the bottom-right pair, you'd say that
    Dancer 0 ends in the position originally held by Dancer 7.
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

Now, imagine that \textit{every} dancer adopts a strategy similar to Dancer 0.
Each dancer $n$ is assigned some dancer $f(n)$ that they're tasked with
following. For each dance after the first, Dancer $n$ then sets up at the spot
where Dancer $f(n)$ was standing at the start of the previous dance.

\begin{enumerate}[resume*]
  \item If all the dancers adopt this strategy, where will Dancer 0 end up at
    the start of the \textit{fourth} dance? Again, express your answer by looking back
    at the original configuration of dancers from the first dance and telling
    us whose position Dancer 0 will be occupying.
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

In parts (iv) and (v) of this problem, you've explored an important idea. We
can use the original positions of the dancers as a way of identifying each
location. That is, rather than saying ``the dancer in the top center
position,'' we can say ``the position that Dancer 0 occupies in the first
dance.''

Let's imagine we want to know where some dancer is going to be in the third
dance. We have a permutation $f$ that explains how all the dancers change
positions from the first dance to the second. Can we somehow manipulate $f$ to
see where everyone ends up for the third dance?

\begin{enumerate}[resume*]
  \item Suppose you pick Dancer $n$ and want to figure out where he starts in
    the third dance. Explain why he will be in the spot originally occupied by
    person $(f \circ f)(n)$ in the first dance. No formal proof is necessary.
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Starting with your answer from part (iii) of this problem, write out
    the permutation $f \circ f$ using two-line notation by filling in the
    following blanks:
\end{enumerate}
\begin{shaded}
$$
  \begin{pmatrix}
    0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
    \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_
  \end{pmatrix}
$$
\end{shaded}

Permutations are important objects in mathematics. We'll see them later this
quarter when exploring how they pin down abstract concepts like ``symmetry'' in
a geometric sense. But you can also use them to deeply explore fundamental
questions of what invertible transformations look like. Curious to learn more
about that? Take Math 120!

\pagebreak

\section{Left, Right, and True Inverses}

In lecture, we briefly touched on the idea of inverse functions. It turns out
that the notion of what an inverse function is is a bit more nuanced than it
appears. Specifically, there are several different notions of what an inverse
can be, each of which behaves in a slightly different way. This question
explores three different notions of inverse functions, along with their
properties.

Let $f : A \to B$ be a function.  A function $g : B \to A$ is called a
\textbf{\textit{left inverse}} of $f$ if the following is true:
$$\forall a \in A.\ g(f(a)) = a.$$

\begin{enumerate}[label*=\roman*.]
  \item Find examples of a function $f$ and two \textit{different} functions
    $g$ and $h$ such that both $g$ and $h$ are left inverses of $f$. This shows
    that left inverses don't have to be unique. (Two functions $g$ and $h$ are
    different if there is some $x$ where $g(x) \neq h(x)$.) Express your answer
    by drawing pictures along the lines of what we did in class: draw ovals
    representing the sets $A$ and $B$, add dots to those ovals to denote their
    elements, then express $f$, $g$, and $h$ by drawing arrows between those
    dots.
\end{enumerate}
\annotate{If you draw $A$ and $B$ as sets, then arrows from $A$ to $B$ represent
  applying the function $f$, and arrows from $B$ back to $A$ represent applying
  the function $g$. So look back at what you found when you expanded out the
  definition. Can you express that in terms of arrows going left and right
  between these sets?}
\begin{shaded}
  Place your picture here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove that if $f$ is a function that has a left inverse, then $f$ is
    injective.
\end{enumerate}
\annotate{As a hint on this problem, look back at the proofs we did with
  injections in lecture. To prove that a function is an injection, what should
  you assume about that function, and what will you end up proving about it?}
\begin{shaded}
  Provide a proof here.
\end{shaded}

Let $f : A \to B$ be a function.  A function $g : B \to A$ is called a
\textbf{\textit{right inverse}} of $f$ if the following is true:
$$\forall b \in B.\ f(g(b)) = b.$$

\begin{enumerate}[resume*]
  \item Find examples of a function $f$ and two different functions $g$ and $h$
    such that both $g$ and $h$ are right inverses of $f$. This shows that right
    inverses don't have to be unique. As in part (i), express your answer by
    drawing pictures of $f$, $g$, and $h$ along the lines of what we did in
    lecture.
\end{enumerate}
\begin{shaded}
  Place your picture here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove that if $f$ is a function that has a right inverse, then $f$ is
    surjective.
\end{enumerate}
\begin{shaded}
  Provide a proof here.
\end{shaded}

If $f : A \to B$ is a function, then a \textbf{\textit{true inverse}} (often
just called an \textbf{\textit{inverse}}) of $f$ is a function $g$ that's
simultaneously a left and right inverse of $f$. In parts (i) and (iii) of this
problem you saw that functions can have several different left inverses or
right inverses. However, a function can only have a single true inverse.

\begin{enumerate}[resume*]
  \item Prove that if $f : A \to B$ is a function and both $g_1 : B \to A$ and
    $g_2 : B \to A$ are inverses of $f$, then $g_1(b) = g_2(b)$ for all $b \in
    B$.
\end{enumerate}
\begin{shaded}
  Provide a proof here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Explain why your proof from part (v) doesn't work if $g_1$ and $g_2$
    are just \textit{left} inverses of $f$, not full inverses. Be specific --
    you should point at a specific claim in your proof that is no longer true
    in this case.
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Explain why your proof from part (v) doesn't work if $g_1$ and $g_2$
    are just \textit{right} inverses of $f$, not full inverses. Be specific --
    you should point at a specific claim in your proof that is no longer true
    in this case.
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

Left and right inverses have some surprising applications. We'll see one of
them next week!

\pagebreak

We've included two optional fun problems for this problem set. Feel free to
work through all of them, but please submit at most one of them for credit. If
you submit answers to more than one, we won't have the bandwidth to grade all
your answers and will just pick one arbitrarily. (Here, by ``arbitrarily,'' we
mean ``based on a whim and without any deeper reason,'' as in ``the CEO made
her decisions arbitrarily and capriciously, much to the chagrin of her
underlings.'')

\section*{Optional Fun Problem One: Semilattices (Extra Credit)}

A preorder $R$ over a set $A$ is called a \emph{semilattice} if it satisfies
the following property:
$$
  \forall a \in A.~\forall b \in A.~\exists c \in A.~(c R a \land c R b \land
    \forall d \in A.~(d R a \land d R b \rightarrow d R c)).
$$
A semilattice $R$ over a set $A$ is called a \emph{full lattice} if it also
satisfies this property:
$$
  \forall a \in A.~\forall b \in A.~\exists c \in A.~(a R c \land b R c \land
    \forall d \in A.~(a R d \land b R d \rightarrow c R d)).
$$
Give an example of a semilattice that is not a full lattice, then prove that
your relation has the required properties. (That is, you'll need to prove it's
a preorder, prove that it does have the first property, and prove that it
doesn't have the second property.)

\begin{shaded}
  Write your example and proof here.
\end{shaded}

\section*{Optional Fun Problem Two: Infinity Minus Two (Extra Credit)}

Let $[0, 1]$ denote the set $\{ x \in \R\ |\ 0 \le x \le 1 \}$ and $(0, 1)$
denote the set $\{ x \in \R\ |\ 0 < x < 1 \}$. That is, the set $[0, 1]$ is the
set of all real numbers between 0 and 1, \textit{inclusive}, and the set $(0,
1)$ is the set of all real numbers between 0 and 1, \textit{exclusive}. These
sets differ only in that the set $[0, 1]$ includes 0 and 1 and the set $(0, 1)$
excludes 0 and 1.

Give the definition of bijection $f : [0, 1] \rightarrow (0, 1)$ via an
explicit rule (i.e. writing out $f(x) = \underline{\hspace{15ex}}$ or defining
$f$ via a piecewise function), then prove that your function is a bijection.

\begin{shaded}
  Write your definition and proof here.
\end{shaded}
\end{document}