1
$\begingroup$

I'm stuck on this proof. Especially in the $\implies$ direction. I've written the following but feel it is more just a restatement of the original equation than a proof. It goes from very specific (intersection) to general (union) and this is turning my brain into mush. Any help is MUCH appreciated. Here is what I have:

Consider $ x \in B \setminus \cap_{i \in I} A_{i}$. Then $x \in B$ and$ \forall A \in F$, $x \not \in A$. $\exists A\in F$ $x\in B$ and $x\not \in $A and therefore $x \not \in \cup_{i \in I} B \setminus A_{i}$.

Thanks again!

$\endgroup$
  • $\begingroup$ x ∈ B ^ ∀A ∈ F (x ∉ A) -> ∃A ∈ F (x ∈ B ^ x ∉ A ) and therefor x ∉ ∪i∈I(B\Ai). Here it is again to fix the little box that showed up. $\endgroup$ – maybedave Nov 28 '16 at 20:24
  • $\begingroup$ You should learn a few simple tricks to type math on this site more easily and make it more readable. First, any math you want to write should be put between dollar signs. So the math $x \in A$ should be written as \$ x \in A \$. Second, as you can see, the $\in$ symbol can be written as \in. The $\cap$ intersection symbol is \cap, and the $\cup$ union symbol is \cup. $\forall$ is just \forall. $\not \in$ is just \not \in. $\endgroup$ – layman Nov 28 '16 at 20:26
  • 1
    $\begingroup$ To get $\cap_{i \in I} A_{i}$ you write \$ \cap_{i \in I} A_{i} \$. Also $\exists$ is \exists. Hope that helps. $\endgroup$ – layman Nov 28 '16 at 20:27
  • 1
    $\begingroup$ I'm currently editing the math in your question to meet the standards in my last comments, then I'll help you if no one else has. :) $\endgroup$ – layman Nov 28 '16 at 20:28
2
$\begingroup$

I will help you do one direction and the other direction is very similar, so I'll leave it to you. If you get stuck, just let me know.

Suppose $x \in B \setminus \cap_{i \in I} A_{i}$. In words, this means $x \in B$ and $x \not \in \cap_{i \in I} A_{i}$. Restated, this means $x$ is in $B$ and $x$ is not in $A_{i}$ for some $i$ (since if $x$ is in $A_{i}$ for every $i$, $x$ would be in the intersection all the $A_{i}$'s).

Since $x$ is in $B$ and $x$ is not in $A_{i}$ for some $i$, that means $x$ is in $B \setminus A_{i}$ for some $i$, right? Then $x$ is in the union of $B \setminus A_{i}$, i.e., $x \in \cup_{i \in I} B \setminus A_{i}$, since being in one of the sets $B \setminus A_{i}$ implies you are in the union of all of them. So the $\implies$ direction is done. The backward direction is similar in spirit, so try it for yourself.

$\endgroup$
  • $\begingroup$ Thank you! So I guess I was wrong. I should have seen that this was the easy direction because we are going from something more specific (intersection) to something more general (union) and proving the more specific is a subset of the more general is easy. I've been going through this and don't see how I could imply that x is an element of some Ai would mean x is an element of ALL Ai. Can you maybe give me a hint? BTW, I'm learning this on my own so I really appreciate the help! $\endgroup$ – maybedave Nov 28 '16 at 22:24
  • $\begingroup$ and by easy, I meant easy for smarter people than me because I didn't see it in the first place :) $\endgroup$ – maybedave Nov 28 '16 at 22:24
  • $\begingroup$ @maybedave So, if $x$ is an element of $A_{i}$ for some $i$, that doesn't imply $x$ is an element of $A_{i}$ for all $i$. Where do you think I said that? $\endgroup$ – layman Nov 29 '16 at 1:30
  • $\begingroup$ I guess I explained it wrong. Sorry about that. I was saying that this would be the logic in the opposite direction because in that direction we would be going from something general like x is an element of some Ai to something more specific like x is an element of all Ai. Sorry if I implied you said this. I know you didn't. I'm just trying to work out the other direction. $\endgroup$ – maybedave Nov 29 '16 at 21:54
  • 1
    $\begingroup$ Thanks user46944. You have been a big help! I'm learning this stuff in a vacuum. I have no background in math and work approximately one million hours a week so I don't really get to talk to anyone about proofs. I will take everything you wrote and review/absorb over time for more breakthroughs. You rock my friend! $\endgroup$ – maybedave Dec 2 '16 at 13:50
1
$\begingroup$

I would simply calculate which elements $\;x\;$ are in both sides of the equality, by expanding the definitions.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $ In this case both sides look equally complex, so we arbitrarily choose to start with the left hand side, and work towards the right hand side: for all $\;x\;$,

$$\calc x \in B \setminus \cap_{i \in I} A_i \op\equiv\hint{definition of $\;\setminus\;$} x \in B \;\land\; \lnot (x \in \cap_{i \in I} A_i) \op\equiv\hint{definition of $\;\cap_{\cdot \in \cdot}\;$} x \in B \;\land\; \lnot \langle \forall i : i \in I : x \in A_i \rangle \op\equiv\hint{logic: DeMorgan -- to simplify} x \in B \;\land\; \langle \exists i : i \in I : \lnot (x \in A_i) \rangle \op\equiv\hints{logic: move part not using $\;i\;$ inside of $\;\forall i\;$}\hint{-- to bring $\;B\;$ and $\;A_i\;$ closer together as in our goal} \langle \exists i : i \in I : x \in B \;\land\; \lnot (x \in A_i) \rangle \op\equiv\hint{definition of $\;\setminus\;$ -- working toward the right hand side} \langle \exists i : i \in I : x \in B \setminus A_i \rangle \op\equiv\hint{definition of $\;\cup_{\cdot \in \cdot}\;$} x \in \cup_{i\in I} B \setminus A_i \endcalc$$

Therefore, by set extensionality, $\;B \setminus \cap_{i \in I} A_i \;=\; \cup_{i\in I} B \setminus A_i\;$.


Note how this proof proves both directions at the same time. See EWD1300 for details about this proof format and the notations which I used.

$\endgroup$
  • $\begingroup$ Very Very Helpful! Thank you! $\endgroup$ – maybedave Dec 2 '16 at 13:50
  • $\begingroup$ Is there a name or logic rule for the part where you wrote "“logic: move part not using i inside of ∀i-- to bring B and Ai closer together as in our goal”. I ask because I didn't really know you could do this and would like to read more about it. Thanks again! $\endgroup$ – maybedave Dec 6 '16 at 22:53

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.