Discrete Mathematics

# Problem Set 5

\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).}

Deliverable: Submit your responses as a single PDF file on the collab site before 6:29pm on 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 or Word).

### Collaboration Policy (Read Carefully - different from PS4)

Unlike previous assignments, for this assignment, you may work in groups of one to three students to write-up a solution together. If you work with teammates, exactly one of your should submit one assignment that represents your collective best work with all of your names and UVA ids clearly marked on it on it. Everyone on a team should understand everything you turn in for the assignment well enough to be able to produce it completely on your own. All teammates must review the submissions before it is submitted to make sure you understand everything on it and that your name and UVA id are clearly marked on it. If you would like to find teammates for this assignment, you may use the #teaming channel on slack.

## Preparation

This problem set focuses on Chapter 4, including Section 4.5 (Cadrinality of Finite Sets) and Chapter 5 (Induction) of the MCS book, and Class 9 and Class 10.

## 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}