# Homework Help: Abstract Algebra, first Proof

1. Sep 6, 2008

### rocomath

Abstract Algebra, first Proof :(

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

http://img329.imageshack.us/img329/2636/abstract001sq3.jpg [Broken]

http://img329.imageshack.us/img329/7108/abstract002ym3.jpg [Broken]

Def U = Definition of Universe

UQ = Universal Quantification

Last edited by a moderator: May 3, 2017
2. Sep 7, 2008

### CompuChip

Re: Abstract Algebra, first Proof :(

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.

3. Sep 7, 2008

### HallsofIvy

Re: Abstract Algebra, first Proof :(

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.

4. Sep 7, 2008

### d_leet

Re: Abstract Algebra, first Proof :(

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.

5. Sep 7, 2008

### rocomath

Re: Abstract Algebra, first 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.

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

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) ... :-\

6. Sep 7, 2008

### CompuChip

Re: Abstract Algebra, first Proof :(

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

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

Good luck, looking forward to your attempt.

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

7. Sep 7, 2008

### CompuChip

Re: Abstract Algebra, first Proof :(

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.

8. Sep 7, 2008

### HallsofIvy

Re: Abstract Algebra, first Proof :(

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

9. Sep 8, 2008

### rocomath

Re: Abstract Algebra, first Proof :(

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

10. Sep 8, 2008

### rocomath

Re: Abstract Algebra, first Proof :(

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

11. Sep 8, 2008

### CompuChip

Re: Abstract Algebra, first Proof :(

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