Results 1 to 5 of 5

Math Help - Question about proof by contradiction

  1. #1
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1

    Question about proof by contradiction

    Hi all!

    I had a very basic question about the logic behind proof by contradiction.
    Firstly, I am trying to understand the rationale behind proof by contradiction. So, what we do is, negate the statement, assume the hypothesis and also assume the negation of the conclusion, and then reach a contradiction. Once we reach that contradiction, what we've done in essence, is show that the negation of the statement we wanted to prove is false, therefore, the statement itself must be true. Is this correct?

    If this is correct, then please help me clear something up. Say we wanted to prove, by contradiction, a biconditional statement p<=>q. The negation of that is p/\~q \/ ~p/\q. I was taught we only need to show that one of these leads to a contradiction, and the proof is complete. But, since we're trying to show that this is false, wouldn't we need to show that BOTH sides are false? I thought that a disjunction is only false if BOTH sides are false, so wouldn't we need to show that both p/\~q and ~p/\q lead to contradiction in order to show its false, and hence, our original statement is true?

    Thanks for any help!
    James
    Follow Math Help Forum on Facebook and Google+

  2. #2
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,823
    Quote Originally Posted by james121515 View Post
    Hi all!

    I had a very basic question about the logic behind proof by contradiction.
    Firstly, I am trying to understand the rationale behind proof by contradiction. So, what we do is, negate the statement, assume the hypothesis and also assume the negation of the conclusion, and then reach a contradiction. Once we reach that contradiction, what we've done in essence, is show that the negation of the statement we wanted to prove is false, therefore, the statement itself must be true. Is this correct?

    If this is correct, then please help me clear something up. Say we wanted to prove, by contradiction, a biconditional statement p<=>q. The negation of that is p/\~q \/ ~p/\q. I was taught we only need to show that one of these leads to a contradiction, and the proof is complete. But, since we're trying to show that this is false, wouldn't we need to show that BOTH sides are false? I thought that a disjunction is only false if BOTH sides are false, so wouldn't we need to show that both p/\~q and ~p/\q lead to contradiction in order to show its false, and hence, our original statement is true?

    Thanks for any help!
    James
    So, you are saying that the biconditional is the conclusion of an argument? If so, then you'll need to let p be false and q true, and then try to avoid contradiction in the premises with the truth values under each main operator being true. You will then have to let q be false and p be false and the same...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Quote Originally Posted by james121515 View Post
    So, what we do is, negate the statement, assume the hypothesis and also assume the negation of the conclusion, and then reach a contradiction.
    That's correct, though the statement does not need to be an implication. For example, below you are trying to prove a biconditional.

    To prove p by contradiction, we assume ~p and derive a contradiction. This means that we proved ~~p, and therefore p.

    To prove p -> q by contradiction following the scheme above, we assume ~(p -> q), which is p /\ ~q. From this we derive a contradiction, thus proving ~(p /\ ~q), which is (equivalent to) p -> q. Here is another way to describe this: to prove p -> q, we assume p and then prove q by contradiction. I.e., we assume ~q (thus we assumed p and ~q so far), derive a contradiction, getting ~~q, i.e., q. Discharging p, we obtain p -> q.

    Quote Originally Posted by james121515 View Post
    Say we wanted to prove, by contradiction, a biconditional statement p<=>q. The negation of that is p/\~q \/ ~p/\q. I was taught we only need to show that one of these leads to a contradiction, and the proof is complete. But, since we're trying to show that this is false, wouldn't we need to show that BOTH sides are false?
    You are absolutely right . We need to prove that a disjunction p/\~q \/ ~p/\q implies a contradiction. Now, for any formulas a, b, and c, (a \/ b) -> c is equivalent to (a -> c) /\ (b -> c). That's what reasoning by cases means: if we know a \/ b and want to prove c, we need to consider two cases, a and b, and prove c in both of them.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,525
    Thanks
    1384
    Quote Originally Posted by james121515 View Post
    Hi all!

    I had a very basic question about the logic behind proof by contradiction.
    Firstly, I am trying to understand the rationale behind proof by contradiction. So, what we do is, negate the statement, assume the hypothesis and also assume the negation of the conclusion, and then reach a contradiction. Once we reach that contradiction, what we've done in essence, is show that the negation of the statement we wanted to prove is false, therefore, the statement itself must be true. Is this correct?

    If this is correct, then please help me clear something up. Say we wanted to prove, by contradiction, a biconditional statement p<=>q. The negation of that is p/\~q \/ ~p/\q. I was taught we only need to show that one of these leads to a contradiction, and the proof is complete. But, since we're trying to show that this is false, wouldn't we need to show that BOTH sides are false? I thought that a disjunction is only false if BOTH sides are false, so wouldn't we need to show that both p/\~q and ~p/\q lead to contradiction in order to show its false, and hence, our original statement is true?

    Thanks for any help!
    James
    No. The statement "p and q are both true" is false if either of p and q is false.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    Quote Originally Posted by HallsofIvy View Post
    No. The statement "p and q are both true" is false if either of p and q is false.
    I think VonNemo was talking about the disjunction p/\~q \/ ~p/\q. To prove that it is false, one needs to show that both p/\~q and ~p/\q lead to contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by contradiction.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 21st 2011, 11:54 AM
  2. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  3. Proof by Contradiction: (n+2)^3 = n^3 + (n+1)^3 ?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 3rd 2009, 06:04 AM
  4. Proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 1st 2009, 10:10 AM
  5. Proof using contradiction!
    Posted in the Calculus Forum
    Replies: 5
    Last Post: May 20th 2008, 06:59 PM

Search Tags


/mathhelpforum @mathhelpforum