4.2. The Boolean Algebra of Sets

It is clear that set theory is closely related to logic. The intersection and union of sets can be defined in terms of the logical ‘and’ and logical ‘or’ operators. The notation \(\{x| P(x)\}\) makes it possible to use predicates to specify sets. And if \(A\) is any set, then the formula \(x\in A\) defines a one place predicate that is true for an entity \(x\) if and only if \(x\) is a member of \(A\). So it should not be a surprise that many of the rules of logic have analogues in set theory.

For example, we have already noted that \(\cup\) and \(\cap\) are commutative operations. This fact can be verified using the rules of logic. Let \(A\) and \(B\) be sets. According to the definition of equality of sets, we can show that \(A\cup B=B\cup A\) by showing that \(\forall x\,\big((x\in A\cup B)\leftrightarrow(x\in B\cup A)\big)\). But for any \(x\),

\[\begin{split}\begin{align*} x\in A\cup B &\leftrightarrow x\in A \vee x\in B &&\text{(definition of $\cup$)}\\ &\leftrightarrow x\in B \vee x\in A &&\text{(commutativity of $\vee$)}\\ &\leftrightarrow x\in B \cup A &&\text{(definition of $\cup$)} \end{align*}\end{split}\]

The commutativity of \(\cap\) follows in the same way from the definition of \(\cap\) in terms of \(\wedge\) and the commutativity of \(\wedge\), and a similar argument shows that union and intersection are associative operations.

The distributive laws for propositional logic give rise to two similar rules in set theory. Let \(A\), \(B\), and \(C\) be any sets. Then

\[\begin{split}\begin{align*} A\cup(B\cap C)&=(A\cup B)\cap(A\cup C)\\ \text{ and }\\ A\cap(B\cup C)&=(A\cap B)\cup(A\cap C) \end{align*}\end{split}\]

These rules are called the distributive laws for set theory. To verify the first of these laws, we just have to note that for any \(x\),

\[\begin{split}\begin{align*} x\in A&\cup(B\cap C) \\ &\leftrightarrow (x\in A)\vee((x\in B)\wedge (x\in C)) &&\text{(definition of $\cup$, $\cap$)}\\ &\leftrightarrow ((x\in A)\vee(x\in B)) \wedge((x \in A)\vee (x\in C)) &&\text{(distributivity of $\vee$)}\\ &\leftrightarrow (x\in A\cup B) \wedge (x \in A\cup C) &&\text{(definition of $\cup$)}\\ &\leftrightarrow x\in ((A\cup B)\cap(A\cup C)) &&\text{(definition of $\cap$)} \end{align*}\end{split}\]

The second distributive law for sets follows in exactly the same way.

4.2.1. Set complement

While \(\cup\) is analogous to \(\vee\) and \(\cap\) is analogous to \(\wedge\), we have not yet seen any operation in set theory that is analogous to the logical ‘not’ operator, \(\lnot\). Given a set \(A\), it is tempting to try to define \(\{x| \lnot(x\in A)\}\), the set that contains everything that does not belong to \(A\). Unfortunately, the rules of set theory do not allow us to define such a set. The notation \(\{x| P(x)\}\) can only be used when the domain of discourse of \(P\) is a set, so there must be an underlying set from which the elements that are/are not in \(A\) are chosen, i.e., some underlying set of which \(A\) is a subset. We can get around this problem by restricting the discussion to subsets of some fixed set. This set will be known as the universal set. Keep in mind that the universal set is only universal for some particular discussion. It is simply some set that is large enough to contain all the sets under discussion as subsets. Given a universal set \(U\) and any subset \(A\) of \(U\), we can define the set \(\{x\in U| \lnot(x\in A)\}\).

Definition 4.1

Let \(U\) be a given universal set, and let \(A\) be any subset of \(U\). We define the complement of \(A\) in \(U\) to be the set \(\overline{A}\) that is defined by \(\overline{A}=\{x\in U| x\not\in A\}\).

Usually, we will refer to the complement of \(A\) in \(U\) simply as the complement of \(A\), but you should remember that whenever complements of sets are used, there must be some universal set in the background. Other textbooks may use \(A^c\) to denote the complement of \(A\) instead.

Given the complement operation on sets, we can look for analogues to the rules of logic that involve negation. For example, we know that \(p\wedge\lnot p=\mathbb{F}\) for any proposition \(p\). It follows that for any subset \(A\) of \(U\),

\[\begin{split}\begin{align*} A\cap\overline{A} &= \{x\in U| (x\in A)\wedge (x\in \overline{A})\} &&\text{(definition of $\cap$)}\\ &= \{x\in U| (x\in A)\wedge (x\not\in A)\} &&\text{(definition of complement)}\\ &= \{x\in U| (x\in A)\wedge \lnot(x\in A)\} &&\text{(definition of $\not\in$)}\\ &= \emptyset \end{align*}\end{split}\]

the last equality following because the proposition \((x\in A)\wedge \lnot(x\in A)\) is false for any \(x\). Similarly, we can show that \(A\cup\overline{A}=U\) and that \(\overline{\overline{A}}=A\) (where \(\overline{\overline{A}}\) is the complement of the complement of \(A\), that is, the set obtained by taking the complement of \(\overline{A}\).)

The most important laws for working with complements of sets are DeMorgan’s Laws for sets. These laws, which follow directly from DeMorgan’s Laws for logic, state that for any subsets \(A\) and \(B\) of a universal set \(U\),

\[\begin{split}\begin{align*} \overline{A\cup B}&=\overline{A}\cap\overline{B}\\ \text{ and }\\ \overline{A\cap B}&=\overline{A}\cup\overline{B} \end{align*}\end{split}\]

For example, we can verify the first of these laws with the calculation

\[\begin{split}\begin{align*} \overline{A\cup B}&= \{x\in U| x \not\in (A\cup B)\} &&\text{(definition of complement)}\\ &= \{x\in U| \lnot( x\in A\cup B)\} &&\text{(definition of $\not\in$)}\\ &= \{x\in U| \lnot(x\in A \vee x\in B)\} &&\text{(definition of $\cup$)}\\ &= \{x\in U| (\lnot(x\in A))\wedge(\lnot(x\in B))\} &&\text{(DeMorgan's Law for logic)}\\ &= \{x\in U| (x\not\in A) \wedge (x\not\in B)\} &&\text{(definition of $\not\in$)}\\ &= \{x\in U| (x\in\overline{A}) \wedge (x\in\overline{B})\} &&\text{(definition of complement)}\\ &= \overline{A}\cap\overline{B} &&\text{(definition of $\cap$)} \end{align*}\end{split}\]

Table 4.2 Some Laws of Boolean Algebra for sets. \(A\), \(B\), and \(C\) are sets. For the laws that involve the complement operator, they are assumed to be subsets of some universal set, \(U\). For the most part, these laws correspond directly to laws of Boolean Algebra for propositional logic as given in this table.

Double complement	\(\overline{\overline{A}}=A\)
Miscellaneous laws	\(A\cup\overline{A}=U\)
	\(A\cap\overline{A}=\emptyset\)
	\(\emptyset\cup A=A\)
	\(\emptyset\cap A=\emptyset\)
Idempotent laws	\(A\cap A= A\)
	\(A\cup A= A\)
Commutative laws	\(A\cap B = B\cap A\)
	\(A\cup B=B\cup A\)
Associative laws	\(A\cap (B\cap C) = (A\cap B)\cap C\)
	\(A\cup (B\cup C) = (A\cup B)\cup C\)
Distributive laws	\(A\cap(B\cup C) = (A\cap B)\cup (A\cap C)\)
	\(A\cup (B\cap C) = (A\cup B)\cap (A\cup C)\)
DeMorgan’s laws	\(\overline{A\cap B} = \overline{A}\cup\overline{B}\)
	\(\overline{A\cup B} = \overline{A}\cap\overline{B}\)

An easy inductive proof can be used to verify generalized versions of DeMorgan’s Laws for set theory.
(In this context, all sets are assumed to be subsets of some unnamed universal set.) A simple calculation verifies DeMorgan’s Law for three sets:

\[\begin{split}\begin{align*} \overline{A\cup B\cup C}&=\overline{(A\cup B)\cup C}\\ &=\overline{(A\cup B)}\cap\overline{C} &\text{(by DeMorgan's Law for two sets)}\\ &=(\overline{A}\cap\overline{B})\cap\overline{C} &\text{(by DeMorgan's Law for two sets)}\\ &=\overline{A}\cap\overline{B}\cap\overline{C} \end{align*}\end{split}\]

From there, we can derive similar laws for four sets, five sets, and so on. However, just saying ‘and so on’ is not a rigorous proof of this fact. Whereas we may have excused ourselves about that in Section 2, we can now prove this fact. Here is a rigorous inductive proof of a generalized DeMorgan’s Law:

Theorem 4.5

For any natural number \(n\geq 2\) and for any sets \(X_1\), \(X_2\), … , \(X_n\), \(\overline{X_1\cup X_2\cup \cdots \cup X_n} = \overline{X_1} \cap \overline{X_2} \cap\cdots\cap \overline{X_n}\)

Proof. We give a proof by induction. In the base case, \(n=2\), the statement is that \(\overline{X_1\cup X_2}=\overline{X_1}\cap\overline{X_2}\). This is true since it is just an application of DeMorgan’s law for two sets.

For the inductive case, suppose that the statement is true for \(n=k\). We want to show that it is true for \(n=k+1\). Let \(X_1\), \(X_2\), … , \(X_{k+1}\) be any \(k+1\) sets. Then we have:

\[\begin{split}\begin{align*} \overline{X_1\cup X_2\cup \cdots \cup X_{k+1}} &= \overline{(X_1\cup X_2\cup \cdots \cup X_k) \cup X_{k+1}}\\ &= \overline{(X_1\cup X_2\cup \cdots \cup X_k)}\cap\overline{X_{k+1}}\\ &= (\overline{X_1}\cap\overline{X_2}\cap\cdots\cap\overline{X_k})\cap\overline{X_{k+1}}\\ &= \overline{X_1}\cap\overline{X_2}\cap\cdots\cap\overline{X_{k+1}} \end{align*}\end{split}\]

In this computation, the second step follows by DeMorgan’s Law for two sets, while the third step follows from the induction hypothesis. Therefore by the principle of induction we have proven the theorem.

□

4.2.2. Link between logic and set theory

Fig. 4.3 The correspondence between set operators and propositional operators. Recreation of: commons.wikimedia.org/wiki/Template:Operations_and_relations_in_set_theory_and_logic

Just as the laws of logic allow us to do algebra with logical formulas, the laws of set theory allow us to do algebra with sets. Because of the close relationship between logic and set theory, their algebras are very similar. The algebra of sets, like the algebra of logic, is Boolean algebra. When George Boole wrote his 1854 book about logic, it was really as much about set theory as logic. In fact, Boole did not make a clear distinction between a predicate and the set of objects for which that predicate is true. His algebraic laws and formulas apply equally to both cases. More exactly, if we consider only subsets of some given universal set \(U\), then there is a direct correspondence between the basic symbols and operations of propositional logic and certain symbols and operations in set theory, as shown in this table:

Logic	Set Theory
\(\mathbb{T}\)	\(U\)
\(\mathbb{F}\)	\(\emptyset\)
\(p\wedge q\)	\(A\cap B\)
\(p\vee q\)	\(A\cup B\)
\(\lnot p\)	\(\overline{A}\)

Any valid logical formula or computation involving propositional variables and the symbols \(\mathbb{T}\), \(\mathbb{F}\), \(\wedge\), \(\vee\), and \(\lnot\) can be transformed into a valid formula or computation in set theory by replacing the propositions in the formula with subsets of \(U\) and replacing the logical symbols with \(U\), \(\emptyset\), \(\cap\), \(\cup\), and the complement operator. Fig. 4.3 illustrates.

Just as in logic, the operations of set theory can be combined to form complex expressions such as \((A\cup C)\cap\overline{(B\cup \overline{C} \cup D)}\). Parentheses can always be used in such expressions to specify the order in which the operations are to be performed. In the absence of parentheses, we need precedence rules to determine the order of operation. The precedence rules for the Boolean algebra of sets are carried over directly from the Boolean algebra of propositions. When union and intersection are used together without parentheses, intersection has precedence over union. Furthermore, when several operators of the same type are used without parentheses, then they are evaluated in order from left to right. (Of course, since \(\cup\) and \(\cap\) are both associative operations, it really doesn’t matter whether the order of evaluation is left-to-right or right-to-left.) For example, \(A\cup B\cap C \cup D\) is evaluated as \((A\cup(B\cap C))\cup D\). The complement operation is a special case. Since it is denoted by drawing a line over its operand, there is never any ambiguity about which part of a formula it applies to.

Warning

Unfortunately in hand-written work this is not always true. Make sure to write neatly and unambiguously when working with complements. Also note that, similarly to parentheses in propositional logic, although parentheses may not be necessary I strongly encourage you to add them them to improve readability of the order of operations.

The laws of set theory can be used to simplify complex expressions involving sets. (As usual, of course, the meaning of ‘simplification’ is partly in the eye of the beholder.) For example, for any sets \(X\) and \(Y\),

\[\begin{split}\begin{align*} (X\cup Y)\cap(Y\cup X)&=(X\cup Y)\cap(X\cup Y) &&\text{(Commutative Law)}\\ &=(X\cup Y) &&\text{(Idempotent Law)} \end{align*}\end{split}\]

where in the second step, the Idempotent Law, which says that \(A\cap A=A\), is applied with \(A=X\cup Y\). For expressions that use the complement operation, it is usually considered to be simpler to apply the operation to an individual set, as in \(\overline{A}\), rather than to a formula, as in \(\overline{A\cap B}\). DeMorgan’s Laws can always be used to simplify an expression in which the complement operation is applied to a formula. For example,

\[\begin{split}\begin{align*} A\cap \overline{B\cup\overline{A}} &= A\cap (\overline{B}\cap\overline{\overline{A}}) && \text{(DeMorgan's Law)}\\ &= A\cap (\overline{B}\cap A) && \text{(Double Complement)}\\ &= A\cap (A\cap\overline{B}) && \text{(Commutative Law)}\\ &= (A\cap A)\cap \overline{B}) && \text{(Associative Law)}\\ &= A \cap \overline{B} && \text{(Idempotent Law)} \end{align*}\end{split}\]

As a final example of the relationship between set theory and logic, consider the set-theoretical expression \(A\cap (A\cup B)\) and the corresponding compound proposition \(p\wedge(p\vee q)\). (These correspond since for any \(x\), \(x\in A\cap(A\cup B) \equiv (x\in A)\wedge ((x\in A)\vee (x\in B))\).) You might find it intuitively clear that \(A\cap(A\cup B)=A\). Formally, this follows from the fact that \(p\wedge(p\vee q)\equiv p\), which might be less intuitively clear and is surprising difficult to prove algebraically from the laws of logic. However, there is another way to check that a logical equivalence is valid: Make a truth table. Consider a truth table for \(p\wedge(p\vee q)\):

\(p\)	\(q\)	\(p\vee q\)	\(p\wedge (p\vee q)\)
0	0	0	0
0	1	1	0
1	0	1	1
1	1	1	1

The fact that the first column and the last column of this table are identical shows that \(p\wedge(p\vee q)\equiv p\). Taking \(p\) to be the proposition \(x\in A\) and \(q\) to be the proposition \(x\in B\), it follows that the sets \(A\) and \(A\cap (A\cup B)\) have the same members and therefore are equal.

Video

In one of the pencasts of the course, we describe how Venn diagrams can also be used as alternatives to truth tables based on an old exam question. You can find that pencast here: youtu.be/5xle5qfrh0k.

4.2.3. Exercises

Exercise (1†)

Use the laws of logic to verify the associative laws for union and intersection. That is, show that if \(A\), \(B\), and \(C\) are sets, then \(A\cup(B\cup C)= (A\cup B)\cup C\) and \(A\cap(B\cap C)= (A\cap B)\cap C\).

Exercise (2†)

Show that for any sets \(A\) and \(B\), \(A\subseteq A\cup B\) and \(A\cap B\subseteq A\).

Exercise (3†)

Recall that the symbol \(\oplus\) denotes the logical exclusive or operation. If \(A\) and \(B\) sets, define the set \(A\bigtriangleup B\) by \(A\bigtriangleup B = \{x| (x\in A)\oplus (x\in B)\}\). Show that \(A\bigtriangleup B = (A\smallsetminus B)\cup(B\smallsetminus A)\). (\(A\bigtriangleup B\) is known as the symmetric difference of \(A\) and \(B\).)

Exercise (4†)

Choose three non-empty sets \(A, B, C\). Draw a Venn diagram of \(A\bigtriangleup B\bigtriangleup C\).

Exercise (5†)

Let \(A\) be a subset of some given universal set \(U\). Verify that \(\overline{\overline{A}}=A\) and that \(A\cup\overline{A}=U\).

Exercise (6†)

Verify the second of DeMorgan’s Laws for sets, \(\overline{A\cap B}=\overline{A}\cup\overline{B}\). For each step in your verification, state why that step is valid.

Exercise (7†)

The subset operator, \(\subseteq\), is defined in terms of the logical implication operator, \(\rightarrow\). However, \(\subseteq\) differs from the \(\cap\) and \(\cup\) operators in that \(A\cap B\) and \(A\cup B\) are sets, while \(A\subseteq B\) is a statement. So the relationship between \(\subseteq\) and \(\rightarrow\) isn’t quite the same as the relationship between \(\cup\) and \(\vee\) or between \(\cap\) and \(\wedge\). Nevertheless, \(\subseteq\) and \(\rightarrow\) do share some similar properties. This problem shows one example.

1. Show that the following three compound propositions are logically equivalent: \(p\rightarrow q\), \((p\wedge q)\leftrightarrow p\), and \((p\vee q)\leftrightarrow q\).

2. Show that for any sets \(A\) and \(B\), the following three statements are equivalent: \(A\subseteq B\), \(A\cap B = A\), and \(A\cup B = B\).

Exercise (8†)

DeMorgan’s Laws apply to subsets of some given universal set \(U\). Show that for a subset \(X\) of \(U\), \(\overline{X}=U\smallsetminus X\). It follows that DeMorgan’s Laws can be written as \(U\smallsetminus(A\cup B)=(U\smallsetminus A)\cap(U\smallsetminus B)\) and \(U\smallsetminus(A\cap B)=(U\smallsetminus A)\cup(U\smallsetminus B)\). Show that these laws hold whether or not \(A\) and \(B\) are subsets of \(U\). That is, show that for any sets \(A\), \(B\), and \(C\), \(C\smallsetminus(A\cup B)=(C\smallsetminus A)\cap(C\smallsetminus B)\) and \(C\smallsetminus(A\cap B)=(C\smallsetminus A)\cup(C\smallsetminus B)\).

Exercise (9†)

Show that \(A\cup (A\cap B)= A\) for any sets \(A\) and \(B\).

Exercise (10†)

Let \(X\) and \(Y\) be sets. Simplify each of the following expressions. Justify each step in the simplification with one of the rules of set theory.

1. \(X\cup (Y\cup X)\)

2. \((X\cap Y) \cap \overline{X}\)

3. \((X\cup Y)\cap \overline{Y}\)

4. \((X\cup Y) \cup (X\cap Y)\)

Exercise (11†)

Let \(A\), \(B\), and \(C\) be sets. Simplify each of the following expressions. In your answer, the complement operator should only be applied to the individual sets \(A\), \(B\), and \(C\).

1. \(\overline{A\cup B \cup C}\)

2. \(\overline{A\cup (B \cap C)}\)

3. \(\overline{\overline{A\cup B}}\)

4. \(\overline{B\cap \overline{C}}\)

5. \(\overline{A\cap \overline{B\cap \overline C}}\)

6. \(A\cap \overline{A\cup B}\)

Exercise (12†)

Use induction to prove the following generalized DeMorgan’s Law for set theory: For any natural number \(n\geq 2\) and for any sets \(X_1\), \(X_2\), … , \(X_n\), \(\overline{X_1\cap X_2\cap \cdots \cap X_n} = \overline{X_1} \cup \overline{X_2} \cup\cdots\cup \overline{X_n}\)

Exercise (13†)

State and prove generalized distributive laws for set theory.