Physics Forums (http://www.physicsforums.com/index.php)
-   Math & Science Software (http://www.physicsforums.com/forumdisplay.php?f=189)
-   -   DISCRETE MATH: Prove a "simple" hypothesis involving sets. Use mathematical induction (http://www.physicsforums.com/showthread.php?t=157405)

 VinnyCee Feb21-07 02:20 AM

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

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

Prove that if $A_1,\,A_2,\,\dots,\,A_n$ and $B$ are sets, then
$$\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)$$

2. Relevant equations

$$A\,\cap\,B\,=\,B\,\cap\,A$$ <----- commutative law

$$A\,\cup\,\left(B\,\cap\,C\right)\,=\,\left(A\,\cup\,B\right)\,\cap\,\le ft(A\,\cup\,C\right)$$ <----- 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.

$$\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)$$

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

 mjsd Feb21-07 02:37 AM

your title says use mathematical induction... so did u try using that method to do this question?

 VinnyCee Feb21-07 03:15 AM

Let $P(n)$ be $$\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)$$

Then $\forall\,n\,\left(P(n)\right)$, right?

First I do the basis step for $P(1)$:

$$A_1\,\cup\,B\,=\,\left(A_1\,\cup\,B\right)$$

Now I need to show that $P(k)\,\longrightarrow\,P(k\,+\,1)$?

For $P(k)$ (Also, assume it is true for induction):

$$\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)$$

EDIT: Removed errors

 matt grime Feb21-07 04:27 AM

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

 VinnyCee Feb21-07 04:46 PM

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 $$A_1\,\cap\,A_2\,\cap\,\dots\,\cap\,A_k$$

$$\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)\,\c up\,B$$

Then use commutative law:

$$B\,\cup\,\left(S\,\cap\,A_{k\,+\,1}\right)$$

Now use distributive law:

$$\left(B\,\cup\,S\right)\,\cap\,\left(B\,\cup\,A_{k\,+\,1}\right)$$ < ----- Equation 1

Now, assuming the $p(k)$ induction:

$$\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)$$

Substitute this assumption into equation 1 above:

$$\left(B\,\cup\,S\right)\,\cap\,\left(B\,\cup\,A_{k\,+\,1}\right)\,\equi v\,\left(A_1\,\cup\,B\left)\,\cap\,\left(A_2\,\cup\,B\right)\,\cap\,\do ts\,\cap\,\left(A_k\,\cup\,B\right)\,\cap\,\left(B\,\cup\,A_{k\,+\,1}\r ight)$$

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

$$\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\righ t)$$

And this proves that for $P(k\,+\,1)$:

$$\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)$$

Is the proof correct?

 All times are GMT -5. The time now is 04:33 PM.