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 document explores how to think about things this way, as well as how to use that perspective to write formal proofs.

The Big Table

Let's begin with The Big Table that covers all of the relevant definitions, as well as what that means for proofs on sets.

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.$
$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 \Delta 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.$

The very last row of this table often gives folks pause, so here's a brief refresher on where it comes from. Think about the set $\set{y \suchthat P(y)}\text.$ 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.

This explains where 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.

Sample Proofs

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.

Proof 1: Core Set Operations

First, let's prove the following result:

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.

Proof 2: Sets and Power Sets

In this next example, we'll prove the following theorem:

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.

Proof 3: Set-Builder Notation

In this final example, we'll prove the following 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!