# Homework Help: Proof by contradiction help

1. Mar 23, 2013

### Cole A.

1. The problem statement, all variables and given/known data
Prove that if $x^2 + y = 13$ and $y \neq 4$, then $x \neq 3$.

2. Relevant equations
N.A.

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

The problem I am having is understanding why this is logically valid. Would it be correct to say that, for the statements
\begin{align*} A &: x^2 + y = 13 \\ B &: y = 4 \\ C &: x = 3, \end{align*}
what has been proven is below?
\begin{align*} &(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. \end{align*}

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 $x = 3$ as the contradictory statement when there are actually three statements that were assumed to be true (and thus possible culprits of the contradiction)).

2. Mar 23, 2013

### Infrared

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 $\neq 4$.

You ask why the other assumptions couldn't be the source of the contradiction. We are taking $x^2 + y = 17$ and $y \neq 4$ for granted. After all, the goal of the proof is to show that $\mathbf {if}$ these two statements are true, then $x \neq 4$.

Last edited: Mar 23, 2013
3. Mar 23, 2013

### SammyS

Staff Emeritus
I'm sure that you have a typo.

You mean $\ x \neq 3 .$

4. Mar 24, 2013