1
$\begingroup$

I'm working on doing a proof by induction on this question:

Use induction to prove that if $X_1, . . . , X_n$ and $X$ are sets, then $X∩(X_1∪X_2∪· · ·∪X_n) = (X∩X_1)∪(X∩X_2)∪· · ·∪(X∩X_n)$.

I've shown the basis case:

$X∩X_1 = X∩X_1$

But I'm having difficulty proving the $n + 1$ case. This is my work so far:

Assume $X∩(X_1∪X_2∪· · ·∪X_n) = (X∩X_1)∪(X∩X_2)∪· · ·∪(X∩X_n)$

Show $X∩(X_1∪X_2∪· · ·∪X_n∪X_{n+1}) = (X∩X_1)∪(X∩X_2)∪· · ·∪(X∩X_n) = (X∩X_1)∪(X∩X_2)∪· · ·∪(X∩X_n)∪(X∩X_{n+1})$

I'm not sure what I'm allowed to do from here. Where can I use the induction hypothesis?

$\endgroup$
  • $\begingroup$ Please use MathJax to format your question correctly $\endgroup$ – Ankit Kumar Jan 11 at 4:57
1
$\begingroup$

Tip show: $X\cap(Y\cup X_{n+1})=(X\cup Y)\cap(X\cup X_{n+1})$ where $Y=X_1\cup\cdots\cup X_n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.