Is my proof by contradiction valid?

[r0bHadz]

Homework Statement

If 3n+2 is odd, then n is odd

Homework Equations

The Attempt at a Solution

assume 3n+2 is even, show n is odd

3n+2 = 2f => 3n+3 = 2f + 1 => 3(n+1) = 2f+1

so 3*(n+1) is odd form. Only odd*odd gives you another odd, so n+1 is odd. That means n is even.

We have a contradiction here, as shown, n is even, not odd.

Or does this proof method only work if we take the negation of the conclusion? The reason I think my proof is invalid:

(p) (q) (p->q) (p -> ~q) (~p -> q )
0 ff 1 ff 1 ffffff 1 ffffffffffff 1
0 ff 0 ff 1 ffffff 1 ffffffffffff 0
1 ff 0 ff 0 ffffff 1 ffffffffffff 1
1 ff 1 ff 1 ffffff 0 ffffffffffff 1

If we look at the second row, p = 0, q = 0, and the last column, we will see ~p -> q is 0

There is no contradiction here. ~p is 1, and q is 0. This implication will always be zero. My proof that I did above, it did not prove anything that isn't obvious already, thus there was never a contradiction and it was wrong.

What I think I need to do:

Look at the third row, where p = 1, q = 0, p->q = 0. I need to show that the case p->q = 0 cannot happen. Meaning, that there will be a contradiction. P will have to be 0, or q will have to be 1. This is where the contradictions is. I cannot possibly show this contradiction with ~p->q because ~p is 0 which will always give me a truth of one. I can however show this with p->~q because if I can show that the value of this implication is 1, there will be a contradiction.Does my reasoning seem right folks?

 

[fresh_42]

Homework Statement

If 3n+2 is odd, then n is odd

Homework Equations

The Attempt at a Solution

assume 3n+2 is even, show n is odd

3n+2 = 2f => 3n+3 = 2f + 1 => 3(n+1) = 2f+1

so 3*(n+1) is odd form. Only odd*odd gives you another odd, so n+1 is odd. That means n is even.

We have a contradiction here, as shown, n is even, not odd.

This doesn't contradict anything. You have shown that $3n+2$ even implies $n$ even. So?

Or does this proof method only work if we take the negation of the conclusion?

No, these are two different things. Proof by contradiction means, that you have to conclude something wrong, like $1=0$ or similar.
I don't know what you mean by "negation of conclusion". To me it means $\nRightarrow$ but I'm not sure if it does to you, too.

The reason I think my proof is invalid:

(p) (q) (p->q) (p -> ~q) (~p -> q )
0 ff 1 ff 1 ffffff 1 ffffffffffff 1
0 ff 0 ff 1 ffffff 1 ffffffffffff 0
1 ff 0 ff 0 ffffff 1 ffffffffffff 1
1 ff 1 ff 1 ffffff 0 ffffffffffff 1

If we look at the second row, p = 0, q = 0, and the last column, we will see ~p -> q is 0

There is no contradiction here. ~p is 1, and q is 0. This implication will always be zero. My proof that I did above, it did not prove anything that isn't obvious already, thus there was never a contradiction and it was wrong.

What I think I need to do:

Look at the third row, where p = 1, q = 0, p->q = 0. I need to show that the case p->q = 0 cannot happen. Meaning, that there will be a contradiction. P will have to be 0, or q will have to be 1. This is where the contradictions is. I cannot possibly show this contradiction with ~p->q because ~p is 0 which will always give me a truth of one. I can however show this with p->~q because if I can show that the value of this implication is 1, there will be a contradiction.Does my reasoning seem right folks?

I haven't checked your logic tables. Your proof is wrong because you got no contradiction. You simple proved something else. You should take the same prove, avoid the word "assume" and start by $3n+2$ is odd, then $3n+2=2f+1$ and so on.

 

[scottdave]

One problem I have with the way you did it: the problem says "If 3n+2 is odd, then (something must be true)"

I worded as such,becuase you have to prove the (something). But you started out "assume 3n+2 is even". But the problem statement gives no idea of what is supposed to happen when 3n+2 is even.

 

[r0bHadz]

If 3n+2 is odd, then n is odd

3n + 2 is odd, show n is even

3n+2 = 2f+1 => 3n+3 = 2f+2 => 3(n+1) = 2(f+1)

n+1 must be even, thus n must be odd

there is a contradiction here. I was suppose to show n is even, but n is odd.

Better??

 

[Mark44]

If 3n+2 is odd, then n is odd

3n + 2 is odd, show n is even

No. You assume that 3n + 2 is add, and you assume (not show) that n is even.
The goal here is to arrive at a contradiction, which is why this is called a proof by contradiction.

3n+2 = 2f+1 => 3n+3 = 2f+2 => 3(n+1) = 2(f+1)

Note that if 3n + 2 is odd, so is 3n. The above is way more complicated than it needs to be.

n+1 must be even, thus n must be odd

there is a contradiction here. I was suppose to show n is even, but n is odd.

As I said before, you're supposed to assume that n is even. If you show by a sequence of logical steps that n is actually odd, that's the contradiction.

Symbolically you're trying to show that $p \Rightarrow q$, where p is the statement "3n + 2 is odd" and q is the statement "n is odd".

In a proof by contradiction, you're investigating the truth value of $p \wedge \sim q$. If you can show this is false, then $\sim (p \wedge \sim q)$ must therefore be true. It turns out that the truth table for $\sim (p \wedge \sim q)$ is identical to that for $p \Rightarrow q$, which means that these two statements are equivalent.

 

[PeroK]

If 3n+2 is odd, then n is odd

3n + 2 is odd, show n is even

3n+2 = 2f+1 => 3n+3 = 2f+2 => 3(n+1) = 2(f+1)

n+1 must be even, thus n must be odd

there is a contradiction here. I was suppose to show n is even, but n is odd.

Better??

Your fundamental problem here is with logic. There are basic elements of logical thinking that underpin mathematics. If you do not understand these logical elements, then you are going to have serious problems, especially in pure mathematics.

It's critical, therefore, that you understand the basic ideas of logical thinking. The idea behind proof by contradiction is this:

1) If you start with a true statement and use sound logical reasoning then all statements that follow are true.

2) If you start with an initial statement and use sound logical reasoning and arrive at a statement that you already know to be false, or contradicts anything in your line of reasoning, then the initial statement must have been false.

In other words:

1) True statements and valid logic lead only to more true statements.

2) If you arrive at a false statement, then either your reasoning was wrong or at least one of the statements you assumed to be true was in fact false.

This forms the basis of "proof by contradiction". Note that the false statement might be something that you already know is generally false (e.g. that $2n$ is odd). Or, the false statement might be something that contradicts the assumption you are testing (e.g. you might assume a cerrtain number $n$ is odd and reach a conclusion, using its other properties, that $n$ is also even). At that point you know something has gone wrong and the statement you are testing must be false.

The other important concept is that of "negation" of a statement. A common approach to proof by contradiction is to assume the negation, reach a falsehood or contradiction and thereby conclude that the negation cannot be true. And, if the negation is false, then the orignal statement must be true.

Your problem is a good example:

Statement: If $3n+2$ is odd, then $n$ is odd.

Negation: There exists $n$, with $3n + 2$ odd, and $n$ is even.

Note that @scottdave made a very good point that your original statement says nothing about what happens when $3n + 2$ is even.

The structure of your proof by contradiction in this case is:

1) Assume $3n+2$ is odd and $n$ is even.

2) By sound logic reach an obviously false conclusion or contradiction to this initial assumption.

3) Conclude that "$3n + 2$ is odd and $n$ is even" is not possible.

4) Conclude that "If $3n + 2$ is odd, then $n$ is odd".

Note, finally, that there is related proof by "contraposition". But, I'd suggest understanding the idea of obtaining a direct contradiction first. And, once you have understood the ideas behind the proof by contradiction, move on to proof by contraposition.

 

[r0bHadz]

I actually found proof by contraposition much easier to grasp intuitively than proof by contradiction. If not q, then not p. But I think I'm starting to get the hang of proof by contradiction. Basically you want to show that p -> (r and ~r)

 

[fresh_42]

I actually found proof by contraposition much easier to grasp intuitively than proof by contradiction. If not q, then not p. But I think I'm starting to get the hang of proof by contradiction. Basically you want to show that p -> (r and ~r)

Yes.

1. $(\lnot \,Q \longrightarrow \lnot \,P) \Longleftrightarrow (P \longrightarrow Q)$

2. $(\,(P \wedge \lnot \,Q)\, \longrightarrow \lnot \,True) \Longleftrightarrow (P \longrightarrow Q)$

Edit: I think proof per contradiction is more natural. E.g.:

Statement: The remainders $R:=\{\,0,1,2,3\,\}$ by a division by $4$ do not form a structure where division by non zero elements is always possible.
Proof: Let's assume the contrary is true, that is: division by all numbers different from zero is possible. Then we have $1\cdot 1 = 1$, check, $3 \cdot 3 = 9 = 2\cdot 4 +1 = 1$, check, and $2\cdot 2 = 4 = 4 \cdot 1 + 0 = 0$. Now if $2\cdot 2 = 0$ and there is a number $x$ for which $2\cdot x = 1$ by our assumption, then $2= 2\cdot 1 = 2\cdot (2\cdot x) =(2\cdot 2) \cdot x = 0 \cdot x = 0$ which is not true. Hence our assumptions were wrong: either division by $2$ is impossible, or one of the calculation laws is wrong. But the latter are not wrong, leaving only the division part as possibility to be wrong: $2 \in R$ has no inverse.

 

[Mark44]

But I think I'm starting to get the hang of proof by contradiction. Basically you want to show that p -> (r and ~r)

No, that isn't it at all. Your conclusion above, $r \wedge \sim r$ can't ever be true. So your implication here boils down to $p \Rightarrow \text{false}$, making the implication meaningless. Again, what you want to establish is that $p\; \wedge \sim q$ is false.

 

[Ray Vickson]

Homework Statement

If 3n+2 is odd, then n is odd

Homework Equations

The Attempt at a Solution

assume 3n+2 is even, show n is odd

3n+2 = 2f => 3n+3 = 2f + 1 => 3(n+1) = 2f+1

so 3*(n+1) is odd form. Only odd*odd gives you another odd, so n+1 is odd. That means n is even.

We have a contradiction here, as shown, n is even, not odd.

Or does this proof method only work if we take the negation of the conclusion? The reason I think my proof is invalid:

(p) (q) (p->q) (p -> ~q) (~p -> q )
0 ff 1 ff 1 ffffff 1 ffffffffffff 1
0 ff 0 ff 1 ffffff 1 ffffffffffff 0
1 ff 0 ff 0 ffffff 1 ffffffffffff 1
1 ff 1 ff 1 ffffff 0 ffffffffffff 1

If we look at the second row, p = 0, q = 0, and the last column, we will see ~p -> q is 0

There is no contradiction here. ~p is 1, and q is 0. This implication will always be zero. My proof that I did above, it did not prove anything that isn't obvious already, thus there was never a contradiction and it was wrong.

What I think I need to do:

Look at the third row, where p = 1, q = 0, p->q = 0. I need to show that the case p->q = 0 cannot happen. Meaning, that there will be a contradiction. P will have to be 0, or q will have to be 1. This is where the contradictions is. I cannot possibly show this contradiction with ~p->q because ~p is 0 which will always give me a truth of one. I can however show this with p->~q because if I can show that the value of this implication is 1, there will be a contradiction.Does my reasoning seem right folks?

Forget about trying to express the problem in formal symbolic logic terms; that does nothing at all towards actually proving the result! (For example, if you take the statement that "the square root of a prime number > 1 is irrational", you could go ahead and express that in formal logic terms, but you would still have gotten precisely nowhere towards proving it.)

In plain language, a proof by contradiction starts by assuming the opposite of your desired conclusion, and then exploring the consequences of that. So, you would start by assuming that $n$ is even and then see where that takes you.

 

[r0bHadz]

Thanks Ray. You bring up a great point, what I'm trying to do is solve a problem. And you explanation makes sense!