1

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!

layman
  • 20,191
maybedave
  • 509
  • 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. – maybedave Nov 28 '16 at 20:24
  • 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. – layman Nov 28 '16 at 20:26
  • 1
    To get $\cap_{i \in I} A_{i}$ you write $ \cap_{i \in I} A_{i} $. Also $\exists$ is \exists. Hope that helps. – layman Nov 28 '16 at 20:27
  • 1
    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. :) – layman Nov 28 '16 at 20:28

2 Answers2

2

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.

layman
  • 20,191
  • 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! – maybedave Nov 28 '16 at 22:24
  • and by easy, I meant easy for smarter people than me because I didn't see it in the first place :) – maybedave Nov 28 '16 at 22:24
  • @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? – layman Nov 29 '16 at 01:30
  • 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. – maybedave Nov 29 '16 at 21:54
  • @maybedave What do you think the other direction should look like? Try to follow your nose. Write down what you know and see what natural direction you can go in. If you want, feel free to write any attempts at a proof in the other direction down, and I can help you if you get stuck. – layman Nov 29 '16 at 22:05
  • Ok, so here goes….suppose $ x \in B $ ^ ∃A ∈ F (x ∉ A)…and this is as far as I get. This doesn’t even represent ∪i∈I(B\Ai) because (B\Ai) produces a family set that you then union where as ∃A ∈ F (x ∉ A) (the same as ∪i∈IAi) produces a plane set. I’m just not seeing how to break this down properly. – maybedave Nov 30 '16 at 21:56
  • this is what I have but I just don't think it is right. $ x \in ∪i∈I(B\Ai) $ then $ x \in B $ ^ $ ∃A \in F (x \not\in A) $ and so because x is not an element of some A then x must not be an element of all A and therefor $ x \in B ^ ∀A \in F (x \not\in A)$ – maybedave Dec 01 '16 at 00:39
  • @maybedave I think you're getting caught up on all of the math symbols, and that's your problem. When writing a proof you should use as many real world words as possible and as few math symbols as possible. Here is how I would write the proof: Suppose $x$ is in $\cup_{i \in I} B \setminus A_{i}$. Then since $x$ is in the union over all $i$, that means for some $i$, $x$ is in $B \setminus A_{i}$. This means for some $i$, we have $x$ is in $B$ and $x$ is not in $A_{i}$. But if $x$ is not in $A_{i}$ for some $i$, then $x$ can't be in $\cap_{i \in I} A_{i}$. But we still have $x$ is in $B$.. – layman Dec 01 '16 at 00:43
  • @maybedave (continued..) so since we have $x$ is in $B$ and $x$ is not in $\cap_{i \in I} A_{i}$, then that means $x$ is in $B \setminus \cap_{i \in I} A_{i}$, which is what we needed. – layman Dec 01 '16 at 00:44
  • I really appreciate the help but to be honest, there is logic in your proof that I'm just not following. If it were broken down more and converted to math symbols I would have an easier time with it. I will have to just take this back and digest it more. Thanks again! – maybedave Dec 01 '16 at 16:52
  • @maybedave It's just my opinion, but you should really be reading the math symbols in plain English anyway. In my personal opinion, you will have a much easier time understanding proofs, and proving things on your own, if you understand them in plain language rather than using math symbols. The math symbols won't help you, and really they only exist so we can write a lot of words on the board with ease. In any case, let me try to adapt the proof in my last comment into math symbols, and post it as a follow up comment to this comment. Please consider my advice though. – layman Dec 01 '16 at 16:57
  • @maybedave Earlier proof restated: Suppose $x \in \cup_{i \in I} (B \setminus A_{i})$. Then $(\exists i \in I)[x \in B \setminus A_{i}]$. Then $x \in B \land (\exists i \in I)[x \not \in A_{i}]$. Then $x \in B \land x \not \in \cap_{i \in I} A_{i}$. Then $x \in B \setminus [\cap_{i \in I} A_{i} ]$, as desired. – layman Dec 01 '16 at 16:58
  • @maybedave If you're anything like me, then you might need the right person to explain this to you in person. I think seeing the proof done on a board and explained step by step by someone that knows how to communicate the key ideas would be extremely beneficial for you. – layman Dec 01 '16 at 17:01
  • 1
    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! – maybedave Dec 02 '16 at 13:50
  • @user46944 "When writing a proof you should use as many real world words as possible and as few math symbols as possible." This is debatable (and debated), and this doesn't hold true for me: for me, a 'wordy' proof is often more difficult to follow. As references for a more 'formal' style, see Dijkstra's "The notational conventions I adopted, and why" (EWD1300), which among other thing advocates "to let the symbols do the work —more precisely: as much of the work as profitability possible—." (Also see my answer here.) – MarnixKlooster ReinstateMonica Dec 03 '16 at 18:10
  • @MarnixKlooster I said what I said from a pedagogical point of view. Math symbols are just shorthand. When one does math, they translate the math symbols into English (or another language) words because we need to interpret the math that's being written in normal language. When you see the $\exists$ symbol, you read it as "there exists". That's what I meant when I told OP about the proof writing in real world words. If he's not writing it in real world words, at least he should be thinking about it in that way. – layman Dec 03 '16 at 21:43
  • At User46944. Ok, so here is where I do not follow the given proof in math symbols. We can’t really say (∃i∈I)[x∈B\Ai] is equivalent to x∈B^(∃i∈I)[x∉Ai]. Its either that or I’m computing it wrong but I don’t think I am. Here is the computation: – maybedave Dec 06 '16 at 23:56
  • B = {1,3} and F = {{1,2},{1,3,4}}. To compute (∃i∈I)[x∈B^x∉Ai] we first find x∈B^x∉Ai which produces family set {{3},{null}}. Then the union of the resulting family set (∃i∈I)[x∈B^x∉Ai] = {3} Now…to compute x∈B^(∃i∈I)[x∉Ai] we first find (∃i∈I)[x∈Ai] which is {1,2,3,4} and then we subtract this set from B to compute x∈B^(∃i∈I)[x∉Ai] = {1,2}{1,2,3,4} = {null}. So we can see that the first set {3} does not equal {null}. – maybedave Dec 06 '16 at 23:57
  • This is why I haven't been able to write this proof. Why doesn't this computation work? – maybedave Dec 06 '16 at 23:58
  • @maybedave I had a little trouble following your logic. First off, when you use the word "compute," I am interpreting what you mean as "find the $x$ such that". So let's "compute" $(x \in B) \land (\exists i \in I)[x \not \in A_{i}]$. You said to do this, we first compute $(\exists i \in I)[x \in A_{i}]$ and then remove those from $x \in B$. This is faulty logic. Here is a rule of logic that you are missing: the negation of "there exists" ($\exists$) is "for all" ($\forall$). Also, the negation of "for all" ($\forall$) is "there exists" ($\exists$). – layman Dec 07 '16 at 02:33
  • @maybedave So, to "compute" $(x \in B) \land (\exists i \in I)[x \not \in A_{i}]$, you can first compute $(\forall i \in I)[x \in A_{i}]$, which will be ${1,2}$, Then you can remove this from $x \in B$, and you are left with ${3 }$. :) – layman Dec 07 '16 at 02:34
  • Be very happy that you are not in the same room with me or I would probably hug you. Thank you! This is exactly what has been messing me up! Thank you! – maybedave Dec 07 '16 at 21:59
  • @maybedave You're welcome! :) – layman Dec 07 '16 at 22:04
1

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.

MarnixKlooster ReinstateMonica
  • 5,576
  • Very Very Helpful! Thank you! – maybedave Dec 02 '16 at 13:50
  • 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! – maybedave Dec 06 '16 at 22:53