%
% 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 --- Spring 2017}
\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 fs a Binary Relation, Anyway?}
\begin{shaded}
Submit your edited $\mathsf{BinaryRelations.cpp}$ and $\mathsf{.relation}$ files through GradeScope.
\end{shaded}
\section{Redefining Equivalence Relations?}
In lecture,
we defined equivalence relations as relations that are
reflexive, symmetric, and transitive.
Are all three parts of that definition necessary?
The answer is yes, and this question explores why this is.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Edit the file $\mathsf{PartD.relation}$ in the $\mathsf{res/}$ directory of the starter files to define a binary relation
that is symmetric, transitive, but not reflexive.
\begin{shaded}
Submit your edited $\mathsf{.relation}$ file through GradeScope.
\end{shaded}
\end{enumerate}
Below is a purported proof that every relation that is
both symmetric and transitive is also reflexive.
\begin{thm}
If $R$ is a symmetric and transitive binary relation over a set $A$, then $R$ is also reflexive.
\end{thm}
\begin{proof}
Let $R$ be an arbitrary binary relation over a set $A$
such that $R$ is both symmetric and transitive.
We need to show that $R$ is reflexive.
To do so, consider an arbitrary $x, y \in A$ where $x R y$.
Since $R$ is symmetric and $x R y$,
we know that $y R x$.
Then, since $R$ is transitive,
from $xRy$ and $yRx$ we learn that $xRx$ is true.
Therefore, $R$ is reflexive, as required.
\end{proof}
This proof has to be wrong,
since as you saw in part (i)
it's possible for a relation to be symmetric and transitive but not reflexive:
\begin{enumerate}[resume*]
\item What's wrong with this proof? Justify your answer.
Be as specific as possible.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
\section{Hasse Diagrams and Covering Relations}
Let $<_A$ be some strict order relation over a set $A$. (We've typically used the letter $R$ as a placeholder for
``some general relation,'' but it's common when working with strict orders to use notation like $<_A$ as a
placeholder name.) We can define a new binary relation $Cov(<_A)$ over the set $A$, called the \textbf{\textit{covering relation for $<_A$}}, as
follows:
\begin{center}
$x$ Cov($<_A$) $y$\quad if\quad $x <_A y \land \neg\exists z \in A.\ (x <_A z \land z <_A y)$
\end{center}
That definition is quite a mouthful, but it has a really nice intuition. In the course of working through this
problem, you'll see what this definition means and get a better feel for it.\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Consider the $<$ relation over the set $\N$.
What is its covering relation? 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{(Hint: Try out some examples and see if you spot a pattern.)}
\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}
\item Prove that the relation 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.
\begin{shaded}
Provide a proof here.
\end{shaded}
\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.
\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 $<_A$ be a strict order over a set $A$.
There is a close connection between Cov($<_A$) and the Hasse diagram of $<_A$.
What is it?
Briefly justify your answer, but no proof is required.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
Provide justification here.
\end{shaded}
\end{enumerate}
Given the explanation you came up with in part (iv), you might wonder why we initially specified the definition
in first-order logic. From a computer science perspective, first-order definitions are really useful because
they give a clear, clean, unambiguous definition that can often be easily expressed in software.
\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 Cov($R$).
(As a reminder, don't forget to fill in the domain of 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. You may want to use
this to check your work for the earlier parts of this problem, and more generally just to get a sense of
what cover relations look like!
\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, given any two \mintinline{c++}{int}s $x$ and $y$, that exactly
one of the following is true:
\begin{center}
$x < y$ \quad\quad $x = y$ \quad\quad $y < x$
\end{center}
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item 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;
}
\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$
\end{center}
Prove or disprove: the relation $F$ 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}
\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}
Prove or disprove: the relation $G$ 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}
\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 $H$ over the set of all pixels:
\begin{center}
$pHq$ \quad\quad if \quad\quad $p.x < q.x$ \quad $\land$ \quad $p.y < q.y$
\end{center}
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}
\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 $I$ over the set of all pixels:
\begin{center}
$pIq$ \quad\quad if \quad\quad $p.x < q.x$ \quad $\lor$ \quad $(p.x = q.x \land p.y < q.y)$
\end{center}
Prove or disprove: the relation $I$ 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}
When writing up your proofs, please feel free to take advantage of the result from the checkpoint problem!
You can prove a relation is a strict order by just showing that it's irreflexive and transitive.
If you're having trouble building an intuition for what these relations look like, it might help to draw a
grid of points, single one out of those points, and shade in all the points it relates to.
\section{Strict Weak Orders and C++ Programming}
\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.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Consider the < relation over the set $\N$. What is the relation $\sim_<$? Provide your answer by fllling 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}
\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}
\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. (It turns out that
the $I$ relation is also a strict weak order, but for brevity's sake you don't need to prove this.)
\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}
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}[resume*]
\item Prove that if $R$ is a strict weak order over a set $A$, then $\sim_R$ is an equivalence relation over $A$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
Your result from part (iii) of this problem shows that a strict order $R$ over a set $A$ effectively partitions the
elements of $A$ into non-overlapping groups. This follows from the Fundamental Theorem of Equivalence
Relations: any equivalence relation defines a partition of the underlying set. \\
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. For each of the relations
from Problem Four that are strict weak orders, 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}
\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. For each of the relations defined in Problem Four that are strict
weak orders, determine what the final contents of the \mintinline{c++}{std::set} will end up being if the set uses
those strict weak orders to compare elements. Briefly justify your answer; no formal proof is necessary.
\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 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 \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 Five, 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$. \\
There's a beautiful interplay between the relation $R$ and the equivalence classes of $\sim_R$.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item 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$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Let $R$ be a strict weak order over a set $A$ and consider any $x, y \in A$ where $xRy$. Prove that for any
$w \in A$ where $w \in [x]_{\sim R}$ that $wRy$.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
These results show 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}
Consider the following Venn diagram:
\begin{center}
\begin{tikzpicture}
\draw (-1.5,0) ellipse [x radius=3cm, y radius=1cm];
\draw (-4,0) node[right] {\textit{Injections}};
\draw (1.5,0) ellipse [x radius=3cm, y radius=1cm];
\draw (4,0) node[left] {\textit{Surjections}};
\draw (0,0) node {\textit{Bijections}};
\draw (0,0) ellipse [x radius=5cm, y radius = 3cm];
\draw (0,2.5) node {\textit{Functions}};
\draw (0,-4) node {\textit{Non-functions}};
\draw (-5.5,-5) rectangle (5.5, 3.5);
\end{tikzpicture}
\end{center}
Below is a list of purported functions.
For each of those purported functions,
determine where in this Venn diagram that object goes.
No justification is necessary.
\begin{enumerate}
\item $f:\N\to\N$ defined as $f(n) = n^2$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\Z\to\N$ defined as $f(n) = n^2$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\N\to\Z$ defined as $f(n) = n^2$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\Z\to\Z$ defined as $f(n) = n^2$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\R\to\N$ defined as $f(n) = n^2$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\N\to\R$ defined as $f(n) = n^2$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\N\to\N$ defined as $f(n) = \sqrt{n}$.
($\sqrt{n}$ is the \textbf{\textit{principle square root}} of $n$,
the nonnegative one.)
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\R\to\R$ defined as $f(n) = \sqrt{n}$.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\R\to\{x\in\R\mid x\geq0\}$ defined as $f(n) = \sqrt{n}$.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\{x\in\R\mid x\geq0\}\to\{x\in\R\mid x\geq0\}$
defined as $f(n) = \sqrt{n}$.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\{x\in\R\mid x\geq0\}\to\R$ defined as $f(n) = \sqrt{n}$.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\N\to\wp(\N)$, where $f$ is some injective function.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\{0,\,1,\,2\}\to\{3,\,4\}$, where $f$ is some surjective function.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item $f:\{\textit{breakfast},\,\textit{lunch},\,\textit{dinner}\}\to
\{\textit{shakshuka},\,\textit{soondubu},\,\textit{maafe}\}$,
where $f$ is some injection.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\section{Left, Right, and True Inverses}
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{(Hint: Define your functions through pictures.)}
\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.
Your proof must call back to the formal definitions
of injectivity and left inverses,
but as with the other proofs in this problem set
must \textit{not} contain any first-order logic.
\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, which talks about the
limits of data compression, next week!
\section*{Optional Fun Problem: Infinity Minus Two (1 Point 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, 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}