Due Friday, October 20 at 1:00 pm Pacific
Solutions are available!
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.
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:
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:
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.
- $f : \mathbb{N} \to \mathbb{N}$ defined as $f(n) = 137$.
-
$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!
-
$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$.
- $f : \mathbb{Z} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
- $f : \mathbb{Z} \to \mathbb{Z}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
- $f : \mathbb{R} \to \mathbb{N}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
- $f : \mathbb{N} \to \mathbb{R}$ defined as $f(n) = \frac{n + \abs{n}}{2}$.
-
$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.
- $f : \mathbb{R} \to \Set{ x \in \mathbb{R}\ \vert\ x \ge 0 }$ defined as $f(n) = \sqrt{n}$.
- $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}$.
- $f : \Set{ x \in \mathbb{R} \ \vert\ x \ge 0 } \to \mathbb{R}$ defined as $f(n) = \sqrt{n}$.
-
$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.\] -
$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.\] -
$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}\] -
$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}\]-
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$.
-
Prove that $f$ is a bijection.
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?
Formally speaking, two sets have the same cardinality when there's a bijection between them. Your result from part (ii) therefore shows that $\abs{\naturals} = \abs{\integers}\text.$
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.
-
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.
-
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.
-
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 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.
-
Let $f : \integers \to \integers$ be the function $f(n) = 2n - 1$. Fill in the blanks below. No justification is required.
- $f^3(2) = \blank$
- $f^{137}(1) = \blank$
- $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.
-
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.
-
Let $f : A \to A$ be a function. Prove that if $f^3$ is injective, then $f$ is injective.
Problem Five: 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.
-
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.
-
Let $S = \Set{ n \suchthat n \in \naturals \land n \not\equiv_3 2 }\text.$ Prove that $S + S = \naturals\text.$
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.$
How does the Minkowski sum iteract with the standard set operations you've grown to know and love? Let's look at two examples.
-
Prove or disprove: for all sets $A, B, C \in \powerset{\naturals}\text,$ we have $A + (B \cup C) = (A + B) \cup (A + C)\text.$
This is a prove-or-disprove problem, so your first task is to figure out whether this statement is true or false. To do that, we recommend doing the following. First, write out the negation of the statement. You know that either the statement is true or the negation is true, and your task is to determine which one of those statements is true. Next, work through some examples and see what you find. If you find an example that disproves the claim, great! You're done - just write it up. If you can't find a counterexample, then maybe the statement is true. Use the two-column organization strategy to map out what you would need to assume and prove. Start working through the proof, and if you find any points where you get stuck or aren't sure what to do, try checking whether there might be a counterexample. After iterating this a few times, you'll either find a counterexample and you have your disproof, or you'll figure out how to get the proof working.
You already know how to write up a proof. If you want to write a disproof, use the following template:
Disproof: We will prove the negation of the claim, namely, [insert negation here]. [proof of negation]. $\qed$
-
Prove or disprove: for all sets $A, B, C \in \powerset{\naturals}\text,$ we have $A + (B \cap C) = (A + B) \cap (A + C)\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!
Problem Six: Galois Connections
Let $f : A \to B$ be a function. In lecture, we proved the following results:
\[\forall X \in \powerset{A}. X \subseteq f^{-1}[f[X]]\text.\] \[\forall Y \in \powerset{B}. f[f^{-1}[Y]] \subseteq Y\text.\]Both of these results are special cases of a broader result about images and preimages.
-
Let $f : A \to B$ be a function. Prove the following:
\[\forall X \in \powerset{A}. \forall Y \in \powerset{B}. (f[X] \subseteq Y \ \leftrightarrow \ X \subseteq f^{-1}[Y])\text.\]Notice that this result is a biconditional.
Let's make things more abstract. A pair of functions $F : \powerset{A} \to \powerset{B}$ and $G : \powerset{B} \to \powerset{A}$ are called a Galois connection if the following is true:
\[\forall X \in \powerset{A}. \forall Y \in \powerset{B}. (F(X) \subseteq Y \ \leftrightarrow \ X \subseteq G(Y))\text.\]Your result from part (i) shows that the image and preimage operators form a Galois connection, though other Galois connections exist as well.
-
Let $F : \powerset{A} \to \powerset{B}$ and $G : \powerset{B} \to \powerset{A}$ be a Galois connection. Prove the following:
\[\left(\forall X \in \powerset{A}. X \subseteq G(F(X))\right) \land \left(\forall Y \in \powerset{B}. F(G(Y)) \subseteq Y\right)\text.\]
Your result from part (ii) of this problem shows that knowing that images and preimages form a Galois connection immediately implies the two results from lecture - just plug in $f[\cdot]$ and $f^{-1}[\cdot]$ in for $F$ and $G$ above.
Galois connections have applications in compiler design, where they're often used to analyze how programs behave. We imagine having two sets, one representing facts that are true about a program, and one representing facts that the compiler knows are true about the program, and use Galois connections to map back and forth between them. For more on program analysis, take CS243 (Program Analysis and Optimization) and CS242 (Programming Languages).
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)}$.