Set Algebra

Mathematicians tend to prove results about sets as they need them, rather than memorizing and using a large collection of rules. 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.

Once you've compiled a collection of known facts about sets, you can use those facts to prove other facts.

There are also various styles for these proofs. You can write a proof formally, as a series of implications or double implications.

Alternatively, you can give a proof that relies more on words.

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 .

First, I'll give a formal proof, written as a series of double implications:

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.

Here's an alternative proof written with more words. I'll prove by showing that each set is contained in the other.

First, I'll show that . Let . By definition of intersection, this means that and .

Now means, by definition of union, or . Combining this with the fact that , this means that either and , or and .

By definition of intersection (twice), this means that either or . And by the definition of union, this means that .

I've shown that if , then . By definition of subset, .

Next, I'll show that . Let . By definition of union, or .

In the first case, . By definition of intersection, this means and . Now by constructing a disjunction, gives or , and by definition of union, I get .

Since I know , the definition of intersection gives .

In the second case, . By definition of intersection, this means and . Now by constructing a disjunction, gives or , and by definition of union, I get .

Since I know , the definition of intersection gives .

Since in both cases I have , I have shown that if , then . By definition of subset, this means that .

Finally, since I've shown that and are each contained in the other, they must be equal: .

You can see that the first proof is shorter, but sometimes shorter proofs require more thinking to understand: The proof is shorter because the reasoning is compressed. The second proof is much longer, but maybe the words make more sense to you.

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 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 the following.

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 following implications:

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 .

Contact information