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.

Introduction to logical operations

Order of Operations

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\}\]

Basic Properties

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.\)

In other words, \(x \in A\) if, and only if, \(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.

Distribution

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

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.