I'm writing today to ask for a heading/starting point in how I might approach this problem proposed to me involving Set Theory.

enter image description here

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.

  • 1
    $\begingroup$ 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? $\endgroup$ – drhab May 6 '18 at 12:37
  • $\begingroup$ I'll try that right now and come back! $\endgroup$ – Pixel Rain May 6 '18 at 12:38
  • $\begingroup$ 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? $\endgroup$ – Pixel Rain May 6 '18 at 12:45

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

  • $\begingroup$ 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 $\endgroup$ – Pixel Rain May 6 '18 at 12:49
  • $\begingroup$ $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. $\endgroup$ – drhab May 6 '18 at 12:56
  • $\begingroup$ 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? $\endgroup$ – Pixel Rain May 6 '18 at 13:02
  • $\begingroup$ Have a look at my edit. I must go now. $\endgroup$ – drhab May 6 '18 at 13:10
  • $\begingroup$ You are welcome $\endgroup$ – drhab May 6 '18 at 15:14

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


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

  • $\begingroup$ Ok so I was thinking this, but don't we need a universal set to draw upon to use complement and stuff? $\endgroup$ – Pixel Rain May 6 '18 at 12:46
  • $\begingroup$ @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'. $\endgroup$ – Bram28 May 6 '18 at 12:49
  • $\begingroup$ That makes sense, as all sets are derived from some universal set, thank you so much! $\endgroup$ – Pixel Rain May 6 '18 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.