Guide to Proofs on Sets

General Principles

To formalize your intuition about sets and how they behave – and to build up better predictions for how sets will interact with one another – you’ll want to shift your thinking from a holistic “$A \cup B$ represents the set you get when you combine $A$ and $B$ together” to a more precise “$x \in A ∪ B$ if and only if $x \in A$ or $x \in B$.” That change in perspective – from the properties of the set as a whole to properties of the individual elements of those sets – will be a key theme throughout this course. It’s not necessarily the most natural perspective to adopt, but once you’ve learned to think about things this way you’ll get a much deeper understanding for how sets behave.

The rest of this handout explores how to think about things this way, as well as how to use that perspective to write formal proofs.

A First Running Example

In the upcoming sections, we’re going to see how to reason rigorously about sets and set theory. Rather than doing that in the abstract, we’ll focus on a specific, concrete example.

Consider the following theorem:

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

Although there are a ton of variables here, this result isn’t as scary as it might look. Before moving on, take a minute to think through what’s going on here. Draw some pictures. Try out some examples. Even though you might not have an idea of where this proof is going to go, you can still at the very least set up the first sentence. As we saw in lecture, there are a number of little mini “proof templates” that you can use to focus your efforts. Here, we’re trying to prove a statement of the form “For all $x$, if $P(x)$ is true, then $Q(x)$ is true.”, and as you saw in class, there’s a nice template for starting off a proof of this form:

• we'll have the reader make an arbitrary choice for $x$ (since this statement is universally-quantified);
• we assume $P(x)$ is true (since that’s the antecedent of an implication); and then
• we want to show that $Q(x)$ is true (since it’s the consequent of an implication).

In this particular example, we might start off a proof like this:

In other words, we’re beginning with a ton of little assumptions, and we have a single goal that we need to prove (namely, $A \subseteq D \cup E$). So now the question is how we go about doing that.

Reasoning About Subsets

The subset-of relation $⊆$ is one of the most fundamental relations we’ll explore in set theory. As a reminder, formally speaking, we say that $S \subseteq T$ if every element of $S$ is also an element of $T$. If you’ll notice, the statement “every element of $S$ is also an element of $T$” is a universal statement – it says that for each object of some type (“every element of $S$”) has some other property (“is also an element of $T$”).

Putting this together, we have the following:

To prove $S \subseteq T$, pick an arbitrary $x \in S$, then prove that $x \in T$.

Using this template, we can continue the proof that we set up. When we left off, we said we needed to prove $A \subseteq D \cup E$. And hey! We just developed a template for that. Let’s use it!

An important detail here: this proof introduces a new variable $x$. The statement of the theorem purely relates $A$, $B$, $C$, $D$, and $E$ to one another. It says nothing whatsoever about anything named $x$. Although there is no variable $x$ in the original theorem, proving that theorem requires us to reason about elements of the sets. How do we proceed from here? It’s not immediately clear, but we can use some of the information we have. For example, we know that $A \subseteq B \cup C$, and we know that $x \in A$. We can combine these pieces of information together given the following principle:

If you know that $S \subseteq T$ and you have an $x \in S$, you can conclude $x \in T$.

This follows from how subsets are defined. If $S \subseteq T$, then every element of $S$ is an element of $T$, and so in particular because $x$ is an element of $S$, we can say that $x$ is an element of $T$.

We can put that into practice here in our example proof:

A detail to point out before we move on: notice that the way that we interact with the relation in a $\subseteq$ proof differs based on whether we are proving that one set is a subset of another or whether we are using the fact that one set is a subset of another. That will be unifying theme throughout the entire quarter, and you’ll see this come up in the rest of this handout. In the first paragraph, we set up a proof that $A \subseteq D \cup E$ by picking an arbitrary $x \in A$. In the second, we used the fact that $A \subseteq B \cup C$ to conclude that $x \in B \cup C$. Proving that one set is a subset of another introduces a new variable; using the fact that one set is a subset of the other lets us conclude new things about existing variables.

To summarize, here's what we learned about the subset relation:

Reasoning About Set Combinations

You probably have a good intuition for unions, intersections, and the like from your lived experience. The union of the set of all your TAs and your classmates represents the set of people you’re mostly like to interact with in a given course. The intersection of the set of people you admire and the set of people who admire you represents the set of people you probably should consider becoming friends with. And so on.

But in the elemental theory of sets, we have to ask – what exactly makes up the sets $S \cup T$, $S \cap T$, $S \Delta T$, etc.? After all, sets are formally defined by their elements. And for that, we need these definitions:

Let’s jump back to the proof we’re working through. Our ultimate goal is to prove that $x \in D \cup E$, so we should check to see what exactly we need to do in order to prove that an element is in the union of two sets:

To prove that $x \in S \cup T$, prove either that $x \in S$ or that $x \in T$.

In our case, this means we need to show that $x \in D$ or that $x \in E$. It’s not immediately clear how we're going to get there, but we have some starting assumptions to work with. Let’s try exploring those to see what we can find, keeping our end goal in the back of our mind.

We know that $x \in B \cup C$, so we can consult our template for what to do when we know that an element is in the union of two sets:

If you assume that $x \in S \cup T$, conclude that $x \in S$ or that $x \in T$.

We can now put that into practice:

We’re making some progress here, because this lets us use some of the facts from our proof setup that we haven’t touched yet. Specifically, we’ve been holding onto the fact that $B \subseteq D$ and that $C \subseteq E$, and here we’re confronted with the fact that either $x \in B$ or $x \in C$. Using what we saw in the previous section about subsets, that means that we can potentially make a lot more progress here. The challenge is that we can’t say for certain whether $x \in B$ or $x \in C$ – that might depend on $x$, $B$, and $C$. But that’s not a problem – that’s the sort of thing a proof by cases was meant for!

Here’s how we might continue from the previous section using both a proof by cases and our knowledge of how $B$, $C$, $D$, and $E$ relate:

This is looking a lot better. In fact, we’ve demonstrated between our two cases that $x$ belongs to one of $D$ or $E$, and so we can conclude that it always belongs to $D \cup E$, which if you’ll recall is what we had set out to show in the first place.

All that remains is to conclude the proof:

And that’s a wrap! Now, look back over this proof. Notice that it is focused on a single element $x$, went with $x$ on a magical journey, and ended up reaching our desired conclusion.

Reasoning About Set Equality

What does it mean for two sets to be equal? This is addressed by the fancy-sounding axiom of extensionality, a term you are totally welcome to toss around at cocktail parties, which says the following:

Two sets $S$ and $T$ are equal ($S = T$) if $S \subseteq T$ and $T \subseteq S$.

We’ll go ahead and summarize what this definition means in the context of proofwriting:

This approach for proving that two sets are equal is sometimes called a proof by double inclusion, though we generally won’t refer to it by that name. You are welcome to toss that around at cocktail parties as well, though, if you so choose.

We want to call your attention to fact that proving set equality involves doing two subset proofs. It is very easy to prove just one direction of the subset relation and forget to address the other direction, so watch out for this when you’re writing your own proofs!

Reasoning About Power Sets

First, let’s recap the formal definition of the power set. The power set of a set $S$ is the set of all subsets of $S$:

$\wp(S) = \Set{\ T \suchthat T \subseteq S\ }$

If you haven’t already done so, take a minute to read over that set-builder notation and to see if you can convince yourself why it says symbolically what we described in plain English right above it.

The above definition is wonderfully useful. You’ll apply it in proofs like so: