# 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: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

Now, let $P(n)$: $(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 $n \in \mathbb{N}, ~n \ge 1$.

$P(1)$ is trivially true.

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

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

then, $(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 $P(n)$ is true. $(C \cup B) = (A_1 \cup B) \cap (A_2 \cup B) \cap \cdots (A_n \cup B)$

so that we have $(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 $P(n + 1)$ is true.

This completes the inductive proof