Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In specific how can I setup a contradiction proof if $3n+2$ is odd then $n$ is odd? I don't want the answer. I just want to know how to set up the proof by contradiction.

I think that I should assume if $3n+2$ is not odd, then $n$ is even then prove that $n$ is in fact odd.

I am unsure of what to assume and what do I prove. I am trying to teach a class you can do the same proof in many different ways.

I know how to prove with a direct proof. Assume $3n+2=2k+1$ and prove $n=2J+1$

I know how to prove with a contrapositive proof. Assume $n=2J$ and prove $3n+2=2k$

How would I do the same setup for a contradiction proof?

share|improve this question
1  
Step 1: If $3n+2$ is not odd (=even), then $3n$ is? –  1015 Mar 5 '13 at 18:02
    
Assume 3n+2 is even, and then prove 3n is odd. –  Whitecat Mar 5 '13 at 18:03
1  
If $x$ is even, then $x-2$ is? –  1015 Mar 5 '13 at 18:04
    
If $x$ is even then $x-2$ must be even also. –  Whitecat Mar 5 '13 at 18:07
    
But how do I set it up? Assume $3n+2$ is not odd and then contradict that it is odd? –  Whitecat Mar 5 '13 at 18:09
show 1 more comment

3 Answers

up vote 6 down vote accepted

For a proof by contradiction, you assume the truth of the premise and the negation of the desired conclusion to obtain a contradiction:

"$3n+2$ is odd then $n$ is odd"

Assume both

(1) $3n + 2$ IS odd, and hence, there $3n + 2 = 2k+1$ for some integer $k$.
(2) $n$ is even, that is, there is some integer $m$ such that $n = 2m$.

From these assumptions, you obtain a contradiction, from which you conclude that the negation of both $(1)$ and $(2)$ entails the affirmation of the statement to be proved:

That it must follow that if $3n+2$ is odd, then $n$ is odd.


In general, a proof by contradiction proceeds as follows:

Prove: $\;p\rightarrow q$.

Assume $\;\lnot (p \rightarrow q) \equiv \lnot(\lnot p \lor q) \equiv (p \land \lnot q)$.

Derive a contradiction.

Conclude $\;\lnot \lnot (p \rightarrow q) \equiv (p\rightarrow q)$, as desired.


Added:

For a general discussion about how the differences and similarities between the two proof strategies, you might want to read an earlier MSE post:

share|improve this answer
    
This makes much more sense with my knowledge of logic. I am a little confused as to Deriving the contradiction. Can I say with the assumption if we have $n = 1$ Then $1$ is true and $2$ is false $\therefore$ we have a contradiction and we can conclude what you wrote at the end? –  Whitecat Mar 5 '13 at 18:42
1  
$\quad$ You can work it out algebraically. You want a "general" contradiction, not a specific counterexample. Work at is a little: remember each term has $n$ in common. If n = 2m, then 3n + 2 = 3(2m) + 2 = 2k+1 for some integers m, k $\implies$ ? See how it goes, and if you get stuck, post a comment and I'll work with you. –  amWhy Mar 5 '13 at 18:49
    
Nice Amy :^D.... –  B. S. Mar 5 '13 at 18:50
    
I just followed your hint and substitution and showed $3(2m) + 2 = 2(3m+1) = 2j$ is even, and derived the contradiction. –  Whitecat Mar 5 '13 at 18:59
1  
Exactly! Good for you! Since, by assumption, we have $3(2m) + 2 = 2k + 1 \implies 2(3m+1) = 2k + 1 \implies 2j = 2k + 1,$ for integers k, j, we have a contradiction, since there's no way that $2j = 2k+1,$ because 2 divides the left hand side, but not the right hand side (or there's no way an even number can equal an odd number.) Feels good, doesn't it, to "crack" a proof? –  amWhy Mar 5 '13 at 19:04
show 1 more comment

Hint: You are trying to prove $3n+2$ odd $\implies\ \ n$ odd. So assume the falsity of this statement, which means $3n+2=2k+1$ for some integer $k$ and $n=2m$ for some integer $m$. Now how can you manipulate $n=2m$ to make it look like the other and find a contradiction?

share|improve this answer
    
I think this is a perfect answer on how to set up the problem. –  Whitecat Mar 5 '13 at 18:20
    
The proof is $p \rightarrow q$ so I want to do contradiction $p \rightarrow \sim q$ But is that wrong? It seems like this contradiction setup is $\sim p \rightarrow q$ –  Whitecat Mar 5 '13 at 18:25
    
You need to assume the truth of the premise AND the negation of the conclusion: Assume $p \land \lnot q$. Whitecat: see my answer for clarification of what I mean. –  amWhy Mar 5 '13 at 18:35
    
@Whitecat: the negation of $p \rightarrow q$ is $p \wedge \sim q$, not $p \rightarrow \sim q$. If $p$ is false, then both $p \rightarrow q$ and $p \rightarrow \sim q$ are true. –  Ross Millikan Mar 5 '13 at 18:36
1  
@Whitecat: no problem. amWhy's answer is a good one. –  Ross Millikan Mar 5 '13 at 19:17
show 4 more comments

With contradiction, I think you should assume $n$ is even, i.e., $n = 2k$, then prove that $3n + 2 = 6k + 2$ is even, which contradicts the fact that $3n + 2$ is odd.

To prove $p\rightarrow q$, you prove that $\;\lnot q \rightarrow\lnot p$. And you say since we have already assumed $p$, we can't have $\lnot q$, because $\;\lnot q \rightarrow\lnot p$. Therefore, you have $q$. That is to say, $p\rightarrow q$.

share|improve this answer
    
That is proving the contrapositive, which is a bit different than proof by contradiction. They are similar, but distinct. See the link in my answer for a more elaborate discussion of the distinction. –  amWhy Mar 6 '13 at 4:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.