Set equality

DeMorgan's Law: .

If we are given specific sets then we could probably calculate the two sets equated in DeMorgan's Law and see that they are in fact equal. To prove this law in general we can use a technique often used to prove the equality of two sets. The idea is simply this: to prove that A=B we could show that and This works very nicely on DeMorgan's Law as follows.

First, assume This says so there exists a with . Thus (for this particular ) and we have . This short argument establishes the fact that by showing that an arbitrary element of the first set must be an element of the second.

Second, assume that . This says that there exists a with . Thus (for this particular ) and we have so This establishes the fact that .

Putting these two results together verifies DeMorgan's Law. Note that the second argument is essentially the first argument in reverse. This is quite often the case when showing two sets are equal by this method and you can see that most of the work is done when the first argument is complete. That's what makes this approach nice to use in many situations.

• About this document ...