Guide to Proofs on Sets

If you explore just about any aspect of theoretical computer science, at some point you will find yourself bumping into sets and set theory. It's therefore important to know how to structure proofs on sets.

Proofs on sets can be tricky to get used to because in many cases your high-level intuition for why the result is true looks very different from the style of reasoning needed in a formal proof. The good news is that as long as you adhere to a few standard rules and are aware of what's expected in a set theory proof, it's quite easy to adjust to the expected format.

This guide outlines some of the formal rules behind proofs on sets and includes worked examples showing how those rules work in practice.

What Folks Get Wrong

By far the most common mistake people make when writing proofs about sets is to operate at the wrong level of detail. Because sets represent groups of things, you might think that a proof about a set would talk holistically about what sorts of objects are in the set and why those objects meet certain requirements. However, that's not what a proof about sets actually looks like. Instead, proofs on sets almost always involve working with individual, arbitrarily-chosen elements of the sets in question. (This is analogous to how proofs of universal statements work by focusing on one arbitrarily-chosen value and telling a story about that value.)

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.

Keep this in mind as you read through the rest of this guide. We'll frequently use a higher-level description of sets to build an intuition for why results are true, but the proofs we write will look quite different from that intuition.

The Big Table

The broad, overarching principle behind proofs is to refer back to formal definitions. Statements about sets have their own definitions, and those definitions are listed here in the following table. Commit this table to memory as it will come up frequently when doing set-theory proofs.

Statement	Definition	If you assume this is true…	To prove this is true…
$S \subseteq T$	$\forall x \in S. x \in T$	Initially, do nothing. Once you find some $z \in S\text,$ conclude $z \in T\text.$	Ask the reader to pick an $x \in S\text.$ Then prove $x \in T\text.$
$S = T$	$S \subseteq T \land T \subseteq S$	Assume $S \subseteq T$ and $T \subseteq S\text.$ Or, equivalently, initially, do nothing. If you find an $z \in S$ you can conclude $z \in T$ and vice-versa.	Prove $S \subseteq T$ and $T \subseteq S\text.$
$S \ne T$	$S \not\subseteq T \lor T \not\subseteq S$	Consider two cases: Case 1: There exists an $x \in S$ where $x \notin T\text.$ Case 2: There exists an $x \in T$ where $x \notin S\text.$	Prove there exists an $x$ where either $x \in S$ and $x \notin T\text,$ or $x \notin S$ and $x \in T\text.$
$x \in A \cap B$	$x \in A \land x \in B$	Assume $x \in A\text.$ Also assume $x \in B\text.$	Prove $x \in A\text.$ Also prove $x \in B\text.$
$x \in A \cup B$	$x \in A \lor x \in B$	Consider two cases: Case 1: $x \in A\text.$ Case 2: $x \in B\text.$	Either prove $x \in A$ or prove $x \in B\text.$
$x \in A - B$	$x \in A \land x \notin B$	Assume $x \in A\text.$ Also assume $x \notin B\text.$	Prove $x \in A\text.$ Also prove $x \notin B\text.$
$x \in A \symdiff B$	$x \in A \leftrightarrow x \notin B$	Consider two cases: Case 1: $x \in A$ and $x \notin B\text.$ Case 2: $x \in B$ and $x \notin A\text.$	Either prove $x \in A$ and $x \notin B\text,$ or prove $x \in B$ and $x \notin A\text.$
$A \in \powerset{B}$	$A \subseteq B$	Assume $A \subseteq B\text.$	Prove $A \subseteq B\text.$
$x \in \set{y \suchthat P(y)}$	$P(x)$	Assume $P(x)\text.$	Prove $P(x)\text.$

A few remarks about this table are in order.

First, notice that this table never actually gives a formal definition to what $A \cup B$ is, or what $A - B$ means, etc. Instead, it talks about what $x \in A \cup B$ means, what $y \in A - B$ means, etc. Surprisingly, this, in a sense, does give a definition to $A \cup B$ and the other set combination operations. The rules governing how $x \in A \cup B$ behaves gives an operational definition to $A \cup B\text.$ An operational definition is a way of defining an object by describing how it behaves and what its properties are, rather than saying what specifically it is. A good example of this is cube roots. We can define the cube root of $x$ to be the real number $y$ where $y^3 = x\text.$ This definition tells us, for example, that 2 is the cube root of 8, since $2^3 = 8\text.$ However, this definition provides no way for us to compute exactly what the cube root of a number is. For example, this definition is not going to give you an algorithm for figuring out what $\sqrt[3]{7}$ is. Rather, the definition "the cube root of $x$ is a real number $y$ where $y^3 = x$" tells you what the cube root does and how it behaves. That's similar to how the this table talks about $A \cup B\text.$ The table describes what the set does (it's the case that $x \in A \cup B$ if and only if $x \in A$ or $x \in B\text{)}$ rather than what the set is.

Next, notice that the statements $A = B$ and $A \ne B$ have definitions given in the table. The statement $A = B$ means that $A \subseteq B$ and $B \subseteq A$ are both true, and so to prove two sets are equal, you need to prove each is a subset of the other. Similarly, $A \ne B$ means that either $A \not\subseteq B$ or $B \not\subseteq A\text,$ which in turn means that there's an element that's in one set and not the other. It's important to keep these definitions in mind, especially because they might clash with your intuition. It's common to think that proving $A = B$ when $A$ and $B$ are sets requires arguing that the two collections have the same elements, perhaps by describing how the sets are formed and what they contain. But the mathematical requirements of proving two sets are equal operate at a much lower level than this, focusing instead on the subset-of relation.

Finally, let's look at the very last row of this table, which often gives folks pause. Here's a brief refresher on where it comes from. Think about the set $\set{y \suchthat P(y)}\text.$ Intuitively, this is the set of all objects for which the predicate $P$ is true. So, for example, the set $\set{n \suchthat n \in \naturals \land n \text{ is even}}$ is the set of all even natural numbers, the set $\set{S \suchthat S \subseteq \naturals}$ is the set of all subsets of $\naturals$ (the power set of the natural numbers), and the set $\set{x \suchthat x \in \reals \land x^2 = 4}$ is the set of all numbers whose square is 4 - a fancy way of writing out the set $\set{-2, 2}\text.$

Notice in this discussion that the variable used on the left-hand side of the set-builder notation ($n$ in the first example, $S$ in the second, and $x$ in the third) are just placeholders. There is no number named $n$ in the first set, there's no set named $S$ in the second, and there's no real number $x$ in the third. So what would it mean if, say, we had $m \in \set{n \suchthat n \in \naturals \land n \text{ is even}}\text?$ Well, the set on the right is the set of all even natural numbers, so if $m$ is an element of that set, it means that $m$ must be an even natural number. In other words, the statement $m \in \set{n \suchthat n \in \naturals \land n \text{ is even}}$ is basically a fancy way of saying that $m \in \naturals$ and $m$ is even. There is no discussion of $n$ at all in this - the placeholder goes away as soon as we start talking about a concrete object.

This explains where the last row in the table comes from. If you want to prove $x \in \set{y \suchthat P(y)}\text,$ you need to show that $x$ is in the set of all objects that have property $P\text,$ so you need to prove that $P(x)$ is true. Similarly, if you assume that $x \in \set{y \suchthat P(y)}\text,$ you're assuming $x$ is in the set of all objects where $P$ is true, so it must be the case that $P(x)$ is true. Notice that the variable $y$ completely disappears here, since, after all, it's just a placeholder name.

Whenever you need to prove a result about sets, consult the above table! It will help you work out what you need to assume and how to "unpack" the definition into something that will enable you to write a rigorous proof.

The rest of this page goes over some sample proofs on sets, showing how to use this table, and along the way covering some helpful advice and lessons for working through set theory proofs.

Proofs on Core Set Operations

The first proof we'll explore together is one involving the "core" set operations. There is no formal definition of what the "core" operations are, but loosely we can think of them as things like $\in\text,$ $\subseteq\text,$ $\cup\text,$ $\cap\text,$ and $=\text.$ These are the sorts of basic operations on sets that most people think of when they first encounter set theory.

We'll explore these definitions in the context of the following theorem:

Theorem: If $A$ and $B$ are sets, then $A \cap B = A$ if and only if $A \subseteq B\text.$

The statement to prove here is a biconditional $\text(A \cap B = A$ if and only if $A \subseteq B\text{),}$ so we'll need to prove each direction of implication separately. Without knowing how to do that, we can at least set up the skeleton of our proof, purely using the normal assume/prove rules for proofs

As is generally the case with proofs of biconditionals, we can work on each direction separately. So let's first work on the forwards direction (if $A \cap B = A\text,$ then $A \subseteq B\text{)}$ and then work on the reverse direction. There's no fundamental reason we have to do things in this order, and we could just as easily do it the other way.

So let's focus on the forward direction first. We need to prove that if $A \cap B = A\text,$ then $A \subseteq B\text.$ This is an implication, and using the standard rules for proving implications, we'll assume the antecedent and prove the consequent. That's shown here:

Now, let's consult our table. What should we do if we assume that $A \cap B = A\text,$ and what should we do if we assume that $A \subseteq B\text?$ First, if we assume $A \cap B = A\text,$ we can do one of two things:

1. Assume $A \cap B \subseteq A$ and $A \subseteq A \cap B\text.$
2. Initially, do nothing. If we find an element $z \in A \cap B\text,$ we can conclude that $z \in A\text,$ and vice-versa.

I personally find it easier to go with Option (2) here, so let's do that. Therefore, we won't do anything right now with the fact that we've assumed $A \cap B = A\text,$ and instead will be on the lookout for an element of $A$ or of $A \cap B\text.$ We don't have those yet, and that's fine. Typically, this early in the proof, we don't have concrete elements of the set to work with.

Next, let's look at what we should do to prove $A \subseteq B\text.$ The table says we should ask the reader to pick an $x \in A\text,$ then prove that $x \in B\text.$ That's something we can do, so let's do that here:

Hey, that's progress! We now have this new element $x \in A$ to work with. What can we do with it? Well, earlier, we said that when we're assuming $A \cap B = A\text,$ it means we should be on the lookout for an element either of $A \cap B$ or of $A\text.$ And hey! Now we have one. Specifically, we know that $x \in A\text.$ That means we can conclude $x \in A \cap B\text,$ which we'll do here:

Now what? Well, we know for sure that $x \in A \cap B\text,$ so if we consult our table above, it means that we can conclude that $x \in A$ and $x \in B\text.$ We already knew that $x \in A\text,$ so that's not immediately helpful. What about the other bit, that $x \in B\text?$ Aha! That is indeed relevant, since that's what we said we were going to prove! In fact, the insight that $x \in B$ immediately finishes this part of the proof. Here's what that looks like:

Tada! One of the two directions of the biconditional is now done. We can now focus on the other.

At this point, our goal will be to prove that if $A \subseteq B\text,$ then $A \cap B = A\text.$ Leaving set theory aside and just using our normal rules for proofwriting, we can set up this part of the proof as follows:

Now, as before, let's consult The Big Table. We are assuming that $A \subseteq B\text.$ What should we do with this? Well, according to the table, this means we should initially do nothing and instead keep an eye out for an object $z \in A\text,$ since once we find one we can conclude that $z \in B\text.$ We don't yet have any specific elements of $A$ to work with, so let's make a note to look for one and otherwise sit tight.

On the other hand, we need to prove that $A \cap B = A\text,$ and according to the table, this means we need to prove $A \cap B \subseteq A$ and that $A \subseteq A \cap B\text.$ We don't know how to do that yet, but this at least gives us a sense of what shape our proof will take. Let's write that out here:

Okay! Now we have a sense of where we're going. These two sections seem to be separate from one another, so a reasonable first guess of what to do is to prove one of them first, then the other. We've coincidentally written them in the order of first proving $A \cap B \subseteq A$ and then proving $A \subseteq A \cap B\text,$ so let's handle things in that order.

We're now tasked with proving $A \cap B \subseteq A\text.$ As you've seen above, this means we should ask the reader to choose an element $x \in A \cap B\text,$ and then we need to prove that $x \in A\text.$ Let's add that to our proof:

This is progress! Let's keep all this nice momentum going.😊

We now know that $x \in A \cap B\text,$ and this means we can consult our table and see that this means we can conclude $x \in A$ and $x \in B\text.$ And hey, that's great! We need to show that $x \in A\text,$ and that's one of the two things we just learned. Given that we don't need the fact that $x \in B\text,$ we can leave it out of the proof, just focusing on the $x \in A$ part:

Hooray! Almost done. Now we just need to prove the other direction of inclusion: that $A \subseteq A \cap B\text.$ This is yet another subset proof, so we can set it up using the same basic pattern as the others: invite the reader to pick an element of $A\text,$ then show that element is in $A \cap B\text.$ Here's what that looks like:

We now have a clear goal: get to $x \in A \cap B\text,$ starting with the fact that $x \in A\text.$ Actually, it's not just $x \in A\text,$ because we also know that $A \subseteq B$ from our initial assumption in this half of the proof. And maybe that will come in handy here, since without $A \subseteq B$ we just know that $x \in A$ and that's not much to work with.

If you'll recall from our earlier discussion, when we assumed $A \subseteq B\text,$ we said we were on the lookout for some element of $A$ to work with. We now have one - it's $x$ - so perhaps this would be a good time to apply $A \subseteq B$ to learn something about $x\text.$ Here's what that looks like:

And this turns out to be exactly what we need to close this one out. We need to prove that $x \in A \cap B\text.$ Looking at our table, that means we need to prove that $x \in A$ and $x \in B\text.$ We already knew $x \in A$ by assumption, and now we have that missing $x \in B$ piece! So let's wrap this one up and call it a day.

Et voila, we're done!

Notice how our proof hinges extensively on asking the reader to pick elements of the relevant sets and then focusing just on those elements. That's super common in proofs on sets and set theory, and it's a consequence of how the definition of $\subseteq$ works. Also notice how instead of trying to take aim at a general pattern, we instead slowly and methodically expanded out definitions one after the other until we arrived at the result we wanted. That's also common in set theory proofs.

Proofs on Power Sets

The core set operations $\cup\text,$ $\cap\text,$ etc. all make nice sense when you look at a Venn diagram. But many of the most important results about sets and set theory involve power sets. Power sets can be tough to reason about intuitively, partially because they are nigh impossible to visualize in a Venn diagram. However, if you proceed slowly and patiently, and make good use of the formal definitions from The Big Table, you'll find that power sets really aren't that bad to work with. You just need to take your time.

We'll explore power sets through the following theorem, which is a lot more nuanced than it might initially seem:

Theorem: If $S \subseteq \powerset{S}\text,$ then $\powerset{S} \subseteq \powerset{\powerset{S}}\text.$

Before going into the proof, though, we should pause for a minute to talk about what this says, because the notation here is very compact and the concepts involved are a little more subtle than they look.

Let's begin with the antecedent: $S \subseteq \powerset{S}\text.$ What does this mean? You might be tempted to think this is true about all sets - aren't all sets contained in their power set? - but that's not quite what this says. The statement $S \in \powerset{S}$ is true for all sets $S$ because each set is a subset of itself, but we're looking at $S \subseteq \powerset{S}\text,$ not $S \in \powerset{S}\text.$ So what sorts of sets are subsets of their own power sets?

Let's try some examples to see if we figure out what these sets look like.

How about $\emptyset\text?$ That will work, since $\emptyset$ is a subset of every set.

How about $\Set{137}\text?$ That will not work. Its power set is $\Set{\emptyset, \Set{137}}\text,$ and $\Set{137} \not\subseteq \Set{\emptyset, \Set{137}}$ because $137 \in \Set{137}$ but $137 \notin \Set{\emptyset, \Set{137}}\text.$ Though, interestingly, we could have figured this out without even computing what $\powerset{\Set{137}}$ is. Remember that the statement $X \in \powerset{S}$ means that $X \subseteq S\text.$ Therefore, if $S \subseteq \powerset{S}\text,$ it means every element of $S$ must be a subset of $S\text,$ and in particular, since $137$ isn't a set, it can't be a subset of anything.

More generally, this means that any set $S$ containing a non-set element can't satisfy $S \subseteq \powerset{S}\text.$ This means that if we want to find other sets $S$ that are subsets of their power sets, we'll need to look purely at sets made of sets.

Let's try, then $\Set{\Set{137}}\text.$ Does this work? If $\Set{\Set{137}} \subseteq \powerset{\Set{\Set{137}}}\text,$ it would mean that every element of $\Set{\Set{137}}$ is a subset of $\Set{\Set{137}}\text.$ And is that true? Unfortunately, no, because the only element of $\Set{\Set{137}}$ is $\Set{137}\text,$ and $\Set{137} \not\subseteq \Set{\Set{137}}\text.$ (Do you see why?)

From this discussion you might be tempted to conclude that the only set $S$ where $S \subseteq \powerset{S}$ is the empty set. But that's actually not the case either. With a little trial and error, you might find the set $S = \Set{\emptyset}\text.$ This set satisfies the requirements because $\emptyset$ is a subset of $S\text.$ You could also find $S = \Set{\emptyset, \Set{\emptyset}}$ works, and in fact there's infinitely many sets that work here.

More generally, if we pause and look at what $S \subseteq \powerset{S}$ means, it intuitively means "every element of $S$ is a subset of $S\text.$" (Do you see why?)

All of this is to say that the statement of the theorem is much more subtle than it looks! This little detour is there to make sure that we're on the same page about what we're talking about before we dive into the proof.

So let's return to the statement of the proof:

Theorem: If $S \subseteq \powerset{S}\text,$ then $\powerset{S} \subseteq \powerset{\powerset{S}}\text.$

The discussion above about what kinds of sets $S$ satisfy $S \subseteq \powerset{S}$ was meant to build intuition for the antecedent. However, if we look at this from a proofwriting lens, we need to think about this one differently. Rather than talking generally about what kinds of sets satisfy these rules, or even listing concrete examples of sets $S$ with these properties, we need to instead proceed slowly and methodically, applying our normal assume/prove rules until we're down to something a bit more concrete to work with.

Even before we fully understand why this result is true, we can start working out what shape the proof must have. That's going to look like this:

Now, let's consult our assume/prove table. We're assuming that $S \subseteq \powerset{S}\text.$ If we look at the table, we see that this means that, for the moment, we should sit tight. We're looking for a $Z$ where $Z \in S\text,$ and once we find one we can say that $Z \in \powerset{S}\text.$ Of course, we don't have such a $Z$ yet, so for now we'll just keep our eyes peeled. (Why are we using a capital $Z$ here rather than a lower-case $z\text?$ It's because if we conclude $Z \in \powerset{S}\text,$ we know that $Z$ has to be a set, and we typically use capital letters for sets. It wouldn't be wrong to use $z$ here; it would just be not the greatest use of notation to indicate intent.)

On the "prove" side of things, we need to prove that $\powerset{S} \subseteq \powerset{\powerset{S}}\text.$ Looking at our table, this means we should invite the reader to choose some $X \in \powerset{S}\text,$ at which point we'll then aim to show that $X \in \powerset{\powerset{S}}\text.$ Here's what that looks like:

At this point, let's pause once more and consult our assume/prove rules, because we now have another assumption to work with $\text(X \in \powerset{S}\text)$ and another item to prove $\text(X \in \powerset{\powerset{S}}\text{).}$ That means our next step will either be to expand out what it means to assume $X \in \powerset{S}$ or to expand out what it means to prove $X \in \powerset{\powerset{S}}\text.$

First, if we were to expand out our assumption that $X \in \powerset{S}\text,$ what would we do? According to our table, we should assume that $X \subseteq A\text,$ since, after all, $\powerset{S}$ is the set of all subsets of $S\text.$ This is good to know - this object $X$ we're working with is actually itself a subset of $S\text.$ (That's why we used a capital letter for the variable. If we had used a lower-case letter, we would go back and change it to upper-case before moving on!)

Next, what should we do if we want to expand out what it means to prove that $X \in \powerset{\powerset{S}}\text?$ According to our table, this means we need to prove that $X \subseteq \powerset{S}\text.$ Ah, interesting! We're proving something else about subsets here. Good to know.

Let's factor these into our proof:

Let's do this same thing once more. We're supposed to prove that $X \subseteq \powerset{S}\text.$ This involves proving a subset relationship, so, once again, we'll ask the reader to pick some $Y \in X\text,$ then prove that $Y \in \powerset{S}\text.$ Interesting - we now have two new variables $X$ and $Y$ in our proof, neither of which appears in the statement of the theorem! We weren't supposed to magically know this at the start of the proof. Instead, it's a consequence of what we've learned in the course of expanding out terms and definitions.

Let's integrate that into the proof, as shown here:

Before moving forward, let's pause and look at the organization of our proof. Typically, when writing a proof, we set up our goals in the first paragraph, then use the text after the first paragraph to actually execute toward that goal. Here, we've got a bit of a mishmash. Our opening paragraph talks about showing $X \in \powerset{\powerset{S}}\text,$ but our second paragraph concludes with a new goal of getting $Y \in \powerset{S}\text.$ While this isn't wrong per se, and isn't even necessarily a style error, it's still not as elegant as it could be. Let's reorganize what we have so that the two major threads of our proof - introducing new facts and clarifying our goals - are kept as separate as possible. Here's what that looks like:

It's worth double-checking that indeed we haven't changed any of the reasoning and instead just moved things around to make the argument cleaner. For what it's worth, it's totally normal in the case of writing up a proof to need to pause and reorganize things. After all, proofwriting is a creative process! It's just like writing code - often you write something, realize there's a better way to do it, and then toss what you have and write something else.

Back to the proof at hand! How do we proceed from here? The path actually opens up a bit at this point. One option is to note that we have said our goal is to prove that $Y \in \powerset{S}\text,$ so we could consult the "prove" column of the table and realize this means we need to show that $Y \subseteq S\text.$ Another would be to realize that we have $Y \in X$ and $X \subseteq S\text,$ so via our "assume" column we could conclude that $Y \in S\text.$ There's no way to know a priori which of these two options will work out better for us. However, I've scouted this one out for us and it turns out the latter option ends up being easier. So let's do that and update our proof to show what we now know about $S\text:$

Again, we have two options available to us. One would be, as above, to recognize that our goal, proving $Y \in \powerset{S}\text,$ is equivalent to proving that $Y \subseteq S\text.$ The other would be to realize that since $Y \in S$ and $S \subseteq \powerset{S}\text,$ that we can get $Y \in \powerset{S}\text.$ And here, there is indeed a clear sense of which option is better. The latter step literally accomplishes what we set out to prove: that $Y \in \powerset{S}\text,$ while the other would change our goal. And any time we can immediately do the thing we said we were going to do, we should! So let's choose that option. Here's the final version of the proof:

And we're done! Hooray!

There are a few important details to note about this proof. First, notice how power sets let us switch between the $\in$ and $\subseteq$ relationship. Specifically, $A \in \powerset{B}$ happens if and only if $A \subseteq B\text.$ Next, notice how we ended up with two new variables in our proof that weren't in the statement of the theorem. This happens because we're repeatedly applying the rules for proving one set is a subset of another. We couldn't "guess" immediately that we'd need two more variables, and instead it "fell out" of applying our standard assume/prove rules. Third, notice that at several points in this proof, we had multiple choices about how to proceed, and it wasn't clear which one to pick. That's a normal part of mathematical reasoning! If everything was "forced," then we wouldn't teach you how to write proofs and would instead just have the computer do it for us. But that's not the case, and often some exploration is required. And finally, notice how midway through our proof, we realized that our organization was getting a bit messy and adjusted accordingly. We don't chisel our proof drafts into stone tablets for a reason - often we have to back up and try something else out.

Proofs on Set-Builder Notation

As we continue through the quarter, we'll make extensive use of set-builder notation. In fact, some of the deepest results we'll explore will involve set-builder notation. Learning to write proofs with set-builder notation will thus be one of the most important skills to develop over the next couple of weeks.

We'll see how to write proofs on set-builder notation through the following example theorem:

Theorem: Let $f : \powerset{\naturals} \to \powerset{\naturals}$ be defined as $f(S) = \Set{n \suchthat n \in S \land \exists k \in \naturals. n = 3k+1}\text.$ Then if $A, B \in \powerset{\naturals}$ and $A \subseteq B\text,$ then $f(A) \subseteq f(B)\text.$

Before we jump into the proof, let's pause and piece together what this notation says. At the core of this theorem is a function $f\text,$ so let's see what that function does.

First, let's look at the domain and codomain of $f\text.$ We see that $f : \powerset{\naturals} \to \powerset{\naturals}\text.$ What does that mean? Well, since the domain of $f$ is $\powerset{\naturals}\text,$ it means that the objects we can feed into $f$ are the elements of the set $\powerset{\naturals}\text.$ And since each element of $\powerset{\naturals}$ is a subset of $\naturals\text,$ we can read this domain rule as saying that $f$ takes as input a subset of $\naturals\text.$ Or, even more clearly, that the input to $f$ is a set of natural numbers.

Similarly, the codomain of $f$ is the set $\powerset{\naturals}\text,$ so everything that comes out of $f$ must be an element of $\powerset{\naturals}\text,$ which, as we saw above, must be a set of natural numbers.

Putting this together, we see that $f$ is a function that takes in a set of natural numbers and outputs a set of natural numbers. Neat!

Okay - but which set of natural numbers does $f$ produce given some input $S\text?$ Well, we have the following rule to guide us:

\[f(S) = \Set{n \suchthat n \in S \land \exists k \in \naturals. n = 3k+1}\text.\]

What does this say? The output set here is defined using set-builder notation. Translating into English, it seems like $f(S)$ is the set of all $n$ where $n \in S$ (so $n$ has to be contained in the set $S$ given to $f$ as input), and where there's a natural number $k$ where $n = 3k+1\text.$ Read differently, it seems like this says "start with the set $S\text,$ then filter it down to just those numbers $n$ that can be written as $3k+1$ for some natural number $k\text.$" So, for example, we'd have $f(\set{1, 2, 3}) = \set{1}\text,$ and we'd have $f(\set{1, 3, 7}) = \set{1, 7}\text.$

So at this point we've done the heavy lifting to figure out what the function $f$ is and how it works. That's a good starting point, but we're not done yet. The crux of the theorem is this part: if $A, B \in \powerset{\naturals}$ and $A \subseteq B\text,$ then $f(A) \subseteq f(B)\text.$ What does this say?

First, we now know what $A, B \in \powerset{\naturals}$ means - this says that $A$ and $B$ are sets of natural numbers. So the theorem says something like "if $A$ and $B$ are sets of natural numbers where $A \subseteq B\text,$ then $f(A) \subseteq f(B)\text.$" And that's something that we can start to play around with.

We can build up an intuition for the result using our knowledge of how $f$ works. Since $f$ "filters out" all elements of its input except those of the form $3k+1\text,$ then this result says that if $A$ is a subset of $B$ and you "filter out" all the elements of $A$ and $B$ except the ones of interest, then you're left with two sets $f(A)$ and $f(B)$ and it's still the case that $f(A) \subseteq f(B)\text.$ That kinda sorta makes sense.

Of course, that's just an intuition - it's not a proof! To formally prove this, we'll have to use our assume/prove table from above. To get the ball rolling, we'll begin by getting the basic setup written:

At this point, we have become pros at handling what it means to assume $A \subseteq B$ - we just sit tight and wait because we don't have any concrete elements of $A$ to work with just yet. And we're also pros at handling what it means to prove $f(A) \subseteq f(B)\text,$ because that means we ask the reader to pick an element of $f(A)$ and then set a new goal for ourselves of proving that element is in $f(B)\text.$ Here's what that looks like:

Now, what do we do here? We are now at a point where we know that $m \in f(A)\text.$ And we also know that $f(A)$ is some complex expression given in set-builder notation (specifically, it's $\Set{n \suchthat n \in A \land \exists k \in \naturals. n = 3k+1}\text{).}$ So let's peek up at our table. It says that, in general, if we find ourselves assuming that $x \in \Set{ y \suchthat P(y) }\text,$ it means we should assume that $P(x)$ is true. In other words, if you know that $x \in \Set{ y \suchthat P(y) }\text,$ since $\Set{y \suchthat P(y)}$ is the set of all $y$ where $P(y)$ is true, and $x$ is in that set, it means that $P(x)$ has to be true.

In our case, we have $m \in \Set{n \suchthat n \in A \land \exists k \in \naturals. n = 3k+1}\text,$ which means that we should conclude that $m \in B$ and that there's a $k \in \naturals$ where $m = 3k+1\text.$ Notice that we do not introduce a variable $n$ here, because $n$ is just a placeholder used in the set-builder notation. Instead, we just say that since $m$ is in the set of all objects with some property, it must be the case that $m$ has that property too. Here's what this looks like:

Hey, that's progress! This tells us quite a lot.

Now, let's look at our goal: that $m \in f(B)\text.$ What do we have to do to prove this? Again consulting The Big Table, we can see that to prove something of the form $x \in \set{y \suchthat P(y)}\text,$ we should prove $P(x)\text.$ (Again, the intuition here is that since $\set{y \suchthat P(y)}$ is the set of all objects where $P$ is true, to prove $x$ is in that set, we need to prove $P(x)\text{.)}$ Since we need to prove that $m \in f(B)\text,$ that means that we need to prove that $m \in B$ and that there's a $k \in \naturals$ where $m = 3k+1\text.$

If we look at where we are in our proof right now, we already have the latter of these two. Great! That means we just need to show that $m \in B\text.$ And hey, look! We know that $m \in A$ and that $A \subseteq B\text,$ so we can easily get that part too.

Here's what we get if we put all this together:

And that's it, we're done! We've gone from a problem statement to an intuition to a proof. Very cool!

Exercises

Here's a small collection of set theory exercises you can use to practice what you've learned in this guide. None of these will be collected or graded for credit, but we still think they're worthwhile to work through.

1. Let $A\text,$ $B\text,$ and $C$ be sets. Prove that $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text.$

   Solution

   Our goal is to prove that two sets are equal, so we need to prove each is a subset of the other. That's basically two separate mini-proofs, each of which can be done independently of the other. Here's one way to do write this up. Notice how the proof's shape is heavily influenced by The Big Table.

   Proof: We need to prove that $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ and that $(A \cup B) \cap (A \cup C) \subseteq A \cap (B \cup C)\text.$

   First, we'll prove $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)\text.$ To do so, choose some $x \in A \cup (B \cap C)\text;$ we need to show that $x \in (A \cup B) \cap (A \cup C)\text.$ Because $x \in A \cup (B \cap C)\text,$ we know either $x \in A$ or $x \in B \cap C\text.$ We consider each case separately:

   • Case 1: $x \in A\text.$ Then since $x \in A\text,$ we know that $x \in A \cup B$ and $x \in A \cup C\text.$ Therefore, we see that $x \in (A \cup B) \cap (A \cup C)\text.$

   • Case 2: $x \in B \cap C\text.$ This means that $x \in B$ and $x \in C\text,$ and so we know that $x \in A \cup C$ and $x \in B \cup C\text.$ This in turn means that $x \in (A \cup B) \cap (A \cup C)\text.$

   In each case, we see that $x \in (A \cup B) \cap (A \cup C)\text,$ as required.

   Next, we'll prove that $(A \cup B) \cap (A \cup C) \subseteq A \cap (B \cup C)\text.$ So let's pick some $x \in (A \cup B) \cap (A \cup C)\text;$ we'll show that $x \in A \cup (B \cap C)\text.$ Since $x \in (A \cup B) \cap (A \cup C)\text,$ we know that $x \in A \cup B$ and $x \in A \cup C\text.$ We now consider two cases:

   • Case 1: $x \in A\text.$ Then we see that $x \in A \cup (B \cap C)\text.$

   • Case 2: $x \notin A\text.$ Since $x \in A \cup B\text,$ we know that $x \in A$ or $x \in B\text.$ We're assuming $x \notin A\text,$ which means that $x \in B\text.$ Similar reasoning applied to $x \in A \cap C$ shows us that $x \in C\text.$ We now have $x \in B$ and $x \in C\text,$ which means that $x \in B \cap C\text,$ and thus that $x \in A \cup (B \cap C)\text.$

   In each case, we see that $x \in A \cup (B \cap C)\text,$ as required. $\qed$

   ---

2. Let $A$ and $B$ be sets. Prove that $(A \symdiff B) \symdiff B = A\text.$

   Solution

   This is a proof on set equality, so we need to show each set is a subset of the other. With a little creativity in how we choose our cases, we can come up with the following proof:

   Proof: We need to show that $(A \symdiff B) \symdiff B \subseteq A$ and that $A \subseteq (A \symdiff B) \symdiff B\text.$

   First, we'll show that $(A \symdiff B) \symdiff B \subseteq A\text.$ So choose some $x \in (A \symdiff B) \symdiff B\text;$ we'll prove $x \in A\text.$ We consider two cases:

   • Case 1: $x \notin B\text.$ Since $x \notin B$ and $x \in (A \symdiff B) \symdiff B\text,$ we know that $x \in A \symdiff B\text.$ And since $x \in A \symdiff B$ and $x \notin B\text,$ this means that $x \in A\text.$

   • Case 2: $x \in B\text.$ Since $x \in (A \symdiff B) \symdiff B$ and $x \in B\text,$ we know that $x \notin A \symdiff B\text.$ This means that either $x \notin A$ and $x \notin B$ or that $x \in A$ and $x \in B\text.$ The first option is impossible because $x \in B\text,$ so we see that $x \in A$ and $x \in B\text,$ which in particular means that $x \in A\text.$

   In each case, we see that $x \in A\text,$ as needed.

   Next, let's prove $A \subseteq (A \symdiff B) \symdiff B$ by picking some $x \in A$ and proving $x \in (A \symdiff B) \symdiff B\text.$ As above, we consider two cases:

   • Case 1: $x \notin B\text.$ Then since $x \in A$ and $x \notin B\text,$ we see that $x \in A \symdiff B\text.$ And since $x \in (A \symdiff B)$ and $x \notin B\text,$ we see that $x \in (A \symdiff B) \symdiff B\text.$

   • Case 2: $x \in B\text.$ Then since $x \in A$ and $x \in B\text,$ we see $x \notin A \symdiff B\text.$ Then, since $x \notin A \symdiff B$ and $x \in B\text,$ we see that $x \in (A \symdiff B) \symdiff B\text.$

   In each case we see that $x \in (A \symdiff B) \symdiff B\text,$ as required. $\qed$

   ---

3. Let $A$ and $B$ be sets. Prove that $\powerset{A} - \powerset{B} \ne \powerset{A - B}\text.$

   Solution

   Here we must prove that two sets are not equal, which means that we need to find an element that is in one set but not the other. After some exploration, we can come up with the following proof.

   Proof: First, we note that $\emptyset \subseteq A\text,$ that $\emptyset \subseteq B\text,$ and that $\emptyset \subseteq A - B\text.$ This means that $\emptyset \in \powerset{A}\text,$ $\emptyset \in \powerset{B}\text,$ and $\emptyset \in \powerset{A - B}\text.$ Accordingly, we see that $\emptyset \notin \powerset{A} - \powerset{B}\text.$ Thus we have $\emptyset \in \powerset{A - B}$ but $\emptyset \notin \powerset{A} - \powerset{B}\text,$ and thus $\powerset{A - B} \ne \powerset{A} - \powerset{B}\text{. } \qed$

   ---

4. Let $A$ and $B$ be sets. Prove that $\powerset{A \cap B} = \powerset{A} \cap \powerset{B}\text.$

   Solution

   The statement of this theorem masks a surprising amount of depth that arises when we unpack all the relevant terms and definitions. Here's one way to prove this result.

   Proof: We need to show that $\powerset{A \cap B} \subseteq \powerset{A} \cap \powerset{B}$ and that $\powerset{A} \cap \powerset{B} \subseteq \powerset{A \cap B}\text.$

   First, we'll prove $\powerset{A \cap B} \subseteq \powerset{A} \cap \powerset{B}\text.$ So pick any $S \in \powerset{A \cap B}\text;$ we need to show that $S \in \powerset{A} \cap \powerset{B}\text.$ Equivalently, we need to show that $S \in \powerset{A}$ and $S \in \powerset{B}\text.$ Since the roles of $A$ and $B$ are symmetric, we'll just prove $S \in \powerset{A}\text.$ To do that, we'll prove $S \subseteq A\text.$

   Pick any $x \in S\text.$ We need to show that $x \in A\text.$ Since $S \in \powerset{A \cap B}\text,$ we know that $S \subseteq A \cap B\text.$ Then, since $x \in S$ and $S \subseteq A \cap B\text,$ we nkow that $x \in A \cap B\text,$ which in turn means that $x \in A\text,$ as required.

   Next, we'll prove that $\powerset{A} \cap \powerset{B} \subseteq \powerset{A \cap B}\text.$ To do so, pick any $S \in \powerset{A} \cap \powerset{B}\text.$ We need to prove that $S \in \powerset{A \cap B}\text.$ To do so, we need to prove that $S \subseteq A \cap B\text.$ So pick some $x \in S\text;$ we need to show that $x \in A \cap B\text.$

   Because $S \in \powerset{A} \cap \powerset{B}\text,$ we know that $S \in \powerset{A}$ and that $S \in \powerset{B}\text.$ This in turn means that $S \subseteq A$ and that $S \subseteq B\text.$ These two facts plus $x \in S$ tell us that $x \in A$ and $x \in B\text.$ And that means that $x \in A \cap B\text,$ which is what we needed to show. $\qed$

   ---

5. Consider the function $f : \powerset{\powerset{\naturals}} \to \powerset{\naturals}$ defined as $f(S) = \Set{ x \suchthat \exists T \in S. x \in T}\text.$ Prove that for all $X, Y \in \powerset{\powerset{\naturals}}$ that $f(X \cup Y) \subseteq f(X) \cup f(Y)\text.$

   Solution

   For starters, what exactly does this function do? Its inputs are elements of $\powerset{\powerset{\naturals}}\text,$ which means that every input to $f$ needs to be a set whose elements are themselves sets of natural numbers. The output of $f$ is an element of $\powerset{\naturals}\text,$ so everything produced by the function has to be a set of natural numbers. In other words, the input set has one more "layer" of set to it than the output.

   And how exactly is the output determined? The rule above says "to compute $f(S)\text,$ gather together everything that belongs to any of the elements of $S$ into a set." Why is this? Well, if you pick an element $x \in f(S)\text,$ you know that there's some $T \in S$ (that is, an element of $S\text)$ where $x \in T$ (that is, $x$ belongs to $T\text{.)}$ In that sense, you can think of $f$ as a "flattening" function that basically breaks open all the sets inside $S$ and pours what comes out into the resulting set.

   Now, how do we prove the theorem? This one looks dense, and the key here is to unpack things one step at a time. Following the normal rules for proofwriting, we'll invite the reader to pick $X$ and $Y\text.$ We need to show that $f(X \cup Y) \subseteq f(X) \cup f(Y)\text,$ so we'll pick a $z \in f(X \cup Y)$ and try to show that $z \in f(X) \cup f(Y)\text.$ From here, we can expand out the definition of $z \in f(X \cup Y)$ to learn more about $z\text,$ and at that point it's off to the races.

   There's a nice intuition for what this result says. If you think of $f$ as the "flattening" function, this says "flattening $X \cup Y$ doesn't give you anything you wouldn't already get by first flattening $X$ and $Y$ and combining the results together." But of course, in Theoryland, we write this up using formal notation.

   With all this in mind, here's what the proof looks like. You could also do this by cases instead of using WLOG, but I like how the WLOG version reads a bit more.

   Proof: Pick any $X, Y \in \powerset{\powerset{\naturals}}\text.$ We will prove that $f(X \cup Y) \subseteq f(X) \cup f(Y)\text.$ To do so, choose an arbitrary $z \in f(X \cup Y)\text.$ We want to show that $x \in f(X) \cup f(Y)\text.$

   Since $z \in f(X \cup Y)\text,$ there is a set $T \in X \cup Y$ where $z \in T\text.$ Because $T \in X \cup Y$ we know that $T \in X$ or $T \in Y\text.$ Assume, without loss of generality, that $T \in X\text.$ Then we have $z \in T$ and $T \in X\text,$ which means that $z \in f(X)\text.$ And since $z \in f(X)\text,$ we see that $z \in f(X) \cup f(Y)\text,$ which is what we needed to show. $\qed$

   ---

6. If $f : A \to B$ is a function and $S \subseteq A\text,$ then the image of $S$ under $f\text,$ denoted $f[S]\text,$ is the set

   \[f[S] = \set{ b \suchthat \exists a \in S. f(a) = b }\text.\]

   Let $f : A \to A$ be an involution. Prove for all sets $S \subseteq A$ that $f[f[S]] = S\text.$

   Solution

   It's worth taking a minute to see what this set $f[S]$ is. With some experimentation, we can see that it's the set formed by applying $f$ to each element of $S\text,$ then gathering together all the elements produced this way.

   The proof itself requires going slowly and methodically through the definitions. Here's one way to do this:

   Proof: Choose some $S \subseteq A\text.$ We must show that $f[f[S]] = S\text,$ which we will do by proving each set is a subset of the other.

   First, we'll prove $f[f[S]] \subseteq S\text.$ So pick some $b \in f[f[S]];$ we must prove $b \in S\text.$

   Since $b \in f[f[S]]\text,$ we know there is some $c \in f[S]$ where $f(c) = b\text.$ Since $b \in f[S]\text,$ we in turn know there is some $d \in S$ where $f(c) = d\text.$ Putting this together, we see that $f(f(d)) = f(c) = b\text.$ And because $f$ is an involution, we know that $d = f(f(d))\text.$ Combining these equalities tells us that $d = b\text.$ Then, since $d = b$ and $b \in S\text,$ we know $b \in S\text,$ as required.

   Next, we'll show $S \subseteq f[f[S]]\text.$ So pick some $x \in S\text;$ we need to show that $x \in f[f[S]]\text.$

   Because we know $x \in S\text,$ we see that $f(x) \in f[S]\text.$ Similarly, since $f(x) \in f[S]\text,$ we know that $f(f(x)) \in f[f[S]]\text.$ Because $f$ is an involution, we know that $x = f(f(x))\text,$ which combined with $f(f(x)) \in f[f[S]]$ tells us that $x \in f[f[S]]\text,$ as required. $\qed$

   ---