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

For any ,

Proof:

By induction. Let be the statement "."

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 is also in . Choose an arbitrary [math]x [/math] in the right hand side. Then [math]x ∈ A [/math] and . This means either (1) [math]x ∈ B_1 [/math] or (2) [math]x ∈ B_2 [/math]. In case (1), we have and , so , and thus . B_2ase (2) is similar. In either case, , 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: