Sets Operations

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: Let's define a few familiar and standard operations on sets. So here's a picture of two sets A and B, where the idea is that the circle represents the points in A. The other circle represents the points in B. The overlapping area, this lens-shaped region, are the points that are in both A and B. And the background are the points that are in neither A and B.

So this sort of a general picture allows you to classify points with respect to And B, and it's called a Venn diagram, in this case for two sets. It's still useful for three sets. It gets more complicated for four sets. And after that point, they're not really very useful. But a lot of the basic operations can be illustrated nicely in terms of the Venn diagram for two sets, and that's what we're about to do.

So the first operation is union. It's the set of points shown here in magenta. It's the set of points that are in either A or B, all of them. And so if we were defining this in terms of set-theoretic notation or predicate notation, the union symbol-- the U is the union symbol. So A union B is defined to be those points x that are in A OR are in B.

And you can already begin to see an intimate relationship between the union operation and the propositional OR connective. But don't confuse them. If you apply an OR to sets, your compiler is going to give you a type error. And if you apply union to propositional variables, your compiler is also going to give you a type error. So let's keep the propositional operators and the set-theoretic operators separate [? and ?] clearly distinct even though they resemble each other.

All right. Next basic operation is intersection where, again, it's the points that are both in A and B, the points in common, which are now highlighted in blue. So the definition of A intersection B-- we use an upside-down union symbol for intersection-- it's the set of points that are in A and are in B.

So let's stop for a minute and make use of the similarity between the set-theoretic operations and the propositional operators. Let's look at a set-theoretic identity, which I claim holds no matter what sets A, B, and C you're talking about. And we're going to prove it by making the connection between set-theoretic operations and propositional operators.

And so let's read the thing. It says that if you take A union the set B intersection C, that's equal to the set A union B intersected with A union C. Now, let's not think through yet how to make this an intuitive argument. It's going to really crank out in an automatic way in a moment.

But we can remember it as saying that you can think of this as union distributing over intersection. So if you think of union as times here and intersection as plus, then we've got a rule that says that A times B plus C is A times B plus A times C.

Now, it's also true that if you reverse the role of union and intersection, you get another distributive law that AND distributes over union, but never mind that. Let's just look at this one. We're trying to prove the distributive law for union over intersection. How shall we prove it just from the definitions?

Well, the way we're going to do it is by showing that the two sets on the left-hand side and the right-hand side have the same set of elements. Namely, if I have an element x that appears in the set described on the left-hand side, then that point is in the right-hand side. And it's an if and only if. So that says that the left-hand side and the right-hand side expressions defines sets with the same set of points. This holds for all x.

And it turns out that the proof is going to follow by analogy to a propositional formula that we're going to make use of in the proof. That was a propositional equivalence that we proved in an earlier talk, namely that OR distributes over AND. So P OR Q AND R is equivalent to P OR Q AND P OR R.

So you can see this equivalence in purple has the same structure as the set-theoretic equality in blue, except that union's replaced by OR, intersection's replaced by AND, and set variables A, B, C is replaced by propositional variables P, Q, R.

So let's just remember that we've already proved this propositional equivalence, and we're going to make use of it in the middle of this proof that these two sets are equal. So again, we said we were going to prove the two sets are equal by showing they have the same points. So here's the proof. It's going to be a lovely if and only if argument the whole way.

So looking at the left-hand side, a point x is in A union B intersection C by definition of union if and only if x is an A OR x is in B intersection C. I've just applied the definition of union there. OK. Now, let's look at this expression. x is in B intersection C. That's the same as x is in B AND x is in C, again, just using the definition of intersection. And now I have a propositional formula involving OR and AND and the basic assertions about sets of x is a member of one of those A's, B's, C's.

Now, at this point, I can immediately apply my propositional equivalence and say that the assertion x is an A OR x is in B AND x is in C holds if and only if this expression, x is an A OR x is in B AND x is in A OR x is in C. Why is that? Well, I'm just invoking the propositional equivalence. Let's look at it.

That if I think of the x is in A as proposition P-- and let's replace all the x [? over ?] A's by P-- and I think of x is in B as a Q and x is in C as an R, then I can see that the first set-theoretic assertion has the form of P OR Q AND R.

And I can transform it by the propositional equivalence into P OR Q AND P OR R. And then remember what P and R are to get back to the set-theoretic membership, basic membership assertions. So now we've just proved that x is in A OR x is in B AND x is in A OR x is in C. And that's if and only if it was in the left-hand side set.

Well, now I'm going to go back the other way. Namely, this OR, that x is in A OR x is in B, is the same as saying that x is in A union B, likewise here just by applying the definition of union. And this assertion that x is in this set AND x is in this set is the same as saying that x is in their intersection. And I've completed my proof, namely the point that was in the left-hand side if and only if it's in the right-hand side. You have to remember that that was the right-hand side of the identity.

So this is a general method actually, where you can take any set-theoretic equality involving union and intersection and the operations of difference and complement that we'll talk about in a moment, and we can convert any such set-theoretic equality into a propositional equality or a propositional equivalence so we can check that the propositional assertion is an equivalence.

And from that, using this method of converting the membership statements in the set expression into a propositional combination, we can check, and automatically check, any kind of set-theoretic identity involving union, intersection, and minus. And that, in fact, is the way that automatic engines like Mathematica can prove these set-theoretic identities.

So let's just for the record put down that last operation. The difference operation is the set of elements that are in A AND not in B. So we'd write it as A minus B is the set of points that are in A AND not in B. and it's Illustrated by this region that's highlighted in orange.

And a special case of the minus operation or the difference operation is complement. When you know the overall domain that you expect all your sets to be part of, then you can define a complement to be everything that's not in A-- the set of x such that x is not in A, where x is understood to be ranging over some domain of discourse. So if we're going to picture that, we're looking at the whole orange region, all of the stuff that's not in A if we think of the whole slide as representing the domain of discourse D.

Free Downloads

Video


Caption

  • English-US (SRT)