# Set Algebra and Proofs Involving Sets

There are a lot of rules involving sets; you'll probably become familiar with the most important ones simply by using them a lot. Usually you can check informally (for instance, by using a Venn diagram) whether a rule is correct; if necessary, you should be able to write a proof. In most cases, you can give a proof by going back to the definitions of set contructions in terms of elements.

Example. ( Distributivity) Let A, B, and C be sets. Prove that

If X and Y are sets, if and only if for all x, if and only if .

Let x be an arbitrary element of the universe.

I've shown that

By definition of set equality, this proves that .

The idea of the proof was to reduce everything to statements about elements. Then I used logical rules to manipulate the element statements.

Note: It's also true that

Example. ( DeMorgan's Law) Let A and B be sets. Prove that

I'll just prove the first statement; the second is similar. This proof will illustrate how you can work with complements. I'll use the {\it logical} version of DeMorgan's law to do the proof.

Let x be an arbitrary element of the universe.

Therefore, .

Example. Let A and B be sets. Prove that .

This example will show how you prove a subset relationship.

By definition, if X and Y are sets, if and only if for all x, if , then .

Take an arbitrary element x. Suppose (conditional proof). I want to show that .

means that and , by definition of intersection. But and implies (decomposing a conjunction), and this is what I wanted to show. Therefore, .

By the way, you usually don't write the logic out in such gory detail. The proof above could be shortened to:

means that and , so in particular . Therefore, .

The "in particular" substitutes for decomposing the conjunction.

The procedure I've followed is so common that it's worth pointing it out.

To prove a subset relationship (an inclusion) , take an arbitrary element of X and prove that it must be in Y.

In the next example, I'll need the following facts from logic. First, is a tautology:

Also, :

In effect, this means that I can drop tautologies from "and" statements. I'll just call this "Dropping tautologies" in the proof below.

Example. Prove that .

Therefore, .

Example. Let A be a set. Prove that

This example will show how you can deal with the empty set.

To prove , let x be an arbitrary element of the universe. First, by definition of ,

I'll show that . To prove , I must prove and .

First, if , then (constructing a disjunction).

Next, suppose . The second statement is false for all x, by definition of . But the -statement is true by assumption, so must be true by disjunctive syllogism. This proves that if , then .

This completes my proof that . So

Therefore, .

To prove that , I must prove that for all x, if and only if .

As usual, x be an arbitrary element of the universe. To prove if and only if , I must prove that the two implications

are true. I'll do this by showing that, in each case, the antecedent (i.e. the "if" part of the statement) is false --- since by basic logic, if P is false, then is true.

For the first implication, consider the statement . By definition of intersection,

Now is false, by definition of the empty set. Therefore, the conjunction is also false. Hence, is false.

It follows that the implication is true, because the "if" part is false.

Likewise, the second implication is true because is false, by definition of the empty set.

Since both implications are true, if and only if . And this in turn proves that .