Results 1 to 14 of 14

Math Help - Proof (A-B)'=B'-A'

  1. #1
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318

    Proof (A-B)'=B'-A'

    I want to prove or disprove (A-B)'=B'-A'.
    So, let x be an element of (A-B)'
    Then x is not an element of A-B

    This is where I get confused...
    Do I say x is an element of A', x is an element of -B'?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2008
    Posts
    39
    Quote Originally Posted by kathrynmath View Post
    I want to prove or disprove (A-B)'=B'-A'.
    So, let x be an element of (A-B)'
    Then x is not an element of A-B

    This is where I get confused...
    Do I say x is an element of A', x is an element of -B'?

    I F xε(A-B) <====> xεA & ~xεB.

    Hence ~xε(A-B) <======> ~(xεA & ~xεB) <=====> ~xεA v xεB BY de morgan. WHICH is equivalent to xεA====> xεB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Quote Originally Posted by poutsos.B View Post
    I F xε(A-B) <====> xεA & ~xεB.

    Hence ~xε(A-B) <======> ~(xεA & ~xεB) <=====> ~xεA v xεB BY de morgan. WHICH is equivalent to xεA====> xεB
    Is there a way to do this proof without the ~? I don't know but that's making it harder for me. So, is this a contradiction? I did it by venn diagrams and it wasn't equal.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by kathrynmath View Post
    Is there a way to do this proof without the ~? I don't know but that's making it harder for me. So, is this a contradiction? I did it by venn diagrams and it wasn't equal.
    I agree that that is not very helpful!
    Mathematicians usually hate such proofs done with logic.
    You ought to know that the statement is formal false.

    Counterexample:
    \begin{gathered}<br />
  U = \left\{ {1,2,3,4,5} \right\},\,A = \left\{ {1,3,4,5} \right\}\,\& \,B = \left\{ {2,3,5} \right\} \hfill \\<br />
  \left( {A\backslash B} \right)^\prime   = \left( {\left\{ {1,4} \right\}} \right)^\prime   = \left\{ {2,3,5} \right\} \hfill \\<br />
  B'\backslash A' = B' \cap A = \left\{ {1,4} \right\} \hfill \\ <br />
\end{gathered}

    BTW: We use this \left( {A - B} \right) = \left( {A\backslash B} \right) it is called "setminus".
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Quote Originally Posted by Plato View Post
    I agree that that is not very helpful!
    Mathematicians usually hate such proofs done with logic.
    You ought to know that the statement is formal false.

    Counterexample:
    \begin{gathered}<br />
U = \left\{ {1,2,3,4,5} \right\},\,A = \left\{ {1,3,4,5} \right\}\,\& \,B = \left\{ {2,3,5} \right\} \hfill \\<br />
\left( {A\backslash B} \right)^\prime = \left( {\left\{ {1,4} \right\}} \right)^\prime = \left\{ {2,3,5} \right\} \hfill \\<br />
B'\backslash A' = B' \cap A = \left\{ {1,4} \right\} \hfill \\ <br />
\end{gathered}

    BTW: We use this \left( {A - B} \right) = \left( {A\backslash B} \right) it is called "setminus".
    Ok, that helps a little more, but I'm trying to do a formal proof without numbers. I'm trying to figure out what to say if I let x be an elemnt of (A-B)'. This is the correct way to start, right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Quote Originally Posted by kathrynmath View Post
    Ok, that helps a little more, but I'm trying to do a formal proof without numbers. I'm trying to figure out what to say if I let x be an elemnt of (A-B)'. This is the correct way to start, right?
    if I say x is an element of (A-B)', could I saw x is an elemnt of B becuase x is an element of not (A-B), so x must be an element of B. Am I on the right track?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by kathrynmath View Post
    Ok, that helps a little more, but I'm trying to do a formal proof without numbers.
    That is impossible!
    One cannot do a formal proof of a false statement (not in mathematics anyway).
    All we do is give a counterexample in the statement is shown to be false.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    Quote Originally Posted by Plato View Post
    That is impossible!
    One cannot do a formal proof of a false statement (not in mathematics anyway).
    All we do is give a counterexample in the statement is shown to be false.
    can't you do a formal proof and show that it equals something else, thus a contradiction?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    You need to have a sit down with a live tutor and discuss your confusion about proofs. When it says, “prove or disprove”, you are to give a formal proof if it is a true statement or give a counterexample if it is false.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Apr 2008
    From
    Vermont
    Posts
    318
    That's just how my teacher taught us.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by kathrynmath View Post
    That's just how my teacher taught us.
    i assure you, that is not what your teacher taught. as Plato said, to disprove something, all you have to do is give a counter-example. if you can find one instance where a claim is false, then the claim is considered false in general. anything else is just giving yourself ideas as to why something might be false. as you said, you drew Venn Diagrams and found that the claim might not be true. so then you know you should start looking for a counter-example. you could also notice that the left hand side, using the defintion of set minus and DeMorgan's laws, simplifies to \neg A \cup B, which is not equal to the other side.

    these are not proofs that the claim is false, however, to disprove something, you must give a counter example
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by kathrynmath View Post
    That's just how my teacher taught us.
    What does "how" mean?
    I do not follow what this response means.
    Are you saying that your teacher thinks that there is a formal proof for a false statement?
    It is a very say fact that many mathematics teachers are not really train in mathematics.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Oct 2008
    Posts
    39
    Quote Originally Posted by kathrynmath View Post
    Ok, that helps a little more, but I'm trying to do a formal proof without numbers. I'm trying to figure out what to say if I let x be an elemnt of (A-B)'. This is the correct way to start, right?


    To have that (A-B)' IS equal to B'-A' THIS must hold for all A AND B.

    However if this equality does not hold then there must be an A or B or both such that :


    (A-B)' IS not equal to B'-A' AND Plato already gave you an example.


    Perhaps an example not using Nos is the following:


    Let B= Φ ( the empty set), and if substitute Φ ΙΝ (Α-Β)' we have:


    ( A-Φ)'= (A)'= A' BECAUSE A-Φ=Α.Αnd substituting Φ in B'-A' we have:


    Φ'-A' = U- A' =A BECAUSE Φ'=U WHERE U is the set of which A, B are subsets.

    Hence we have A'= A NOT true.


    But we can give a proof in propositional calculus without using a counter example by the following procedure:


    Let xε( A-B)' <===> ~xεΑ v xεB as it was shown


    Let xε(B'-A') <===> ~xεB & ~xεA' <====> ~xεB & xεA.


    Now put xεA=p and xεB=q. So if we want (A-B)' = B'-A' W must have ,by the axiom of extensionality :


    xε(A-B)' <====> xε(B'-A') or ~xεΑ v xεB <=====>~xεB & xεA or


    ~p v q <=====> p & ~q which means that ~p vq logicaly implies p & ~q and p & ~q logicaly implies ~p v q,which means that ;


    The conditional ~p v q ------> p & ~q must be a tautology and,



    The conditional p & ~q ------->~p v q must also be a tautology.


    Now by forming the true tables of the above we see that none of the above is a tautology.


    Now by a theorem in propositional logic that states:



    A formula is a theorem ( hence provable ) of the propositional logic if and only if it is a tautology.

    And the fact that the above two conditionals are not tautologies we conclude:


    ~p v q <=====> p & ~q is not provable ,hence xε(A-B)' <====> xε(B'-A') is not provable and ,



    (A-B)' Is not equal to B'-A'


    Note ~xεΑ x does not belong to A, AND ~p means not p
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by poutsos.B View Post
    To have that (A-B)' IS equal to B'-A' THIS must hold for all A AND B.

    However if this equality does not hold then there must be an A or B or both such that :Let B= Φ ( the empty set), and if substitute Φ ΙΝ (Α-Β)' we have:
    ( A-Φ)'= (A)'= A' BECAUSE A-Φ=Α.Αnd substituting Φ in B'-A' we have:
    Φ'-A' = U- A' =A BECAUSE Φ'=U WHERE U is the set of which A, B are subsets.
    Hence we have A'= A NOT true.
    But we can give a proof in propositional calculus without using a counter example by the following procedure:
    Let xε( A-B)' <===> ~xεΑ v xεB as it was shown
    Let xε(B'-A') <===> ~xεB & ~xεA' <====> ~xεB & xεA.
    Now put xεA=p and xεB=q. So if we want (A-B)' = B'-A' W must have ,by the axiom of extensionality :
    xε(A-B)' <====> xε(B'-A') or ~xεΑ v xεB <=====>~xεB & xεA or
    ~p v q <=====> p & ~q which means that ~p vq logicaly implies p & ~q and p & ~q logicaly implies ~p v q,which means that ;
    The conditional ~p v q ------> p & ~q must be a tautology and,
    The conditional p & ~q ------->~p v q must also be a tautology.
    Now by forming the true tables of the above we see that none of the above is a tautology.
    Now by a theorem in propositional logic that states:
    A formula is a theorem ( hence provable ) of the propositional logic if and only if it is a tautology.
    And the fact that the above two conditionals are not tautologies we conclude:
    ~p v q <=====> p & ~q is not provable ,hence xε(A-B)' <====> xε(B'-A') is not provable and ,
    (A-B)' Is not equal to B'-A'
    Note ~xεΑ x does not belong to A, AND ~p means not p
    All of that is truly preposterous. Only a logician could have produced that.
    For a mathematical statement it is totally meaningless.
    I think that is a perfect example why “Symbolic Logic” is dieing as a separate subject.
    The American Symbolic Logic Society meets at the joint meeting of the American Mathematical Society and The Mathematical Association of America. Over the last thirty years I have tried to attend sessions of the Logical Association, but lately the average session has no more that five in attendance
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum