1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by contradiction help

  1. Mar 23, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that if [itex] x^2 + y = 13 [/itex] and [itex] y \neq 4 [/itex], then [itex] x \neq 3 [/itex].

    2. Relevant equations

    3. The attempt at a solution
    The proof itself is simple enough: suppose [itex] x^2 + y = 13 [/itex] and [itex] y \neq 4 [/itex]. Suppose for the sake of contradiction that [itex] x = 3 [/itex]. Then
    (3)^2 + y &= 13 \\
    y &= 4.
    But this contradicts the knowledge that [itex] y \neq 4 [/itex]. Therefore, if [itex] x^2 + y = 13 [/itex] and [itex] y \neq 4 [/itex], then [itex] x \neq 3 [/itex].

    The problem I am having is understanding why this is logically valid. Would it be correct to say that, for the statements
    A &: x^2 + y = 13 \\
    B &: y = 4 \\
    C &: x = 3,
    what has been proven is below?
    &(A \wedge \neg B \wedge C) \rightarrow B \\
    \text{which is equivalent to}~ &(A \wedge \neg B) \rightarrow (C \rightarrow B) \\
    \text{which is equivalent to}~ &(A \wedge \neg B) \rightarrow (\neg B \rightarrow \neg C) \\
    \text{which is equivalent to}~ &(A \wedge \neg B \wedge \neg B) \rightarrow \neg C \\
    \text{which is equivalent to}~ &(A \wedge \neg B) \rightarrow \neg C.

    Is this the proper way to think about the validity of proof by contradiction? (Sorry if this is a dumb question, I'm not a mathematician. What I am finding hard to stomach is identifying [itex] x = 3 [/itex] as the contradictory statement when there are actually three statements that were assumed to be true (and thus possible culprits of the contradiction)).
  2. jcsd
  3. Mar 23, 2013 #2
    There is no need to write out the argument in symbolic logic. It works as follows: If x were 3 then y would have to be 4. Since we know that y is not 4, our assumption that x=3 must be false since we obtained an incorrect result with it. Therefore x [itex] \neq 4 [/itex].

    You ask why the other assumptions couldn't be the source of the contradiction. We are taking [itex] x^2 + y = 17 [/itex] and [itex] y \neq 4 [/itex] for granted. After all, the goal of the proof is to show that [itex]\mathbf {if} [/itex] these two statements are true, then [itex] x \neq 4 [/itex].
    Last edited: Mar 23, 2013
  4. Mar 23, 2013 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    I'm sure that you have a typo.

    You mean [itex]\ x \neq 3 . [/itex]
  5. Mar 24, 2013 #4
    @HS-Scientist: Thanks for your answer.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted