Set Identities

Home → 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

\[A \cup \varnothing = A,\;\;A \cap U = A\]

Domination Laws

\[A \cup U = U,\;\;A \cap \varnothing = \varnothing\]

Idempotent Laws

\[A \cup A = A,\;\;A \cap A = A\]

Complement Laws

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

Double Complement Law

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

Commutative Laws

\[A \cup B = B \cup A,\;\;A \cap B = B \cap A\]

Associative Laws

\[A \cup \left( {B \cup C} \right) = \left( {A \cup B} \right) \cup C,\;\;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),\;\;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},\;\;{\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,\;\;{\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.