Math Home

This lesson parallels lesson 1.3 Analysis With Fundamental Logic Operations. The properties of the operations of sets directly follow from the operations of logic once the statements are appropriately converted.

The first operation to be performed is always complement. Then \(\cap\) and \(\cup\) are on the same level after complement. Parentheses are used to impose an order of operation.

For example, if the universal set is \(U = \{1, 2, 3, 4, 5\},\) and \(A = \{1, 3, 5\}\) and \(B = \{1, 2, 3\},\) then \[A \cup B^C = \{1, 3, 5\} \cup \{1, 2, 3\}^C= \{1, 3, 5\} \cup \{4, 5\} = \{1, 3, 4, 5\}\] \[(A \cup B)^C = (\{1, 3, 5\} \cup \{1, 2, 3\})^C = \{1, 2, 3, 5\}^C = \{4\}\]

Complement is the only unary operator, which means it takes one input. Performing complement twice will cancel the complement.

Claim: For any set \(A\), \((A^C)^C = A.\)

This claim can be proved by showing the following:

- If \(x \in (A^C)^C,\) then \(x \in A.\)
- If \(x \in A,\) then \(x \in (A^C)^C.\)

The following is a derivation of the claim: \begin{align} x \in (A^C)^C & = \neg(x \in A^C) \\ & = \neg(\neg (x \in A)) \\ & = x \in A \end{align}

The operations \(\cap\) and \(\cup\) are commutative and associative. As an example, we state explicitly what this means for \(\cap.\)

- Associativity of \(\cap\): For any sets \(A, B,\) and \(C,\) \((A \cap B) \cap C = A \cap (B \cap C).\)
- Commutativity of \(\cap\): For any sets \(A\) and \(B\), \(A \cap B = B \cap A.\)

Since the operations are all associative, we do not need to use parentheses when all the operations are the same. For example, \(A \cap B \cap C\) is well defined.

The operation \(\cup\) distributes over \(\cap\), and the operation \(\cap\) distributed over \(\cup.\) For any sets \(A,\) \(B,\) and \(C,\)
\[A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\]
\[A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\]
We will check the distributivity of \(\cup\) over \(\cap.\) The result follows from the distributivity of \(\vee\) over \(\wedge.\)

The following derivation shows that \(x \in (A \cup (B \cap C))\) if, and only if, \(x \in ((A \cup B) \cap (A \cup C)):\)
\begin{align}
x \in (A \cup (B \cap C)) & = (x \in A) \vee (x \in B \cap C) \\
& = (x \in A) \vee ((x \in B) \wedge (x \in C)) \\
& = ((x \in A) \vee (x \in B)) \wedge ((x \in A) \vee (x \in C)) \\
& = (x \in A \cup B) \wedge (x \in A \cup C) \\
& = x \in ((A \cup B) \cap (A \cup C))
\end{align}
The third line uses the distributivity of \(\vee\) over \(\wedge.\) Every other line is a conversion between statements of logic and statements of set theory.

De Morgan's Laws hold for sets since they hold for logic: \[(A \cap B)^C = A^C \cup B^C\] \[(A \cup B)^C = A^C \cap B^C\]

We will verify the statement \((A \cup B)^C = A^C \cap B^C\) by showing \(x \in (A \cup B)^C\) if, and only if, \(x \in A^C \cap B^C.\) \begin{align} x \in (A \cup B)^C & = \neg (x \in A \cup B) \\ & = \neg ((x \in A) \vee (x \in B)) \\ & = \neg (x \in A) \wedge \neg (x \in B) \\ & = (x \in A^C) \wedge (x \in B^C) \\ & = x \in A^C \cap B^C \end{align} The third line uses De Morgan's Law. Every other line is a conversion between statements of logic and statements of set theory.

Check your understanding:

Unanswered

\((A \cap B)^C \cap C=\)

Unanswered

\((A \cap B) \cup A^C=\)

Unanswered

\((A^C \cap B)^C=\)

Unanswered

Unanswered

\((A \cap B)^C \cap C=\)

Unanswered

\((A \cap B) \cup A^C=\)

Unanswered