Set Identities and Properties

Section 7.4 Set Identities and Properties

There are various relationships between sets and their various operations which are true regardless of the particular sets involved. You may recall that an equation which is universally true for any values of the variables is called an identity. Then, these are set identities.

Subsection 7.4.1 Basic Properties of Union and Intersection

Theorem 7.4.1.

Let \(A\) be a set, in a universal set \(U\text{.}\)

Identity laws, \(A \cup \emptyset = A\) and \(A \cap U = A\text{.}\)
Domination laws, \(A \cup U = U\) and \(A \cap \emptyset = \emptyset\text{.}\)
Idempotent laws, \(A \cup A = A\) and \(A \cap A = A\text{.}\)
Double complement law, \(\overline{\overline{A}} = A\text{.}\)

Subsection 7.4.2 Properties of Union and Intersection

Theorem 7.4.2.

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

Commutative property of union and intersection.
\begin{equation*} A \cup B = B \cup A \qquad \text{and} \qquad A \cap B = B \cap A \end{equation*}
Associative property of union and intersection.
\begin{equation*} A \cup (B \cup C) = (A \cup B) \cup C \qquad \text{and} \qquad A \cap (B \cap C) = (A \cap B) \cap C \end{equation*}

Intuitively, the commutative laws are true because they rely on the commutative law of disjunction and conjunction.

The associative law means that when writing a union of more than 2 sets, or an intersection of more than 2 sets (but not a mix of unions and intersections), omitting parentheses is justified.

Subsection 7.4.3 Distributive Property of Union and Intersection

Theorem 7.4.3.

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

Distributive property of union over intersection.
\begin{equation*} A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \end{equation*}
Distributive property of intersection over union.
\begin{equation*} A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \end{equation*}

Intuitively, the distributive laws are true because of the distributive law of disjunction over conjunction and conjunction over disjunction.

Proof.

First,

\begin{align*} x \in A \cup (B \cap C) \amp \equiv x \in A \lor x \in B \cap C\\ \amp \equiv x \in A \lor (x \in B \land x \in C)\\ \amp \equiv \brac{x \in A \lor x \in B} \land \brac{x \in A \lor x \in C} \amp\amp \text{by distributive property of disjunction over conjunction}\\ \amp \equiv \brac{x \in A \cup B} \land \brac{x \in A \cup C}\\ \amp \equiv x \in (A \cup B) \cap (A \cup C) \end{align*}

Then, similarly,

\begin{align*} x \in A \cap (B \cap C) \amp \equiv x \in A \land x \in B \cup C\\ \amp \equiv x \in A \land (x \in B \lor x \in C)\\ \amp \equiv \brac{x \in A \land x \in B} \lor \brac{x \in A \land x \in C} \amp\amp \text{by distributive property of disjunction over conjunction}\\ \amp \equiv \brac{x \in A \cap B} \lor \brac{x \in A \cap C}\\ \amp \equiv x \in (A \cap B) \cup (A \cap C) \end{align*}

Subsection 7.4.4 Union and Intersection Analogy to Addition and Multiplication

Unions and intersections have many similar properties to addition and multiplication, respectively. The similarities between union and addition are somewhat intuitive, since the union of two sets is somewhat like “adding” the elements of each set together. The intuition relating intersection and multiplication is less intuitive.

Recall that addition and multiplication are both associative and commutative, in that for any real numbers \(a, b, c\text{,}\) we have the identities \(a + b = b + a\text{,}\) \(ab = ba\text{,}\) \(a + (b + c) = (a + b) + c\text{,}\) and \(a(bc) = (ab)c\text{.}\)

Union and intersection both have these properties. For sets \(A, B, C\text{,}\) we have,

\begin{gather*} A \cup B = B \cup A \qquad \text{and} \qquad A \cap B = B \cap A\\ A \cup (B \cup C) = (A \cup B) \cup C \qquad \text{and} \qquad A \cap (B \cap C) = (A \cap B) \cap C \end{gather*}

Also, for distribution of multiplication over addition, we have \(a(b + c) = ab + ac\text{.}\) Similarly, for the “distribution” of intersection over union,

\begin{equation*} A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \end{equation*}

However, one warning is that for distribution union over intersection, we have,

\begin{equation*} A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \end{equation*}

The analogue would be \(a + bc = (a + b)(a + c)\text{,}\) which is not true in general.

Subsection 7.4.5 Other Basic Properties of Union and Intersection

There are other basic properties which relate union and intersection to subsets, and complements. Most of these are intuitive, and they follow almost directly from the definitions.

Theorem 7.4.4.

\(A \subseteq A \cup B\text{.}\) If \(x \in A\text{,}\) then \(x \in A \cup B\text{.}\)
\((A \cap B) \subseteq A\text{.}\) If \(x \in A \cap B\text{,}\) then \(x \in A\text{.}\)
If

Theorem 7.4.5.

If \(A \subseteq B\text{,}\) then \(A \cup B = B\text{,}\) and conversely.
If \(A \subseteq B\text{,}\) then \(A \cap B = A\text{,}\) and conversely.
Absorption laws, \(A \cup (A \cap B) = A\) and \(A \cap (A \cup B) = A\text{.}\)
Complement laws, \(A \cup \overline{A} = U\) and \(A \cap \overline{A} = \emptyset\text{.}\)

Subsection 7.4.6 Generalized Distributive Property

Theorem 7.4.6.

Let \(A, B_1, B_2, \dots, B_n\) be sets. Then,

Generalized distributive property of union over intersection.
\begin{equation*} A \cup (B_1 \cap B_2 \cap \cdots \cap B_n) = (A \cup B_1) \cap (A \cup B_2) \cap \cdots \cap (A \cup B_n) \end{equation*}
Generalized distributive property of intersection over union.
\begin{equation*} A \cap (B_1 \cup B_2 \cup \cdots \cup B_n) = (A \cap B_1) \cup (A \cap B_2) \cup \cdots \cup (A \cap B_n) \end{equation*}

Subsection 7.4.7 Venn Diagrams

Venn diagrams can be used to intuitively understand set identities, however, they can't be used to rigorously prove them.

Subsection 7.4.8 The Empty Set

Recall that the empty set is a set with no elements. In fact, there is only one such set, so it is called the empty set, and this is why it is denoted by a symbol, \(\emptyset\text{.}\)

First, the empty set is a subset of every set. That is,

Theorem 7.4.7.

If \(E\) is a set with no elements, and \(A\) is any set, then \(E \subseteq A\text{.}\)

Intuitively, this is because for the conclusion \(E \subseteq A\) to be true, this means that for all \(x\text{,}\) if \(x \in E\text{,}\) then \(x \in A\) (a universal conditional). However, \(E\) contains no elements, so this statement is vacuously true. The only way this statement could be false is if there existed an element in \(E\) which was not in \(A\text{.}\) Since \(E\) contains no element, no such element of this kind exists. More precisely, this can be proven by contradiction.

Proof.

By contradiction, suppose that \(E\) is a set with no elements, \(A\) is any set, and \(E \not\subseteq A\text{.}\) Then, there exists \(x \in E\) such that \(x \notin A\text{.}\) However, this contradicts the assumption that \(E\) has no elements. Thus, \(E \subseteq A\text{.}\)

Then, we can prove that the empty set is unique.

Theorem 7.4.8.

The empty set is unique. In other words, if \(E_1, E_2\) are two sets with no elements, then \(E_1 = E_2\text{.}\)

Proof.

Let \(E_1, E_2\) be sets with no elements. Then, since \(E_1\) has no elements, \(E_1 \subseteq E_2\text{.}\) Also, since \(E_2\) has no elements, \(E_2 \subseteq E_1\text{.}\) Combining these together, \(E_1 = E_2\text{.}\)

In summary,

Theorem 7.4.9.

The empty set is a subset of all other sets. In other words, for all sets \(A\text{,}\) \(\emptyset \subseteq A\text{.}\) Also, the empty set is a strict subset of every set, except for the empty set.

Then, to prove that a set is equal to the empty set, it is sufficient to prove that it has no elements. Typically, the easiest way to do this is by contradiction: suppose the set does have an element, and derive a contradiction.

Subsection 7.4.9 De Morgan's Laws

The definitions of union and intersection rely on the logical “or” and “and”. This means to define the set complement of a union or intersection requires negating these “or” or “and” statements. First, by definition,

\begin{align*} \overline{A \cup B} \amp = \set{x: x \notin A \cup B}\\ \overline{A \cap B} \amp = \set{x: x \notin A \cap B} \end{align*}

Theorem 7.4.10. De Morgan's laws.

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

\begin{equation*} \overline{A \cap B} = \overline{A} \cup \overline{B} \qquad \text{and} \qquad \overline{A \cup B} = \overline{A} \cap \overline{B} \end{equation*}

In other words,

\(x \notin A \cup B\) if and only if \(x \notin A\) and \(x \notin B\text{.}\)
\(x \notin A \cap B\) if and only if \(x \notin A\) or \(x \notin B\)

Again, recall De Morgan's laws,

\begin{equation*} \neg (P \land Q) \equiv (\neg P) \lor (\neg Q) \qquad \text{and} \qquad \neg (P \lor Q) \equiv (\neg P) \land (\neg Q) \end{equation*}

Proof.

First, consider \(\overline{A \cup B}\text{.}\)

\begin{align*} x \in \overline{A \cup B} \equiv x \notin A \cup B \amp \equiv \neg (x \in A \cup B)\\ \amp \equiv \neg (x \in A \lor x \in B)\\ \amp \equiv \brac{\neg (x \in A) \land \neg (x \in B)} \amp\amp \text{by De Morgan's laws}\\ \amp \equiv \brac{x \notin A \land x \notin B}\\ \amp \equiv \brac{x \in \overline{A} \land x \in \overline{B}}\\ \amp \equiv \brac{x \in \overline{A} \cap \overline{B}} \end{align*}

Similarly, for \(\overline{A \cap B}\text{,}\) the steps are similar, except replacing “and” with “or”,

\begin{align*} x \in \overline{A \cap B} \equiv x \notin A \cap B \amp \equiv \neg (x \in A \cap B)\\ \amp \equiv \neg (x \in A \land x \in B)\\ \amp \equiv \brac{\neg (x \in A) \lor \neg (x \in B)} \amp\amp \text{by De Morgan's laws}\\ \amp \equiv \brac{x \notin A \lor x \notin B}\\ \amp \equiv \brac{x \in \overline{A} \lor x \in \overline{B}}\\ \amp \equiv \brac{x \in \overline{A} \cup \overline{B}} \end{align*}