Discrete Mathematical Structures, Lecture 2.8: Set-theoretic proofs

Discrete Mathematical Structures, Lecture 2.8: Set-theoretic proofs

Up until now, our main tool for verifying set identities, such as A∩(B∪C)=(A∩B)∪(A∩C), was to convince ourselves using a Venn diagram. Of course, this is not rigorous, especially because diagrams can be misleading or incomplete. In this lecture, we see three technique for formally proving such identities: (i) directly, i.e., by writing them in set notation, (ii) by showing that both ⊆ and ⊇ hold, and (iii) indirectly, i.e., using either the contrapositive or by contradiction.