Calculus

Set Theory

Set Theory Logo

Set Identities

We now consider the basic set identities that relate the various set operations.

The sets \(A,\) \(B,\) \(C\) below are subsets of a universal set \(U.\)

Identity Laws

\[\require{AMSsymbols}{A \cup \varnothing = A,\;\;}\kern0pt{A \cap U = A}\]

Domination Laws

\[{A \cup U = U,\;\;}\kern0pt{A \cap \varnothing = \varnothing}\]

Idempotent Laws

\[{A \cup A = A,\;\;}\kern0pt{A \cap A = A}\]

Complement Laws

\[{A \cup {A^c} = U,\;\;}\kern0pt{A \cap {A^c} = \varnothing}\]

Double Complement Law

\[{\left( {{A^c}} \right)^c} = A\]

Commutative Laws

\[{A \cup B = B \cup A,\;\;}\kern0pt{A \cap B = B \cap A}\]

Associative Laws

\[{A \cup \left( {B \cup C} \right) = \left( {A \cup B} \right) \cup C,\;\;}\kern0pt{A \cap \left( {B \cap C} \right) = \left( {A \cap B} \right) \cap C}\]

Distributive Laws

\[{A \cup \left( {B \cap C} \right) = \left( {A \cup B} \right) \cap \left( {A \cup C} \right),\;\;}\kern0pt{A \cap \left( {B \cup C} \right) = \left( {A \cap B} \right) \cup \left( {A \cap C} \right)}\]

De Morgan’s Laws

\[{{\left( {A \cup B} \right)^c} = {A^c} \cap {B^c},\;\;}\kern0pt{{\left( {A \cap B} \right)^c} = {A^c} \cup {B^c}}\]

Absorption Laws

\[{A \cup \left( {A \cap B} \right) = A,\;\;}{A \cap \left( {A \cup B} \right) = A}\]

Complements of \(U\) and \(\varnothing\)

\[{{U^c} = \varnothing,\;\;}\kern0pt{{\varnothing^c} = U}\]

Set Difference Law

\[A \backslash B = A \cap {B^c}\]

There are different ways to prove set identities.

The basic method to prove a set identity is the element method or the method of double inclusion. It is based on the set equality definition: two sets \(A\) and \(B\) are said to be equal if \(A \subseteq B\) and \(B \subseteq A\). In this method, we need to prove that the left-hand side \(\left({LHS}\right)\) of a set identity is a subset of the right-hand side \(\left({RHS}\right)\) and vice versa.

Another way to prove is to use the basic algebraic identities considered above (the algebraic method). It is also worthwhile to mention methods based on the use of membership tables (similar to truth tables) and set builder notation.


Solved Problems

Click or tap a problem to see the solution.

Example 1

Prove the identity \(A\backslash B = A \backslash \left( {A \cap B} \right)\) using the element method.

Example 2

Prove the identity \(\left( {A\backslash B} \right) \cap C = \left( {A \cap C} \right)\backslash \left( {B \cap C} \right)\) using the element method.

Example 3

Show that \(A \cap \left( {{A^c} \cup B} \right) = A \cap B.\)

Example 4

Show that \(A \backslash \left( {B \cup C} \right) = \left( {A \backslash B} \right) \cap \left( {A \backslash C} \right).\)

Example 5

Show that \(\left( {A \cap B} \right) \cup \left( {A \cap {B^c}} \right) = A.\)

Example 6

Show that \(A \backslash B = A \,\triangle\, \left( {A \cap B} \right).\)

Example 7

Using a membership table, prove that \(A \cap \left( {B\backslash A} \right) = \varnothing.\)

Example 8

Using a membership table, prove that \(A \cup \left( {{A^c} \cap B} \right) = A \cup B.\)

Example 9

Prove the identity \(A \cup \left( {B\backslash A} \right) = A \cup B\) using set builder notation and logical equivalences.

Example 10

Prove the identity \(A\backslash \left( {A\backslash B} \right) = A \cap B\) using set builder notation and logical equivalences.

Example 1.

Prove the identity \(A\backslash B = A \backslash \left( {A \cap B} \right)\) using the element method.

Solution.

  1. We show that the left-hand side of the identity is a subset of the right side. Let’s take an arbitrary element \(x \in {A \backslash B}.\) By the set difference identity, we have \(x \in A \cap {B^c}.\) If \(x \in {B^c},\) then \(x \in {A^c} \cup {B^c}.\) Using De Morgan’s law, this means that \(x \in {\left( {A \cap B} \right)^c}.\) Thus, \(x \in A\) and \(x \in {\left( {A \cap B} \right)^c}.\) By the definition of set intersection, we have \(x \in A \cap {\left( {A \cap B} \right)^c}.\) Applying the set difference identity, we conclude that \(x \in A\backslash \left( {A \cap B} \right) = RHS.\)
  2. Consider now the right-hand side and show that it is a subset of the left side. Let \(x \in A\backslash \left( {A \cap B} \right).\) Using the set difference identity, we can write that \(x \in A \cap {\left( {A \cap B} \right)^c}.\) By De Morgan’s law, \({\left( {A \cap B} \right)^c} = {A^c} \cup {B^c}.\) Hence, \(x \in A \cap \left( {{A^c} \cup {B^c}} \right).\) Apply the distribution law: \(x \in \left( {A \cap {A^c}} \right) \cup \left( {A \cap {B^c}} \right).\) Here, \(A \cap {A^c} = \varnothing,\) by the complement law. Next, \(\varnothing \cup \left( {A \cap {B^c}} \right) = A \cap {B^c},\) by the commutative and identity laws. So, we see that \(x \in A \cap {B^c}.\) By the set difference identity, this means that \(x \in A\backslash B = LHS.\)
  3. This proves that \(A\backslash B = A\backslash \left( {A \cap B} \right).\)

Example 2.

Prove the identity \(\left( {A\backslash B} \right) \cap C = \left( {A \cap C} \right)\backslash \left( {B \cap C} \right)\) using the element method.

Solution.

  1. First we show that the left-hand side of the identity is a subset of the right side. Take an arbitrary element \(x \in \left( {A \backslash B} \right) \cap C.\) By definition of set intersection, \(x \in \left( {A \backslash B} \right)\) and \(x \in C.\) Using the definition of set difference, we conclude that \(x \in A,\) \(x \notin B,\) and \(x \in C.\) If \(x \in A\) and \(x \in C,\) then \(x \in \left( {A \cap C} \right)\) by definition of set intersection. If \(x \notin B,\) then \(x \in B^c,\) by definition of set complement. Using the definition of set union, we can extend the last statement and rewrite it as \(x \in \left({{B^c} \cup {C^c}}\right).\) Now we apply De Morgan’s law, which states that \(x \in \left({B \cap C}\right)^c.\) So, we have that \(x \in \left( {A \cap C} \right)\) and \(x \in \left({B \cap C}\right)^c.\) By definition of set intersection, we can write \(x \in \left( {A \cap C} \right) \cap {\left( {B \cap C} \right)^c}.\) Finally, using the set difference identity, we get \(x \in \left( {A \cap C} \right)\backslash \left( {B \cap C} \right),\) or \(x \in RHS.\)
  2. Similarly we prove that the right-hand side is a subset of the left side. Suppose that \(x \in \left( {A \cap C} \right) \backslash \left( {B \cap C} \right).\) Using the set difference identity we can write this as \(x \in \left( {A \cap C} \right) \cap {\left( {B \cap C} \right)^c}.\) Apply De Morgan’s law \({\left( {B \cap C} \right)^c} = {B^c} \cup {C^c}.\) This gives: \(x \in \left( {A \cap C} \right) \cap \left( {{B^c} \cup {C^c}} \right).\) By the distributive law, \(x \in \left( {\left( {A \cap C} \right) \cap {B^c}} \right)\) \(\cup \left( {\left( {A \cap C} \right) \cap {C^c}} \right).\) By the associative and commutative laws, \(x \in \left( {\left( {A \cap {B^c}} \right) \cap C} \right) \) \(\cup \left( {A \cap \left( {C \cap {C^c}} \right)} \right).\) Here \(C \cap {C^c} = \varnothing\) by the complement law, and \(A \cap \varnothing = \varnothing\) by the domination law. Hence, \(x \in \left( {\left( {A \cap {B^c}} \right) \cap C} \right) \cup \varnothing.\) So, \(x \in \left( {A \cap {B^c}} \right) \cap C\) (by the identity law). Using the set difference identity, we have \(x \in \left( {A\backslash B} \right) \cap C,\) or \(x \in LHS.\)
  3. This shows that \(\left( {A\backslash B} \right) \cap C = \left( {A \cap C} \right)\backslash \left( {B \cap C} \right).\)

Example 3.

Show that \(A \cap \left( {{A^c} \cup B} \right) = A \cap B.\)

Solution.

We prove algebraically that the left hand side \(\left({LHS}\right)\) is equal to the right-hand side \(\left({RHS}\right).\)

By distributive laws,

\[{LHS = A \cap \left( {{A^c} \cup B} \right) }={ \left( {A \cap {A^c}} \right) \cup \left( {A \cap B} \right).}\]

Now we apply the complement law \({A \cap {A^c} = \varnothing.}\) This yields:

\[{LHS = \varnothing \cup \left( {A \cap B} \right)}\]

Finally, we use the commutative law \(A \cup B = B \cup A\) and the identity law \({A \cup \varnothing = A}.\)

\[{LHS = \varnothing \cup \left( {A \cap B} \right) }={ \left( {A \cap B} \right) \cup \varnothing }={ A \cap B }={ RHS.}\]

Example 4.

Show that \(A \backslash \left( {B \cup C} \right) = \left( {A \backslash B} \right) \cap \left( {A \backslash C} \right).\)

Solution.

We prove this identity using the algebraic method. Consider the left-hand side \(\left({LHS}\right).\) By the set difference law, we can write it in the form

\[{LHS = A \backslash \left( {B \cup C} \right) }={ A \cap {\left( {B \cup C} \right)^c}.}\]

By De Morgan’s law, \({\left( {B \cup C} \right)^c} = {B^c} \cap {C^c}.\) Given that \(A = A \cap A\) (the idempotent law), and using the associative and commutative rules, we obtain

\[{LHS = A \cap \left( {{B^c} \cap {C^c}} \right) }={ \left( {A \cap A} \right) \cap \left( {{B^c} \cap {C^c}} \right) }={ A \cap A \cap {B^c} \cap {C^c} }={ \left( {A \cap {B^c}} \right) \cap \left( {A \cap {C^c}} \right).}\]

Finally, applying the set difference law, we have

\[{LHS = \left( {A \cap {B^c}} \right) \cap \left( {A \cap {C^c}} \right) }={ \left( {A \backslash B} \right) \cap \left( {A \backslash C} \right) }={ RHS.}\]

Example 5.

Show that \(\left( {A \cap B} \right) \cup \left( {A \cap {B^c}} \right) = A.\)

Solution.

We prove algebraically that the left hand side \(\left({LHS}\right)\) of the identity is equal to the right-hand side \(\left({RHS}\right).\)

Using the distribution law

\[{A \cap \left( {B \cup C} \right) }={ \left( {A \cap B} \right) \cup \left( {A \cap C} \right),}\]

we can write

\[{LHS = \left( {A \cap B} \right) \cup \left( {A \cap {B^c}} \right) }={ A \cap \left( {B \cup {B^c}} \right).}\]

Recall that by complement laws,

\[B \cup {B^c} = U.\]

Hence,

\[{LHS = A \cap \left( {B \cup {B^c}} \right) }={ A \cap U.}\]

Finally, using the identity law \(A \cap U = A,\) we conclude that

\[{LHS = A \cap U }={ A = RHS.}\]

Example 6.

Show that \(A \,\triangle\, \left( {A \cap B} \right) = A \backslash B.\)

Solution.

We prove this identity algebraically – using the basic laws of set theory.

The symmetric difference in the left-hand side \(\left({LHS}\right)\) can be written as

\[{LHS = A \,\triangle\, \left( {A \cap B} \right) }={ \left( {A \backslash \left( {A \cap B} \right)} \right) }\cup{ \left( {\left( {A \cap B} \right) \backslash A} \right).}\]

Apply the set difference law:

\[{LHS = \left( {A \cap {{\left( {A \cap B} \right)}^c}} \right) }\cup{ \left( {\left( {A \cap B} \right) \cap {A^c}} \right).}\]

By De Morgan’s law, \({\left( {A \cap B} \right)^c} = {A^c} \cup {B^c}.\)

Using the commutative and associative laws, we have

\[{\left( {A \cap B} \right) \cap {A^c} }={ {A^c} \cap \left( {A \cap B} \right) }={ \left( {{A^c} \cap A} \right) \cap B.}\]

By the complement law, \({{A^c} \cap A} = \varnothing\), and by the domination and commutative laws, \(\varnothing \cap B = B \cap \varnothing = \varnothing.\) Hence, \(\left( {A \cap B} \right) \cap {A^c} = \varnothing.\) Applying the identity law, we represent the left-hand side in the form

\[{LHS \text{ = }}\kern0pt{ \left( {A \cap \left( {{A^c} \cup {B^c}} \right)} \right) \cup \left( {\left( {A \cap B} \right) \cap {A^c}} \right) }={ \left( {A \cap \left( {{A^c} \cup {B^c}} \right)} \right) \cup \varnothing }={ A \cap \left( {{A^c} \cup {B^c}} \right).}\]

Using the distributive law, we get

\[LHS = \left( {A \cap {A^c}} \right) \cup \left( {A \cap {B^c}} \right).\]

Obviously that \({A \cap {A^c}} = \varnothing\), by the complement law. This yields:

\[LHS = \varnothing \cup \left( {A \cap {B^c}} \right).\]

Now we use again the commutative and identity laws:

\[{LHS = \varnothing \cup \left( {A \cap {B^c}} \right) }={ \left( {A \cap {B^c}} \right) \cup \varnothing }={ A \cap {B^c}.}\]

By the set difference law, we conclude that

\[{LHS = A \cap {B^c} =} {A \backslash B }={ RHS.}\]

Example 7.

Using a membership table, prove that \(A \cap \left( {B\backslash A} \right) = \varnothing.\)

Solution.

We build a membership table for the sets \(A \cap \left( {B\backslash A} \right)\) and \(\varnothing.\) The number \(1\) represents membership in a set and \(0\) represents nonmembership. We consider all possible membership combinations in the original sets \(A\) and \(B\) and calculate the membership values for the sets in the left and right side of the identity. The results are shown in the following table:

Membership table to prove the set identity A and (B\A) = empty set.
Figure 1.

Since the last two columns have the same values, the set identity holds.

Example 8.

Using a membership table, prove that \(A \cup \left( {{A^c} \cap B} \right) = A \cup B.\)

Solution.

We construct a table which shows the membership relations for the sets in the left-hand side and the right-hand side of the identity. The number \(1\) indicates that an element is in a set, and \(0\) means that an element is not in a set. The table contains each combination of sets \(A\) and \(B\) that an element can belong to.

Membership table to prove the set identity A or ((A^c) and B) = A or B.
Figure 2.

Since the answers in the last two columns are the same, the identity is proved.

Example 9.

Prove the identity \(A \cup \left( {B\backslash A} \right) = A \cup B\) using set builder notation and logical equivalences.

Solution.

We represent the left-hand side in set builder notation:

\[{LHS = A \cup \left( {B\backslash A} \right) }={ \left\{ {x \mid x \in A \lor \left( {x \in B \land x \notin A} \right)} \right\}.}\]

Rewrite the statement \({x \notin A}\) with the negation operation:

\[{LHS \text{ = }}\kern0pt{\left\{ {x \mid x \in A \lor \left( {x \in B \land \neg \left( {x \in A} \right)} \right)} \right\}.}\]

By the distributive law,

\[{LHS \text{ = }}\kern0pt{\left\{ {x \mid \left( {x \in A \lor x \in B} \right) }\right.}\kern0pt{\left.{\land \left( {x \in A \lor \neg \left( {x \in A} \right)} \right)} \right\}.}\]

The disjunction of \({x \in A}\) and \({\neg \left( {x \in A} \right)}\) is a true statement:

\[x \in A \lor \neg \left( {x \in A} \right) = T.\]

So, by the identity law,

\[{LHS \text{ = }}\kern0pt{\left\{ {x \mid \left( {x \in A \vee x \in B} \right) \wedge T} \right\} }={ \left\{ {x \mid x \in A \vee x \in B} \right\}.}\]

Returning back to algebraic form, we conclude that

\[LHS = A \cup B = RHS.\]

Example 10.

Prove the identity \(A\backslash \left( {A\backslash B} \right) = A \cap B\) using set builder notation and logical equivalences.

Solution.

The left-hand side of the identity is represented in set builder notation as follows:

\[{LHS = A\backslash \left( {A\backslash B} \right) }={ \left\{ {x \mid x \in A \land x \notin \left( {A\backslash B} \right)} \right\}.}\]

The negation of the “element of” statement is written as

\[x \notin \left( {A\backslash B} \right) \leftrightarrow \neg x \in \left( {A\backslash B} \right).\]

Using again the definition of set difference, we have

\[{LHS \text{ = }}\kern0pt{ \left\{ {x \mid x \in A \land x \notin \left( {A\backslash B} \right)} \right\} }={ \left\{ {x \mid x \in A \land \neg \left( {x \in A \land x \notin B} \right)} \right\}.}\]

Replace \(x \notin B\) with \(\neg \left( {x \in B} \right):\)

\[{LHS \text{ = }}\kern0pt{ \left\{ {x \mid x \in A \land \neg \left( {x \in A \land \neg \left( {x \in B} \right)} \right)} \right\}.}\]

Apply De Morgan’s law:

\[{LHS \text{ = }}\kern0pt{\left\{ {x \mid x \in A \land \left( {\neg \left( {x \in A} \right) \lor x \in B} \right)} \right\}.}\]

By the distributive law,

\[{LHS \text{ = }}\kern0pt{\left\{ {x \mid \left( {x \in A \land \neg \left( {x \in A} \right)} \right) }\right.}\kern0pt{\left.{\lor \left( {x \in A \land x \in B} \right)} \right\}.}\]

Note that the conjunction of \({x \in A}\) and \({\neg \left( {x \in A} \right)}\) is a false statement:

\[x \in A \land \neg \left( {x \in A} \right) = F.\]

Hence, by the commutative and identity laws,

\[{LHS \text{ = }}\kern0pt{\left\{ {x \mid F \lor \left( {x \in A \land x \in B} \right)} \right\} }={ \left\{ {x \mid \left( {x \in A \land x \in B} \right)} \right\}.}\]

Converting back from set builder notation to algebraic form, we get

\[LHS = A \cap B = RHS.\]