Raising the bar

Chapter 4. Probability

Unit 4.2. Set identities

To solve some exercises in NCT you need to use certain set relations. All of them can be established using Venn diagrams. There is no need to remember them but try to understand the logic which will help you to pick the right relation for the exercise at hand.

Result 1. A set $latex B$ can be obtained as a union of two disjoint sets, $latex B = (A \cap B) \cup (\bar A \cap B)$, where $latex A \cap B$ is the common part of $latex A$ and $latex B$ and $latex \bar A \cap B$ is the common part of $latex \bar A$ and $latex B$.

Try to express verbally the other results.

Result 2. $latex A \cup B = A \cup (\bar A \cap B)$.

Result 3. Distributive law: $latex A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

Result 4. De Morgan's laws: $latex \overline {A \cup B} = \bar A \cap \bar B,\ \overline {A \cap B} = \bar A \cup \bar B$ (you pass to complements by interchanging unions and intersections).

These equations can be established using Venn diagrams but there is a more powerful method which works when using the Venn diagrams would be infeasible. We say that two sets, $latex U$ and $latex V$, are equal, $latex U = V$, when $latex U \subset V$ and $latex V \subset U$ (that is each element of $latex U$ belongs to $latex V$ and vice versa). To prove the first de Morgan law, denote $latex U = \overline {A \cup B}$, $latex V = \bar A \cap \bar B$.

Suppose $latex x \in U$. By definition, $latex x \in S \backslash (A \cup B)$ which means two things: $latex x \in S$, $latex x \notin A \cup B$. Hence, $latex x \in \bar A,\ x \in \bar B$ and $latex x \in \bar A \cap \bar B$. Since the implication $latex x \in U \Rightarrow x \in V$ is true for any element of $latex U$, we have proved that $latex U \subset V$. The proof of $latex V \subset U$ is left as an exercise.

Remark. In English "or" is nonexclusive whereas "either or" is exclusive. In some other languages there is only one "or" and one has to specify whether it is exclusive or nonexclusive.

Previous: Set operations | Next: Set versus probabilistic terminology

Want the whole book (all 14 chapters, exercises, and the index) as a single PDF? Available on Lulu for $1.99.