The Student Room Group

Proof by contradiction

I find this topic really tricky and sometimes I can't fully believe the "Therefore" part.

Here's an example

Prove: If pq is even then at least one of p or q is even.
Assume: If pq is even then neither p nor q is even

let p = 2m+1 and q = 2s+1 (both now odd)
pq = 2(2ms + m + s) +1
pq is odd

This contradicts the assumption
Therefore if pq is even then at least one of p or q is even

BUT does it prove that? Yes in as much as we know that and even times and odd gives an even as does an even times an even. But if we don't already know that an odd times an odd gives an odd then why can we make the final statement without proof that and even times and even or an odd times an even gives an even by some other means?

Thanks
The 3 lines:

let p = 2m+1 and q = 2s+1 (both now odd)
pq = 2(2ms + m + s) +1
pq is odd


prove that if p and q are odd then pq is odd.

It's not clear whether you understand/accept this or not - please elaborate.
Original post by DFranklin
The 3 lines:

let p = 2m+1 and q = 2s+1 (both now odd)
pq = 2(2ms + m + s) +1
pq is odd


prove that if p and q are odd then pq is odd.

It's not clear whether you understand/accept this or not - please elaborate.

Well, again, we know that multiplying by 2 makes a number even and adding on one makes an even odd so that statement is there without proof. So throughout the proof we are relying on prior knowledge. We have written that there is a contradiction to the assumption BUT just as we have used prior knowledge in the proof we have relied on prior knowledge for the Therefore line. But if we are relying so much on prior knowledge then why can't we just KNOW that to get an even by multiplying 2 numbers then at least one of them must be even. Doing the contradiction stuff is full of assumptions that have not been proved. So unless you then actually prove some other way that at least one of the numbers has to be even for the product to be even then the Therefor line is unbelievable.

See how much I don't get?
Original post by maggiehodgson
~snip~ See how much I don't get?

Without wanting to get snarky, I asked you a question about whether you understood 3 particular lines in the proof, and I can't see that anything in the paragraph you posted actually answers my question.
Original post by DFranklin
Without wanting to get snarky, I asked you a question about whether you understood 3 particular lines in the proof, and I can't see that anything in the paragraph you posted actually answers my question.

I think I do. If you multiply in integer by 2 then it’s even and by adding 1 you make it odd
Multiplying pand q gives 4ms + 2m + 2s +. 1 and that can be factorised as shown. The first term is even because an integer has been multiplied by 2 so Pi is odd.
Original post by maggiehodgson
I think I do. If you multiply in integer by 2 then it’s even and by adding 1 you make it odd
Multiplying pand q gives 4ms + 2m + 2s +. 1 and that can be factorised as shown. The first term is even because an integer has been multiplied by 2 so Pi is odd.

OK, so we've shown that if p, q are both odd, then pq is odd (*)
Then the argument goes:

Claim: If pq is even then at least one of p or q is even.
Assume (for contradiction) that pq is even but neither p or q is even (**)
Then p and q must both be odd.
And then by (*) pq must be odd.
But (**) says that pq is even, so we have a contradiction.
Therefore (**) can't ever be true.

If you still don't agree with the conclusion, try to decide exactly which line in the above argument you disagree with.
Reply 6
As an aside
https://nrich.maths.org/4717
Is pretty good and emphasises that some things are more natural/easier to prove by contradiction. For problems like the OP, there are several ways to prove it, all fairly straightforward.
Original post by mqb2766
As an aside
https://nrich.maths.org/4717
Is pretty good and emphasises that some things are more natural/easier to prove by contradiction. For problems like the OP, there are several ways to prove it, all fairly straightforward.

As you've already gone "meta": I didn't want to detail things too much, but I'm really not liking " If pq is even then neither p nor q is even" as an implied negation of "If pq is even then at least one of p or q is even" (you wouldn't want to claim the negation of "if p is prime then p is even" is "if p is prime then p is odd"), but I fear it would only confuse things further at this point.
Reply 8
Original post by DFranklin
As you've already gone "meta": I didn't want to detail things too much, but I'm really not liking " If pq is even then neither p nor q is even" as an implied negation of "If pq is even then at least one of p or q is even" (you wouldn't want to claim the negation of "if p is prime then p is even" is "if p is prime then p is odd"), but I fear it would only confuse things further at this point.

Didn't want to detail things :-). Was simply meant as an aside (but agree with this).
fwiw those aren't assumptions, those are the definitions of even/odd. (ie. an even integer is an integer that's divisible by 2, an odd integer is 1 + an even integer)

You're fine to say pq is divisible by 2, but to then conclude either p or q is divisible by 2 is a logical jump that isn't as obvious as it seems and is just restating the result. If you begin to explain roughly why you will likely invoke more general statements about prime factorisations or divisibility which in turn either are, or rely on, a more general statement of what you're trying to prove, which defeats the object at best and is circular at worst. (means you'd have to prove those general statements to have a complete argument) You are right that this is intuitively obvious, though. Annoyances like this will be common if you study maths further.
(edited 3 years ago)
Original post by DFranklin
OK, so we've shown that if p, q are both odd, then pq is odd (*)
Then the argument goes:

Claim: If pq is even then at least one of p or q is even.
Assume (for contradiction) that pq is even but neither p or q is even (**)
Then p and q must both be odd.
And then by (*) pq must be odd.
But (**) says that pq is even, so we have a contradiction.
Therefore (**) can't ever be true.

If you still don't agree with the conclusion, try to decide exactly which line in the above argument you disagree with.

I agree with up to and including But(**
However, all that's been shown is that if p, q are odd then pq is not even but we haven't necessarily shown that if p and/or q is even then pq is - maybe two evens multiply to give an odd (BTW I know they don't). That extra bit hasn't been shown so I don't think the conclusion is perfect.
Original post by maggiehodgson
I agree with up to and including But(**
However, all that's been shown is that if p, q are odd then pq is not even but we haven't necessarily shown that if p and/or q is even then pq is - maybe two evens multiply to give an odd (BTW I know they don't). That extra bit hasn't been shown so I don't think the conclusion is perfect.


The original question claims that: "If pq is even then at least one of p or q is even."
It does NOT claim that "pq is even if p and/or q is".

You are complaining that something hasn't proved that was never attempted to be proved.

Again, more generally:

The question is of the form: "Show that: if A is true, then B is true".
You are complaining that the proof does not show: "If B is true, then A is true".
Original post by DFranklin
The original question claims that: "If pq is even then at least one of p or q is even."
It does NOT claim that "pq is even if p and/or q is".

You are complaining that something hasn't proved that was never attempted to be proved.

Again, more generally:

The question is of the form: "Show that: if A is true, then B is true".
You are complaining that the proof does not show: "If B is true, then A is true".

OK. I get that. That has been the missing link.
Many thanks.
Original post by maggiehodgson
OK. I get that. That has been the missing link.
Many thanks.

Great.

One word of encouragement: I think these "prove something completely obvious" can be quite tricky, because you're right - you do need to worry about "am I assuming something that's basically the same (or very similar to) the thing I'm trying to prove?". Most "real" proofs by contradiction aren't like this, and in many ways that makes them easier (or at least, you don't have the same "am I breaking the rules by assuming this obvious fact?" question running through your head the entire time).
Original post by maggiehodgson
I find this topic really tricky and sometimes I can't fully believe the "Therefore" part.

Here's an example

Prove: If pq is even then at least one of p or q is even.
Assume: If pq is even then neither p nor q is even

let p = 2m+1 and q = 2s+1 (both now odd)
pq = 2(2ms + m + s) +1
pq is odd

This contradicts the assumption
Therefore if pq is even then at least one of p or q is even

BUT does it prove that? Yes in as much as we know that and even times and odd gives an even as does an even times an even. But if we don't already know that an odd times an odd gives an odd then why can we make the final statement without proof that and even times and even or an odd times an even gives an even by some other means?

Thanks


NO BECAUSE WHY WAS THIS THE ACTUAL QUESTION ON PAPER 1 pure maths edexcel 2022 😐😐
Original post by meema1035
NO BECAUSE WHY WAS THIS THE ACTUAL QUESTION ON PAPER 1 pure maths edexcel 2022 😐😐

a few questions from 2019 were reused from IAL papers, esp with proof by contradiction there's not a huge amount you can ask

but yes it is quite irritating
(edited 1 year ago)

Quick Reply

Latest