Set operations

There are operations we can perform on sets, including union, intersection, difference, symmetric difference, complementation, and Cartesian (or cross) product.

Euler diagrams

Because they are commonly used and very handy, we鈥檒l include some Euler diagrams here. An Euler diagram (named after the great mathematician Leonhard Euler, 1707鈥�1783) is used to show sets and their relations. Euler diagrams show sets (usually as circles) within some 鈥渦niverse鈥� of possible sets (usually a box enclosing the diagram).

Let A be the set of all English words that start with the letter 鈥渢.鈥� That is,

A = \{w \: | \: w \text{ is an English word and } w \text{ begins with the letter ``t''}\}.

Here鈥檚 an Euler diagram, depicting A, letting \mathscr{U} denote the universe.

The interior of the circle representing A is shaded to indicate the region of interest鈥攊n this case, the region containing the elements of A.

What is \mathscr{U}? Sometimes, it鈥檚 clear from context鈥攂ut not always. For example, it could be all words in all written natural (human) languages. It could be all words in all written natural languages that use an alphabet. Here, it鈥檚 not entirely clear. However, as we will soon see, it鈥檚 important to know what the universe is.

Relations among sets

Sets can have different relations to one another: they may have some elements in common, all the elements of one set could be elements of another, they may have no elements in common.

Take, for instance, the set of all odd natural numbers and the set of all numbers that are a multiple of three. These two sets have many elements in common, and so we鈥檇 say their intersection is non-empty.

Subset relation

One set can be a subset of another, that is, given two sets A and B, if all the elements of B are also elements of A, we say B is a subset of A, and we write B \subseteq A.

A strict subset is simply the case where one set is a subset of the other and the two subsets are not equal. This can be written two ways: B \subset A or B \subsetneq A, where B \subseteq A and B \neq A. This notation varies by author. Here鈥檚 an example: the set of all English words that start with a 鈥渢鈥� and have exactly three letters. This is a strict subset of English words that start with a 鈥渢鈥�.

\begin{equation*} \begin{split} A = \{w \: | \: &w \text{ is an English word and } \\ &w \text{ begins with the letter ``t''}\}. \end{split} \end{equation*}

\begin{equation*} \begin{split} B = \{w \: | \: &w \text{ is an English word and } \\ &w \text{ begins with the letter ``t'' and } \\ &w \text{ has exactly three letters}\}. \end{split} \end{equation*}

Disjoint sets

If two sets have no elements in common we say they are disjoint. Here鈥檚 an example of two sets which are disjoint: A, the set of all Taylor Swift hits, and B, the set of all restaurants in Burlington, VT.

Clearly these two sets have no elements in common.

Now on to set operations where we will see different relations.

Complementation

The complement of some set A is the set of all things in the (relevant) universe that are not elements of A. We write this with an overline: \overline{A} (though some texts will use different notation: A', A^{c}, or some other wacky stuff).

\overline{A} = \{x \: | \: x \not\in A\}

Here鈥檚 the corresponding Euler diagram:

Notice that the shaded region is everything outside the circle representing the set A.

Understanding the universe is especially important when it comes to complementation. \overline{A} is the complement of A, that is, everything in the universe that鈥檚 not in A. But what is the universe here? Is the word 鈥渟ziv谩rv谩ny鈥� in \overline{A}? (This is the Hungarian word for 鈥渞ainbow.鈥�) Maybe. Maybe not. It might be the case that our universe consists only of English words, in which case 鈥渟ziv谩rv谩ny鈥� would not be in \overline{A}. A different universe might consist of all words written using a Latin-derived alphabet, in which case 鈥渟ziv谩rv谩ny鈥� would be in \overline{A}. Maybe the universe is the set of all strings of Unicode symbols of arbitrary length. In this case, 鈥渟ziv谩rv谩ny鈥� would be in \overline{A} but so would 鈥溹磳峄�岜羔幋釕メ摰啜�茊鈥�. Moreover, because the lexicons of languages are finite, if the universe were all words written using a Latin-derived alphabet, then A and \overline{A} would both be finite sets. But if the universe were the set of all strings of Unicode symbols of arbitrary (and thus unbounded) length, then \overline{A} would be an infinite set. So you see, understanding the universe is important!

Difference

Set difference is analogous to subtraction. A \setminus B is all the elements of A that are not in B. That is,

A \setminus B = \{x \: | \: x \in A \text{ and } x \not \in B \}.

Note: This is sometimes written A - B. Same thing.

Here, let A be the set of all street-legal vehicles (VT regulations), and let B be the set of all objects which weigh less than 4,000 lb. The set difference, excluding elements of A which are also in B, gets us the following:

Union

The union of two sets A and B is the set of all elements in either A or B (or both). We write

A \cup B = \{x \: | \: x \in A \text{ or } x \in B\}.

When we say 鈥渙r鈥� here we mean x \in A or x \in B or possibly an element of both.

What is A \cup \emptyset? The empty set is the identity element for the union operation, so

A \cup \emptyset = A.

This is because the empty set contains no elements, and thus can add nothing to the union.

We can take the union of more than two sets, and we may notate this with a big cup. For example,

A_1 \cup A_2 \cup \ldots \cup A_n = \bigcup\limits_{i = 1}^n A_i

for an indexed family of sets, or sometimes

\bigcup\limits_{A \in S} A

for some set of sets, S. For example, if we have the sets A_1 = \{1, 2, 3\}, A_2 = \{4, 5, 6\}, A_3 = \{7, 8, 9\}, then

\bigcup\limits_{i = 1}^n A_i = A_1 \cup A_2 \cup A_3 = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}.

Set union is commonly represented as an Euler diagram, thus:

Notice that the shaded region includes all elements of A and all elements of B.

Intersection

The intersection of two sets, A and B, includes only those elements in A which are also in B (and vice versa).

A \cap B = \{x \: | \: x \in A \text{ and } x \in B\}.

Here, let A be all things that would be yucky (or dangerous) to eat, and let B be the set of all things that are red (or mostly red, anyway).

(Now you know how I feel about beets.)

Note: If A and B have no elements in common then A \cap B = \emptyset. If this is the case, we say that A and B are disjoint.

As with union, we can take the intersection of more than two sets, and we may notate this with a big cap. For example,

A_1 \cap A_2 \cup \ldots \cup A_n = \bigcap\limits_{i = 1}^n A_i

for an indexed family of sets, or sometimes

\bigcap\limits_{A \in S} A

for some set of sets, S. For example, if we have the sets A_1 = \{1, 2, 3\}, A_2 = \{2, 3, 4\}, A_3 = \{2, 4, 6\}, then

\bigcap\limits_{i = 1}^n A_i = A_1 \cap A_2 \cap A_3 = \{2\}.

Symmetric difference

Symmetric difference of two sets, A and B, consists of all the elements that are either in A or in B, but not in both. This is analogous to the exclusive or in logic: XOR.

Unlike union and intersection, there is no standard symbol for symmetric difference. It is variously notated \Delta, \oplus, and several other symbols. I favor \oplus, since it is reminiscent of XOR, which is closely related to symmetric difference. I鈥檓 grudgingly OK with \Delta, and it is used in some very fine textbooks on set theory. (If you鈥檙e curious, you鈥檒l have to look up the other symbols yourself, but don鈥檛 say I didn鈥檛 warn you!)

We can find the symmetric difference by taking the union of the differences between A and B

A \oplus B = (A \setminus B) \cup (B \setminus A)

or, we subtract the intersection from the union

A \oplus B = (A \cup B) \setminus (A \cap B).

Cartesian product

The Cartesian product (or cross-product) of two sets, A and B, is the set of all ordered pairs (2-tuples), the first element of which is an element of A and the second of which is an element of B.

The Cartesian product, written A \times B, is

A \times B = \{(a, b) \: | \: a \in A, b \in B\}.

For example, let A = \{\text{S}, \text{M}, \text{L}\} and let B = \{\text{pink}, \text{blue}, \text{grey}\}. Then, the Cartesian product is

\begin{equation*} \begin{split} A \times B = \{&(\text{S}, \text{pink}), (\text{S}, \text{blue}), (\text{S}, \text{grey}), \\ &(\text{M}, \text{pink}), (\text{M}, \text{blue}), (\text{M}, \text{grey}), \\ &(\text{L}, \text{pink}), (\text{L}, \text{blue}), (\text{L}, \text{grey})\}. \end{split} \end{equation*}

There are a few things of note here. First, the Cartesian product is a set鈥攁 set containing tuples. Second, the Cartesian product is all possible ordered combinations of size (S, M, L) and color (pink, blue, grey).

The cardinality of the Cartesian product of two sets, A and B, is the product of the cardinality of the two sets. That is,

\lvert A \times B \rvert = \lvert A \rvert \times \lvert B \rvert.

In the example above, this gives us 3 \times 3 = 9 and if you check, you鈥檒l see there are indeed nine ordered pairs in the Cartesian product.

Notice that the Cartesian product is not commutative because the resulting tuples are ordered. Were we to take the product B \times A, that would get us

\begin{equation*} \begin{split} B \times A = \{&(\text{pink}, \text{S}), (\text{blue}, \text{S}), (\text{grey}, \text{S}), \\ &(\text{pink}, \text{M}), (\text{blue}, \text{M}), (\text{grey}, \text{M}), \\ &(\text{pink}, \text{L}), (\text{blue}, \text{L}), (\text{grey}, \text{L})\} \end{split} \end{equation*}

which is a different set!

We can take the Cartesian product of more than two sets. If we do so, the number of elements in each tuple of the result will equal the number of sets for which we鈥檙e taking the product. For example,

A \times B \times C = \{(a, b, c) \: | \: a \in A, b \in B, c \in C\}

resulting in a set of 3-tuples, and

A \times B \times C \times D = \{(a, b, c, d) \: | \: a \in A, b \in B, c \in C, d \in D\}

and so on.

Exercises

1. Given A = \{\text{cat}, \text{dog}, \text{goldfish}\} and B = \{\text{table}, \text{horse}, \text{dog}, \text{cat}\} evaluate the following:
   1. A \cup B
   2. A \cap B
   3. A \setminus B
   4. B \setminus A
   5. A \oplus B
   6. B \oplus A
   7. A \cup \emptyset
   8. A \cap \emptyset
   9. A \setminus \emptyset
   10. B \oplus \emptyset
   11. \emptyset \cap \emptyset

2. Let A, B be sets. Determine the set operation which corresponds to:
   1. all the elements which are in A and in B
   2. all the elements which are in A or in B
   3. all the elements which are not in A but are in B
   4. all the elements which are in A or in B but not in both
   5. all the elements which are not in B

3. Which of the following set operations are commutative?
   1. union
   2. intersection
   3. set difference
   4. symmetric difference
   5. Cartesian product

4. Let A = \{1, 2, 3\}, B = \{\text{a}, \text{b}\}\text{, and } C = \{\text{red}, \text{blue}, \text{green}\}. Which of the following are true?
   1. (\text{a}, 1) \in A \times B
   2. (\text{a}, 1) \in N \times A
   3. (3, \text{b}, \text{red}) \in A \times B \times C
   4. (2, \text{b}, \text{green}) \subset A \times B \times C
   5. \{(2, \text{b}, \text{green})\} \subset A \times B \times C
   6. (2, \text{b}, \text{blue}) \in C \times B \times A
   7. (2, \text{c}, \text{blue}) \in A \times B \times C
   8. \lvert A \times B \rvert = 9
   9. \lvert A \times B \times C \rvert = 27
   10. (3, \text{b}) \in A \times B \times C
   11. \emptyset \subset B \times C

5. A French deck of playing cards (excluding jokers) is a Cartesian product. Consider any card in the deck. Say we have the queen of hearts. You can think of this as a tuple (\text{queen}, \text{heart}).
   1. What are the two sets in the product that generates all the cards in a French deck?
   2. What are the cardinalities of these sets?
   3. What is the cardinality of a French deck?

6. Let A, B be sets. Which of the following are true?
   1. If x \in A \times B then x \in B \times A
   2. If x \in A \oplus B then x \not \in \overline{A \cap B}
   3. If x \in (A \cap B) \setminus B then x \in A \cup \overline{B}

7. Let A, B be sets. Prove that (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B).

Copyright 漏 2024鈥�2025 Clayton Cafiero