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:
The operations \(\cap\) and \(\cup\) are commutative and associative. As an example, we state explicitly what this means for \(\cap.\)
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.
\((A^C \cap B)^C=\)
Unanswered