# Set Theory Identities

\begin{align} A \cup \overline{A} & = & \Omega \qquad & \mbox{Complementation law}\\ A \cap \overline{A} & = & \emptyset \qquad & \mbox{Exclusion law}\\ \\ A \cap \Omega & = & A \qquad & \mbox{Identity laws} \\ A \cup \emptyset& = & A \qquad & \\ \\ A \cup \Omega &= & \Omega \qquad & \mbox{Domination laws} \\ A \cap \emptyset & = & \emptyset \qquad & \\ \\ A \cup A & = & A \qquad & \mbox{Idempotent laws} \\ A \cap A & = & A \qquad & \\ \\ \overline{\left(\overline{A}\right)} & = & A \qquad & \mbox{Double Complement} \\ \\ A \cup B & = & B \cup A \qquad & \mbox{Commutative laws} \\ A \cap B & = & B \cap A \qquad & \\ \\ \left(A \cup B\right) \cup C & = & A \cup \left(B \cup C\right) \qquad & \mbox{Associative laws} \\ \left(A \cap B\right) \cap C & = & A \cap \left(B \cap C\right) \qquad & \\ \\ A \cup \left(B \cap C\right) & = & \left(A \cup B\right) \cap \left(A \cup C\right) \qquad & \mbox{Distributive laws} \\ A \cap \left(B \cup C\right) & = & \left(A \cap B\right) \cup \left(A \cap C\right) \qquad \\ \\ \overline{\left(A \cap B \right)} & = & \overline{A} \cup \overline{B} \qquad & \mbox{De Morgans laws} \\ \overline{\left(A \cup B \right)} & = & \overline{A} \cap \overline{B} \qquad & \\ \end{align}

## Other Useful Identities

\begin{align} B - A \equiv B \cap \overline{A} \qquad & \mbox{Definition of set difference} \\ \left(R \cap S\right) \cup \left(R \cap \overline{S}\right) = R \end{align}

## Further Reference

You may use the identities available in the following Wikipedia article, as long as they are not the identity you are currently trying to prove:

cs-401r/set-theory-identities.txt · Last modified: 2014/10/06 07:08 by ringger
Back to top