1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 21, 2007 #1
    DISCRETE MATH: Prove a "simple" hypothesis involving sets. Use mathematical induction

    1. The problem statement, all variables and given/known data

    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]



    2. Relevant 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



    3. 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: Feb 21, 2007
  2. jcsd
  3. Feb 21, 2007 #2

    mjsd

    User Avatar
    Homework Helper

    your title says use mathematical induction... so did u try using that method to do this question?
     
  4. Feb 21, 2007 #3
    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: Feb 21, 2007
  5. Feb 21, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.....
     
  6. Feb 21, 2007 #5
    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: Feb 21, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: DISCRETE MATH: Prove a simple hypothesis involving sets. Use mathematical induction
  1. Mathematical Induction (Replies: 15)

  2. Mathematical induction (Replies: 0)

Loading...