Another Set Equality Example

In this video, we're going to talk about a proof, but instead of well discovering it we're going to read a proof, that I had just written and then talk about it. So the statement that we're going to prove is the following:

Prove that $A \cap B=A-(A-B)$

Proof

First we show that $A \cap B \subseteq A-(A-B)$ . Let $x \in A\cap B$ . Then $x\in A$ and $x\in B$ . By definition, $x\notin(A-B)$ . However, since $x\in A$ and $x\notin (A-B)$ , we have that $x\in A-(A-B)$ .

Next, we show that $A-(A-B) \subseteq A\cap B$ . Let $x \in A-(A-B)$ By definition, this means that $x\in A$ and $x \notin (A-B)$ For $x\notin (A-B)$ to be true, either $x\notin A$ (which we know is false) or $x\in A$ and $x\in B$ . Thus $x\in A$ and $x\in B$ and hence by definition, $x\in A\cap B$ .

Therefore, $A\cap B=A-(A-B)\quad\blacksquare$

So there is the proof, now let's talk about it.

Discussion of Proof

So again we have a proof involving set equalities, so in order to show this, we're going to first show that the left-hand set is contained inside the right-hand set, and then we'll show that the right-hand set is contained inside the left-hand set.

So first, we show that $A\cap B \subseteq A-(A-B)$ . So to do this, we start with an element from the left-hand set. Let $x\in A\cap B$ , and what does that mean? So now we unwind the definition, so if $x$ is inside the intersection, then it must be inside both the sets, right? So then $x\in A$ and $x\in B$ .

By definition, what do we know? Well if $x\in A$ and $x\in B$ , then we know that $x\notin (A-B), right, because it's in the intersection.

So what does that tell us? Well however, we already know that $x\in A$ inside A and we know that $x\notin (A-B)$ , and so by definition again we have that $x\in A-(A-B)$ . Again this is just definition pushing.

So you just have to remember what these definitions mean, right? $A\cap B$ means that each element of $A$ is contained in $B$ , and $A-B$ means that $x$ is an element of $A$ and $x$ is not an element of $B$ . That's what the set difference set is.

Now we try the reverse inclusion. So let $x\in A-(A-B)$ . By definition, we know that this means that $x\in A$ and that $x\notin (A-B)$ . That is the definition of $x$ belonging to this set.

Now the next question is for $x\notin (A-B)$ , what does that mean? Well this means one of two things, it either means that $x\notin A$ , in which case would be done, but we already know that's false so we know that this part can't be true, but there's an “or”, right? So either $x\notin A$ or $x\in A$ and $x\in B$ , right, because if it's inside both of these sets, then it's not in the set difference because it's common.

Since we know the first part is false, right, we already have that $x\in A$ , what can we conclude? Well we conclude that the second part has to be true, so then thus $x\in A$ and $x\in B$ , and then hence, by definition, $x\in A\cap B$ .

That shows the reverse containment, so now we've shown the double containment, therefore the claimed statement is true. $A\cap B=A-(A-B)$

Okay, hopefully this helped. Thank you very much.