# How to approach this set proof question (Iterative Union/Intersection)

I'm writing today to ask for a heading/starting point in how I might approach this problem proposed to me involving Set Theory. From my understanding, this proof is asking us to show that the set containing all the elements in A minus the set of all elements common to the sets B1,B2,...,Bn is equal to the set containing all the elements of A not in a particular set on Bn. I can see this making sense, as it's saying there's a set of values in B1, B2, Bn that are not in at least one of the iterations of the Union of (A-Bi), however I am very stuck on how to begin formally proving this using Set Theory. Can someone give me a direction/heading for this? I'm familiar with calculus and more number theory proofs but I'm completely lost on how to begin such a proof like this.

• If you must prove that $U=V$ where $U,V$ are sets, then the usual procedure is proving that $x\in U$ implies $x\in V$ and vice versa. Have you tried that out? – drhab May 6 '18 at 12:37
• I'll try that right now and come back! – Pixel Rain May 6 '18 at 12:38
• So we have for an arbitrary positive integer n, an element x such that: $$x \in A$$ and $$x \notin the set of all y common to all the sets B_n$$. I'm uncertain how to show mathematically that this element is in the RHS of the equation; it's obvious X in A on the RHS, but how can I express X not in the set of all values y common to all the B's? – Pixel Rain May 6 '18 at 12:45

## 2 Answers

Let $x\in A-\bigcap_{i=1}^nB_i$.

Then $x\in A$ and not $x\in \bigcap_{i=1}^nB_i$ or equivalently some $i_0\in\{1,\dots,n\}$ exists with $x\notin B_{i_0}$.

Then we have $x\in A-B_{i_0}$ and this set is evidently a subset of $\bigcup_{i=1}^n(A-B_i)$ so that also $x\in\bigcup_{i=1}^n(A-B_i)$.

This proves: $$A-\bigcap_{i=1}^nB_i\subseteq\bigcup_{i=1}^n(A-B_i)$$

Give the other side a try yourself.

edit (the other way).

Let $x\in\bigcup_{i=1}^n(A-B_i)$.

Then $x\in A-B_{i_0}$ for some $i_0\in\{1,\dots,n\}$.

Then $x\in A$ and $x\notin B_{i_0}$.

Then it cannot be true that $x\in\bigcap_{i=1}^nB_i$.

This because $\bigcap_{i=1}^nB_i\subseteq B_{i_0}$ so that $x\in\bigcap_{i=1}^nB_i$ leads to $x\in B_{i_0}$ which is not true.

We conclude that $$x\in A-\bigcap_{i=1}^nB_i$$

• Can you explain the equivalent $i_0$ to me a bit more? Is it just saying there exists some index i in the positive integers from 1 to our arbitrary n value such that the $B_i_0$ set doesn't contain that x? I'm just trying to understand why it's equivalent – Pixel Rain May 6 '18 at 12:49
• $x\in\bigcap_{i=1}^nB_i$ means that $x\in B_i$ is true for every $i\in\{1,\dots,n\}$. So if it is false then some $i\in\{1,\dots,n\}$ must exists for which that is not true. Picking out one of the indices (there might be more that one) for which it is not true and denoting it by $i_0$ we can say that $x\notin B_{i_0}$. If conversely $x\notin B_{i_0}$ for some $i_0\in\{1,\dots,n\}$ then $x\notin\bigcap_{i=1}^nB_i$. So the statements are equivalent. – drhab May 6 '18 at 12:56
• Right, that makes alot of sense. Going the other way we would say $x \in A$ and $x \notin$ the intersection between all of them, I mean that seems a little too easy to show but like we know that the union of all the sets A - B_n is going to have x in A and x not in the set of the elements common to all the B_n so what else do we really need to say? – Pixel Rain May 6 '18 at 13:02
• Have a look at my edit. I must go now. – drhab May 6 '18 at 13:10
• You are welcome – drhab May 6 '18 at 15:14

Use the fact that $A - B = A \cap B^{\complement}$, and then just typical algebra rules:

So:

$$A - \bigcap_{i=1}^n B_i = A \cap \big( \bigcap_{i=1}^n B_i \big)^{\complement} \overset{DeMorgan}=A \cap \big( \bigcup_{i=1}^n B_i^{\complement} \big)\overset{Distribution}=\bigcup_{i=1}^n \big( A \cap B_i^{\complement} \big)= \bigcup_{i=1}^n \big( A - B_i \big)$$

• Ok so I was thinking this, but don't we need a universal set to draw upon to use complement and stuff? – Pixel Rain May 6 '18 at 12:46
• @PixelRain We can assume there is some set of which $A$ and all the $B_i$'s are subsets; this would be your domain that would act as your 'universal set'. – Bram28 May 6 '18 at 12:49
• That makes sense, as all sets are derived from some universal set, thank you so much! – Pixel Rain May 6 '18 at 12:50