Results 1 to 7 of 7

Math Help - Is this proof correct?

  1. #1
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200

    Is this proof correct?

    I found a Abstract algebra book in goodwill

    I can not get how do prove something. It seems almost impossible in some cases.
    This is a question in it:

    Prove : (A\cap B)'= A' \cup B'

    Where n'=U\setminus n

    and U is the universal set.

    Here is my attempted proof:
    (A \cap B)'  \Rightarrow
    x\in (U\setminus (A\cap B)  \Rightarrow
    (x\in U) \wedge (x\notin (A\cap B))  \Rightarrow
    (x\in U) \wedge (x\notin A \wedge x\notin B)  \Rightarrow
    (x\in U \wedge x\notin A) \vee  (x\in U \wedge x\notin B)  \Rightarrow
    (x\in (U \setminus A) \vee x\in(U\setminus B)  \Rightarrow
    x\in (U\setminus A \cup U\setminus B)  \Rightarrow
    x\in A' \cup B'

    \therefore\,\, A'\cup B' \subseteq (A\cap B)'

    And the reverse is true. Therefore they must be equal.
    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Not all the steps are correct.

    Your first step needs to be

    x\in(A \cap B)'\Rightarrow...

    Also,
    x\not\in(A\cap B) implies
    (x\not\in A)\vee(x\not\in B), not
    (x\not\in A)\land(x\not\in B).
    That's essentially a DeMorgan Law application. You fix this error, incidentally, in the next step.

    Also, you should be more careful with your parentheses here:
    x\in (U\setminus A \cup U\setminus B).
    In context, I can tell that you meant
    x\in ((U\setminus A) \cup (U\setminus B)),
    but you don't want to write so that people can understand. Write so that no one can misunderstand!

    All your steps are reversible, correct? So just change your implications to double implications, and you can then omit the sentence "And the reverse is true." (You mean converse, by the way.)

    As Strunk and White have told us, "Omit needless words!"
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200
    How does x\notin (A \cap B) \Rightarrow (x\notin A) \vee (x\notin B)? A \cap B is the intersection so you would say A and B are true, else it is false. Thus logical conjunction :" \wedge"
    Last edited by integral; July 20th 2010 at 07:18 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    Except that you are negating the whole thing. You're essentially saying this:

    \neg(x\in(A\cap B)), which is the same as
    \neg((x\in A)\land(x\in B)), which is the same as
    (\neg(x\in A))\vee(\neg(x\in B)), which is the same as
    (x\not\in A)\vee(x\not\in B).

    Does that make sense?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    Posts
    289
    Hi, I will try prove this using pure logic notation.

    To prove (A \cap B)' = A' \cup B' we need to show the following to be true:

    1. If x \in A' \cup B' then x \in (A \cap B)'

    and

    2. If x \in (A \cap B)' then x \in A' \cup B'

    Now I will show you how to prove 1. You can try 2. yourself

    Let p: x \in A' \cup B' and q : x \in (A \cap B)' now 1. becomes p \to q

    To prove this conditional proposition is true we will now go through all the possibilities. If p is false, then p \to q is vacuously true. We can ignore this trivial case.

    Thus we need to show if p is true and q is true then p \to q is true.

    Assume p is true.

    p: x \in A' \cup B' = (x \in A') \lor (x \in B')

    Now p is only true under 3 conditions: (using the 'inclusive-or' definition we have)

    a) (x \in A') is true and (x \in B') is false

    b) (x \in A') is false and (x \in B') is true

    c) (x \in A') is true and (x \in B') is true

    Now notice in a) (x \in A') = \neg (x \in A)

    So if \neg(x \in A) is true then x \in A is false. Similarly x \in B is true.

    Likewise from b) you should conclude x \in A is true and x \in B is false.

    c) x \in A is false and x \in B is false.

    Now consider q: x \in (A \cap B)' = \neg[x \in (A \cap B)] = \neg[(x \in A) \land (x \in B)]

    Using the results from a), b) and c) we see q is always true. Thus 1. is now proven.

    Try 2. with the same principles
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member integral's Avatar
    Joined
    Dec 2009
    From
    Arkansas
    Posts
    200
    Oh! I get it!.

    I was thinking of OR as XOR.

    If we use OR then the elements could be in the location AND is.

    Proving that ( A intercect B)' is a subset. And once we prove the converse, we prove they are equal.


    Right?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I'm not sure I follow this post. Are you referring to usagi_killer's proof in post # 5?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 11th 2010, 12:13 PM
  2. Is this proof correct?
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 8th 2010, 02:34 PM
  3. lcm, gcd proof correct?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2010, 06:32 AM
  4. Proof of n^5 = n mod 5 .. is this correct?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 9th 2006, 08:24 PM
  5. Is proof correct?
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 13th 2006, 10:35 AM

Search Tags


/mathhelpforum @mathhelpforum