%
% 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.
%
\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{tabu}
\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#3}
\author{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#3}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2018}
\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}
\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{\parindent}{0pt}
\pagestyle{fancy}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\begin{document}
\maketitle
\section{So What Exactly is a Binary Relation, Anyway?}
\begin{shaded}
Submit your edited $\mathsf{BinaryRelations.cpp}$ and $\mathsf{.relation}$ files through GradeScope.
\end{shaded}
\section{Redefining Strict Orders}
In Friday's lecture,
we defined equivalence relations as relations that are
reflexive, symmetric, and transitive.
Interestingly, it turns out that we could have left asymmetry out of our definition and just gone with
irreflexivity and transitivity.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that a binary relation $R$ over a set $A$ is a strict order if and only if the relation $R$ is irreflexive
and transitive.
\textit{\textcolor{blue}{ Once you've written up your proof, take a minute to critique your proof by applying the Proofwriting
Checklist and the Discrete Structures Proofwriting Checklist. Also, think about the following:
\begin{itemize}
\item The statement you need to prove here is a biconditional. How do you prove a biconditional statement?
What should you be assuming in each part of the proof? What do you need to prove?
\item At some point, you'll need to prove that R is asymmetric under some set of assumptions. What does
a proof of asymmetry look like? What should you be assuming? What should you be proving?
\item The proof you will be doing here will involve reasoning about arbitrarily-chosen binary relations
where you have no idea what the relation is or what set it's over and only know some properties that
it must have (say, that it's irreflexive). In cases like these, be very careful not to make claims about
how the relation works that don't immediately follow from your assumptions. After all, your relation
could be something like the $<$ relation over $\N$, or the $\subsetneq$ relation over $\wp(\R)$, or the ``runs strictly
faster than'' relation over people.
\end{itemize}
}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
Going forward, it turns out that one of the easiest ways to prove that a relation is a strict order is to prove
that it's irreflexive and transitive. In fact, that's such good advice that we're going to remind you of it later
on in this problem set. \smiley \\
While we could have left irreflexivity out of the definition of a strict order, we could \textit{not} have left out transitivity.
\begin{enumerate}[resume*]
\item Edit the file $\mathsf{PartD.relation}$ in the $\mathsf{res/}$ directory of the starter files to define a binary relation
that is irreflexive and asymmetric, but not transitive. This shows that a relation that's asymmetric and irreflexive isn't
necessarily a strict order.
\begin{shaded}
Submit your edited $\mathsf{.relation}$ file through GradeScope.
\end{shaded}
\end{enumerate}
As a final note, it turns out that we \textit{also} could have equivalently defined strict orders to be binary relations
that are asymmetric and transitive. We're not going to ask you to prove this, but it's a great exercise if you
want to give it a try!
\section{Covering Relations and Hasse Diagrams}
Let $R$ be some strict order over a set $A$. The \textit{\textbf{covering relation for R}}, denoted \textbf{Cov}$\mathbf{(R)}$, is a binary relation over the set $A$ that's defined as follows:
\begin{center}
$x$ Cov($R$) $y$\quad if\quad $x R y \land \neg\exists z \in A.\ (x R z \land z R y)$
\end{center}
That definition is quite a mouthful, and, as with many dense mathematical definitions, you're not expected
to be able to look at it and immediately understand it. Instead, you'll build up an understanding for what
the definition means by playing around with it in a few example cases and seeing if you can spot a pattern.
Trust us -- the above definition has a really nice intuition once you've gotten the hang of it. (In case you're
wondering, the notation $x \text{Cov}(R) y$ is read aloud as ``$y$ covers $x$'' or ``$x$ is covered by $y$.'') \\
The above definition works for any strict order $R$ over any set $A$, but it's probably easier to see how it
works by looking at how it works for a particular choice of a strict order.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Consider the $<$ relation over the set $\N$.
What is its covering relation $\text{Cov}(<)$? To provide your answer,
fill in the blank below,
then briefly justify your answer:
\begin{center}
$x$ Cov($<$) $y$\quad if\quad \underline{\hspace{35ex}}
\end{center}
For full credit, you should fill in the blank in the simplest way possible. There's a really short answer
you can provide that doesn't require any first-order logic. See if you can find it!
\textit{\textcolor{blue}{As a hint for how to approach the above problem, a perfectly reasonable strategy is to start off by picking
random pairs of natural numbers $x$ and $y$ and seeing whether $x \text{Cov}(<) y$ by looking at the above definition.
If you repeat this enough times, you can start formulating a hypothesis of how you think $\text{Cov}(<)$ behaves,
and eventually you'll land at the answer. Another option would be to plug in $<$ and $\N$ into the above definition,
then to look over what comes back and see if you can make sense of what you've found.}}
\begin{shaded}
\begin{answer}
$ $
\begin{center}
$x$ Cov($<$) $y$\quad if\quad \underline{Write your answer here.}
\end{center}
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
Now that you've found out what $\text{Cov}(R)$ looks like in one particular instance, it's reasonable to go and ask
what properties you might expect of a cover relation. Are cover relations equivalence relations? Are they
strict orders? It's hard to tell this just by eyeballing the definition given above, but now that you have a
concrete example of a cover relation in hand, you can start to think about how to answer these questions.
\begin{enumerate}[resume*]
\item Prove that the relation $\text{Cov}(<)$ you found in part (i) is \textbf{\textit{not}} a strict order. This shows that if you
start with a strict order and take its cover, you don't necessarily get back a strict order.
\textit{\textcolor{blue}{As a hint, if you're trying to show that some relation isn't a strict order, what exactly is it that you need to
prove about that relation? Start of by getting out a piece of scratch paper and writing out what you'd need
to prove. If you do this properly, you should find that you need to prove that one of three (or two) things is
true about the binary relation. You can then investigate whether each of those properties is true about
$\text{Cov}(<)$ and use that to determine what you'll need to prove.}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
So you now know what $\text{Cov}(<)$ looks like, and you know that cover relations aren't always strict orders.
But at this point, you only have a single example of a cover relation. To get a better sense for what cover
relations look like more generally, it might help to look at some other strict orders and their covers.
\begin{enumerate}[resume*]
\item Consider the $\subsetneq$ relation over the set $\wp(\N)$.
This relation is the strict subset relation, where $S \subsetneq T$ means that $S \subseteq T$ but that $S \neq T$.
What is its covering relation?
Provide your answer in a similar fashion to how you answered part (i)
of this problem, and briefly justify your answer.
\textit{\textcolor{blue}{As you're working through this problem, make sure you can answer the following question: what does it
mean for $\subsetneq$ to be a binary relation over $\wp(\N)$?}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
You might be wondering why on earth you'd ever want to look at cover relations. It turns out that they
have a nice visual intuition.
\begin{enumerate}[resume*]
\item Let $R$ be a strict order over a set $A$.
There is a close connection between the covering relation $\text{Cov}(R)$ and the Hasse diagram of the strict order $R$.
What is it? Briefly justify your answer, but no proof is required.
\textit{\textcolor{blue}{You may want to draw some pictures.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
At this point, you've started with a Hairy Scary Definition that's full of dense first order logic terms, gotten
to see what it looks like in some concrete cases, and learned some of the properties of that definition.
Nice job! To round out this section, we'd like you to write a short piece of code that lets you get a visual
intuition for what covering relations look like.
\begin{enumerate}[resume*]
\item Implement a function
\begin{center}
$\mathsf{Relation\ coverOf(Relation\ R);}$
\end{center}
that takes as input a binary relation $R$, which you can assume is a strict order, and returns $\text{Cov}(R)$.
(As a reminder, don't forget to fill in the domain of $\text{Cov}(R)$ before you return it!)
\begin{shaded}
Submit your edited $\mathsf{BinaryRelations.cpp}$ file through GradeScope.
\end{shaded}
\end{enumerate}
Our provided starter files are designed so that you can see what the cover relations of different strict orders
look like. Just choose the ``Show Covering Relation'' option from the middle dropdown menu. If
you've selected a strict order, it will show just the arrows from the covering relation. \\
The provided example relations include a sample of the less than relation over $\N$ and a sample of the
strict subset relation over $\wp(\N)$. We strongly recommend using the code you wrote to visualize what their
cover relations look like and to compare what you find against the answers you came up with in parts (i)
and (iii). Does what you see in practice match what you predicted in theory?
\section{Strict Orders and C++ Operator Overloading}
The C++ programming language lets you define your own custom types. For example, here's a type representing
a pixel's position on the screen:
\begin{minted}{c++}
struct Pixel {
int x;
int y;
};
\end{minted}
This is a \textit{structure}, a type representing a bunch of different objects all packaged together as one. Here, this
structure type groups together two \mintinline{c++}{int}s named x and y. The name \mintinline{c++}{Pixel} refers to a type, just
like \mintinline{c++}{int} or \mintinline{c++}{string}. You can create variables of type \mintinline{c++}{Pixel} just as you can variables of any other
type, like this:
\begin{minted}{c++}
Pixel p;
\end{minted}
One you have a variable of type \mintinline{c++}{Pixel}, you can access the constituent elements of the \mintinline{c++}{struct} by using
the dot operator. For example:
\begin{minted}{c++}
Pixel p;
p.x = 137;
p.y++;
\end{minted}
As you've seen in Problem Set One and Problem Set Two, in the C++ standard library there's a type
called \mintinline{c++}{std::set} which represents a set of values. The \mintinline{c++}{std::set} is (usually) implemented with a data
structure called a \textit{binary search tree}. (The details of how binary search trees work are covered in CS106B,
and so we won't go into detail about how they work). Of interest here, this means that the \mintinline{c++}{std::set} type
requires that elements of the stored type be comparable using the < operator. For primitive types like \mintinline{c++}{int}
and \mintinline{c++}{double}, that's not a problem. However, if you took the above \mintinline{c++}{Pixel struct} and tried to form a
\mintinline{c++}{std::set}, you'd get some horrible compiler errors because, by default, it's not possible to compare
two \mintinline{c++}{Pixels} using the < operator. On my system, making a \mintinline{c++}{std::set} generates \textit{ninety-six}
lines of compiler errors that ultimately track back to the missing less-than operator. \\
To address this, C++ has a feature called \textit{operator overloading} that us define how to apply the < operator
to \mintinline{c++}{Pixel}s so that we can make a \mintinline{c++}{std::set} without the compiler yelling at us. In C++, the syntax
for overloading the less-than operator on \mintinline{c++}{Pixel}s looks like this:
\begin{minted}{c++}
bool operator < (Pixel lhs, Pixel rhs) {
/* ... do some work, then return true or return false ... */
}
\end{minted}
That syntax might look a bit frightening, so let's dissect it. The above is a definition of a C++ function.
The name of the function is \mintinline{c++}{operator <} (yes, that's a legal function name). It takes in two \mintinline{c++}{Pixels}, which
correspond to the two operands to the < sign (the first argument is the one on the left, and the second is
the one on the right), and it returns a \mintinline{c++}{bool} indicating whether the \mintinline{c++}{Pixel} named \mintinline{c++}{lhs} is ``less than'' the \mintinline{c++}{Pixel} named \mintinline{c++}{rhs}. Aside from the funny name, this function behaves just like every other C++ function, and you can put whatever code in it that you'd like. \\
The folks who designed the C++ programming language happened to be very familiar with discrete mathematics,
and so the language standard gives a bunch of rules about how this \mintinline{c++}{operator <} function should
behave. If you define a custom \mintinline{c++}{operator <} function for a type you want to use with \mintinline{c++}{std::set}, C++ requires
that the < relation be a strict order over the underlying type. \\
This question explores the connection between C++ coding and all this theory we've built up about binary
relations. For the purposes of this problem, you can assume that the $<$ relation over integers is a strict order
and that it behaves the way you've seen it behave in high school math classes.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Now let's imagine that we implement \mintinline{c++}{operator <} for \mintinline{c++}{Pixel}s using the following function:
\begin{minted}{c++}
bool operator < (Pixel lhs, Pixel rhs) {
return lhs.x < rhs.x && lhs.y < rhs.y;
}
\end{minted}
This corresponds to the following relation $F$ over the set of all pixels:
\begin{center}
$pFq$ \quad\quad if \quad\quad $p.x < q.x$ \quad $\land$ \quad $p.y < q.y$
\end{center}
Prove that the relation $F$ defined over the set of all \mintinline{c++}{Pixel}s this way is a strict order.
\textit{\textcolor{blue}{As a reminder, as you saw on Problem One, to prove that F is a strict order, you just need to show that it's
irreflexive and transitive. There's no need to prove asymmetry.}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Alternatively, suppose that we implement \mintinline{c++}{operator <} for \mintinline{c++}{Pixel}s using the following function:
\begin{minted}{c++}
bool operator < (Pixel lhs, Pixel rhs) {
return lhs.x < rhs.x || lhs.y < rhs.y;
}
\end{minted}
This corresponds to the following relation $G$ over the set of all pixels:
\begin{center}
$pGq$ \quad\quad if \quad\quad $p.x < q.x$ \quad $\lor$ \quad $p.y < q.y$
\end{center}
\textit{\textbf{Prove or disprove}}: the relation $G$ defined over the set of all \mintinline{c++}{Pixel}s this way is a strict order.
\textit{\textcolor{blue}{At this point you have experience both proving that a relation is a strict order (you did this on the checkpoint
and in part (i) of this problem) and proving that a relation is not a strict order (you did this in part (ii) of
the problem on cover relations). To solve this problem, you'll need to first determine whether G is a strict order,
then write up a proof or disproof as appropriate. So consider approaching things this way: write out
what it is that you'd need to prove if you want to show that G is a strict order, and write out what it is that
you'd need to prove if you wanted to show that G is not a strict order. Then, look at what you find, play
around with what this would say about G, and see if you can decide which option is correct.}}
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
\item And finally, suppose that we implement \mintinline{c++}{operator <} for \mintinline{c++}{Pixel}s using the following function:
\begin{minted}{c++}
bool operator < (Pixel lhs, Pixel rhs) {
return (lhs.x < rhs.x) || (lhs.x == rhs.x && lhs.y < rhs.y);
}
\end{minted}
This corresponds to the following relation $H$ over the set of all pixels:
\begin{center}
$pHq$ \quad\quad if \quad\quad $p.x < q.x$ \quad $\lor$ \quad $(p.x = q.x \land p.y < q.y)$
\end{center}
\textit{\textbf{Prove or disprove}}: the relation $H$ defined over the set of all \mintinline{c++}{Pixel}s this way is a strict order.
\begin{shaded}
Provide a proof or disproof here.
\end{shaded}
\end{enumerate}
\section{Strict Weak Orders and C++ Operator Overloading}
\textit{(This is a follow-up to Problem Four, so you may want to complete it before attempting this problem.)} \\
The \mintinline{c++}{std::set} type imposes more restrictions on \mintinline{c++}{operator <} than just requiring it to be a strict order.
Specifically, the C++ requires that if you define a \mintinline{c++}{operator <} function for use in \mintinline{c++}{std::set}, that function
has to define a special kind of relation called a \textbf{\textit{strict weak order}} over the underlying type. \\
To understand what a strict weak order is, we need to introduce the notion of incomparability. Given a binary
relation $R$ over a set $A$, the \textbf{\textit{incomparability relation}} of $R$, denoted $\sim_R$, is this binary relation over $A$:
\begin{center}
$x \sim_R y$ \quad\quad if \quad\quad $x \cancel{R} y$ and $y \cancel{R} x$
\end{center}
Notice that there are slashes through those $R$'s, so $x \sim_R y$ means ``neither $xRy$ nor $yRx$ are true.'' This definition
might seem pretty abstract, so let's start by trying to make this a bit more concrete. (In case you're
wondering, the notation $x \sim_R y$ would be read aloud as ``$x$ is indistinguishable from $y$.'')
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Consider the $<$ relation over the set $\N$. What is the relation $\sim_<$? Provide your answer by filling in
the blank below. Briefly justify your answer, and see if you can find the simplest answer you can:
\begin{center}
$x \sim_< y$\quad if\quad \underline{\hspace{35ex}}
\end{center}
\textit{\textcolor{blue}{You already have experience solving problems like this one from when you did the cover relations problem.
See if the approach or approaches you took when solving that problem can help you out here.}}
\begin{shaded}
\begin{answer}
$ $
\begin{center}
$x \sim_< y$\quad if\quad \underline{Write your answer here.}
\end{center}
\end{answer}
Provide justification here.
\end{shaded}
\item Look at the $F$, $G$, and $H$ relations from Problem Four and determine what the $\sim_F$, $\sim_G$, and $\sim_H$
relations are by filling in the following blanks. As before, try to find the simplest possible answers that
you can, but no justifications are necessary.
\begin{center}
$p \sim_F q$\quad if\quad \underline{\hspace{35ex}} \\
$p \sim_G q$\quad if\quad \underline{\hspace{35ex}} \\
$p \sim_H q$\quad if\quad \underline{\hspace{35ex}}
\end{center}
\textit{\textcolor{blue}{The later parts of this problem will reference the answers that you came up with here, so make sure that
you've checked your work before moving on. Not sure how to do that? Pick a few random pairs of pixels.
Check whether the F, G, and H relations hold between those pixels in each direction. Based on that, determine
whether $\sim_F$, $\sim_G$, and $\sim_H$ should hold between those pixels. Then, see whether the definitions you came
up with above agree with those results. If you see a mismatch, it means that you probably didn't pin the
definition down correctly.}}
\begin{shaded}
\begin{answer}
$ $
\begin{center}
$p \sim_F q$\quad if\quad \underline{Write your answer here.}
\end{center}
\end{answer}
Provide justification here.
\end{shaded}
\begin{shaded}
\begin{answer}
$ $
\begin{center}
$p \sim_G q$\quad if\quad \underline{Write your answer here.}
\end{center}
\end{answer}
\end{shaded}
\begin{shaded}
\begin{answer}
$ $
\begin{center}
$p \sim_H q$\quad if\quad \underline{Write your answer here.}
\end{center}
\end{answer}
\end{shaded}
\end{enumerate}
And now, our key definition for this problem. A binary relation $R$ over a set $A$ is called a \textbf{\textit{strict weak order}}
if it is a strict order and its incomparability relation $\sim_R$ is transitive.
\begin{enumerate}[resume*]
\item Look at the $F$, $G$, and $H$ relations from Problem Four. For each of those relations, prove or disprove
the following claim: that binary relation is a strict \textit{weak} order over \mintinline{c++}{Pixel}s. You can reference
the definitions of $\sim_F$, $\sim_G$, and $\sim_H$ that you found above in the course of writing your proofs
without justifying why those definitions are correct.
\textit{\textcolor{blue}{As with all prove-or-disprove problems, we recommend getting out a sheet of scratch paper and writing out
two columns: what you'd need to show if you want to prove that a relation is a strict weak order, and what
you'd need to show if you want to disprove that a relation is a strict weak order.}}
\textit{\textcolor{blue}{As a hint, if you've done everything correctly up to this point, you should have found that exactly one of F,
G, and H is a strict weak order.}}
\begin{shaded}
Provide a proof or disproof for relation $F$ here.
\end{shaded}
\begin{shaded}
Provide a proof or disproof for relation $G$ here.
\end{shaded}
\begin{shaded}
Provide a proof or disproof for relation $H$ here.
\end{shaded}
\end{enumerate}
\section{Strict Weak Orders and Equivalence Classes}
\textit{(This is a follow-up to Problem Five, so you may want to complete it before attempting this problem.)} \\
As a refresher from Problem Five, a \textbf{\textit{strict weak order}} is a strict order $R$ over a set $A$
where the following relation, called the \textit{\textbf{incomparability relation}} is transitive:
\begin{center}
$x \sim_R y$ \quad\quad if \quad\quad $x \cancel{R} y$ and $y \cancel{R} x$.
\end{center}
You might wonder what's so special about the definition of a strict weak order that the C++ folks decided
to enshrine it in the formal language specification. The reason has to do with a specific property of strict
weak orders that connects them back to equivalence relations.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Prove that if $R$ is a strict weak order over a set $A$, then $\sim_R$ is an equivalence relation over $A$.
\textit{\textcolor{blue}{This is one of those problems where you need to be precise with what it is that you're assuming and what it
is you need to prove. The two-column strategy from lecture is a good one to use here. What exactly is it that
you're assuming about R? What do you need to prove about $\sim_R$? For each claim you need to prove about
$\sim_R$, how would you go about proving it?}}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
The Fundamental Theorem of Equivalence Relations, which we mentioned in class, essentially says that
every equivalence relation splits the elements of its underlying set apart into non-overlapping groups (the
equivalence classes of that relation). Your result from part (i) of this problem shows that if you have a strict weak
order $R$ over a set $A$, then $\sim_R$ ends up splitting the elements of $A$ into non-overlapping
equivalence classes. \\
A reasonable question to ask, then, is what exactly those equivalence classes would look like. Since you
happen to have a few strict weak orders lying around right now, it's reasonable to see what equivalence
classes you get back from those orders. \\
As a reminder, the notation $[p]_{\sim R}$ denotes the equivalence class of $p$ with respect to the $\sim_R$ relation.
\begin{enumerate}[resume*]
\item Let $p$ be a point whose $x$ and $y$ components $p.x$ and $p.y$ are chosen arbitrarily. In Problem Five
you found that one of the binary relations $R$ from Problem Four of this problem is a strict weak
order. For that relation, determine what $[p]_{\sim R}$ is and express your
answer as simply as possible by filling in the following blank. No proof is necessary.
\begin{center}
$[p]_{\sim R}$\quad =\quad \{\ \underline{\hspace{35ex}}\ \}
\end{center}
\textit{\textcolor{blue}{There are a few ways you might go about solving this problem. You could start of by writing out the definition
of an equivalence class, plugging in some point p, and then trying to simplify what you have by using
the definition of the incomparability relations you came up with earlier on. Or you could pick some pixel p
and start thinking about what pixels it would be incomparable with, then see if you can spot a pattern.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
The \mintinline{c++}{std::set} type, like the mathematical sets we've studied up to this point, does not allow for duplicate
elements. However, the way that it determines what a ``duplicate'' is is by looking at the $\sim_R$ relation corresponding
to \mintinline{c++}{operator <}. Specifically, whenever you insert an element $x$ into an \mintinline{c++}{std::set},
the \mintinline{c++}{std::set} will add it if there are no other elements of $[x]_{\sim R}$ already in the set and will discard
it otherwise. In other words, the \mintinline{c++}{std::set} only stores the first element of each equivalence class inserted into it.
\begin{enumerate}[resume*]
\item Suppose you insert the pixels (137, 42), (42, 137), (137, 103), and (42, 103) into an empty
\mintinline{c++}{std::set}, in that order, assuming that \mintinline{c++}{std::set} uses the strict weak order you
identified from Problem Four. Determine what the fnal contents of the \mintinline{c++}{std::set} will end up being. Briefly justify your answer; no formal proof is necessary.
\textit{\textcolor{blue}{As a hint, use your result from part (ii).}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
\section{Strict Weak Orders in Theoryland}
\textit{(This is a follow-up to Problem Six, so you may want to complete it before attempting this problem.)} \\
As a refresher from Problem Five, a \textbf{\textit{strict weak order}} is a strict order $R$ over a set $A$ where the following relation, called the \textbf{\textit{incomparability relation}}, is transitive:
\begin{center}
$x \sim_R y$ \quad\quad if \quad\quad $x \cancel{R} y$ and $y \cancel{R} x$
\end{center}
As you proved in Problem Six, if $R$ is a strict weak order, then $\sim_R$ is an equivalence relation. The notation
$[a]_{\sim R}$ refers to the equivalence class of $\sim_R$ containing $a$. It turns out that there's a beautiful interplay between the relation $R$ and the equivalence classes of $\sim_R$. \\
Let $R$ be a strict weak order over a set $A$ and consider any $x, y \in A$ where $xRy$. Prove that for any
$z \in A$ where $z \in [y]_{\sim R}$ that $xRz$. \\
\textit{\textcolor{blue}{ This is probably the trickiest proof involving binary relations that you've seen up to this point. Here are
some things to watch out for when you're working through this problem:
\begin{itemize}
\item We definitely don't recommend immediately jumping into a final proof of this result. You'll want to
go through some scratch work first.
\item Unpack the relevant terms and definitions. If $z \in [y]_{\sim R}$, what can you say about how y and z are related
by the relation R?
\item Be very careful not to make any claims that don't follow from your previous assumptions and the
definitions of the relevant terms. If you want to claim something like the following, for example,
you?d need to prove it first, since nothing in the definition of R or $\sim_R$ says that this should be true:
\begin{center}
If aRb and b $\sim_R$ c, then aRc
\end{center}
\end{itemize}
}}
\begin{shaded}
Provide a proof here.
\end{shaded}
And now some context! Your result from above shows that given two equivalence classes $[x]_{\sim R}$ and $[y]_{\sim R}$ of the incomparability relation, either every element of $[x]_{\sim R}$ relates to every element of $[y]_{\sim R}$, or every element of $[y]_{\sim R}$ relates to every element
of $[x]_{\sim R}$, or $[x]_{\sim R}$ and $[y]_{\sim R}$ are just different names for the same set. \\
Practically speaking, this makes strict weak orders excellent for setups where you need to keep things in
sorted order. If you pick any group of elements from a strict weak order, you sort them so that each element
relates to or is indistinguishable from all the elements after it. \\
Theoretically speaking, this means that the Hasse diagrams of strict weak orders can be nicely split apart
into a bunch of different ``layers,'' where each layer represents an equivalence class and each element of
each layer is connected directly to the layer above it. The layers must stack on top of one another and
there can't be any two ``incomparable'' layers thanks to what you proved above. \\
Here are some examples of what these might look like:
\begin{center}
\begin{tabu}{X[c] | X[c] | X[c]}
\begin{tikzpicture}[auto,node distance=1.5cm, minimum size=0.75cm,
thick,main node/.style={circle,draw}]
\node[main node] (1) {};
\node[main node] (2) [right of=1] {};
\node[main node] (3) [right of=2] {};
\node[main node] (4) [below left of=2] {};
\node[main node] (5) [below right of=2] {};
\node[main node] (6) [below right of=4] {};
\node[main node] (7) [below left of=6] {};
\node[main node] (8) [below of=6] {};
\node[main node] (9) [below right of=6] {};
\path[every node/.style={font=\sffamily\small}]
(1) edge node {} (4)
edge node {} (5)
(2) edge node {} (4)
edge node {} (5)
(3) edge node {} (4)
edge node {} (5)
(4) edge node {} (6)
(5) edge node {} (6)
(6) edge node {} (7)
edge node {} (8)
edge node {} (9);
\end{tikzpicture} & \begin{tikzpicture}[auto,node distance=1.5cm, minimum size=0.75cm,
thick,main node/.style={circle,draw}]
\node[main node] (1) {};
\node[main node] (2) [below of=1] {};
\node[main node] (3) [below of=2] {};
\node[main node] (4) [below of=3] {};
\path[every node/.style={font=\sffamily\small}]
(1) edge node {} (2)
(2) edge node {} (3)
(3) edge node {} (4);
\end{tikzpicture} & \begin{tikzpicture}[auto,node distance=1.5cm, minimum size=0.75cm,
thick,main node/.style={circle,draw}]
\node[main node] (1) {};
\node[main node] (2) [below of=1] {};
\node[main node] (3) [below of=2] {};
\node[main node] (4) [below of=3] {};
\node[main node] (5) [right of=1] {};
\node[main node] (6) [below of=5] {};
\node[main node] (7) [below of=6] {};
\node[main node] (8) [below of=7] {};
\path[every node/.style={font=\sffamily\small}]
(1) edge node {} (2)
edge node {} (6)
(2) edge node {} (3)
edge node {} (7)
(3) edge node {} (4)
edge node {} (8)
(5) edge node {} (6)
edge node {} (2)
(6) edge node {} (7)
edge node {} (3)
(7) edge node {} (8)
edge node {} (4);
\end{tikzpicture}
\end{tabu}
\end{center}
\section{Properties of Functions}
\textit{\textbf{(We will cover the material necessary to solve this problem in Monday's lecture.)}}
\begin{shaded}
Submit your edited $\mathsf{FunctionsVennDiagram.h}$ file through GradeScope.
\end{shaded}
\section{Left, Right, and True Inverses}
\textit{\textbf{(We will cover the material necessary to solve this problem in Monday's lecture.)}} \\
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*.,ref=\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)$.)
\textit{\textcolor{blue}{Although you're probably tempted to define functions by writing out some expression like $f(x) = x^2
+ 3x - 1$, for the purposes of this problem it's actually a lot easier to define your functions by drawing diagrams of
their domains and codomains like we did in lecture. This gives you more precise control over what maps to
what.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Prove that if $f$ has a left inverse,
then $f$ is injective.
\textit{\textcolor{blue}{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}
\end{enumerate}
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.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Prove that if $f$ has a right inverse, then $f$ is surjective.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
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$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Explain why your proof from part (v) doesn't work
if $g_1$ and $g_2$ are just left inverses of $f$,
not full inverses.
Be specific -- you should point at a specific claim
in your proof of part (v) that is no longer true in this case.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Explain why your proof from part (v) doesn't work
if $g_1$ and $g_2$ are just right inverses of $f$,
not full inverses.
Be specific -- you should point at a specific claim
in your proof of part (v) that is no longer true in this case.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Left and right inverses have some surprising applications. We'll see one of them next week!
\section*{Optional Fun Problem: Infinity Minus Two (1 Point Extra Credit)}
\textit{\textbf{(We will cover the material necessary to solve this problem in Monday's lecture.)}} \\
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, inclusive, and the set $(0, 1)$ is the set of all real
numbers between 0 and 1, 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}
\begin{answer}
Write your answer here.
\end{answer}
Provide a proof here.
\end{shaded}
\end{document}