Addition Theorem
Addition Theorem
\[ P(A) + P(B) = P(A \cup B) + P(A \cap B) \]
\[ A \cup B = (A - B) \cup (A \cap B) \cup (B - A) \]
Claim 1: \(A \cup B \subset (A - B) \cup (A \cap B) \cup (B - A)\)
Proof.
- Pick \(x \in A \cup B\) [Ass.]
- \(\therefore x \in A\) OR \(x \in B\) [defn \(\cup\)]
Case 1: \(x \in A\) AND \(x \notin B\)
\[ \begin{aligned} &\therefore x \in A \text{ AND } x \in B^c &&\text{[defn } {}^c\text{]} \\ &\therefore x \in A \cap B^c &&\text{[defn } \cap\text{]} \\ &\therefore x \in A - B &&\text{[defn } -\text{]} \end{aligned} \]
Case 2: \(x \notin A\) AND \(x \in B\)
\[ \begin{aligned} &\therefore x \in A^c \text{ AND } x \in B &&\text{[defn } {}^c\text{]} \\ &\therefore x \in B \cap A^c &&\text{[defn } \cap\text{]} \\ &\therefore x \in B - A &&\text{[defn } -\text{]} \end{aligned} \]
Case 3: \(x \in A\) AND \(x \in B\)
\[ \therefore x \in A \cap B \qquad \text{[defn } \cap\text{]} \]
How to justify using cases? Propositional logic (see Lemma below).
- \(\therefore x \in (A - B) \cup (A \cap B) \cup (B - A)\) [Lemma]
- \(\therefore A \cup B \subset (A - B) \cup (A \cap B) \cup (B - A)\) [defn \(\subset\)]
\(\square\) Claim 1.
Propositional Logic Lemma
\[ P \lor Q \iff (P \mathbin{\&} \neg Q) \lor (P \mathbin{\&} Q) \lor (\neg P \mathbin{\&} Q) \]
Note: start \(\rightarrow\), then see need \(\leftarrow\) for Claim 2.
Proof. By truth table:
| \(P\) | \(Q\) | \(P \lor Q\) | \((P \mathbin{\&} \neg Q)\) | \((P \mathbin{\&} Q)\) | \((\neg P \mathbin{\&} Q)\) | RHS |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
\(\therefore\) valid. \(\square\)
Claim 2: \((A - B) \cup (A \cap B) \cup (B - A) \subset A \cup B\)
Proof.
- Pick \(x \in (A - B) \cup (A \cap B) \cup (B - A)\) [Ass.]
- \(\therefore x \in (A - B)\) OR \(x \in A \cap B\) OR \(x \in B - A\) [defn \(\cup\)]
Case 1: \(x \in A - B\)
\[ \begin{aligned} &\therefore x \in A \cap B^c &&\text{[defn } -\text{]} \\ &\therefore x \in A \text{ AND } x \in B^c &&\text{[defn } \cap\text{]} \\ &\therefore x \in A &&\text{[Lemma: } P \mathbin{\&} Q \Rightarrow P\text{]} \\ &\therefore x \in A \text{ OR } x \in B &&\text{[Lemma: } P \Rightarrow P \lor Q\text{]} \\ &\therefore x \in A \cup B &&\text{[defn } \cup\text{]} \end{aligned} \]
Or can stop at \(x \in A\) and use reasoning above.
Case 2: \(x \in A \cap B\) – similarly follows.
Case 3: \(x \in B - A\) – similarly follows.
- \(\therefore x \in A \cup B\)
- \(\therefore (A - B) \cup (A \cap B) \cup (B - A) \subset A \cup B\) [defn \(\subset\)]
\(\square\) Claim 2.
Completing the Proof
\[ \therefore A \cup B = (A - B) \cup (A \cap B) \cup (B - A) \qquad \text{[defn } =\text{, Claim 1 + 2]} \]
\(\square\) Lemma.
\[ \begin{aligned} \therefore P(A) + P(B) &= P(A - B) + P(A \cap B) + P(B - A) + P(A \cap B) \\ &= P\Big((A - B) \cup (A \cap B) \cup (B - A)\Big) + P(A \cap B) &&\text{[disjoint, CA]} \\ &= P(A \cup B) + P(A \cap B) &&\text{[Lemma]} \end{aligned} \]
\(\square\)
QED = quod erat demonstrandum (“which was to be demonstrated”)