\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29:00pm} on {\bf Friday, 29 September}. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX).}

Directions

Solve as many of the nine problems as you can. For maximum credit, your answers should be correct, clear, well-written, and convincing. The problem (4) marked with $(\star)$ is more challenging than others, and so it is not necessary to solve it fully to get a ``green-star level” grade on this assignment (although we certainly hope you will try and some will succeed!)

Properties of functions and relations

1. In last week’s problem set we considered the relation, $\le$, with the domain set, $\mathbb{N}$ and codomain set $\mathbb{N}$. Which of these properties does the relation have: function, total, injective, surjective, bijective? (You do not need to provide a detailed proof, but should support your answer with a very brief explanation.)

2. As we saw in class, five basic properties of binary relations $R : A \rightarrow B$ are: \begin{quote} \begin{enumerate}[(1)] \item $R$ is a surjection [$\ge 1$ in] \item $R$ is an injection [$\le 1$ in] \item $R$ is a function [$\le 1$ out] \item $R$ is total [$\ge 1$ out] \item $R$ is empty [$= 0$ out] \end{enumerate} \end{quote}

   Below are some assertions about a relation $R$. For each assertion, write the numbers (1, 2, 3, 4, 5 from above) of all properties above that the relation $R$ must have (that is, the properties that are implied by the stated assertion); write ``none” if $R$ might not have any of these properties.

   Variables $a, a_1, a_2, \cdots$ are elements of $A$, and $b, b_1, b_2, \cdots$ are elements of $B$.

   The first answer is provided as an example. \begin{quote} \begin{enumerate}[a.] \item $\forall a \ldotp \forall b \ldotp a R b.$ \qquad\qquad Answer: (1), (4) \item $\neg(\forall a \ldotp \forall b \ldotp a R b).$ \item $\forall a \ldotp \exists b \ldotp a R b.$ \item $\forall b \ldotp \exists a \ldotp a R b.$ \item $R$ is a bijection. \item $\forall a_1, a_2, b \ldotp (a_1 R b \wedge a_2 R b) \implies a_1 = a_2.$ \item $\forall a_1, a_2, b_1, b_2 \ldotp (a_1 R b_1 \wedge a_2 R b_2 \wedge b_1 \neq b_2) \implies a_1 \neq a_2.$ \end{enumerate} \end{quote}

3. (Problem 4.34 from the LCN book.) Let $R \colon A \to B$ and $S \colon B \to C$ be binary relations such that $S \circ R$ is a bijection and $|A|=2$. Give an example of such $R, S$ where neither R nor S is a function. Indicate exactly which properties (of total, surjection, function, and injection) your examples of $R$ and $S$ have.

4. ($\star$) Consider the sets $A$ and $B$ where $|A| = n$ and $|B| = m$.

\begin{quote} \begin{enumerate}[a.]

\item Assuming $n = m$ (just for this sub-part), how many {\em bijective} relations are there $R: A \rightarrow B$.

\item How many {\em partial} functions are there $f: A \rightarrow B$. (Note that the set of {\em partial} functions includes all {\em total} functions; partial means there {\em may} be domain elements with no associated codomain element.)

\item How many {\em injective} relations are there $R: A \rightarrow B$. (Hint: try to relate it to previous part.) \end{enumerate} \end{quote}

Cardinality of Finite Sets

1. Assume $R: A \rightarrow B$ is an total injective relation between $A$ and $B$. What must be true about the relationship between $|A|$ and $|B|$?

2. Assume $R: A \rightarrow B$ is an total surjective function between $A$ and $B$. What must be true about the relationship between $|A|$ and $|B|$?

Induction

1. In Problem Set 2 (Problem 6) you used the well-ordering principle to prove that any non-negative integer value less than $2^{k+1}$ can be written as $a_0 \cdot 2^0 + a_1 \cdot 2^1 + a_2 \cdot 2^2 + \cdots + a_k \cdot 2^k$ where all the $a_i$ values are either 0 or 1. Prove the same property using induction. (Hint: the induction should be on $k$.)

2. Prove by induction that every non-empty finite set of rational numbers has a minimum element. (Bonus: explain why this does not contradict the fact that the rational numbers are not well ordered.)

3. A convex polygon is a polygon where all line segments connecting any two points in the polygon are fully contained in the polygon. For example, of the three polygons below, the left two are convex, but the rightmost one is not. Prove by induction that any convex polygon with $n$ sides can be divided into $n - 2$ triangles.

\begin{center} \newdimen\R \R=0.8cm \begin{tikzpicture}[scale=1.0] \node[draw, regular polygon, regular polygon sides=5] at (0,0) {Convex}; \node[draw, regular polygon, regular polygon sides=7] at (4.5,0) {Convex}; \node[draw, star, star points=6, star point ratio=.6] at (9,0) {non-convex};

\end{tikzpicture} \end{center} \begin{comment} \draw (1,0) – (0,2) – (3,3) – (4,2.5) – (2.5, -1) – cycle; \draw (1,0) – (0,2) – (2,3) – (4,2.5) – (2, 1.5) – (4, 1) – cycle; \end{comment}