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.