Set operations

We may construct a new set by combining existing sets through set operations. Thus, sets equipped with set operations form an algebra of sets, so to speak. We will see set operations are closely related to logical operations.

Definition (union of sets)

Let \(A\) and \(B\) be sets. Then, their union, denoted \(A \cup B\), is defined as

\[A\cup B = \{x | x \in A \lor x \in B\}.\]

That is, \(A \cup B\) is a set consisting of elements that are in \(A\) or in \(B\).

Remark: "\(x \in A\)" and "\(x \in B\)" are logical propositions (predicates).

Example: If \(A = \{1, 2, 3\}\) and \(B = \{1, 3, 5\}\), then \(A \cup B = \{1, 2, 3, 5\}\).

Definition (intersection of sets)

Let \(A\) and \(B\) be sets. Then, their intersection, denoted \(A \cap B\), is defined as

\[A\cap B = \{x | x \in A \land x \in B\}.\]

That is, \(A \cap B\) is a set consisting of elements that are in \(A\) and in \(B\).

Remark: The logical "and" (i.e., conjunction) is often written as a comma (",") so that the above definition is often written as 

\[A\cap B = \{x | x \in A, x \in B\}.\]

Example: If \(A = \{1, 2, 3\}\) and \(B = \{1, 3, 5\}\), then \(A \cap B = \{1, 3\}\).

Definition (disjoint sets)

The two sets \(A\) and \(B\) are said to be disjoint if \(A \cap B = \emptyset\).

We know that addition and multiplication of real numbers are commutative. That is, for any \(x, y\in\mathbb{R}\), we have

\[x + y = y + x\]

and

\[xy = yx.\]

Similarly, the set union and intersection are commutative:

Lemma

Let \(A\) and \(B\) be sets. Then,

\[\begin{eqnarray} A\cup B &=& B\cup A\\ A\cap B &=& B\cap A.\\ \end{eqnarray}\]

Proof. Let us prove this for the union. Suppose \(x \in A\cup B\). Then, by definition of union, \(x \in A \lor x \in B\). But this proposition is equivalent to \(x \in B \lor x\in A\). Again by the definition of union, this means that \(x \in B \cup A\). Therefore, \(A \cup B \subset B \cup A\). By reversing this argument, we can also show that \(B \cup A \subset A\cup B\). Therefore, \(A \cup B = B \cup A\). More concisely, we can say

\[A \cup B = \{x | x \in A \lor x \in B\} = \{x | x \in B \lor x\in A\} = B \cup A.\]

The proof for the intersection is left as an exercise. ■

We also know that the addition and multiplication of real numbers are associative. That is, for any \(x, y, z \in \mathbb{R}\), we have

\[x + (y + z) = (x + y) + z\]

and

\[x(yz) = (xy)z.\]

This means that, if we first add \(y\) and \(z\), and then add \(x\), the result is the same as if we first add \(x\) and \(y\), and then add \(z\) (similar for the multiplication). The associativity also holds for set union and intersection.

Lemma

Let \(A, B,\) and \(C\) be sets. Then,

\[\begin{eqnarray} A \cup (B \cup C) &=& (A\cup B) \cup C,\\ A \cap (B \cap C) &=& (A \cap B)\cap C. \end{eqnarray}\]

Proof. Exercise. ■

For ordinary numbers, we have the distributive law. That is, for any \(x, y, z\in \mathbb{R}\), we have \[x(y + z) = xy + xz.\]

Similar, but different, laws apply to set union and intersection.

Lemma

For any sets \(A, B,\) and \(C\), we have \[\begin{eqnarray} A \cap (B \cup C) &=& (A\cap B) \cup (A \cap C),\\ A \cup (B \cap C) &=& (A\cup B) \cap (A \cup C). \end{eqnarray}\]

Proof. Exercise. ■

Note that both the union and intersection distribute over one another. In contrast, addition does not distribute over multiplication: \[x + (y\cdot z) \neq (x+y)\cdot(x+z).\]

In ordinary numbers, the number 0 (zero) plays a special role. For any \(x \in \mathbb{R}\), we have \[\begin{eqnarray} x + 0 &=& x,\\ x\cdot 0 &=& 0.\end{eqnarray}\] In sets, the empty set \(\emptyset\) plays a similar role.

Lemma

For any set \(A\), we have \[ \begin{eqnarray} A \cup \emptyset &=& A,\\ A \cap \emptyset &=& \emptyset.\end{eqnarray}\]

Proof.  Noting that \(x \in \emptyset\) is always false, \(x \in A \lor x\in\emptyset\) is true if and only if \(x \in A\) is true (if in doubt, write down the truth table). Thus,

\[A \cup \emptyset = \{x | x \in A \lor x \in \emptyset\} =\{x | x \in A\} = A.\]

The other equality is an exercise. ■

Definition (Set difference)

Let \(A\) and \(B\) be sets. The set difference, denoted \(A \setminus B\), is defined as

\[A\setminus B = \{x | x \in A \land x\not\in B\}.\]

Note that \(x \not\in B\) may be also written as \(\lnot (x \in B).\) 

Lemma

\(A \setminus B\) and \(B \setminus A\) are disjoint. That is,

\[(A \setminus B) \cap (B \setminus A) = \emptyset.\]

Proof. Exercise. Hint: \(x \not\in B\) may be also written as \(\lnot (x \in B)\).  ■

It is often convenient to consider a universal set (or universe), that is, the set of all things we ever want to consider, as long as it makes sense. In other words, everything we consider in mathematics is (supposed to be) an element of that universal set. If \(U\) is a universal set, then, by definition, \(x \in U\) is always true for any \(x\).

Definition (Set complement)

Let \(U\) be a universal set. For any set \(A\), its complement, denoted \(A^c\), is defined as \[A^c = U\setminus A.\]

Remark: Some people have different notations for the set complement: instead of \(A^c\), we may use \(A'\) or \(\bar{A}\), or something else.

Lemma

For any set \(A\), we have \[(A^c)^c = A.\]

That is, the complement of the complement of \(A\) is \(A\) itself.

Proof. By definition, \[A^c = \{x | x \in U \land \lnot(x \in A)\}\] and

\[(A^c)^c = \{x | x \in U \land \lnot (x \in A^c)\}.\]

Since \(x \in A^c \equiv x \in U \land \lnot (x \in A)\) (equivalence), we have

\[\begin{eqnarray} \lnot (x \in A^c) &\equiv& \lnot(x \in U \land \lnot (x \in A))\\ &\equiv&\lnot(x \in U) \lor \lnot(\lnot (x \in A)) ~~ \text{(De Morgan's law for logical operations)}\\ &\equiv& \bot \lor x \in A\\ &\equiv& x \in A \end{eqnarray}\]

Thus, \[(A^c)^c = \{x | x \in U \land x \in A\} = \{x | x \in A\} = A \] because \(x \in U\) is always true (\(\top\)) by definition. ■

Lemma

Let \(U\) be a universal set and \(A\) be any set. Then,

\[\begin{eqnarray} A \cup A^c &=& U,\\ A\cap A^c &=& \emptyset.\end{eqnarray}\]

Proof. Exercise. ■

Theorem (De Morgan's laws (set version))

For any sets \(A\) and \(B\), we have \[ \begin{eqnarray} (A \cup B)^c &=& A^c\cap A^c,\\ (A \cap B)^c &=& A^c \cup B^c. \end{eqnarray}\]

Proof. Exercise. ■

Set of sets

A set can contain sets as its elements. For example,

\[\{1, 2, \emptyset, \{1\}, \{1, 2, 3\}\}\]

is a set. The set of all subsets of a set is called the power set.

Definition (Power set)

Let \(A\) be a set. The set of all subsets of \(A\) is called the power set of \(A\) and denoted \(P(A)\) or \(\mathbf{2}^A\). That is, \[P(A) = \{a \mid a \subset A\}.\]

Example. Let \(A = \{1, 2\}\). Then, \(P(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\).

Example. Let \(B = \{a, b, c\}\). Then, \(P(B) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{c, a\}, \{a, b, c\}\}\).

Exercise. What is \(P(\emptyset)\), the power set of the empty set?

Cartesian products and tuples

We can combine two or more sets to make another set.

Definition (Cartesian product)

Let \(A\) and \(B\) be sets. The Cartesian product of \(A\) and \(B\), denoted \(A\times B\), is the set defined as

\[A\times B = \{ (a, b) \mid a \in A, b \in B\}.\] That is, \(A\times B\) is the set of all ordered pairs \((a, b\), one from \(A\), the other from \(B\). (We may simply say "pairs" to mean ordered pairs.)

Example. Let \(A = \{1, 2\}\) and \(B = \{a, b\}\). Then, \(A\times B = \{(1, a), (1, b), (2, a), (2, b)\}\).  □

Note that \((a, b) \in A\times B\) does not imply \((b, a) \in A\times B\). The order matters! Let \((a, b), (c, d) \in A\times B\) be two (ordered) pairs. We say that two ordered pairs are equal, \((a, b) = (c, d)\) if and only if \(a = c\) and \(b = d\).

Since \(A\times B\) is a set, we can make a Cartesian product between \(A\times B\) and yet another set, say \(C\): \((A\times B) \times C\). That is,

\[(A\times B)\times C = \{((a,b), c) \mid (a,b) \in A\times B, c \in C\}.\] Note that this set is different from \(A \times (B\times C)\) as

\[A\times (B\times C) = \{(a, (b, c)) \mid A\in A, (b, c)\in B\times C\}.\]

Nevertheless, we may define them to be equal:

\[(A\times B)\times C \stackrel{\text{def.}}{=} A\times (B\times C).\]

More precisely, we regard the pairs \(((a_1, b_1), c_1) \in (A\times B)\times C\) and \((a_2, (b_2, c_2)) \in A\times (B\times C)\) as equal if and only if \(a_1 = a_2, b_1 = b_2,\) and \(c_1 = c_2\). 

Remark: We are actually defining a bijection \((A\times B)\times C \to A\times(B\times C)\) by \(((a,b),c) \mapsto (a,(b,c))\). If there exists a bijection between two sets, then these sets are said to be isomorphic. This means they are essentially identical. See the post on maps for some more details about bijections.

Accordingly, we omit the parenthesis:

\[A\times B \times C = (A\times B)\times C = A\times (B\times C).\]

So,

\[A\times B\times C = \{(a, b, c) \mid a\in A, b\in B, c\in C\}.\]

The elements of \(A\times B\times C\) are called (ordered) triples. 

More generally, let \(A_1, A_2, \cdots, A_n\) be sets, and we define

\[A_1\times A_2 \times \cdots \times A_n = \{(a_1, a_2, \cdots, a_n) \mid a_i \in A_i, i = 1, 2, \cdots, n\},\] the elements of which are called \(n\)-tuples, or simply tuples.

These \(A_1, \cdots, A_n\) can be the same set. In that case, we define the Cartesian power as 

\[A^n = \underbrace{A\times A\times \cdots \times A}_{\text{$n$ times}}.\]

For example, \(A\times A = A^2\), \(A\times A\times A = A^3\).