# Thread: Induction and Set Operations(Thinking)

1. ## Induction and Set Operations(Thinking)

Hey I missed a few days, could anyone help me solve this proof?

Prove that A1, A2, . . . ., An and B are sets, then (A1 ∩ A2 ∩ . . . ∩An) U B = (A1 U B) ∩ (A2 U B) ∩ . . . ∩(An U B).

This comes from the Induction and Recursion chapter of Mathematical Induction.

2. Originally Posted by Saint22
Hey I missed a few days, could anyone help me solve this proof?

Prove that A1, A2, . . . ., An and B are sets, then (A1 ∩ A2 ∩ . . . ∩An) U B = (A1 U B) ∩ (A2 U B) ∩ . . . ∩(An U B).

This comes from the Induction and Recursion chapter of Mathematical Induction.
recall the distributive law for sets: $\displaystyle A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

Now, let $\displaystyle P(n)$: $\displaystyle (A_1 \cap A_2 \cap \cdots \cap A_n) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap \cdots \cap (A_n \cup B)$ for all $\displaystyle n \in \mathbb{N}, ~n \ge 1$.

$\displaystyle P(1)$ is trivially true.

Assume $\displaystyle P(n)$ is true. We show $\displaystyle P(n + 1)$

Define $\displaystyle C = A_1 \cap A_2 \cap \cdots \cap A_n$

then, $\displaystyle (A_1 \cap A_2 \cap \cdots \cap A_n \cap A_{n + 1}) \cup B = (C \cap A_{n + 1}) \cup B = (C \cup B) \cap (A_{n + 1} \cup B)$ By the distributive law.

since $\displaystyle P(n)$ is true. $\displaystyle (C \cup B) = (A_1 \cup B) \cap (A_2 \cup B) \cap \cdots (A_n \cup B)$

so that we have $\displaystyle (A_1 \cap A_2 \cap \cdots \cap A_n \cap A_{n + 1}) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap \cdots \cap (A_{n + 1} \cup B)$

so that $\displaystyle P(n + 1)$ is true.

This completes the inductive proof