# Prove: Sets Union & Intersection Hypothesis

• Mathematica
• VinnyCee
In summary, the mathematician is trying to 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

#### VinnyCee

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

## Homework Statement

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

## Homework Equations

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

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

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

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

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

Last edited:
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...

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

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

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?

Last edited:

## 1. What is the Sets Union & Intersection Hypothesis?

The Sets Union & Intersection Hypothesis is a mathematical conjecture that states that for any two finite sets, their union and intersection must also be finite sets.

## 2. How is the Sets Union & Intersection Hypothesis used in mathematics?

The Sets Union & Intersection Hypothesis is used as a tool in many mathematical proofs and theorems, particularly in the fields of set theory, algebra, and topology.

## 3. Has the Sets Union & Intersection Hypothesis been proven?

No, the Sets Union & Intersection Hypothesis is still an open problem in mathematics and has not been proven to be true or false. It remains a conjecture that has not yet been resolved.

## 4. What are some potential implications if the Sets Union & Intersection Hypothesis is proven?

If the Sets Union & Intersection Hypothesis is proven to be true, it would have significant implications for mathematics and could potentially lead to the development of new theories and techniques in various branches of mathematics.

## 5. Are there any known counterexamples to the Sets Union & Intersection Hypothesis?

No, there are no known counterexamples to the Sets Union & Intersection Hypothesis. However, the fact that it has not been proven means that it is still possible for a counterexample to exist.