Set proof
A set proof is a method of direct proof that can be used to show that two sets are equal, or that one set is a subset of the other.
In general, set proofs involve the instantiation of arbitrary elements about which workable logical statements can be derived from the definitions of the set operations. From there, you can deduce until enough facts are obtained to prove set membership. Essentially, a set proof takes a statement about being an element of one set, translates it into pure logic, and then reaches a conclusion that can be converted back into a statement about membership, but of another set.
Inclusion
In this type of set proof, you are tasked with showing that one set is a subset of the other. In other words, you have to prove that being an arbitrary element of the first set implies being an arbitrary element of the second set.
Inclusion proof: Let \(x\) be an arbitrary element of \(A.\)
Then we can write: $$x \in A$$ By the addition rule of inference: $$x \in A \lor x \in B$$ By the definition of union: $$x \in A \cup B$$ Therefore, being an arbitrary element of \(A\) implies being an element of \(A \cup B.\) We can conclude that \(A \subseteq A \cup B.\) \(■\)
Double-inclusion
To prove set equality, you need to show that both sets are subsets of each other. That's why a double-inclusion proof resembles two inclusion proofs, done in both directions.
Double-inclusion proof: To prove \(\overline{A \cup B} = \overline A \cap \overline B\), we will need to prove \(\overline{A \cup B} \subseteq \overline A \cap \overline B\) and \(\overline A \cap \overline B \subseteq \overline{A \cup B}.\)
1. First, I'll prove \(\overline{A \cup B} \subseteq \overline A \cap \overline B\):
Let \(x\) be an arbitrary element of \(\overline{A \cup B}.\)
Then we can write: $$x \in \overline{A \cup B}$$ By the definition of complement: $$x \notin A \cup B$$ By the definition of union: $$\lnot(x \in A \lor x \in B)$$ By De Morgan's Law (from the logic laws): $$x \notin A \land x \notin B$$ By the definition of complement: $$x \in \overline A \land x \in \overline B$$ Finally, by the definition of intersection: $$x \in \overline A \cap \overline B$$ Therefore, being an arbitrary element of \(\overline{A \cup B}\) implies being an element of \(\overline A \cap \overline B.\) We can conclude that \(\overline{A \cup B} \subseteq \overline A \cap \overline B.\)
2. Next, I'll prove \(\overline A \cap \overline B \subseteq \overline{A \cup B}\):
Let \(y\) be an arbitrary element of \(\overline A \cap \overline B.\)
Then we can write: $$y \in \overline A \cap \overline B$$ By the definition of intersection: $$y \in \overline A \land y \in \overline B$$ By the definition of complement: $$y \notin A \land y \notin B$$ By De Morgan's Law (from the logic laws): $$\lnot(y \in A \lor y \in B)$$ By the definition of union: $$y \notin A \cup B$$ Finally, by the definition of complement: $$y \in \overline{A \cup B}$$ Therefore, being an arbitrary element of \(\overline A \cap \overline B\) implies being an element of \(\overline{A \cup B}.\) We can conclude that \(\overline A \cap \overline B \subseteq \overline{A \cup B}.\)
Since \(\overline{A \cup B} \subseteq \overline A \cap \overline B\) and \(\overline A \cap \overline B \subseteq \overline{A \cup B}\), it is true that \(\overline{A \cup B} = \overline A \cap \overline B\) due to double-inclusion. \(■\)
Because this particular double-inclusion proof used only definitions and logic laws as steps, the two inclusion proofs were simply reverses of each other. To delve into exactly why, it's because each step is connected by a biconditional (either a definition or logic law), which means they're all logically equivalent. However, if you happened to use a rule of inference, or take some other kind of step that maintains truth but not logical meaning, your proof would no longer be reversible. Unless you fully understand the mechanics of this, just to be safe, always write two separate inclusion proofs to prove double-inclusion.