Problem Set 3

Due Friday, October 15 at 2:30 pm Pacific

---

This third problem set explores functions and cardinality. 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 Cantor's Theorem for an in-depth analysis of how the formal proof of Cantor's theorem works.

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

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.

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) = \left\lbrace \begin{aligned} &n^2 - 3n + 2 &\text{if } n \le 2 \\ &n &\text{if } n \ge 2 \end{aligned} \right.\]

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

    \[f(n) = \left\lbrace \begin{aligned} &\frac{n}{2} &\text{if } n \text{ is even} \\ &-\frac{n+1}{2} &\text{if } n \text { is odd} \end{aligned} \right.\]

Problem Two: Iterated Functions, Part One

Here’s a surprising mathematical fact that was discovered accidentally in 2007. Take any number you’d like and compute its cosine (we’ll assume your number is represented in radians). Then take the cosine of that number. Then take the cosine of that number. Repeat this process a couple more times. Something unexpected happens.

1. Open the file IteratedFunctions.cpp and implement a function

   double cos100(double x);
   

   that computes $\cos \cos \cos \dots \cos x$, where there are 100 cosines in the expression. Our provided starter code will evaluate your function on a variety of real numbers between 0 and 1. What do you notice?

   This problem has two steps: writing some code and then interpreting the result of what you find. We’ll only be grading the “interpreting the results” bit, which you should write up in your written solutions.

This idea of iteratively applying a function to a value comes up all the time in mathematics, and using our formal definitions of functions we can work out, mathematically, what it looks like.

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.

2. Let $f : \mathbb{N} \to \mathbb{N}$ 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$

The behavior you get back when iterating a function multiple times depends entirely on what function you’re working with. Sometimes, that behavior can be unexpected.

3. Let $f : \mathbb{R} \to \mathbb{R}$ be the function $f(x) = 2.00x(1 - x)$. Implement the function

   double magic2_00(double x);
   

   so that it takes as input a real number $x$ and returns $f^{100}(x)$. Our provided starter files will then evaluate your function on a range of real numbers between 0 and 1. What do you notice?

   As with part (i) of this problem, we’ll be grading your written answer rather than your code. Submit your observations in your writeup.

4. Repeat part (iii) using the function $f(x) = 2.75x(1 - x)$. Implement it as magic2_75.

5. Repeat part (iii) using the function $f(x) = 3.25x(1 - x)$. Implement it as magic3_25.

6. Repeat part (iii) using the function $f(x) = 3.50x(1 - x)$. Implement it as magic3_50.

7. Repeat part (iii) using the function $f(x) = 3.75x(1 - x)$. Implement it as magic3_75.

8. Repeat part (iii) using the function $f(x) = 3.99x(1 - x)$. Implement it as magic3_99.

Problem Three: Infinity Times Two

If $A$ and $B$ are sets, the Cartesian product of $A$ and $B$, denoted $A \times B\text,$ is the set

\[A \times B = \Set{ (x, y) \ \vert \ x \in A \land y \in B }.\]

Intuitively, $A \times B$ is the set of all ordered pairs you can make by taking one element from $A$ and one element from $B$, in that order. For example, the set $\textcolor{blue}{\Set{1, 2}} \times \textcolor{purple}{\Set{u, v, w}}$ is

\[\Set{ (\textcolor{blue}{1}, \textcolor{purple}{u}), (\textcolor{blue}{1}, \textcolor{purple}{v}), (\textcolor{blue}{1}, \textcolor{purple}{w}), (\textcolor{blue}{2}, \textcolor{purple}{u}), (\textcolor{blue}{2}, \textcolor{purple}{v}), (\textcolor{blue}{2}, \textcolor{purple}{w}) }.\]

For the purposes of this problem, let’s have $\heartsuit$ and $\clubsuit$ denote two arbitrary objects where $\heartsuit \ne \clubsuit$. Over the course of this problem, we’re going to ask you to prove that $\abs{\mathbb{N} \times \Set{\heartsuit, \clubsuit}} = \abs{\mathbb{N}}$.

1. Define a bijection $f : \mathbb{N} \times \Set{\heartsuit, \clubsuit} \to \mathbb{N}$. The inputs to this function are elements of $\mathbb{N} \times \Set{\heartsuit, \clubsuit}$, so you can define your function by writing

   \[f(n, x) = \blank\]

   where $n \in \mathbb{N}$ and $x \in \Set{\heartsuit, \clubsuit}$.

   You might want to draw some pictures of the set $\mathbb{N} \times \Set{\heartsuit, \clubsuit}$ so that you can get a better visual intuition.

   As a hint, start off by drawing a picture showing a way to pair off the elements of $\mathbb{N} \times \Set{\heartsuit, \clubsuit}$ with the elements of $\mathbb{N}$ so that no elements of either set are uncovered or paired with multiple elements. Then, find a way of encoding your drawing symbolically.

   In defining this function, you cannot assume $\heartsuit$ or $\clubsuit$ are numbers, since they’re arbitrary values out of your control. See if you can find a way to define this function that doesn’t treat $\heartsuit$ and $\clubsuit$ algebraically.

   You may find it helpful to use piecewise functions.

2. Prove that the function you came up with in part (i) is a bijection.

   This proof will consist of three "mini proofs." First, prove that your function $f$ obeys the domain/codomain rule, in that every element of the domain maps to some element of the codomain. Next, prove your function is injective. Finally, prove your function is surjective.

   You may find it helpful to proceed by cases.

The result you’ve proved here shows that $2\aleph_0 = \aleph_0$. Isn’t infinity weird?

Problem Four: Monotone Functions

A function $f : \mathbb{Z} \to \mathbb{Z}$ is called monotone 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)).\]

Monotone functions have a bunch of nice properties.

1. Is the function $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(x) = x^2$ monotone? 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 monotone functions. Prove that $g \circ f$ is monotone.

   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 monotone 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$." 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 monotone 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 Five: Idempotent Functions

Some crosswalks have buttons pedestrians can push to indicate that they wish to cross. Pushing the button once will let the crosswalk know that you want to cross, but pushing the button any more times has no effect. The same is true when selecting which floor you want in an elevator (pushing the button for your floor multiple times has no effect), hitting the “save” button multiple times in a row (it’s as if you just saved once), etc.

We can model this idea in the realm of functions. A function $f : A \to A$ is called idempotent if the following is true about $f$:

\[\forall x \in A. f(f(x)) = f(x).\]

In other words, the effect of applying $f$ twice is the same as the effect of applying $f$ once.

1. Below are four functions defined symbolically. Which are idempotent? No justification is necessary.

   1. $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(n) = \abs{n}$.
   2. $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(n) = n + \abs{n}$.
   3. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = 2n - 2\floor{\frac{n}{2}}$.
   4. $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = 2n - 2\ceil{\frac{n}{2}}$.

2. Below are four pictures of functions from a set back to itself. Since idempotent functions by definition have to be from a set to itself, we’ve drawn these functions by drawing out the domain/codomain as a single set with arrows leading from elements to where the function sends them. (See the slides on involutions for more examples of this.)

   Which of these functions are idempotent? No justification is necessary.

   1. 
   2. 
   3. 
   4. 

3. Let $f : A \to A$ be an idempotent function. Prove that if $f$ is injective, then $f(x) = x$ for all $x \in A$.

4. Let $f : A \to A$ be an idempotent function. Prove that if $f$ is surjective, then $f(x) = x$ for all $x \in A$.

The concept of idempotency arises in the design of reliable systems. For example, clicking "place order" twice on the same website should have the same effect as clicking it once, but making that happen requires attention to detail with how the system is designed. Want to learn more about idempotency as applied to databases? Take CS145 and CS245!

Problem Six: Understanding Diagonalization

Proofs by diagonalization are tricky and rely on nuanced arguments. In this problem, we'll ask you to review the formal proof of Cantor’s theorem to help you better understand how it works.

(Please read the Guide to Cantor's Theorem before attempting this problem.)

1. Consider the function $f : \mathbb{N} \to \wp(\mathbb{N})$ defined as $f(n) = \emptyset$. Trace through our formal proof of Cantor's theorem with this choice of $f$ in mind. In the middle of the argument, the proof defines some set $D$ in terms of $f$. Given that $f(n) = \emptyset$, what is that set $D$? Provide your answer without using set-builder notation. Make sure you see why $f(n) \ne D$ for any $n \in \mathbb{N}$, though you don’t need to explain this in your answer.

   Make sure you can determine what the set $D$ is both by using the visual intuition behind Cantor’s theorem and by symbolically manipulating the formal definition of $D$ given in the proof.

2. Let $f$ be the function from part (i). Find a set $S \subseteq \mathbb{N}$ such that $S \ne D$, but $f(n) \ne S$ for any $n \in \mathbb{N}$. Justify your answer. This shows that while the diagonalization proof will always find some set $D$ that isn't covered by $f$, it won't find every set with this property.

3. Repeat part (i) of this problem using the function $f : \mathbb{N} \to \wp(\mathbb{N})$ defined as

   \[f(n) = \Set{m \in \mathbb{N} \ \vert \ m \ge n }.\]

4. Repeat part (ii) of this problem using the function $f$ from part (iii).

5. Give a function $f : \mathbb{N} \to \wp(\mathbb{N})$ such that the set $D$ obtained from the proof of Cantor’s theorem is the set $\Set{ n \in \mathbb{N} \ \vert \ n \text{ is even} }$. Briefly justify your answer.

Problem Seven: Simplifying Cantor's Theorem?

Below is a purported proof that $\abs{S} \ne \abs{\wp(S)}$ that doesn't use a diagonal argument:

Unfortunately, this argument is incorrect. What's wrong with this proof? Justify your answer by pointing to a specific incorrect claim that’s made here and explaining why it’s incorrect.

Problem Eight: Iterated Functions, Part Two

As you saw in Problem Two, the behavior of an iterated function depends on which function you’re iterating. However, in some cases, we can run this process backwards and infer properties of a function by looking at how its iterated function behaves.

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

   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 injective and prove $f^3$ is injective; that follows from what we proved in lecture and is a different argument.

   As a reminder from earlier in this problem set, $f^3$ is the function $f \circ f \circ f$.

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

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