Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proofs involving Negations and Conditionals

  1. Feb 11, 2016 #1
    Suppose that A\B is disjoint from C and x∈ A . Prove that if x ∈ C then x ∈ B .

    So I know that A\B∩C = ∅ which means A\B and C don't share any elements.
    But I don't necessarily understand how to prove this. I heard I could use a contrapositive to solve it, but how do I set it up. Which is P and which is Q (for P implies Q, or as the contrapositive: not Q implies not P)?
     
  2. jcsd
  3. Feb 11, 2016 #2

    RUber

    User Avatar
    Homework Helper

    You are looking to prove:
    ## (x \in C) \implies (x \in B) ##
    The contrapositive is:
    ## ( x \notin B) \implies (x \notin C) ##
    Your given (supposed) information will not change.
     
  4. Feb 11, 2016 #3
    So here is what I have:
    If x∉B then x∉C
    So, we can assume x∈A\B and since A\B and C are disjoined, then x∈A\B∩C which is true since x∉C. Would this be correct or is there any error in my logic?
     
  5. Feb 11, 2016 #4

    RUber

    User Avatar
    Homework Helper

    I don't think you can say x∈A\B∩C, since you said above that that was the empty set. And, you should not use "since x∉C", because you are trying to prove this for the contrapositive.

    x is in A. This was given.
    If x is not in B, then, it is in A\B.
    C is disjoint from A\B. This was given.
    x in A\B should tell you what you need to know about C.
     
  6. Feb 12, 2016 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, that is NOT "what you have", it is you are trying to prove.

    Simply that you have assumed what you want to prove!
     
  7. Feb 13, 2016 #6
    I am interested too. I understand that A intersection C would be X. or written as:

    A intersection C = ( X IS AN ELEMENT OF A) AND (X IS AN ELEMENT OF C)

    [ A and NOT B] Intersection C = NULL = [[(X IS AN ELEMENT OF A) AND (X IS NOT AN ELEMENT OF B)]] AND (X IS AN ELEMENT OF C)

    A/B intersection C ^^

    this logical statement, i believe can be expanded below through commutative property to become:


    [[(X IS AN ELEMENT OF A) AND (X IS AN ELEMENT OF C)]] AND [[(X IS NOT AN ELEMENT OF B) AND (X IS AN ELEMENT OF C)]]

    ^^ A intersection C intersection C/B = null set.
    we already know that a intersection C is x..that intersection C AND NOT B is null means that C and NOT B contains x..therefore B contains X?
    http://i.imgur.com/BkaBtjf.png

    http://i.imgur.com/EKkKdFu.png

    o_O sorry I really try to improve my maths
     
    Last edited: Feb 13, 2016
  8. Feb 13, 2016 #7
    is the above post of mine on the right track? ^^
     
  9. Feb 13, 2016 #8

    fresh_42

    Staff: Mentor

    You are basically right but a little too expressive if you avoid the language of symbols.
    First you have to be precise in the wording. NULL is a computer term reserved for, e.g. empty datasets. In mathematics a null set is something different. E.g. a single point as 1 on the line of reals is a null set. So tiny compared to the reals that it cannot be measured. In set theory we say empty set to ∅.

    The proposed way of proving the statement was by contradiction.
    It means that one cannot derive a false statement from a true statement.
    From a false statement you can derive everything. E.g. if ##1 = 0## then for any number ##x## is ##x = x \cdot 1 = x \cdot 0 = 0## which means ##0## is the only number at all, which is false.
    Or you can derive a true statement. E.g. if ##1=0## then ##1=1-0=0-0=0=1##, which is true.

    However from a true statement you can only derive other true statements.

    In the above statement it is given that ##A##\##B ∩ C = ∅## and ##x∈A## and ##x∈C## which is the same as ##x∈A∩C##.
    We need to show that ##x∈B##.
    So if we assume we have an element (##∃## meaning there is) ## x_0∉B## and end up with a false statement, then this assumption could not have been true.
    The essential part is this: ##x_0∈A## (given) and ##x_0∉B## (assumed), i.e. ##x_0∈A##\##B##. But ##x_0∈C## (given) which means ##x_0∈A##\##B∩C.## But this intersection is empty so ##x_0## cannot exist. A contradiction, a false statement.
    Therefore our assumption ##x_0∉B## must have been a false statement, too. This means the opposite of it is true. And the opposite statement is any (##∀## meaning for all) ##x∈B## what we wanted to show.

    The negation of there is (∃) is for all (∀) and vice versa.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proofs involving Negations and Conditionals
Loading...