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

Does this constitute a proof

  1. Jul 11, 2007 #1
    Hi. I am new to formal proofs. Is the following a legitimate method for proving this assertion by contradiction.

    Show [tex]A\cap B = \{\} \Leftrightarrow A \subseteq B^c[/tex]

    If [tex]A\cap B \neq \{\} [/tex] then [tex]\exists \ x \ ST \ x \in A \ AND \ x \in B [/tex]

    Since [tex]x \in A \ \ \ A \subseteq B^c \Rightarrow x \in B^c[/tex]

    [tex]\Rightarrow x \in U \ AND \ x \notin B [/tex]

    This is a contradiction and thus no such x exists and therefore

    [tex]A\cap B = \{\} \Leftarrow A \subseteq B^c[/tex]

    is this half the proof?
  2. jcsd
  3. Jul 12, 2007 #2
    Yes, that proof is valid, but it could be cleaned up a bit.

    Either you should state that you are assuming [itex]A \subseteq B^c[/itex] at the beginning of the proof, or simply directly show the contrapositive (which is what you've done - no contradiction there).

    I would write it as follows:

    Assume [itex]A \subseteq B^c[/itex].
    Now suppose [itex]A\cap B \neq \{\}[/itex]. Then there is an [itex]x[/itex] such that [itex]x \in A[/itex] and [itex]x \in B[/itex].
    But, by our assumption, [itex]x \in A[/itex] implies [itex]x \in B^c[/itex], which implies [itex]x \notin B[/itex]. This is a contradiction, so our supposition must be in error. Therefore, [itex]A\cap B = \{\} \Leftarrow A \subseteq B^c[/itex]
  4. Jul 12, 2007 #3
    In your problem, I think the most economical proof is direct, and carried out through a chain of biconditionals.
    Anytime you have a choice between direct proof and any of the indirect methods, the direct method should be taken (unless of course it turns into a nightmare).
  5. Jul 12, 2007 #4
    Here is a go at a direct proof:

    [tex]A\cap B = \{\} \Leftrightarrow \forall x \in U \ \ x \notin A\cap B[/tex]
    [tex]\Leftrightarrow x \in (A\cap B)^c[/tex]
    [tex]\Leftrightarrow x \in A^c\cup B^c[/tex]
    Now suppose [tex]x \in A[/tex] then [tex]x \in B^c[/tex] and
    [tex]\Leftrightarrow A \subseteq B^c[/tex]

    is this correct? is this what you meant by bidirectional fopc?
  6. Jul 13, 2007 #5

    A complete chain of biconditionals in a proof makes the proof "bidirectional".

    Remember these proofs are all about definition. Use the definitons immediately.

    Below is an informal derivation that follows what I've tried to say about the importance of definitions.
    Sorry about notation, but I haven't found time to learn tex stuff.

    Let (x) denote "given any x in U", where U is domain of discussion. ~ denotes "not".
    -> denotes "only if". ' denotes set complement. <-> denotes "if and only if".

    [A intersect B = {}] <->
    (x)[~(x in A and x in B)] <->
    (x)[~(x in A) or ~(x in B)] <->
    (x)[x in A -> ~(x in B)] <->
    [A subset of B'].

    Edit: (correction to poorly worded remarks)
    Certainly, definitions are important and must be used, but equally important are the "identities" of the (presupposed) underlying logic.
    Last edited: Jul 13, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook