# Proof by Contradiction revision

Watch
Thread starter 1 week ago
#1
I understand that some people say this is the most tricky topic to tackle in A level maths. I think it's because there is no straight forward method to tackle every question the same way, since the questions have their own specific proof. In that case, wouldn't I just need to actually try and go through all these types and try to memorize each specifically. Of course there are similar questions with overlapping proofs...
0
1 week ago
#2
(Original post by GogetaORvegito?)
I understand that some people say this is the most tricky topic to tackle in A level maths. I think it's because there is no straight forward method to tackle every question the same way, since the questions have their own specific proof. In that case, wouldn't I just need to actually try and go through all these types and try to memorize each specifically. Of course there are similar questions with overlapping proofs...
If you do a lot of these then you will adapt your way of thinking when it comes to a new problem.

No point memorising each one specifically. This is a waste of time.

Memorising infinitude of primes proof is probably the one you should.

Irrationality of rt(2) can be memorised, but what happens if you are required to prove rt(p) is irrational for any prime p?
Last edited by RDKGames; 1 week ago
1
Thread starter 1 week ago
#3
(Original post by RDKGames)
If you do a lot of these then you will adapt your way of thinking when it comes to a new problem.

No point memorising each one specifically. This is a waste of time.

Memorising infinitude of primes proof is probably the one you should.

Irrationality of rt(2) can be memorised, but what happens if you are required to prove rt(p) is irrational for any prime p?
Alright then thanks. That last one got me stumped tho
0
1 week ago
#4
(Original post by GogetaORvegito?)
Alright then thanks. That last one got me stumped tho
It really shouldn't. Here's a proof that sqrt(2) is irrational:

Suppose (for contradiction) rational. Then we can write as a fraction with a, b in lowest terms.

But then , so .

Since 2 divides the RHS, we deduce 2 divides the LHS too, and so a = 2N for some N.

But then we have , so .

Now 2 divides the LHS, so we deduce 2 divides the RHS, so b = 2M for some M.

But this implies that a, b were not in lowest terms after all! Contradiction.

Now, to prove sqrt(p) is irrational, just take the above proof, and replace 2 by p. (To state the obvious, note that the exponents remain as 2).

Note: I did make sure that I worded the proof in such a way that it was trivial to change to a proof for a general prime p. You might want to compare with the proof that sqrt(2) is irrational that you have in your textbook.

Challenge: To test your understanding, where would this proof break down if p is actually a square. (e.g. if p = 4, there's obviously going to be a problem claiming that sqrt(4) is irrational!).
2
Thread starter 1 week ago
#5
(Original post by DFranklin)
It really shouldn't. Here's a proof that sqrt(2) is irrational:

Suppose (for contradiction) rational. Then we can write as a fraction with a, b in lowest terms.

But then , so .

Since 2 divides the RHS, we deduce 2 divides the LHS too, and so a = 2N for some N.

But then we have , so .

Now 2 divides the LHS, so we deduce 2 divides the RHS, so b = 2M for some M.

But this implies that a, b were not in lowest terms after all! Contradiction.

Now, to prove sqrt(p) is irrational, just take the above proof, and replace 2 by p. (To state the obvious, note that the exponents remain as 2).

Note: I did make sure that I worded the proof in such a way that it was trivial to change to a proof for a general prime p. You might want to compare with the proof that sqrt(2) is irrational that you have in your textbook.

Challenge: To test your understanding, where would this proof break down if p is actually a square. (e.g. if p = 4, there's obviously going to be a problem claiming that sqrt(4) is irrational!).
Thanks for taking the time out to do this, although my confusion was the question "but what happens if you are required to prove rt(p) is irrational for any prime p?" I guess I thought it was a mixture of both the proof of infinite primes and root 2. But yes if p does equal to 4 then it wouldn't work to call it irrational because a/b would just equal to 2 which is a rational number.
0
1 week ago
#6
(Original post by GogetaORvegito?)
Thanks for taking the time out to do this, although my confusion was the question "but what happens if you are required to prove rt(p) is irrational for any prime p?" I guess I thought it was a mixture of both the proof of infinite primes and root 2. But yes if p does equal to 4 then it wouldn't work to call it irrational because a/b would just equal to 2 which is a rational number.
It does seem you're confused.

For the first question, I've just told you exactly what you should do. If it's the "for any prime p" part (as opposed to being asked to, say prove that sqrt(7) is irrational), then you just need to start with "Let p be any prime." and then go straight into the proof. (i.e. the next line would start "Suppose (for contradiction) rational", and so on...)

For the 2nd question, you're missing the point. We know sqrt(4) is rational. But if I'm just "replacing 2 by p" in the proof (and you'll note the proof doesn't ever obviously use the fact that p is prime), I can just say "p = 4" to get a "proof" that sqrt(4) is irrational. Obviously that proof is invalid. But what I'm challenging you to do is to find out which step in the proof is the one that goes wrong.

Thinking about things like "where does this proof go wrong when I try to adapt it to prove something obviously false?" is important in terms of truly understanding what's going on.
0
Thread starter 1 week ago
#7
(Original post by DFranklin)
It does seem you're confused.

For the first question, I've just told you exactly what you should do. If it's the "for any prime p" part (as opposed to being asked to, say prove that sqrt(7) is irrational), then you just need to start with "Let p be any prime." and then go straight into the proof. (i.e. the next line would start "Suppose (for contradiction) rational", and so on...)

For the 2nd question, you're missing the point. We know sqrt(4) is rational. But if I'm just "replacing 2 by p" in the proof (and you'll note the proof doesn't ever obviously use the fact that p is prime), I can just say "p = 4" to get a "proof" that sqrt(4) is irrational. Obviously that proof is invalid. But what I'm challenging you to do is to find out which step in the proof is the one that goes wrong.

Thinking about things like "where does this proof go wrong when I try to adapt it to prove something obviously false?" is important in terms of truly understanding what's going on.
Is it that the proof falls apart in the last part where b and a are both multiples of p therefore p is a rational number and not an irrational one?
0
1 week ago
#8
(Original post by GogetaORvegito?)
Is it that the proof falls apart in the last part where b and a are both multiples of p therefore p is a rational number and not an irrational one?
We're saying p=4. Rational/irrational doesn't come into it.

If you're stuck: set p=4 and try to break the proof. Choose a and b so you'd expect the proof to fail. (i.e. a = 2, b = 1), and go through step by step until you find a step that's invalid (i.e. it will tell you something about a, b that you know isn't true).
0
Thread starter 3 days ago
#9
(Original post by DFranklin)
We're saying p=4. Rational/irrational doesn't come into it.

If you're stuck: set p=4 and try to break the proof. Choose a and b so you'd expect the proof to fail. (i.e. a = 2, b = 1), and go through step by step until you find a step that's invalid (i.e. it will tell you something about a, b that you know isn't true).
I've lost the plot. What is the point of this and what's the actual question again? Sorry I just can't keep up with you
1
3 days ago
#10
(Original post by GogetaORvegito?)
I've lost the plot. What is the point of this and what's the actual question again? Sorry I just can't keep up with you
don't worry... DFranklin is a world class mathematician: we are lucky to have him on here
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### With no certainty that exams next year wil take place, how does this make you feel?

More motivated (30)
27.27%
Less motivated (80)
72.73%