Problem Set 3

Due Friday, October 21 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.

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: $\abs{\naturals} = \abs{\integers}$

Although intuitively it might seem like there are more integers than natural numbers, surprisingly, the two sets have the same cardinality.

Consider the function $f : \naturals \to \integers$ defined as follows:

\[f(n) = \begin{cases} k & \text{if } \exists k \in \naturals. n = 2k \\ -(k+1) & \text{if } \exists k \in \naturals. n = 2k+1 \end{cases}\]

1. Fill in the blanks below. No justification is necessary.

   • $f(0) = $ $\blank$.
   • $f(1) = $ $\blank$.
   • $f(2) = $ $\blank$.
   • $f(3) = $ $\blank$.
   • $f(4) = $ $\blank$.
   • $f(5) = $ $\blank$.

2. Prove that $f$ is a bijection. This means that $\abs{\naturals} = \abs{\integers}$.

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

One way of interpreting the result you've just proved here is that $\aleph_0 = 2\aleph_0$, since you can think of $\integers$ as having twice as many elements as $\naturals\text.$ Isn't infinity weird?

Problem Three: 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 Four: 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 Five: 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 }.\]

   Some things to think about: what is $f(0)\text?$ How about $f(1)\text?$ How about $f(137)\text?$

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 Six: 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 Seven: Proofs on Sets

On Problem Set One, you explored the language of sets and set theory. On this problem, you'll see how to write proofs about sets.

One of the trickier details when writing proofs about sets is a disconnect between how we usually conceptualize sets and how proofs about sets actually work. When you think about sets at a high level, you typically think about "the collection of all items with some property" and think more holistically about what the items of the set look like. However, proofs about sets tend to instead focus more on individual elements of the sets and how they relate to one another.

Let's begin with an example. You're familiar with the notation $S \subseteq T$, which says that $S$ is a subset of $T$. The formal definition of $S \subseteq T$ is given here:

\[S \subseteq T \qquad \text{if} \qquad \forall x. (x \in S \to x \in T)\text.\]

This is a universally-quantified statement. That means that to prove that $S \subseteq T$, the general pattern is the following:

• Pick an arbitrary $x \in S$.
• Prove that $x \in T$.

This means that proofs about sets almost always focus on specific elements of those sets rather than properties of the sets in general. For example, here's a sample proof on sets:

Notice that this proof focuses on the element $x$ and repeatedly applies the definition of subsets to learn more about it.

1. Fill in the blanks below to complete the following proof. As always, the relative sizes of the blanks does not necessarily indicate how much you need to write.

   Theorem: For all sets $A$, $B$, and $C$, if $A \subseteq B$ and $A \subseteq C$, then $A \subseteq B \cap C$.

   Proof: Let $A$, $B$, and $C$ be arbitrary sets where $\blank$. We need to show that $\blank$. To do so, pick an arbitrary $x \in $ $\blank$. We want to show that $x \in $ $\blank$.

   Since $\blank$ and $\blank$, we know that $x \in $ $\blank$. Similarly, since $\blank$ and $\blank$ we know that $x \in$ $\blank$. This means that $\blank$ and $\blank$, and so $x \in $ $\blank$, as required. $\qed$

2. Fill in the blanks below to complete the following proof. As always, the relative sizes of the blanks does not necessarily indicate how much you need to write.

   Theorem: For all sets $A$, $B$, and $C$, if $A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$.

   Proof: Let $A$, $B$, and $C$ be arbitrary sets where $\blank$. We need to show that $\blank$. To do so, pick an arbitrary $x \in $ $\blank$. We want to show that $x \in $ $\blank$.

   Since $\blank$, we know that either $x \in $ $\blank$ or $x \in $ $\blank$. We consider each case separately.

   Case 1: $x \in $ $\blank$. $\blank$.

   Case 2: $x \in $ $\blank$. $\blank$.

   In either case, we see that $\blank$, which is what we needed to show. $\qed$

Now that you have a bit more of a feel for what these proofs look like, let's introduce one more concept. Formally speaking, if $S$ and $T$ are sets, we say that $S = T$ when $S \subseteq T$ and $T \subseteq S$. In other words, two sets are equal when each is a subset of the other.

3. Prove for all sets $A$ and $B$ that if $\powerset{A} = \powerset{B}\text,$ then $A = B\text.$

Problem Eight: The Universal Set

What happens if we take absolutely everything and throw it into a set? If we do, we would get a set called the universal set, which we denote $\mathscr{U}$. This set is defined by the following property:

\[\forall x. x \in \mathscr{U}\text.\]

Absolutely everything would belong to this set:

\[1 \in \mathscr{U}, \quad \mathbb{N} \in \mathscr{U}, \quad \text{CS103} \in \mathscr{U}, \quad \text{whimsy} \in \mathscr{U}, \quad \dots\]

In fact, we'd even have $\mathscr{U} \in \mathscr{U}$, which is strange but not immediately a problem.

Unfortunately, the set $\mathscr{U}$ doesn't actually exist, as its existence would break mathematics. In this problem, you'll discover why that is.

1. Prove that if $A$ and $B$ are arbitrary sets where $A \subseteq B$, then $\abs{A} \le \abs{B}$.

   Formally speaking, if you want to prove that $\abs{A} \le \abs{B}$, you need to find an injection $f : A \to B$. Your proof will therefore probably take the form of defining a function $f : A \to B$ and then proving that it's an injection.

   As you saw in Problem Seven, the statement $S \subseteq T$ is formally defined to mean $\forall x. (x \in S \to x \in T)$. You will need to use this formal definition somewhere in your proof. As with all other formal definitions, this definition will guide your proof, but you won't explicitly write any quantifiers or connectives in your answer.

2. Using your result from (i), prove that if $\mathscr{U}$ exists, then $\abs{\wp(\mathscr{U})} \le \abs{\mathscr{U}}$.

3. The Cantor-Bernstein-Schroeder Theorem says that if $A$ and $B$ are sets such that $\abs{A} \le \abs{B}$ and $\abs{B} \le \abs{A}$, then $\abs{A} = \abs{B}$. Using the Cantor-Bernstein-Schroeder Theorem and the formal definitions of cardinality, prove that if $A$ and $B$ are sets where $\abs{A} \le \abs{B}$, then $\abs{B} \not\lt \abs{A}$.

   In this proof you're essentially showing that the $\le$ and $\lt$ relations involving set cardinality work like the $\le$ and $\lt$ relations over regular numbers. Since the goal of the proof is to show that these cardinality relations work like regular inequality symbols, this result isn't "obvious" and you'll need to use formal definitions. For example, we say that $\abs{A} \lt \abs{B}$ when $\abs{A} \le \abs{B}$ and $\abs{A} \ne \abs{B}$. Those relations are in turn defined by types of functions between these sets. So be careful in this proof not to accidentally assume something you need to prove.

4. Using Cantor's theorem, plus the results you proved in this problem, prove that $\mathscr{U}$ does not exist.

The result you've proven shows that there is a collection of objects (namely, the collection of everything that exists) that cannot be put into a set. When this was discovered at the start of the twentieth century, it caused quite a lot of chaos in the math world and led to a reexamination of logical reasoning itself and a more formal definition of what objects can and cannot be gathered into a set. If you're curious to learn more about what came out of that, take Math 161!

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