We have briefly described some aspects of set equality when we first introduced what sets were. We talked about how repetition and order are irrelevant with respect to what elements are contained within a set. As such, even if some elements are repeated in various elements, they still represent the same set.

However, as we have also seen, there are a wide variety of methods to describe a set and what elements are contained within. Just because we come up with different descriptions, that does not necessarily mean we are describing different sets, but sometimes we may be describing exactly the same set.

However, defining set equality by having the same elements is not exactly rigorous. Two sets can share some number of elements, while also having different elements. As such, we don’t define set equality by simply having the same elements. Instead, we look to the end of Example 3.5.1 for inspiration.

This definition is precise because we can determine if a set is a subset of another set under scrutiny. As such, because the definition of set equality requires we show two things to be true, proofs showing two sets to be equal are usually broken up into two parts.

It’s this definition of set equality that makes the next two theorems somewhat straight-forward to prove.

Thus, by Theorem 3.5.1, whenever we know that A ⊆ B, we can replace A ∩ B with just A anytime we see A ⊆ B in an equation.It’s worth stressing that we can only make such a replacement when we know A ⊆ B. Otherwise, doing so may not be correct.

There are a few more such equalities we can make use of, which we now show in the next theorem.

Because of Theorem 3.5.2, whenever we know one of

are true, we automatically know that the other 3 are true as well.

The total opposite of two sets A and B being equal, is when A and B have absolutely no elements in common. Of course, if two sets share no element in common, then their intersection is a set that has no elements in it, which is just the empty set.

Many of the concepts discussed so far may seem disparate. However, they are more connected than may initially appear.

Theorem 3.5.3 connects the concepts of equal sets, disjoint sets, unions, and symmetric differences.

Remember that

x ∈ A

is a statement about x being a member of set A. Because it is a statement, it has a truth value of either 0 or 1.

One powerful tool we had at our disposal for analyzing logical expressions was a truth table. We can adapt truth tables to analyze set relationships as well. In this case, membership tables offer a tabular way of representing element arguments.

Instead of using some generic symbol for a generic object whose membership in some set we want to analyze, we could simply list whatever sets we’re analyzing. As such, we could rewrite the above table like so:

All of the set operations have their corresponding tables, which we can include inside one large table, like the one below:

In addition to the set operations, we can determine subset relationships. Let’s take a look at one more table to see some kind of example:

Notice that the columns

have all 1s. As such, we can write

which is exactly the definition of subset. As such, we can determine that a set A is a subset of some other set B by comparing their respective columns. If A has 1s in all rows where B has 1s, then we know that A ⊆ B.

Let’s prove a simple observation we may have had in our study of set relationships and operations.

Membership tables can be a convenient way to represent an element argument in tabular form. However, membership tables will not totally replace element arguments, as sometimes, the element argument is simpler to make for more esoteric situations where tables can be cumbersome to use.

We’ve already examined a number of some simple laws (referred to as theorems) above, and have demonstrated their truth by way of element arguments and membership tables. What’s demonstrated above only scratches the surface of the multitude of equal set relationships we can exploit. Below, we present a large table offering even more such laws.

As you look over this table, it would be wise to compare this table with the table presented in Chapter 1, Section 4. You should see many analogues.

Certainly, many more such laws and equivalencies exist, but the above table represents some of the more ubiquitous laws that are often used.

These laws present us an opportunity to directly compare three different proof techniques. First, we use a membership table.

Now, compare such a simple strategy with a standard element argument used in the next proof.

The last of these laws we’ll prove in this section will be the Distributive Laws. Instead of making two separate element arguments to establish that A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C) and (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C), we will use logical equivalencies to show that A ∪ (B ∩ C) and (A ∪ B) ∩ (A ∪ C) are subsets of each other simultaneously.

Of course, the rest of the Laws of Set Theory can be be proven in many different ways. Because it is a good exercise to provide a proof for all the above laws, proofs for the remaining laws are asked for in this chapter’s practice questions.

Just as we can use the Laws of Logic to simplify complicated logical expressions, we can also use the Laws of Set Theory to simplify complicated expressions involving sets.

We did make use of a fact (an additional law of Set Theory) where we can express the set difference operation using only intersection and complement:

Y – X = Y ∩ X^C.

We will now justify that equality:

As a matter of fact, we can also express the Symmetric Difference operation using only union, intersection, and complement operators as well, which we justify below:

This just goes to show how important the Union, Intersection, and Complement operations are when it comes to sets, because no matter how we want to combine any combination of sets, we can always do so using just those three operations.

We’ve seen DeMorgan’s Laws applied to two sets at a time. Let’s see what happens when we have three sets at a time:

It stands to reason that repeated applications of DeMorgan’s Laws would work for intersection as well.

Furthermore, no matter how many sets we have, it seems as if we can just repeatedly apply DeMorgan’s Laws and the Associative Law. Based on this observation, we make the following observations:

Figure 3.5.4: Above are depicted the generalized versions of DeMorgan’s Laws. In (a), we see the general version of taking the complement of a multiple union. In (b), we see a general version of taking the complement of a multiple intersection.

In Figure 3.5.4, I is an index set over which the multiple union or intersection is taken.

Of course, mere intuition doesn’t prove anything to be true. Instead, we must rely on rigorous tools, such as element arguments and logical equivalencies, to establish truth without any doubt.

Theorem 3.5.8

For a universal set 𝒰 and index set I, the following equalities hold:

Proof

General Strategy: we’ll make use of various definitions of Set Theory, including Complement. We also make use of the logical rules that apply when negating quantified statements as discussed in Chapter 1, Section 9.

We’ve just shown why the equivalence in (a) is true. By similar logic, part (b) is also shown to be true. This establishes both equivalencies as desired.

The generalized versions of DeMorgan’s Laws will prove extremely useful in our further study of math.