Problem Set 3

Due Friday, October 18 at 1:00 pm Pacific

---

This third problem set explores functions and set theory. 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.
• Read the Guide to Proofs on Sets, which talks about how to write proofs involving sets (e.g. $\cap\text,$ $\subseteq\text,$ etc.)

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. In particular, the two-column proof organizer and the table of how to assume/prove things will be extremely helpful here.

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

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: All You Need Is Love

Let $P$ be a set consisting of some number of entities (cats, robots, and people). Here are three possible properties the set $P$ might have:

\[\begin{aligned} \text{(I)} & \quad \forall x \in P. Loves(x, x). \\ \text{(II)} & \quad \forall x \in P. \forall y \in P. (Loves(x, y) \to Loves(y, x)). \\ \text{(III)} & \quad \forall x \in P. \forall y \in P. \forall z \in P. (Loves(x, y) \land Loves(y, z) \to Loves(x, z)). \end{aligned}\]

Below is an incorrect proof of an incorrect theorem.

The error in this proof turns out to be one of the most common mistakes we see on this problem set, so before we jump into formal proofwriting, let's take a minute to figure out what's the error is.

1. The proof (correctly) starts off by assuming property (II) is true. Based on the assume/prove table for first-order logic, what variables, if any, should the proof introduce as a result of this? If any variables are introduced, what assumptions, if any, should the proof make about them? If any variables are introduced, what should the proof aim to show about them?

2. The proof (correctly) starts off by assuming property (III) is true. Based on the assume/prove table for first-order logic, what variables, if any, should the proof introduce as a result of this? If any variables are introduced, what assumptions, if any, should the proof make about them? If any variables are introduced, what should the proof aim to show about them?

3. The proof (correctly) starts off by stating it will prove property (I) is true. Based on the assume/prove table for first-order logic, what variables, if any, should the proof introduce as a result of this? If any variables are introduced, what assumptions, if any, should the proof make about them? If any variables are introduced, what should the proof aim to show about them?

4. Based on your answers to parts (i), (ii), and (iii) of this problem, what is the error in this proof? Be as specific as possible. (If the proof contains multiple logical errors, we just care about the first one. After all, once it's made a logical error, everything after that point is irrelevant.)

5. The "theorem" in this problem is not true. Draw an example of a world in which properties (II) and (III) are true, but property (I) is not. No justification is required.

Problem Three: Amidakuji

This problem explores a technique called amidakuji (Japanese: 阿弥陀籤) that is useful for divvying up tasks or rewards among a group of people, along with its mathematical properties.

As a motivating example, suppose there are four people (Amy, Breaunna, Chioma, and Devney) and four desserts (eclairs, froyo, gujhia, and halva). Each person gets one dessert. To divvy them up, they decide to use an amidakuji. They begin by drawing four vertical lines. The top of each line is labeled with a person, and the bottom of each line is labeled with a dessert. Then, they draw a random collection of horizontal lines called rungs. Each rung links up two adjacent vertical lines, like the rungs of a ladder. The only rules about where the horizontal lines go is that no two horizontal lines are allowed to touch. The resulting figure is called an amidakuji. Here's an example of what this might look like:

Here's how to use the amidakuji to see who gets which dessert. Each person begins at her name, then traces a path downward. Whenever the path reaches a rung, the path moves across that rung from one vertical line to the next. Eventually, the path reaches the bottom of one of the vertical lines, revealing which dessert the person gets. For example, in the above amidakuji, Amy ends up with gujhia and Breaunna gets eclairs:

1. What desserts do Chioma and Devney get? No justification is required.

Here's a simple mathematical model of amidakuji. Rather than working with people and desserts, let's imagine instead that we're working with a set $[n] = \set{ k \suchthat k \in \naturals \land k \lt n }$ for some natural number $n\text.$ The top and bottom of the amidakuji will then be labeled with elements of the set $[n]\text,$ with each number appearing once on the top and once on the bottom. Each amidakuji can then be thought of as a function $f : [n] \to [n]$ that maps numbers on the top to numbers on the bottom. For example, consider the amidakuji below:

This amidakuji represents the function

\[f(x) = \begin{cases} \quad 2 & \text{if } x = 0 \\ \quad 4 & \text{if } x = 1 \\ \quad 0 & \text{if } x = 2 \\ \quad 6 & \text{if } x = 3 \\ \quad 1 & \text{if } x = 4 \\ \quad 5 & \text{if } x = 5 \\ \quad 3 & \text{if } x = 6 \\ \end{cases}\]

2. Draw an amidakuji representing the function $f : [5] \to [5]$ defined as $f(n) = 4 - n\text.$ No justification is required.

We can say more about the structure of functions $f$ that arise from amidakuji. The overall behavior of the amidakuji is a consequence of each individual rung. Each rung links together two columns $i$ and $i + 1\text.$ The rung has the effect of swapping $i$ and $i + 1$ while leaving the other columns unmodified. Mathematically, this is called a transposition. Mathematically, in an $n$-column amidakuji, for each $i \in [n - 1]$ we define the function $\sigma_i : [n] \to [n]$ as follows:

\[\sigma_i(x) = \begin{cases} i + 1 & \text{if } x = i \\ i & \text{if } x = i+1 \\ x & \text{otherwise} \end{cases}\]

3. Suppose we have an $n$-column amidakuji. Briefly explain why, in the definition of $\sigma_i\text,$ we require $i \in [n - 1]$ rather than $i \in [n]\text.$ Your answer should be at most one or two sentences.

4. Prove for all $n \in \naturals$ and $i \in [n - 1]$ that $\sigma_i$ is a bijection (a function that is both injective and surjective).

   This one is all about calling back to definitions. To prove a function is a bijection, you need to prove it's injective and surjective. What do you need to prove to show that a function is injective? What do you need to prove to show that a function is surjective?

An amidakuji can be thought of as a composition of some (large) number of tranpositions. In lecture, we proved that the composition of two injections is injective and that the composition of two surjections is surjective. Therefore, since each transposition is a bijection, the resulting amidakuji is always a bijection. This explains why it works well for divvying up items: each output is produced by exactly one input.

There's a lot more to explore with amidakuji beyond what we did here. If you're interested in exploring a bit more, here's some questions to get you started. (None of these will be collected for credit.)

1. Every amidakuji defines a bijection from $[n]$ to itself. Can every bijection $f : [n] \to [n]$ be formed from some amidakuji?

2. How much of a difference can a single rung in an amidakuji make? That is, if you were to add or remove a single rung from the middle of an amidakuji, how wildly can the output of the amidakuji change?

3. Are amidakuji "fair" in the sense that, assuming the rungs are added more or less at random, each person is equally likely to get each output?

Problem Four: 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!

Problem Five: Eventual Bijections

Suppose you have a function $f : A \to A$ from some set back to itself. This allows us to compose $f$ with itself multiple times. To make things a bit easier to talk about, let’s introduce some notation. For any natural number $n$, we’ll define $f^n : A \to A$ to be the function $f \circ f \circ \dots \circ f$, with $f$ appearing $n$ times in the expression. So, for example, $f^1$ is just the function $f$ itself, while $f^2$ is the function $f \circ f$ and $f^3$ is the function $f \circ f \circ f$. As a special case, we’ll say that $f^0$ is the function $f^0(x) = x$; this is chosen to make things behave more consistently.

1. Let $f : \integers \to \integers$ be the function $f(n) = 2n - 1$. Fill in the blanks below. No justification is required.

   1. $f^3(2) = \blank$
   2. $f^{137}(1) = \blank$
   3. $f^0(137) = \blank$

In many cases, if you know something about how a power of a function works, you can learn something about the function itself.

2. Let $f : A \to A$ be a function. Prove that if $f^3$ is surjective, then $f$ is surjective.

   Make sure you’re proving the right thing. Here, you know something about $f^3$, and your goal is to infer something about $f$ itself. Make sure not to instead assume $f$ is surjective and prove $f^3$ is surjective; that follows from what we proved in lecture and is a different argument.

   This is a great place to write out what it is that you're assuming and what it is you're proving. Much of the complexity of this problem stems from differentiating between the two.

3. Let $f : A \to A$ be a function. Prove that if $f^3$ is injective, then $f$ is injective.

Problem Six: Set Theory Warmup

Proofs on sets and set theory can take some time to get used to, largely because so many lines of reasoning that seem like they're rigorous or precise operate at a much higher level than is required. Make sure you've read the Guide to Proofs on Sets before starting this problem.

Below is an invalid proof of a true statement about sets:

Proofs written in the above style are not sufficiently rigorous to prove a result about set theory. Here's a few reasons why:

• The proof (correctly) states that it needs to show $A \cup B \subseteq C\text.$ Consulting our set theory assume/prove table, we see that this means that we need to choose an arbitrary element of $A \cup B$ And prove that it's in $C\text.$ This proof doesn't do that. Instead, it talks holistically about the structure of $A\text,$ $B\text,$ and $C$ and tries to infer the subset relationship from this. While that might make intuitive sense, it's not sufficiently rigorous reasoning for a formal proof.

• The proof states that it assumes $A \subseteq C$ and $B \subseteq C\text.$ Consulting the set theory assume/prove table, we see that this means we should initially do nothing, then wait for a specific element of $A$ or a specific element of $B$ to arise. However, this proof instead uses these facts to write $C$ as a set of a specific form. While that might be intuitively true, that's not something we can conclude from $A \subseteq C$ and $B \subseteq C\text.$

• By writing $A = \set{a_1, a_2, \dots, a_n}\text,$ we're implicitly assuming that the set $A$ only has $n$ elements in it for some natural number $n\text.$ But if $A$ is an infinite set - say, $A = \naturals$ - then there is no value of $n$ for which the "last" element of $A$ would be $n\text.$ And if $A$ is a set bigger than $\naturals\text,$ then we might run out of natural numbers before we've numbered all the elements of $A\text.$ For this reason, we almost never write out sets this way in a formal proof.

Now that you've seen what not to do, we'd like you to prove this result using the formal assume/prove rules you're familiar with.

Prove that if $A \subseteq C$ and $B \subseteq C\text,$ then $A \cup B \subseteq C\text.$

Problem Seven: Sets and Power Sets

Power sets come up all the time in the context of functions and computation. This problem is designed to help you get comfortable working with them.

1. Prove by contradiction that for all sets $A\text,$ we have $A \subseteq A\text.$

   The goal of this problem is to show you how to prove something that may seem "obvious" by calling back to formal definitions. What is the formal definition of the statement $A \subseteq A\text?$ What is its negation?

   As a reminder, proofs by contradiction do not include a want-to-show statement the way that direct proofs do. It's implicitly understood by the reader that your goal is to arrive at a contradiction.

2. Prove for all sets $A$ and $B$ that $A \subseteq B$ if and only if $\powerset{A} \subseteq \powerset{B}\text.$

   Note that this result is a biconditional rather than a regular implication.

   Check the Guide to Proofs on Sets and the table in the set theory lecture slides for information about how to write proofs involving power sets.

Problem Eight: Set-Builder Notation

Let $f : \reals \to \powerset{\reals}$ be the function defined as follows:

\[f(x) = \set{y \suchthat y \in \reals \land y \le x}\text.\]

Below is an invalid proof of a true statement:

Here's our explanation as to why this proof is not sufficiently rigorous.

• The Guide to Proofs on Sets includes a specific definition of what it means for two sets to not be equal to one another. Specifically, that definition says that $A \ne B$ when there is an element $x$ where $x \in A$ and $x \notin B$ or where $x \notin A$ and $x \in B\text.$ Thus to show that two sets are not equal, the proof needs to find a specific value that belongs to one of $f(x_1)$ and $f(x_2)$ but not the other. This proof doesn't do this, so it's not properly engaging with the definitions and thus can't be correct.

• The proof talks at a high level about what the sets $f(x_1)$ and $f(x_2)$ represent and uses this as the basis for its reasoning. While this is great from an intuition-building perspective, as you've seen, this style of argumentation makes it very easy to make incorrect claims. As a result, we don't use this style of reasoning in formal proofs, instead focusing one element at a time.

There are also two style errors we want to call attention to:

• The proof redefines the function $f\text.$ Generally speaking, if an object, function, set, etc. is defined outside a proof, you shouldn't redefine it inside the proof. You should instead assume the reader is familiar with all the relevant terms and definitions. And on the plus side, this will save you a lot of typing!

• The proof expands out $f(x_1) = \set{y \suchthat y \in \reals \land y \le x_1}$ and $f(x_2) = \set{y \suchthat y \in \reals \land y \le x_2}\text.$ Although these are true statements, you can assume that the reader is familiar with how $f$ is defined and can plug $x_1$ and $x_2$ into the definition of $f$ on their own. Writing things out this way doesn't add anything to the argument.

Now that you've seen one way not to write this proof, we'd like you to try your hand at proving this result yourself.

1. Suppose $a \in \reals\text.$ Consult the Guide to Set Theory Proofs. If you assume that $a \in \set{y \suchthat y \in \reals \land y \le x}\text,$ what should you do?

2. Based on your answer to (i), if you assume that $a \notin \set{y \suchthat y \in \reals \land y \le x}\text,$ what should you do?

3. Suppose $a \in \reals\text.$ Consult the Guide to Set Theory Proofs. If you want to prove that $a \in \set{y \suchthat y \in \reals \land y \le x}\text,$ what should you do?

4. Based on your answer to (iii), if you want to prove that $a \notin \set{y \suchthat y \in \reals \land y \le x}\text,$ what should you do?

5. Prove that $f$ is injective.

Problem Nine: Minkowski Sums

Let's begin with a new definition. Suppose we have two sets $A, B \in \powerset{\naturals}\text.$ The Minkowksi sum of $A$ and $B\text,$ denoted $A + B\text,$ is defined as follows:

\[A + B = \Set{ x \suchthat \exists m \in A. \exists n \in B. x = m + n }\text.\]

To get a better feel for that definition, let's explore some simple cases.

1. Answer each of the following questions. No justification is required.

   • Let $A = \set{1, 2, 3}$ and $B = \emptyset\text.$ Is $1 \in A + B\text?$
   • Let $A = \set{1, 2, 3}$ and $B = \set{0}\text.$ Is $1 \in A + B\text?$
   • Let $A = \set{1, 2, 3}$ and $B = \set{1}\text.$ Is $1 \in A + B\text?$
   • Let $A = \set{1, 2, 3}\text.$ Is $1 \in A + A\text?$

2. Fill in each of the following blanks without using set-builder notation. No justification is necessary.

   • $\Set{1, 2, 3} + \Set{10, 20} = \blank\text.$
   • $\emptyset + \Set{1, 2, 3} = \blank\text.$
   • $\naturals + \naturals = \blank\text.$

Here's an interesting fact about Minkowski sums that, surprisingly, was a key part of a landmark paper on string data structures from 2003. Specifically, the paper used the theorem below to ensure that all possible cases for how two sets would interact with another were covered.

3. Let $S = \Set{ n \suchthat n \in \naturals \land n \not\equiv_3 2 }\text.$ Prove that $S + S = \naturals\text.$

   The hardest part of this problem is getting the setup correct and figuring out what you need to show in the proof. You aren't expected to see this immediately. Instead, work slowly and deliberately to unpack the definitions and see what they tell you to do. We recommend using the two-column strategy shown in lecture where you write out one column for “what I’m assuming” and one for “what I need to show.”

   This is a proof on sets, so proceed accordingly. What does it mean for two sets to be equal? How do you prove one set is a subset of another? What does it mean to assume $x \in \Set{ y \suchthat P(y) }\text?$ Proceed slowly and deliberatively here to make sure you set up the proof correctly and prove all the right things.

   Feel free to use the following fact: for every integer $x\text,$ exactly one of the following is true: $x \equiv_3 0\text,$ $x \equiv_3 1\text,$ or $x \equiv_3 2\text.$

Minkowksi sums have applications in computer graphics. Here, we're dealing with Minkowksi sums on sets of natural numbers, but they can be generalized to work with sets of vectors as well. There, they're used to define operations that expand and contract images given in a vector representation. Want to learn more about computer graphics and image processing? Take CS148!

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

Give a definition of bijection $f : [0, 1] \to (0, 1)$ via an explicit rule (i.e. writing out $f(x) = \blank$ or defining $f$ as a piecewise function), then prove that your function is a bijection. This proves that $\abs{[0, 1]} = \abs{(0, 1)}$.