Combining Sets

by George E. Hrabovsky, President, MAST

Where We Have Been

Up to now we have laid the foundations of how mathematics is done. We have discussed sets, logic, and proof techniques. Last column we explored ideas of universality, existences, and uniqueness.

Where Will We Go in This Column

In this column we will apply what we have covered so far to explore some of the mathematics of sets.

Defining Sets

As we have seen ("Setting up for the Future") making the statement that a set is a collection of objects leads to a paradox. On the other hand, if we decide on three axioms we can make a general definition of a set.

Axiom 5-1: Any objects is either an element of a set or it is not.

This axiom is an extension of the law of the excluded middle.

Axiom 5-2: An element of a set must always be distinguishable from every other element.

This axiom stems from the convention of listing each element of a set only once.

Axiom 5-3: No set is an element of itself.

This axiom prevents the paradox of the set of all sets. We can now state the following definition of a set: Any collection of objects that obey Axioms 5-1, 5-2, and 5-3 is called a set.
    Now that we have a definition of a set, it is fair to ask the question, "How can we combine sets?"

Union

The first way to combine two sets is to combine all elements of both sets, thus forming a new set. This is called the union of sets. Given the sets A and B we can write the union symbolically,

From this definition we can derive the following theorems:

Theorem 5-1:

Proof: We begin with (1), , by the permutation rule (see "The Proof is in the...") is the same as , applying this to (1) gives us . Thus, . The theorem is proved.

Theorem 5-2:

Proof: This is a direct consequence of the principle of associativity (see "The Proof is in the..."), I leave the details as an exercise.

Theorem 5-3:

Proof: This is a direct consequence of the rule of tautology (see "The Proof is in the..."), I leave the details as an exercise.

Theorem 5-4:

Proof: I leave this as an exercise. It is simple if you take it step by step from the definition of the union of two sets (1).

Theorem 5-5:

Proof: I leave this as an exercise. You should have little difficulty if you apply the definitions of subsets and union.

Theorem 5-6:

Proof: I leave this as an exercise. You should have little difficulty if you apply the definitions of subsets and union. Recall that you need to show not only does the conclusion follow from the hypothesis, but also that the hypothesis follows from the conclusion.

Theorem 5-7:

Proof: I leave this as an exercise. Again you will need to show not only does the conclusion follow from the hypothesis, but also that the hypothesis follows from the conclusion.

•Intersection

Another way to combine two sets is to combine all elements common to both sets, thus forming a new set. This is called the intersection of sets. Given the sets A and B we can write the intersection symbolically,

From this definition we can derive the following theorems:

Theorem 5-8:

Proof: We begin with (1), . As in the permutation rule, it seems reasonable that the order of a conjunction doesn't matter, so we can say that   is the same as , applying this to (2) gives us . Thus, . The theorem is proved.

Theorem 5-9:

Proof: This is a direct consequence of the principle of associativity (see "The Proof is in the..."), I leave the details as an exercise.

Theorem 5-10:

Proof: This is a direct consequence of (2), I leave the details as an exercise.

Theorem 5-11:

Proof: I leave this as an exercise. It is simple if you take it step by step from the definition of the intersection and the definition of the empty set.

Theorem 5-12:

Proof: I leave this as an exercise. You should have little difficulty if you apply the definitions of subsets and intersection.

Theorem 5-13:

Proof: I leave this as an exercise. You should have little difficulty if you apply the definitions of subsets and intersection.

Theorem 5-14:

Proof: By combining (1) and (2) we have . By the distributive principle (see "The Proof is in the...") we have,

By the permutation rule this can be rewritten as,

By applying (1) and (2), we have,

so,

This proves the theorem.

Theorem 5-15:

Proof: I leave this as an exercise, though it is similar to theorem 5-14.

Difference

Another way to combine two sets is to list all elements of one set that are not members of the second set, thus forming a new set. This is called the difference of sets. Given the sets A and B we can write their difference symbolically,

From this definition we can derive the following theorems:

Theorem 5-16:

Proof: This is a direct consequence of (3) and the definition of the empty set, I leave the details as an exercise.

Theorem 5-17:

Proof: Apply (2) to (3) in the pattern of the hypothesis. Then apply (3) to the conclusion and show this is equivalent to the results of the hypothesis. I leave the details as an exercise.

Theorem 5-18:

Proof: Apply (2) to (3) in the pattern of the hypothesis. Then apply (3) to the conclusion and show this is equivalent to the results of the hypothesis. I leave the details as an exercise.

Theorem 5-19:

Proof: Apply (1) to (3) in the pattern of the hypothesis. Then apply (3) to the conclusion and show this is equivalent to the results of the hypothesis. I leave the details as an exercise.

Theorem 5-20:

Proof: Apply (1) to (3) in the pattern of the hypothesis. Then apply (3) to the conclusion and show this is equivalent to the results of the hypothesis. I leave the details as an exercise.

Theorem 5-21:

Proof: Apply (2) to (3) in the pattern of the hypothesis. I leave the details as an exercise.

Theorem 5-22:

Proof: Apply (2) to (3) in the pattern of the hypothesis. I leave the details as an exercise.

Theorem 5-23:

Proof: By applying both (1) and (3) the hypothesis can be rewritten . This allows us to use the principle of distributivity (see "The Proof is in the...") to rewrite it again as,

Another way of writing is . We can apply one of De Morgan's laws to rewrite this . So we now have . Applying this result to (4) gives us  . Using (3) we can write this  . Using (2) we can write . So the hypothesis leads to the conclusion, the theorem is proved.

Theorem 5-24:

Proof: This can be similarly to Theorem 5-23, I leave the details as an exercise.

Symmetric Difference

The final way to combine sets that we will consider in this column is to list all elements of two sets that are not common to both, thus forming a new set. This is called the symmetric difference of sets. Given the sets A and B we can write their difference symbolically,

From this definition we can derive the following theorems:

Theorem 5-25:

Proof: This is a direct consequence of (5) and the definition of the empty set, I leave the details as an exercise.

Theorem 5-26:

Proof: This is a direct consequence of (5), I leave the details as an exercise.

Theorem 5-27:

Proof: Apply (5) to the principle of associativity (see "The Proof is in the..."), I leave the details as an exercise.

Theorem 5-28:

Proof: Apply (2) to (5) and use the principle of distributivity (see "The Proof is in the..."), I leave the details as an exercise.

Theorem 5-29:

Proof: Apply (3) and (5) to the definition of a subset. I leave the details as an exercise.

Theorem 5-30:

Proof: Apply (5) to the definitions of equivalence and the empty set. I leave the details as an exercise.

Theorem 5-31:

Proof: Apply (5) to the definition of equivalence. I leave the details as an exercise.

Suggested Practice Problems

1. Invent three pairs of sets. What is the union, the intersection, the difference, and the symmetric difference of each pair?
2. Provide proofs for and or all of the theorems not proved in detail.

Converted by Mathematica  (November 12, 2002)