We will now discuss De Morgan's laws that are some
very useful relations between sets and their complements.
One of the De Morgan's laws takes this form.
If we take the intersection of two sets and then take the
complement of this intersection, what we obtain
is the union of the complements of the two sets.
Pictorially, here is the situation.
We have our universal set.
Inside that set, we have a set, S, which is this one.
And we have another set, T, which is this one.
Let us look at this side.
The complement of S is this part of the diagram.
The complement of T is this part of the diagram.
What is left?
What is left is just this region here, which is the
intersection of S with T. So anything that does not belong
here belongs to the intersection.
This means that the complement of the intersection is
everything out there, which is the set.
If you're not convinced by this pictorial proof, let us
go through an argument that is a little more formal.
What does it take for an element to belong
to the first set?
In order to belong to that set, x belongs to the
complement of S intersection T. This is the same as saying
that x does not belong to the intersection [of]
S with T.
What does that mean?
Since it is not in the intersection, this is the same
as saying that x does not belong to S or x does not
belong to T. But this is the same as saying that x belongs
to the complement of S or x belongs to the complement of
T. And this is equivalent to saying that x belongs to the
union of the complement of S with the complement of T.
So this establishes this first De Morgan's law.
There's another De Morgan's law, which is obtained from
this one by a syntactic substitution.
We're going to play the following trick.
Wherever we see an S, we're going to replace it by S
complement.
And wherever we see an S complement, we will replace it
with an S.
And similarly, whenever we see a T, we'll replace it by T
complement.
And when we see a T complement, we will replace it
by T. So doing this syntactic substitution, what we obtain
is S complement intersection with T complement--
everything gets complemented--
is the same as S union T.
Now, let us take complements of both sides.
The complement of a complement is the set itself.
So we obtain this.
And now, we take the complement of the other side,
which is this one.
And this is the second De Morgan's law.
It tells us that the complement of a union is the
same as the intersection of the complements.
We derived it from the first De Morgan's law by a syntactic
substitution.
If you're not convinced, it would be useful for you to go
through an argument of this kind to show that something is
an element of this set if and only if it is an element of
that set as well.
Finally, it turns out that De Morgan's laws are valid when
we take unions or intersections of
more than two sets.
There is a more general form.
And the general form is as follows--
an analogy with this one.
If we have a collection of sets, Sn, perhaps an infinite
collection, we take the intersection of those sets and
then the complement, what that is is the union of the
complements.
So this is analygous to this law.
And this law extends to this one: if we have the union of
certain sets and we take the complement of the union, what
we obtain is the intersection of the complements.
We will have many occasions to use De Morgan's laws.
They're actually very useful.
They allow us, in general, to go back and forth between
unions and intersections.