Can the Rule of Simplification be Applied to Not (P and Q)?

[rocomath]

Abstract Algebra, first Proof :(

I really want to do well in this class! :)

http://img329.imageshack.us/img329/2636/abstract001sq3.jpg

http://img329.imageshack.us/img329/7108/abstract002ym3.jpg

Def U = Definition of Universe

UQ = Universal Quantification

 

[CompuChip]

First of all, how do you "simplify" from $$\neg(x \in B \wedge x \in A)$$ to $$\neg(x \in A)$$? If it is not true that x is in both, it does not mean it isn't in just one of them.
Secondly, even if this conclusion was valid, why didn't you just draw it from $$\neg(x \in A \wedge x \in B)$$ but took a lot of steps to rewrite that to $$\neg(x \in B \wedge x \in A)$$?
Finally, how is this an indirect proof? For me, an indirect proof is assuming the negation (i.e. $$A \cap B \not\subset A$$, so there is an x in the intersection on the left hand side which is not in the set on the right hand side) and showing a contradiction.

I really do think a direct proof is easier here. Assume that $$x \in A \cap B$$ and show that $$x \in A$$. It's almost trivial.
If you insist on indirect proof, please review the structure of an indirect proof.

 

[HallsofIvy]

First of all, how do you "simplify" from $$\neg(x \in B \wedge x \in A)$$ to $$\neg(x \in A)$$? If it is not true that x is in both, it does not mean it isn't in just one of them.

It certanly is true that if x is not in $B\cap A$ then x is not in A. It happens to also be true that x is not in B but if you don't need that it is not necessary to say it.

Secondly, even if this conclusion was valid, why didn't you just draw it from $$\neg(x \in A \wedge x \in B)$$ but took a lot of steps to rewrite that to $$\neg(x \in B \wedge x \in A)$$?
Finally, how is this an indirect proof? For me, an indirect proof is assuming the negation (i.e. $$A \cap B \not\subset A$$, so there is an x in the intersection on the left hand side which is not in the set on the right hand side) and showing a contradiction.

I really do think a direct proof is easier here. Assume that $$x \in A \cap B$$ and show that $$x \in A$$. It's almost trivial.
If you insist on indirect proof, please review the structure of an indirect proof.

 

[d_leet]

It certanly is true that if x is not in $B\cap A$ then x is not in A. It happens to also be true that x is not in B but if you don't need that it is not necessary to say it.

That isn't true, if A={1,2,3,4,5} B={2,4,6} then 3 is not in $B\cap A$, but it is definitely in A.

 

[rocomath]

First of all, how do you "simplify" from $$\neg(x \in B \wedge x \in A)$$ to $$\neg(x \in A)$$? If it is not true that x is in both, it does not mean it isn't in just one of them.
Secondly, even if this conclusion was valid, why didn't you just draw it from $$\neg(x \in A \wedge x \in B)$$ but took a lot of steps to rewrite that to $$\neg(x \in B \wedge x \in A)$$?
Finally, how is this an indirect proof? For me, an indirect proof is assuming the negation (i.e. $$A \cap B \not\subset A$$, so there is an x in the intersection on the left hand side which is not in the set on the right hand side) and showing a contradiction.

I really do think a direct proof is easier here. Assume that $$x \in A \cap B$$ and show that $$x \in A$$. It's almost trivial.
If you insist on indirect proof, please review the structure of an indirect proof.

I'm only allowed to use an Indirect Proof for this problem. I can see why you said I had too many steps, but this is my first Proof ever and I'm encouraged to write out all my steps even if they're obvious.

It certanly is true that if x is not in $B\cap A$ then x is not in A. It happens to also be true that x is not in B but if you don't need that it is not necessary to say it.

As Hall's said, I used the rule of Simplification, p^q=>p.

That isn't true, if A={1,2,3,4,5} B={2,4,6} then 3 is not in $B\cap A$, but it is definitely in A.

I'm not allowed to use numbers :-\

I'm going to work it again, are my other problems okay? I only got a comment for (b) ... :-\

 

[CompuChip]

I'm only allowed to use an Indirect Proof for this problem. I can see why you said I had too many steps, but this is my first Proof ever and I'm encouraged to write out all my steps even if they're obvious.

OK, so you should start by: Assume that not $A \cap B \subset A$ and try to derive a contradiction. To get you started: you can go from that assumption to $\exists x \in A \cap B \text{ such that } x \not\in A$ (it will take some proof though, using UQ).

As Hall's said, I used the rule of Simplification, p^q=>p.

But you used it to conclude ~p from ~(p^q) which is not true. For example, if p is the statement "2 is even" and q is the statement "2 is odd" then clearly p and q are not both true, so ~(p^q). But you cannot conclude ~p, e.g.: 2 is not even.

I'm not allowed to use numbers :-\

I think the example with the numbers was to give a counterexample. That is, to show an inference rule you used is wrong (or, actually, you used it in a wrong way).

I'm going to work it again

Good luck, looking forward to your attempt.

are my other problems okay? I only got a comment for (b) ... :-\

That was the easiest part, because it was obviously wrong (sorry ). The other ones look OK, though I haven't looked at them very closely (yet).

 

[CompuChip]

I also looked at the other ones.
Why did you use the commutativity rule in d?
In e, you are making some implicit steps in the first line. That's no problem, but since you want to be rigorous, you might want to add them. I would say that, in the first place, x in A \ (B u C) means x in A and x not in (B u C). Then you have that: x not in (B u C) = not (x in (B u C)) = not(x in B and x in C) = (not x in B) or (not x in C) = (x not in B) or (x not in C).

So you have a small redundancy in d and you were a bit quick in e. But technically speaking, everything you did is correct.

As a small point, let me add, that to prove the equality of sets you should prove inclusion both ways. So if A = B you should have a proof: Let x in A, then [...] so x in B, and: Let x in B, then [...] so x in A. So A is a subset of B and vice versa: they are equal. You didn't really do this explicitly, but all the steps you used in your proof work both ways. So though it is correct, you might want to think about that for a second... you might encounter proofs later where this is not true and you need to have a different proof for the one inclusion than for the other way.

 

[HallsofIvy]

That isn't true, if A={1,2,3,4,5} B={2,4,6} then 3 is not in $B\cap A$, but it is definitely in A.

Oops! For some reason I had reversed the statement in my head.

 

[rocomath]

Oh man my head hurts! I'm working on it now since I was working all weekend, I'll post my 2nd attempt tonight since I'm at school with no scanner. Thanks for all your help!

 

[rocomath]

Is the reason why I can't derive not p from not p and q bc the rule of simplification is for Tautologies?

 

[CompuChip]

The rule of simplification works if you have (some statement) AND (some other statement). So, for example, you can derive "not p" from "(not p) and q".

You cannot use it for "not (p and q)", however. You can show that this statement is equivalent to "(not p) or (not q)", which is not of the form required for the rule of simplification. In this case, you can only derive "not p" if you know that "not not q" (i.e., if q). As an intuitive argument: If it is always either rainy, or sunny then you cannot just conclude that it is rainy. But if you also have given that it is not sunny, then it must be rainy. Replace rainy and sunny by "not p" and "not q" respectively...