Almost there. This is a continuation of the previous WitCHes, here and here and here, on the Logic and Proof chapter of VicMaths, Nelson’s Specialist Mathematics Year 12 text. It is the penultimate section, Proof by contrapositive and contradiction. Most of the worked examples are OK (including Example 18, a correct and reasonably well-written proof “by contrapositive” that if n2 is divisible by 3 then n is divisible by 3). But, there are issues, notably in the exercises.
EXERCISES
ANSWERS
1. C
2. A
6. B
8. Prove that ¬c → ¬(ab +c), c is even so ab is even. ¬(ab +c) means ab + c is even.
So… why is
odd…? We know that either 
or 
or both are odd, but we do not know 
is odd.
Proof by contradiction for this could be done a bit differently:
3 is prime.
So 3 has exactly two factors.
All square numbers have an odd number of factors.
Two is not odd.
So 3 cannot be a square number.
Therefore the square-root of 3 cannot be an integer…
(Yes, I know this is different to rational, but I think it is an improvement on the proof supplied…)
Note Example 18. It seems they deliberately set things up for the standard proof you give. Why they then didn’t do it, God only knows.
I’m not particularly enamoured with your theorem.
Thanks, RF. There’s a reason to give the type of proof they give (but not stuffed up, of course).
I agree, RF. The proof in worked example 19 is stuffed. For exactly the reason you state. Here is how it should continue from
:
(1) shows that 3 is a factor of a. (Theorem: If p is a prime number and p divides
, then p divides a. Here 3 is the prime number that divides 
, thus 3 divides a and thus 3 is a factor of a).
Since 3 is a factor of a, we can write a = 3c (where c is an integer). Substitute
into (1):
(2) shows that 3 is a factor of b.
Therefore 3 is a factor of both a and b which is a contradiction since a and b are co-prime.
You can prove the irrationality of sqrt(3) in a similar spirit by appealing to the FTA: if a^2 = 3b^2, the left and right side differ in the parity of the exponent of 3 in their prime factorisation.
Yes, which is what RF was suggesting. But there’s a reason to do it in the “divisible by 3” way.
I agree that there are reasons to do it in the usual way using contradiction*; I’m just responding to RF’s comment “I know this is different to rational” to explicitly note how RF’s proof that sqrt(3) is not an integer can be extended to show irrationality.
* technically negation, but the subtlety of this distinction isn’t particularly helpful or relevant in most cases
I might run through and detail my thoughts when I’m freer — but from a quick glance, I am baffled as to what the authors intended with exercise 8 given it’s so obviously wrong as written. Perhaps they meant ‘at least one of a, b, or c is odd’, as this lends itself naturally to contraposition? A better interpretation evades me.
Me, too. I assume there’s some missing hypothesis, which implies ab is even, and I was tempted to let it go on that basis. But the solution is so garbled, I figured i had to include it.
If Ex 8 is taken on face value, then proof by contrapositive requires proving that
if c is even then ab + c is even.
Which is clearly false without further restriction(s) on one or more of a, b, c.
We could speculate on what the writer actually meant and make suggestions on how to rehabilitate the question. But it’s such a ‘plainly worded’ question that I prefer to be uncharitable and say that the writer meant exactly what is written. Which says a lot.
Just say “proof by contradiction”. Proof by contrapositive is not really a thing.
Yet the study design (Page 58 for those playing along) says “…proof using the contrapositive…”
I suppose they said “using the” instead of “by”, but still…
EDIT: Page 109 actually says “…proof by contrapositive.” So textbooks are now forgiven, somewhat.
Thanks, RF. In response:
(1) Yes, I am aware that “proof by/using contrapositive” is in the Study Design (Word, idiots), although to an unclear degree. See (4) and (5), below.
(2) Yes, (1) somewhat excuses the textbook companies, although that defence is pretty Robodebt-ish. And robotic. Just because VCAA writes crap doesn’t mean that authors/publishers can’t think about how to relay that crap in at least a somewhat less crappy manner. To their credit, Cambridge tries pretty hard to do this, even if they are often unsuccessful.
(3) Teachers are of course caught in the same semi-bind. My point to BiB was, when discussing this stuff generally, like intelligent human beings rather than VCAA’s robots, go with the general, sufficient and accepted expression: proof by contradiction.
(4) Yes, “proof by/using the contrapositive” may be in the SD, but we have already established that VCAA does not know what “contrapositive” means.
(5) It is actually not clear whether “proof by the contrapositive” is a thing in the SD, beyond the (garbled) notion of “contrapositive”. Note that the sample Exam 1 questions contain not a single reference to “contrapositive” (although, of course, there are other issues). And the sample Exam 2 questions only refers to “contrapositive” (wrongly) as a statement: see (4). And, VCAA’s “contradiction” webinar makes no reference to “contrapositive” whatsoever.
Thanks Marty. If I may respond, briefly (it has been a long week!) to point (3).
There are a LOT of out-of-field teachers in schools, trying to put together lessons on Specialist Mathematics. Sometimes, if not most of the time, they are the only teacher of Specialist Mathematics in the school. They do a good enough job because of their engineering/physics/whatever background, but they never were mathematicians.
They go to the study design to decide what they need to teach, because the course is new, so past exams aren’t much help.
Maybe they know what contrapositive is, maybe they don’t. They need something to assist, so they go to the textbook.
Both these steps, one would assume, are fair and reasonable steps for a teacher to take.
Of course, point (4) to some extent and point (5) to a greater extent sufficiently rebut this, so consider it an explanation not a justification.
RF, of course it is perfectly reasonable for teachers to go to VCAA’s curriculum and resources with the expectation that these materials will be clear and correct. That this is not the case, is of course unreasonable. I’m merely emphasising the second point.
I will disagree.
You can prove that a => b by proving not b => not a. This is different to proof by contradiction and often provides a simpler proof than proof by contradiction might.
Give me an example.
Let x be a positive integer. If
is even then x is odd.
Let x be a real number. If
then 
.
The first you should just prove directly. For the second, how is a contrapositive proof any different from a contradiction proof? (EDIT. No, of course do the first by contradiction, whatever, as well.)
I’m arguing that the proof of both is simpler using contrapositive. You’re contradicting me.
You’re not arguing it: you’re claiming it. You haven’t written any proofs whatsoever.
You asked for an example. Now you’re asking for a contrapositive proof?
Prove: If x is even then
is odd.
is odd since 
is an integer. Olé!
Let x = 2n where n is an integer.
I await your contradiction.
Prove: If
then 
.
.
. Olé!
Let
Suppose x is not odd. Then x is even …
What is the Grand Glorious Difference?
I don’t see it. It makes no sense. How does that prove the first example?
I’ve provided the examples and I’ve provided the contrapositive proofs. Ball’s in your court to provide a proof by contradiction that’s simpler (and has enough detail to make sense rather than take the piss).
Surely the first line in a proof by contradiction would be
is even and x is even.”
“Assume for the sake of contradiction that
Now you have to work for the contradiction to conclude that x is odd. It is this work (as well as getting the contradiction correct) that I’m arguing makes contrapositive simpler (*)
It seems to me that there’s bad blood between you and contrapositive.
* I should have added the qualifier “under certain circumstances (such as the two examples I gave).
Sigh.
We want to prove that if THINGY is even then x is odd. Suppose not. Then x is even. But that implies by the same obvious computations that THINGY is odd, which is a contradiction.
Assume for the sake of contradiction that
is even and x is even.
where n is an integer.
is odd since 
is an integer.
is even.
Let
Then
But this is a contradiction since
Therefore x is not even. Therefore x is odd.
I’m arguing that proof using the contrapositive is simpler:
1) The first line is simpler (I wonder how many students screw up the contradiction assumption), and
2) Yes, getting the contradiction uses the same calculation (but I wonder how many students will recognise to do those calculations) but then you have to write the last few lines to finalise the proof.
I’d like to know what your beef is with contrapositive. Is it because anything you can do using contrapositive can be done using contradiction and you’re argument is that contradiction is more ‘elegant’ or ‘powerful’?
There’s no goddam difference worth stating as a difference. It is madness.
To an extent, I agree with this notion, but you have to be very careful what is meant by NOT.
In some settings, NOT A is very clear. In others it is less so.
Unless the meaning of NOT is explicitly clear, I would try a direct proof or proof by contradiction. It may be longer, but I’m more confident of its validity.
In Boolen logic, for example, I feel that NOT is well defined and so the implication statement made above is a valid approach and quite possibly a very efficient one in the right setting.
As a previous WiTCH illustrated though, the NOT operation can sometimes be less than clear.
I agree that deciding what “not” means requires thought, or lack of thought, depending upon your approach. However, that requirement is identical, whether framing things as contrapositive or contradiction.
True.
Or “1” if you prefer the Boolean answer.
The bit that bothers me the most (and by quite some margin) is that these proofs are pretty damned standard. There are LOTS of examples of GOOD proofs as to why certain surds are irrational. Yet we have an error-laden textbook chapter.
There may well be 400 different proofs of Pythagoras Theorem. That doesn’t mean each new textbook has to give a different one.
I don’t think they tried to give a new proof. I can only see Example 18 as setting up for the standard proof.
Even more reason not to stuff it up.
Indeed.
Just get some three-legged friends to help.
T-Shirt reference?
If so – nice.
I seem to have misremembered one of the Maths Masters columns. Turns out I was thinking of them using base 3 to prove sqrt2 is irrational, and not using the three-legged alien to prove (using base 3) that sqrt3 is irrational.
https://www.qedcat.com/archive_cleaned/58.html
https://www.qedcat.com/archive_cleaned/172.html
You need a different alien for base 3.
Sorry: you need a different alien for root 3.
No one’s gonna give the exercises a go?
Marty:
1) It’s SAC season. This means SACs are being written, vetted, marked and results entered into spreadsheets. Enough work if you’re teaching one Unit 4 class. And some teachers have two classes or even three. Furthermore,
2) Nelson makes money from its textbooks. So Nelson can pay for someone(s) to do a competent proof reading job and fix its mistakes.
Nevertheless, I’ll offer a brief critique on Ex 1: None of the options are correct.
A less brief critique: The conjecture is an existence conjecture. It claims the existence of a natural number y for all natural numbers x > 3 such that x + y less than 10. Obviously such values of y exist when x = 6 (y = 1, 2 or 3 spring to mind). Therefore option C is not a counter-example (that disproves the conjecture), it’s a dumbass example (*).
The question can easily be rehabilitated by including an option with x > 8. (Thankyou Nelson, that will be 20 dollars please).
Ex 8 has already been critiqued. It can be rehabilitated by deletion.
* Or, if you prefer, an example of a pair of values for which the inequality is not satisfied that is completely irrelevant to the conjecture being true or false.
(Note: The latex and formatting is screwing up again. And parts of the comment do not appear when submitting. I’m on a different computer and not copying and pasting from a file. The ‘less than’ symbol is causing problems and the latex will not format when editing).
Ex 1 is not an existence conjecture.
Whatever. It claims the existence of a natural number y for all natural numbers x > 3 such that x + y less than 10 and none of the options are a counter-example that disproves the conjecture.
(But I’ll admit I might not be understanding exactly what the whole try-hard-to-look-impressive-and-learned conjecture is saying. The whole thing is mutton dressed up as lamb and the mutton is rancid).
You can’t nitpick logic, even nonsense logic, and throw up your hands with “whatever”. It does not claim the existence of y. It claims that, for every x, something is true.
You have to read the entire sentence, from beginning to end.
OK. It’s pretty obvious what I think it’s saying. In plain simple English, what do you think it’s saying?
By the way, is it too hard to use s.t. for “such that” rather than, I assume, brackets.
It may be pretty obvious, but you got it wrong.
It is saying that:
For every natural number x, IF x > 3 THEN …
Question 1 has no correct answer in my opinion. Any answer that has
would be valid, and a simple counter-example.
Unless I’ve missed something (it happens a lot)
Pretty much. But note that a counterexample would consist of an x value alone, not also a y value. So, the listed answers are not even of the right form to be counterexamples. Also, x = 9 also works as a counterexample.
Yes, thanks. That is (basically) what I was trying to say.
The strict inequality (not allowing the “or equal to”) combined with the (not quite adequately defined) requirement that x and y are natural numbers makes finding A counter example pretty easy.
Whether
would be considered a single counter example in this instance might be debatable… but surely, in a multiple-choice exercise it is not hard to give at least one correct answer…?
What is debatable about x = 9?
Remarks:
I really dislike the second paragraph.
– Proof by contradiction is not restricted to implications.
– The contradiction does not arise from (P -> ~Q); it arises from (P and ~Q). More pedantically, one does not need to ‘accept [the truth of] P’, as an assumption is enough.
As others note, step 2 of the worked example is nonsensical. I’m also not sure what the authors mean by ‘types of variables’, as opposed to just ‘variables’…
1. I’m not sure why values for y are specified in the options — and even ignoring the y values in the options, none are counterexamples. Did the authors mean ‘for all y’ ?
2. I see very little value in rephrasing vague statements in the language of logic. In the absence of quantifiers, I also don’t understand this statement at all. Describing y = 3x + b as a line only makes sense if b is fixed, and so the statement really is that for all (x, y) satisfying y = 3x + b, if y = 0 then x > 0.
I don’t understand the options either: what does it mean for something like ∃b to imply a statement? My only explanation here is that -> really means ‘such that’ here — and even then, none of these options are appropriate. What are they even meant to mean?
6. Nowhere in the question is it mentioned what ‘statements P and Q’ are in a proof by contradiction. If we’re writing the claim as an implication P -> Q, then all the options have it the wrong way round. Even if we ignore this, both the initial statement and the options are missing quantifiers. And even if I ignore that, the question’s effectively asking us to prove a definition*, which is rather stupid.
* I guess you can define two vectors being parallel as their mutual angle being 0, and that this conclusion follows from Cauchy-Schwarz, but I doubt the curriculum introduces vector geometry in this way. Even then, you don’t use contradiction.
8. Discussed earlier.
I’m still genuinely confused by exercise 2 — I’ve spent more time on this than all of Witch 110 combined. If you have an explanation, I’d be extremely grateful. In the meantime, I’ve sent an message to Cengage support asking how I can contact the authors to report errors.
Thanks very much, confused. I think I might sack my regular contributors. Yes, the second paragraph is a mess, and yes to all your comments on the exercises.
Re Step 2, I assume “types of variable” is somehow referring to integers being the variables, but who really knows.
Re Exercise 1, I don’t think “for all y” would make much sense.
Re Exercise 2, yes, I’ve tried hard and I’ve not been able to make any sense of it whatsoever, even given the very weird goal of the exercise.
Exercise 2 just gets more difficult to understand, the more I try…
Let’s start with
intersects the POSITIVE 
axis.
Then
which is perhaps where the rot begins…?
Not really sure the question is salvageable. I was hoping for a few hours there, but can’t find a fix.
Proof by contradiction: this description is extremely confusing. I don’t see why you need to involve implications at all, just say: to prove P, show that ¬P leads to a contradiction.
The other commentors have commented on the absurdity of Worked Example 19.
For the exercises:
1. Counterexamples don’t exist for true statements.
2. I’m not completely familiar with the notation and different variants of it, so I might be wrong, but C seems to be the only statement that is syntactically valid, and of course that’s not the answer. Unless they’re somehow treating logical quantifiers as propositions, which seems insane to me.
6. P and Q shouldn’t be explicitly defined. And the original statement is that ∃k(u = kv) –> (u and v are parallel), so they messed up their own definitions. And this is generally a definition, not a proposition. Just an entirely messed up question.
8. a = 1, b = 3, c = 2. Magic.
Their suggested answer is nonsensical. c is not a proposition, and neither is (ab+c).
Edit: Oops, it appears as if my comment is pretty much exactly what confused wrote above, but reworded. I must have missed it.
Why is 1 true?
Oops, didn’t see that x and y were specified to be natural numbers. Why can’t they just say ∀x∈N?
To be pedantic, the variables x and y stated in the first part of the sentence are different from the variables quantified in the statement. It is clear what they meant (that the domain of discourse is the natural numbers), but the first part of that sentence implies that x and y have specific values, which could be confusing, even moreso because the answers they give have specific values for y as well, when as pointed earlier a counterexample would only have a value for x. Or maybe the authors confused themselves into thinking that x and y have specific values in the statement, even though they have been quantified.
Re: “Why can’t they just say ∀x∈N?”
They probably didn’t want the conjecture to be gratuitously-notation-dense and hence difficult to read and hence lose all focus on the point of the question (which one would assume is disproof by counter-example).
(I would ask why can’t they just use plain English? Except that I already know the answer)
Joe, the point about x and y is a good one. They want to have the quantifiers refer only to natural numbers, but without (further) muddying the logical notation, and I think that’s reasonable. But doing by talking about x and y as if they were explicit but own things, and then using the same x and y as variables in quantifiers, is simply wrong.
Can Q2 be salvaged by changing the direction of the final inequality in Option A?
Similarly, can Q6 be fixed by changing the not equal symbol to “equal”?
OK, neither is a particularly good question, but maybe they can be at least made to have a correct answer…
Q2, I don’t see how A makes any sense whatsoever. The inequality doesn’t even enter into it.
Q6, I don’t get what you’re asking. Which answer? But the main issues are: the original statement amounts to a (debatable) definition, making the idea of proving it by contradiction fundamentally absurd; it makes no sense to ask for P and Q, since their roles in the statement or its contrapositive are not defined.
OK. Sure.
I’m trying to work out (and failing) what the question writer was trying to say by making as few modifications as possible to the existing text.
Maybe, as you say, this is pointless since the whole idea of the question makes no sense.
I think the idea of the question makes sense, even if poorly executed. I think the fundamental problem is that the writers seem to believe that a counterexample should consist of a pair, an x and a y, rather than simply an x.