DISCRETE MATH: Prove a simple hypothesis involving sets. Use mathematical induction

  • Mathematica
  • Thread starter VinnyCee
  • Start date
  • #1
489
0

Main Question or Discussion Point

DISCRETE MATH: Prove a "simple" hypothesis involving sets. Use mathematical induction

Homework Statement



Prove that if [itex]A_1,\,A_2,\,\dots,\,A_n[/itex] and [itex]B[/itex] are sets, then
[tex]\left(A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_n\right)\,\cup\,B\,=\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A_n\,\cup\,B\right)[/tex]



Homework Equations



[tex]A\,\cap\,B\,=\,B\,\cap\,A[/tex] <----- commutative law

[tex]A\,\cup\,\left(B\,\cap\,C\right)\,=\,\left(A\,\cup\,B\right)\,\cap\,\left(A\,\cup\,C\right)[/tex] <----- distributive law



The Attempt at a Solution



I don't know how to start this other than that I need to use the two laws above. Maybe change the notation? I don't know.

[tex]\bigcap_{i\,=\,1}^{n}\,A_i\,\cup\,B\,=\,\left(A_1\,\cap\,B\right)\,\cup\,\left(A_2\,\cap\,B\right)\,\cup\dots\,\cup\,\left(A_n\,\cap\,B\right)[/tex]

What should be the next step or is there a better way of going about this?





NOTE: For LaTeXers, \cup is a union and \cap is an intersection.
 
Last edited:

Answers and Replies

  • #2
mjsd
Homework Helper
726
3
your title says use mathematical induction... so did u try using that method to do this question?
 
  • #3
489
0
Let [itex]P(n)[/itex] be [tex]\left(A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_n\right)\,\cup\,B\,=\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A_n\,\cup\,B\right)[/tex]

Then [itex]\forall\,n\,\left(P(n)\right)[/itex], right?



First I do the basis step for [itex]P(1)[/itex]:

[tex]A_1\,\cup\,B\,=\,\left(A_1\,\cup\,B\right)[/tex]



Now I need to show that [itex]P(k)\,\longrightarrow\,P(k\,+\,1)[/itex]?

For [itex]P(k)[/itex] (Also, assume it is true for induction):

[tex]\left(A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_k\right )\,\cup\,B\,=\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A _k\,\cup\,B\right)[/tex]


EDIT: Removed errors
 
Last edited:
  • #4
matt grime
Science Advisor
Homework Helper
9,395
3
1. Don't start by writing out what you want to prove (just after the 'For P(k+1)').

2. P(k) is a statement that two things are equal. So why have you used the symbol P(k) as if it were a set?

3. Use strong induction.

4. If that doesn't mean anything to you then consider this:

take AnBnCnDnEnF. Let X=AnBnCnDnE and Y=F. Then we can rewrite that as XnY. I've gone from a statement about 6 sets to one about 2 sets. Now can I use anything I know to be true for 2 sets.....
 
  • #5
489
0
Strong induction is covered in the next section. It says that it is easier to use strong induction in many cases, I am sure this is one, but we have to use "mathematical induction". Isn't strong induction just a special case of mathematical induction?

Let S be [tex]A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_k[/tex]

[tex]\left(A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_k\,\cap \,A_{k\,+\,1}\right)\,\cup\,B\,=\,\left(S\,\cap\,A_{k\,+\,1}\right)\,\cup\,B[/tex]

Then use commutative law:

[tex]B\,\cup\,\left(S\,\cap\,A_{k\,+\,1}\right)[/tex]

Now use distributive law:

[tex]\left(B\,\cup\,S\right)\,\cap\,\left(B\,\cup\,A_{k\,+\,1}\right)[/tex] < ----- Equation 1

Now, assuming the [itex]p(k)[/itex] induction:

[tex]\left(B\,\cup\,S\right)\,\equiv\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A_k\,\cup\,B\right)[/tex]

Substitute this assumption into equation 1 above:

[tex]\left(B\,\cup\,S\right)\,\cap\,\left(B\,\cup\,A_{k\,+\,1}\right)\,\equiv\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A_k\,\cup\,B\right)\,\cap\,\left(B\,\cup\,A_{k\,+\,1}\right)[/tex]

Now use the commutative law again on the last two terms:

[tex]\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A_k\,\cup\,B\right)\,\cap\,\left(A_{k\,+\,1}\,\cup\,B\right)[/tex]

And this proves that for [itex]P(k\,+\,1)[/itex]:

[tex]\left(A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_k\,\cap\,A_{k\,+\,1}\right)\,\cup\,B\,=\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\dots\,\cap\,\left(A_k\,\cup\,B\right)\,\cap\,\left(A_{k\,+\,1}\,\cup\,B\right)[/tex]




Is the proof correct?
 
Last edited:

Related Threads on DISCRETE MATH: Prove a simple hypothesis involving sets. Use mathematical induction

Replies
41
Views
12K
Replies
4
Views
2K
Replies
3
Views
3K
Replies
7
Views
3K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
3K
Top