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

Indirect Proof (Logic question)

  1. Sep 18, 2005 #1
    Hi all,

    I've got a question about indirect proof, whether I have understood it correctly:

    a) Suppose I want to show A=>B, where A and B are two statements.

    In the method of indirect proof I assume that [tex]\neg B[/tex] (not B) is true and use the given statement A to show a contradiction. Therefore, B must be true (because either B or [tex]\neg B[/tex] is true).

    In short what I do:
    [tex]\neg B[/tex] true (assumption) and A true (given statement) => contradiction

    Is that correct?

    b) Now another question:
    Suppose I assume B is true (instead of [tex]\neg B[/tex] true) and use the given statement A such that it leads to a true statement like 1=1.
    Have I showed anything with that?

    In short what I do here:
    B true (assumption) and A true (given statement) => no contradiction.
    But that doesn't tell me anything, right?
  2. jcsd
  3. Sep 18, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    If you assume:

    1) ~B
    2) A

    and derive a contradiction, then you will have proven that A & ~B is false, i.e. you will have proven ~(A & ~B), which is equivalent to (A => B).

    For part b), no that's useless. First of all, you can derive a true statement like 1=1 from the contradictory premises as well. There's a difference between deriving something that isn't a contradiction, and proving that no contradiction can be derived whatsoever. You can derive 1=1 from anything, in fact you can derive 1=1 from nothing - it is a theorem.
  4. Sep 20, 2005 #3
    Thanks for you answer.

    Is that a theorem proven in logic? Or is it an axiom?

    Is (A => B) <=> (~B => ~A) an axiom?
  5. Sep 20, 2005 #4


    User Avatar
    Gold Member

    What do => and <=> mean to you? Is (A => B) a statement that can be either true or false? Or does (A => B) mean that (A -> B) is always true?
  6. Sep 20, 2005 #5


    User Avatar
    Science Advisor
    Homework Helper

    Those are both theorems, unless honestrosewater wants to add something about the difference between -> and =>. As far as mathematicians and others who do math are concerned, the symbols can be used interchangeable, and we're normally not concerned with whether our conditional is technically a material conditional or necessary conditional.
  7. Sep 21, 2005 #6


    User Avatar
    Gold Member

    No, if the difference isn't the source of the confusion, I have nothing to add. :smile:

    Eh, except that I don't know what 'an axiom or theorem of logic' is anymore than I know what 'an axiom or theorem of math' is. Even 'an axiom or theorem of classical propositional calculus' doesn't narrow it down enough for me to say whether a certain statement is an axiom or theorem, as there are several different versions of the so-called 'classical propositional calculus' (some of which don't even have any axioms). And if => denotes logical (or necessary) implication, you're talking about the metatheory, which isn't even usually set down explicitly and I imagine can be different even for the same object theory. And IMO, whether a certain statement is an axiom or theorem isn't even of much importance outside of a particular calculus, as you can adopt any theorem as an axiom and can derive the same set of theorems from different sets of axioms. Anywho, if you guys know what you're talking about, don't let me get in the way. :smile:
  8. Oct 11, 2005 #7


    User Avatar
    Science Advisor

    Strictly speaking, that's wrong. What you show is not that B is true but rather than A implies B.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook