% % 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 \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{Your Name(s) Here} \date{\today} \lhead{Your Name(s) Here} \chead{Problem Set 3} \rhead{\today} \lfoot{} \cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2019} \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}} % 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 \begin{document} \maketitle \begin{center} \textit{These two checkpoint problems are due on Monday at 2:30PM.} \end{center} \section*{Checkpoint Problem One: Binary Relations IRL} 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)$. \begin{enumerate}[label=\roman*.] \item Prove that $E$ is an equivalence relation over $\R^2$. \annotate{Remember that the ``if'' in the definition of the relation $E$ means ``is defined as'' and isn't an implication.} \annotate{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. You may want to start or by taking the first-order statement in the definition here and determining what it says in plain English.} \begin{shaded} Write your proof here. \end{shaded} \end{enumerate} \annotate{Once you've written a draft of your proofs of these results, take a few minutes to read over them and apply both the standard Proofwriting Checklist (the one you've used on the first two problem sets) and the new Discrete Structures Proofwriting Checklist. Here are a few specific things to keep an eye on:} \begin{itemize} \item \annotate{The key terms in binary relations (reflexivity, symmetry, transitivity, irreflexivity, and asymmetry) are defined in first-order logic and proofs of those properties depend on those first-order definitions. However, as a reminder, you should \emph{not} include first-order logic notation (quantifiers, connectives, etc.) anywhere in your proofs. Look at the proofs from the Guide to Binary Relations and last week's lectures for some examples of what we're expecting.} \item \annotate{Make sure that you've set all of your proofs up properly. For example, what should a proof that a relation is symmetric look like? What should you assume, and what you should prove? Does your proof match this pattern?} \item \annotate{You don't need to -- and in fact, shouldn't -- repeat the definition of the $E$ relation in your proof. You can assume that the reader knows how it's defined.} \end{itemize} \pagebreak \section*{Checkpoint Problem Two: Redefining Equivalence Relations?} Below is a purported proof that every relation that is both symmetric and transitive is also reflexive. \\ \textbf{Theorem}: If $R$ is a symmetric and transitive binary relation over a set $A$, then $R$ is also reflexive. \textbf{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 $x R y$ and $y R x$ we learn that $x R x$ is true. Therefore, $R$ is reflexive, as required. \qedhere \\ This proof, unfortunately, is incorrect. \begin{enumerate}[label=\roman*.] \item Draw a picture of a binary relation that is symmetric and transitive but not an equivalence relation. Briefly justify your answer, though no formal proof is required. This shows that the ``theorem'' here isn't even true to begin with. \annotate{What has to happen for a binary relation to not be an equivalence relation? What, specifically, has to happen if you know that that relation is symmetric and transitive?} \begin{shaded} Place your picture and write your justification here. \end{shaded} \item What's wrong with this proof? Justify your answer. Be as specific as possible. \annotate{We've given this proof as an example because the error it contains is one that we see a lot of people make consistently throughout the problem set. That often leads to folks having errors in every single one of the proofs they submit. Read over the Guide to Proofs on Discrete Structures and Discrete Structures Proofwriting Checklist and make sure you're confident that you see what the issue is. If you aren't sure, feel free to ask on Piazza or to stop by office hours. Regardless of what you write, be sure to read the checkpoint solutions as soon as they come out! It would be a shame if you missed the issue here and then made this exact mistake later on in this problem set.} \begin{shaded} Write your answer and justification here. \end{shaded} \end{enumerate} \pagebreak \begin{center} \emph{These remaining problems are due on Friday at 2:30PM.} \end{center} \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} \pagebreak \section{Fun with Equivalence Relations} Throughout mathematics, it's helpful to switch back and forth between the rigorous definitions we've developed for various terms and the intuitions that got us to those terms in the first place. \begin{enumerate}[label=\roman*.] \item Let $A = \{1, 2, 3\}$. How many different equivalence relations are there over the set $A$? Explain how you arrived at your answer and why you know there aren't any more. No formal proof is required. \annotate{Two binary $S$ and $T$ over the same set are the same if, for any $x$ and $y$, $xSy$ holds if and only if $xTy$ holds. For example, The relation $xSy$ over $\R$ defined as $|x| = |y|$ is exactly the same relation as $x T y$ over $\R$ defined as $x^2 = y^2$, since $x S y$ and $x T y$ are always either both true or both false.} \\ \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} Let's suppose you have an equivalence relation $R$ over a set $A$. The Fundamental Theorem of Equivalence Relations says that $R$ partitions the elements of $A$ into different equivalence classes. If you pick exactly one element from each equivalence class and gather the result into a set, you get what's called a \emph{system of representatives} for $R$. Stated differently, a system of representatives for an equivalence relation $R$ over a set $A$ is a set $X \subseteq A$ such that $X$ contains exactly one element of each equivalence class of $R$. \begin{enumerate}[resume*] \item Consider the equivalence relation $\equiv_5$ over the set $\mathbb{Z}$. Give two different systems of representatives for $\equiv_5$, and briefly justify your answer. \begin{shaded} Write your answer and justification here. \end{shaded} \item Consider the equivalence relation = over the set $\mathbb{Z}$. List all the systems of representatives for that equivalence relation. Briefly justify your answer; in particular, explain how you know you have all possible systems of representatives. \begin{shaded} Write your answer and justification here. \end{shaded} \end{enumerate} Systems of representatives are a powerful idea, and we'll return to them later in the quarter. \pagebreak \section{The Co-Prime Relation} We define a relation $\bot$ (note we are reusing our First-Order Logic symbol for false, but that meaning of this symbol is unrelated to this new meaning we are giving it just for this problem) over $\mathbb{Z}$ as: \begin{center} x$\bot$y if x and y are co-prime \end{center} Two integers a and b are said to be co-prime if the only positive integer that divides both of them is 1. \begin{enumerate}[label=\roman*.] \item Is the relation $\bot$ reflexive? \begin{shaded} Write your answer and justification here. \end{shaded} \item Is the relation $\bot$ irreflexive? \begin{shaded} Write your answer and justification here. \end{shaded} \item Is the relation $\bot$ symmetric? \begin{shaded} Write your answer and justification here. \end{shaded} \item Is the relation $\bot$ asymmetric? \begin{shaded} Write your answer and justification here. \end{shaded} \item Is the relation $\bot$ transitive? \begin{shaded} Write your answer and justification here. \end{shaded} \end{enumerate} For each property it does have, give a brief (one-sentence) justification why. For each property it doesn`t have, write a short disproof. \pagebreak \section{Revisiting the Star-Drawing} \emph{This problem uses the concept of coprime introduced above to continue your work from the star-drawing problem on pset2. You will need to pull up the pset2 handout to refer to the description and definitions there again, since we will not reiterate them here.} \\ \\ An observation you may have had so far is that in cases where we do have a simple star (say, \{7 / 2\}, \{7 / 3\}, \{8 / 3\}, \{10 / 3\}, \{12 / 5\}, etc.) the values of $p$ and $s$ have no common factors, whereas in the stars we've seen that aren't simple (say, \{6 / 2\}, \{8 / 2\}, \{9 / 3\}, \{10 / 4\}, etc.) the values of $p$ and $s$ do have a common factor. Perhaps that's important? \\ Let's introduce some new definitions to make our math a little more precise. If $a$ and $b$ are integers, we say that $a$ \emph{divides} $b$ if there is an integer $q$ such that $b = aq$. We'll say that $a$ and $b$ are coprime if there are no integers that divide both $a$ and $b$ besides $\pm 1$. \\ With this in mind, we can form a guess of what we think is necessary for a star to work: \begin{center} \emph{Conjecture}: A $p$-point star with a step size of $s$ is a simple star if and only if $p$ and $s$ are coprime. \end{center} At this point, this is just a conjecture -- something we \textit{think} is true, but aren't totally sure about. Our goal will be to try to see whether this statement is a \emph{theorem}, meaning that it's something we have a rigorous proof for, or whether it's actually not true. \\ We'll need to develop a little bit more mathematical machinery before we can fully take aim at resolving this question, but with the tools you've developed so far, you actually have enough to show that at least one direction of this result is true. Let $p$ and $s$ be natural numbers where $p > 0$. \emph{Prove} that if \{$p$ / $s$\} is a simple star, then $p$ and $s$ are coprime. You may want to use the following fact, which you can use without proof: if $x$ and $y$ are integers and $xy = 1$, then either $x = y = 1$ or $x = y = -1$. Also, feel free to use the result from part (ii) of this problem. \begin{shaded} Provide a proof here. \end{shaded} \annotate{You have three proof techniques at your disposal at this point: direct proof, proof by contradiction, and proof by contrapositive. If you're having trouble with one of these approaches, try switching to another.} \pagebreak \section{Properties of Functions} \begin{shaded} Submit your edited $\mathsf{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 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)$? \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} 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. \annotate{It might help to think of things this way: what happens if that function isn't a bijection?} \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} 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: \begin{shaded} $$ \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ \end{pmatrix} $$ \end{shaded} \end{enumerate} 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 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. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} 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 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. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} 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. \begin{shaded} Write your answer here. \end{shaded} \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: \annotate{You can solve this problem either by working this out mathematically, or by using the intuition from part (vi). Before you move on, make sure you can solve it both ways!} \begin{shaded} $$ \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ & \_ \end{pmatrix} $$ \end{shaded} \item Explain why Dancer $n$'s position in the fourth dance is the given by the spot originally occupied by Dancer $(f \circ f ∘ f)(n)$ in the first dance. No formal proof is necessary. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} Given a permutation $\sigma : A \rightarrow A$, the \emph{kth power} of $\sigma$, for some natural number $k \geq 1$, is defined as $$\sigma^k = \sigma \circ \sigma \circ \dots \circ \sigma,$$ where there are $k$ copies of $\sigma$ composed together. For example, $\sigma^4 = \sigma \circ \sigma \circ \sigma \circ \sigma$. As a useful edge case, we'll define $\sigma^0$ to be the function given by the rule $\sigma^0(x) = x$. \\ Powers of permutations give us a really nice way of figuring out where all the dancers will be at the start of the $k$th dance. Specifically, the positions are given by the outputs of $f^{k-1}$, where, as before, positions are given by the number of the dancer who was originally at that position in the first dance. \\ Imagine that the dancers keep changing their positions using the setup described above. At some point, it's guaranteed that all the dancers will end up returning to their original positions. \begin{enumerate}[resume*] \item How many different configurations will the dancers go through before everyone returns back to their original positions? Justify your answer, but no formal proof is necessary. \begin{shaded} Write your answer and justification here. \end{shaded} \end{enumerate} One final piece of terminology. If $\sigma : A \rightarrow A$ is a permutation, the order of $\sigma$ is the smallest positive number $k$ for which $\sigma^k = \sigma^0$. With regards to part (ix) of this problem, the order of $f$ happens to be the number of unique configurations the dancers will end up going through. \\ Permutations are a useful building block in mathematics. We'll see them again in the next problem set, where we'll use them to talk about symmetries. \pagebreak \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*.] \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 of $f$, $g$, and $h$ along the lines of what we did in class. \begin{shaded} Place your picture here. \end{shaded} \item Prove that if $f$ is a function that has a left inverse, then $f$ is injective. \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} \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. As in part (i), express your answer by drawing pictures of $f$, $g$, and $h$ along the lines of what we did in lecture. \begin{shaded} Place your picture here. \end{shaded} \item Prove that if $f$ is a function that 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 \textit{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} Write your answer here. \end{shaded} \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 of part (v) that is no longer true in this case. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} Left and right inverses have some surprising applications. We'll see one of them next week! \pagebreak We've included \textit{three} 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: High-Order Dancing (Extra Credit)} In Problem Seven, we modeled ten dancers changing places as a permutation $\sigma : \llbracket 10 \rrbracket \rightarrow \llbracket 10 \rrbracket$. The order of that permutation, as you saw, corresponds to the number of unique configurations the dancers will take on before everyone returns to their starting positions. \\ Find a permutation $\sigma : \llbracket 10 \rrbracket \rightarrow \llbracket 10 \rrbracket$ of order 30. Justify your answer \textit{without} actually computing $\sigma^{30}$. \begin{shaded} Write your answer and justification here. \end{shaded} \section*{Optional Fun Problem Two: Infinity Minus Two (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, \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} \section*{Optional Fun Problem Three: Reversing a Fundamental Theorem (Extra Credit)} The Fundamental Theorem of Equivalence Relations (FToER) says that if $R$ is an equivalence relation over a set $A$, then every $a \in A$ belongs to exactly one equivalence class of $R$. Here, an equivalence class is a set of the form $\left[ x \right]_R = \{ y \in A \mid xRy \}$. \\ The general convention is to not speak of the equivalence classes of a binary relation $R$ unless $R$ actually happens to be an equivalence relation. But let's say that we decide to break with that tradition. After all, for any relation $R$, the set $\left[ x \right]_R = \{ y \in A \mid xRy \}$ is a perfectly well-defined set -- it just might not happen to correspond to our intuition about how equivalence classes behave. \\ For the purposes of this problem, if $R$ is any binary relation over a set $A$, we'll call a set $$\left[ x \right]_R = \{ y \in A \mid xRy \}$$ a \emph{pseudoequivalence class} of $R$. If $R$ is indeed an equivalence relation, then the pseudoequivalence classes of $R$ are the equivalence classes of $R$, and if $R$ isn't then these sets might not have a nice structure. \\ Prove or disprove: if $R$ is a binary relation over a set $A$ and every element of $A$ belongs to exactly one pseudoequivalence class of $R$, then $R$ is an equivalence relation. In other words, we'd like you to prove or disprove whether you can flip the direction of implication in the FToER. \begin{shaded} Write your proof or disproof here. \end{shaded} \end{document}