Proof:A ∩ (B 1 ∪ ... ∪ B n) ⊆ (A ∩ B 1) ∪ ... ∪ (A ∩ B n)

From CS2800 wiki
For any [math]n ≥ 2 [/math], [math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]


Proof:
By induction. Let [math]P(n) [/math] be the statement "[math]A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) [/math]."

We must show [math]P(2) [/math] and [math]P(n+1) [/math] assuming [math]P(n) [/math].

In the base case, when [math]n = 2 [/math], we want to show to show that every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2) [/math] is also in [math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_2) [/math]. Choose an arbitrary [math]x [/math] in the right hand side. Then [math]x ∈ A [/math] and [math]x ∈ B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_2 [/math]. This means either (1) [math]x ∈ B_1 [/math] or (2) [math]x ∈ B_2 [/math]. In case (1), we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] and [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B_1 [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1 [/math], and thus [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. B_2ase (2) is similar. In either case, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math], as required.

For the inductive step, choose an arbitrary [math]n [/math] and assume we have already proved [math]P(n) [/math]. Our goal is to show [math]P(n+1) [/math]. We compute:


[math]\begin{align*} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) &= A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} ((B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_{n+1}) \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} (B_1 \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B_n)) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by P(2)} \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_n) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by P(n) and }\href{/cs2800/wiki/index.php/If_A_%E2%8A%86_B_then_A_%E2%88%A9_C_%E2%8A%86_B_%E2%88%A9_C_claim}{ \text{lemma}} \\ &⊆ (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_1) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \cdots \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B_{n+1}) && \text{by definition} \end{align*} [/math]