Section 4 – Unions and Intersections

We are now ready to discuss a couple of familiar set theoretic operations: unions and intersections. Given two sets and , it would be “nice” to have a set that contains all the elements that belong to at least one of or . In fact, it would be nicer to generalize this to a collection of sets instead of just two, though we must be careful about using words like “two”, “three” and so on, since we haven’t really defined what numbers are so far. We don’t want to run the risk of inadvertently introducing circularity in our arguments! Anyway, this brings us to the following axiom.

Axiom of unions: For every collection of sets, there exists a set that contains all the elements that belong to at least one set of the given collection.

In other words, for every collection , there exists a set such that if for some in , then . Now, the set may contain “extra” elements that may not belong to any in . This can be easily fixed by invoking the axiom of specification to form the set . This set is called the union of the collection of set. Its uniqueness is guaranteed by the axiom of extension.

Generally, if is a collection of sets, then the union is denoted by , or .

A quick look at a couple of simple facts.

1) , and

2) .

We finally arrive at the definition of the union of two sets, and . .

Below is a list of a few facts about unions of pairs:

• ,
• (commutativity),
• (associativity),
• (idempotence),
• if and only if .

Now, we define the intersection of two sets, and as follows.

.

Once again, a few facts about intersections of pairs (analogous to the ones involving unions):

• ,
• ,
• ,
• ,
• if and only if .

Also, if , then the sets and are called disjoint sets.

Two useful distributive laws involving unions and intersections:

• ,
• .

We prove the first one of the above. The proof of the second one is left as an exercise to the reader. The proof relies on the idea that we show each side is a subset of the other. So, suppose belongs to the left hand side; then and , which implies and or , which implies or , which implies ; hence belongs to the right hand side. This proves that the left hand side is a subset of the right hand side. A similar argument shows that the right hand side is a subset of the left hand side. And, we are done.

The operation of the intersection of sets from a collection, , is similar to that of the union of sets from . However, the definition will require that we prohibit from being empty, and we will see why in the next section. So, for each collection, , there exists a set such that if and only if for every in . To construct such a set , we choose any set in – this is possible because – and write .

Note that the above construction is only used to prove that exists. The existence of doesn’t depend on any arbitrary set in the collection . We can, in fact, write

.

The set is called the intersection of the collection of sets. The axiom of extension, once again, guarantees its uniqueness. The usual notation for such a set is or .

EXERCISE: if and only if .

SOLUTION: We first prove the “if” part. So, suppose . Now, if , then either or . In the first case, and , which implies and . In the second case, we again have (since ), which implies and . In either case, we have . Hence, is a subset of .

Similarly, if , then and . Now, if , then , which implies . And, if , then once again . Thus, in either case, . Hence, is a subset of . We, thus, proved . This concludes the proof of the “if” part.

Now, we prove the “only if” part. So, suppose . If , then belongs to the left hand side of the equality, which implies belongs to the right hand side. This implies (and .) Hence, . And, we are done.