Problem Five: 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:
Theorem: If $A \subseteq C$ and $B \subseteq C\text,$ then $A \cup B \subseteq C\text.$
(Incorrect!) Proof: Let $A\text,$ $B\text,$ and $C$ be any sets where $A \subseteq C$ and $B \subseteq C\text.$ We need to prove that $A \cup B \subseteq C\text.$
Let's begin by writing $A = \set{a_1, a_2, \dots, a_n}$ and $B = \set{b_1, b_2, \dots, b_m}\text.$ We know that $A \subseteq C$ and $B \subseteq C\text,$ so $C$ must have the form $C = \set{a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_m, c_1, c_2, \dots, c_r}\text,$ where $c_1, c_2, \dots, c_r$ are elements of $C$ that are not in $A$ and not in $B\text.$
With the notation from above, we can write $A \cup B = \set{a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_m}\text,$ and by looking at how we defined $C$ above we can see that $A \cup B \subseteq C\text{. }\qed$
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.$
Don't start with the above proof and try to make edits to it to correct the errors identified above. Instead, throw the above proof away and start over from scratch. Follow the assume/prove rules for set theory, using the examples from lecture and the Guide to Proofs on Sets as a reference.
Problem Six: 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.
-
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.
-
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 Seven: 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:
Theorem: The function $f$ is injective.
(Incorrect!) Proof: Let $f : \reals \to \powerset{\reals}$ be defined as follows:
\[f(x) = \set{y \suchthat y \in \reals \land y \le x}\text.\]We will prove that $f$ is injective. To do so, pick any $x_1, x_2 \in \reals$ such that $x_1 \ne x_2\text.$ We need to show that $f(x_1) \ne f(x_2)\text.$
We see that $f(x_1) = \set{y \suchthat y \in \reals \land y \le x_1}$ and that $f(x_2) = \set{y \suchthat y \in \reals \land y \le x_2}\text.$ This means that $f(x_1)$ is the set of all real numbers less than $x_1$ and that $f(x_2)$ is the set of all real numbers less than $x_2\text.$ Since $x_1 \ne x_2\text,$ these sets can't be equal to one another, so $f(x_1) \ne f(x_2)\text{. } \qed$
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.
-
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?
-
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?
-
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?
-
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?
-
Prove that $f$ is injective.
Don't try proving this result by starting with the above proof and making modifications to it to try to get it to work. Instead, start from a clean slate and prove the result from scratch. The incorrect proof above is so far off track that it's best to scrap it and start over.
Problem Eight: 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.
-
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?$
-
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.$
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!