Problem Set 3

Due Friday, July 21 at 4:00 pm Pacific

---

This third problem set explores functions and graphs. We've chosen these problems to help you learn how to reason about injections, surjections, bijections, and the like; how to write proofs using formal mathematical definitions; and why all this matters in practice. Before beginning this problem set, we strongly recommend doing the following:

• Read the Guide to Proofs on Discrete Structures, which explores how to write proofs when definitions are rigorously specified in first-order logic. This handout contains both general guiding principles to follow and some sample proof templates that you’re welcome to use here.
• Read the Discrete Structures Proofwriting Checklist, which contains some specific items to look for when proofreading your work. We will be applying the items on this checklist when grading your work, so it’s worthwhile to apply this checklist to your work before submitting.

We also recommend that you take a look at the proofs from this week’s lectures to get a sense of what this looks like and how to approach these problems.

Good luck, and have fun!

Starter Files

Here are the starter files for the problems you'll submit electronically:

📦 PS3 Starter Files

Unpack the files somewhere convenient and open up the bundled project.

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS3 $\LaTeX$ Template

Problem One: Properties of Functions

To start, let's introduce a new definition. A bijection is a function that is both injective and surjective. Recall that:

• An injective function associates at most one element of the domain with each element of the codomain.
• A surjective function associates at least one element of the domain with each element of the codomain.

A bijective function is thus one that associates exactly one element of the domain with each element of the codomain.

Below is a list of purported functions. For each of those purported functions, determine where in the following Venn diagram that object goes.

To get you started, we’ve shown you where functions 1 and 2 go.

To submit your answers, run the starter files for PS3 and choose the “Properties of Functions” option. This program will write your answers to res/PropertiesOfFunctions.answers. You can use the provided test cases to check your work, and when you’re ready you can submit this file to Gradescope. Do not manually edit this file; use the program instead.

As a reminder, in this class we consider $0$ to be a natural number.

1. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = 137$.

2. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = -137$.

   Make sure you can explain why these first two items go where they do in this diagram!

3. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.

   The notation $\abs{n}$ means “the absolute value of n.” For example, $\abs{\pi} = \abs{-\pi} = \pi$.

4. $f : \mathbb{Z} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
5. $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
6. $f : \mathbb{R} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
7. $f : \mathbb{N} \to \mathbb{R}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.

8. $f : \mathbb{R} \to \mathbb{R}$ defined as $f(n) = \sqrt{n}$.

   The notation $\sqrt{n}$ denotes the principal square root of $n$, the nonnegative one.

9. $f : \mathbb{R} \to \Set{ x \in \mathbb{R}\ \vert\ x \ge 0 }$ defined as $f(n) = \sqrt{n}$.
10. $f : \Set{ x \in \mathbb{R} \ \vert\ x \ge 0 } \to \Set{ x \in \mathbb{R}\ \vert\ x \ge 0 }$ defined as $f(n) = \sqrt{n}$.
11. $f : \Set{ x \in \mathbb{R} \ \vert\ x \ge 0 } \to \mathbb{R}$ defined as $f(n) = \sqrt{n}$.

12. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \left\lbrace \begin{aligned} &n^2 + 2 &\text{if } n \lt 137 \\ &n^2 - 2 &\text{if } n \gt 137 \end{aligned} \right.\]

13. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \left\lbrace \begin{aligned} &2 - n &\text{if } n \le 2 \\ &n - 2 &\text{if } n \ge 2 \end{aligned} \right.\]

14. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \begin{cases} n-1 & \text{if } n \text{ is even} \\ n+1 & \text{if } n \text{ is odd} \\ \end{cases}\]

15. $f : \mathbb{N} \to \mathbb{N}$ defined as follows:

    \[f(n) = \begin{cases} n+1 & \text{if } n \text{ is even} \\ n-1 & \text{if } n \text{ is odd} \\ \end{cases}\]

Problem Two: Strictly Increasing Functions

A function $f : \mathbb{Z} \to \mathbb{Z}$ is called strictly increasing if the following statement is true about $f\text:$

\[\forall x \in \mathbb{Z}. \forall y \in \mathbb{Z}. (x \lt y \ \to \ f(x) \lt f(y)).\]

Strictly increasing functions have a bunch of nice properties.

1. Is the function $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(x) = x^2$ strictly increasing? How about if we defined it as $f(x) = x^3$? No justification is necessary.

2. Let $f : \mathbb{Z} \to \mathbb{Z}$ and $g : \mathbb{Z} \to \mathbb{Z}$ be arbitrary strictly increasing functions. Prove that $g \circ f$ is strictly increasing.

   This is a proof of the form “any object with property $X$ also has property $Y\text{.”}$ Look back at the lecture examples involving involutions for some guidance about how to proceed here.

   Make sure to distinguish what you're assuming from what you're proving. Introduce variables when you're asked to prove a universally-quantified statement, and don't introduce them when you're assuming a universally-quantified statement.

3. Let $f : \mathbb{Z} \to \mathbb{Z}$ be an arbitrary strictly increasing function. Prove that $f$ is injective.

   If you have two integers $x$ and $y$ where $x \ne y$, then you know either that $x \lt y$ or that $y \lt x$. If $x$ and $y$ are otherwise arbitrarily chosen, you can avoid doing a proof by cases by using this magic phrase:

   "Assume, without loss of generality, that $x \lt y$."

   This phrase tells the reader "dear reader, who I am sure is well-dressed, very refined, and very classy, there really isn't a difference in the logic between the cases where $x \lt y$ and $y \lt x$. Therefore, to avoid boring you, I'm going to just prove one of those two cases. And since you are so Smart and Wise and Funny, you surely are smart enough to see what the other case would be, because it's literally the same except that we swap the roles of $x$ and $y\text{."}$ It's a great way to cut down on the amount you have to write without losing anything.

   You can use this phrase in other contexts where there are two symmetric choices. Just make sure that those cases really truly are identical except for which variable plays which part!

4. Let $f : \mathbb{Z} \to \mathbb{Z}$ be a strictly increasing function and consider any integers $x$ and $y$. Prove that if $f(x) = y$ and $f(y) = x$, then $x = y$.

   Here, the notation “$f(x) = y$” means “the function $f$, applied to the specific input $x$ that we picked in the first sentence, gives back the specific value $y$.” Similarly, the function $f$, applied to the specific input $y$ that we picked in the first sentence, gives back the specific value $x$. Under those assumptions, show that $x = y$.

Problem Three: Independent and Dominating Sets

As a refresher from lecture, an independent set in a graph $G = (V, E)$ is a set $I \subseteq V$ with the following property:

\[\forall u \in I. \forall v \in I. \Set{u, v} \not\in E \text.\]

Now, a new definition. A dominating set in $G$ is a set $D \subseteq V$ with the following property:

\[\forall v \in V. (v \not\in D \to \exists u \in D. \Set{u, v} \in E)\text.\]

In general, whenever you find a new definition or new mathematical term, it’s good to play around with the definition a bit to get a feel for what it looks like.

1. Give two different examples of dominating sets of the graph shown below, each of which has cardinality four or less. No justification is necessary.

   

2. Let $G = (V, E)$ be an arbitrary graph with the following property: every node in $G$ is adjacent to at least one other node in $G$. Prove that if $I$ is an independent set in $G$, then $V - I$ is a dominating set in $G$.

   Notice that we're asking you to show that $V - I$ is a dominating set, not that $I$ is a dominating set. Also, we recommend drawing some pictures here to get a sense of how this works.

   Use the formal definitions to guide your proofs. If you proceed via a direct proof or via contrapositive, what, exactly, will you be assuming, and what will you be proving? If you write this as a proof by contradiction, what specifically is it that you’re assuming for the sake of contradiction?

An independent set $I$ in a graph $G$ is a maximal independent set in $G$ if there is no independent set $I'$ in $G$ where $I \subsetneq I'$. (Here, $I \subsetneq I'$ denotes that $I$ is a strict subset of $I'$, meaning that $I \subseteq I'$ and $I \ne I'$).

3. Find independent sets $I$ and $J$ of the graph from part (i) of this problem such that $I$ is maximal but $\abs{I} \lt \abs{J}$. No justification is necessary.

   Yes, this is possible. The definition of a maximal independent set is meant to be taken literally.

4. Prove that if $I$ is a maximal independent set in $G = (V, E)$, then $I$ is a dominating set of $G\text.$

   You can build a great intuition for this result by drawing some pictures and thinking about what has to happen for a set of nodes to be an independent set and for a set of nodes to be a dominating set. When it comes time to write out your proof, however, you’ll need to use the formal first-order definitions of independent sets, maximal independent sets, and dominating sets.

Independent and dominating sets have applications in complexity theory, error-correcting codes, and resource allocation. Take CS154 and CS250 to learn more!

Problem Four: Left and Right Inverses

Let $f : A \to B$ be a function. A function $g : B → A$ is called a left inverse of $f$ if the following is true:

\[\forall a \in A. g(f(a)) = a.\]

1. Find examples of a function $f$ and two 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.

2. Prove that if $f$ is a function that has a left inverse, then $f$ is injective.

   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?

Let $f : A \to B$ be a function. A function $g : B \to A$ is called a right inverse of $f$ if the following is true:

\[\forall b \in B. f(g(b)) = b.\]

3. 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.

4. Prove that if $f$ is a function that has a right inverse, then $f$ is surjective.

Problem Five: True Inverses

If $f : A \to B$ is a function, then a true inverse (often just called an inverse) of $f$ is a function $g$ that's simultaneously a left and right inverse of $f$. In Problem Five you saw that functions can have several different left inverses or right inverses. However, a function can only have a single true inverse.

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$.

Problem Six: Bipartite Graphs

The bipartite graphs are an important and common family of graphs. They appear in a huge number of settings – error-correcting codes, computational social choice theory, and algorithm design, to name a few.

Let’s begin with a formal definition. An undirected graph $G = (V, E)$ is called bipartite if there exist two sets $V_1$ and $V_2$ such that

• every node $v \in V$ belongs to at least one of $V_1$ and $V_2$;
• no node $v \in V$ belongs to both $V_1$ and $V_2$; and
• every edge $e \in E$ has one endpoint in $V_1$ and the other in $V_2$.

The sets $V_1$ and $V_2$ here are called bipartite classes of $G$.

1. Suppose you have an $8 \times 8$ chessboard. We form a graph from the board as follows: there's a node for each square on the board, and an edge between any pair of squares that are immediately adjacent in one of the four cardinal directions (up, down, left, and right).

   Explain why this is a bipartite graph by telling us what the bipartite classes are and briefly explaining why all the edges have one endpoint in each bipartite class.

   Don’t do this in your head – draw lots of pictures!

Bipartite graphs have many interesting properties. One of the most fundamental is this one:

Theorem: An undirected graph $G$ is bipartite if and only if it contains no closed walks of odd length.

The forward direction of this implication has a nice intuition.

2. Explain, intuitively, why if $G$ is bipartite, then it has no closed walks of odd length. Specifically, give us a brief, informal explanation as to why every closed walk in $G$ has to have even length.

   It might help to draw some pictures.

The reverse direction of this implication – that if $G$ has no closed walks of odd length, then $G$ is bipartite – requires a different sort of argument.

Let’s pick some arbitrary graph $G = (V, E)$ that has no closed walks of odd length. For simplicity’s sake, we’ll assume that $G$ has just one connected component. If $G$ has two or more connected components, we can essentially treat each one of them as independent graphs. (Do you see why?)

Now, choose any node $x \in V$. Using node $x$ as an “anchor point,” we can define two sets $V_1$ and $V_2$ that we’ll need for the remainder of this argument:

\[V_1 = \Set{v \in V \suchthat \text{there is an odd-length walk from } x \text{ to } v }\] \[V_2 = \Set{v \in V \suchthat \text{there is an even-length walk from } x \text{ to } v }\]

This turns out to be a really useful way to group the nodes of $G$.

3. Given the choices of $G$ and $x$ from above, prove that $V_1$ and $V_2$ have no nodes in common.

   Remember that there might be multiple different walks of different lengths from $v$ to some other node $x$, so be careful not to talk about “the” walk between $v$ and $x$. Also note that these walks are not necessarily paths.

4. Using your result from part (iii), prove that $G$ is bipartite.

   The most common mistake on this problem is to not address all the parts of the definition of a bipartite graph. Specifically, your proof must address all three bullet points in the definition supplied in the problem statement. So start off by writing down a list of what you need to prove, then address each part in turn.

Want to learn more about bipartite graphs and their applications? Take CS166, CS224W, CS250, or CS261!

Optional Fun Problem: Infinity Minus Two

Let $[0, 1]$ denote the set $\Set{ x \in \mathbb{R} \ \vert \ 0 \le x \le 1 }$ and $(0, 1)$ denote the set $\Set{ x \in \mathbb{R} \ \vert \ 0 \lt x \lt 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$.

Find a function $f : [0, 1] \to (0, 1)$ that is both injective and surjective. Define it via an explicit rule (i.e. writing out $f(x) = \blank$ or defining $f$ as a piecewise function), then prove that your function is both an injection and a surjection.

Recall from our very first lecture that two sets have the same size if there is a way to pair their elements of without leaving any elements uncovered. Defining a function that is both an injection and a surjection (referred to as a bijection) is how we formally specify such a pairing, so this proves that $\vert[0, 1]\vert = \vert(0, 1)\vert$.