How do I make a student understand contradiction?

Question

We were trying to prove that if $3p^2=q^2$ for nonnegative integers $p$ and $q$, then $3$ divides both $p$ and $q$. I finished writing the solution (using Euclid's lemma) when a student asked me

"How can you assume $3p^2=q^2$ when that implies $\sqrt 3$ is rational which we know is false?"

I told him that question at hand is used as a lemma in proving that $\sqrt 3$ is irrational. But he gave another argument using fundamental theorem of arithmetic to independently prove that $\sqrt 3$ is irrational. So I could not convince him that one can give a chain of arguments starting from a hypothesis without actually knowing the truth value of the hypothesis itself. Later I came back and tried to think more about this a bit fundamentally to understand what it means to prove the implication $"A \to B"$ without worrying about truth of $A$ and how different is it from proving $B$ when we know $A$ to be true (or false, as in this case, using some other method). But I am also confused. Another student made this remark, "you are giving me one false statement, and asking me to prove another false statement, I don't understand". Can someone please resolve this?

Answer 1

Proof by contradiction is simple. It is not so much that if a false statement is true, then we arrive at a contradiction. Rather, a better way to think of it is, "if a given statement is true--a statement whose truth or falsity is not yet established--then we arrive at a contradiction; thus the original statement cannot be true."

Take your proof of the irrationality of $\sqrt{3}$ as an example. At the outset, we have not yet established whether or not $\sqrt{3}$ is irrational (or rational). And we don't know until the proof is complete. But you certainly can reason about it by first supposing that if $\sqrt{3}$ were rational, then there exist two positive integers $p, q$ such that $q$ does not divide $p$, for which $p/q = \sqrt{3}$. That follows from the supposition of rationality. Then by continuing the logical chain, you arrive at a contradiction. So if all the consequential steps from the original supposition are valid, but the conclusion is inconsistent, then the original supposition could not be true. Note that in this chain of reasoning, at no point do we actually claim that the original supposition is true, because as we have taken care to mention, we do not know if it is or not until the proof is complete. We are merely saying that if it were the case, we would arrive at a contradiction.

Here is a less trivial example. Some conjectures remain open in the sense that we do not know what the answer is. Consider the Collatz recursion $$x_{n+1} = \begin{cases} 3 x_n + 1, & x_n \text{ is odd} \\ x_n / 2, & x_n \text{ is even}. \end{cases}$$ The conjecture is that for every positive integer $m$, the sequence $\{x_n\}_{n=1}^\infty$ with $x_0 = m$ contains $1$ as an element in the sequence.

If we were to attempt to prove this conjecture is TRUE by contradiction, the supposition we would presumably start with is that there exists a positive integer $m^*$ such that if $x_0 = m^*$, the sequence $\{x_n\}_{n=1}^\infty$ never contains $1$, and then by using some as-yet-unknown logical deduction from this supposition, if we can arrive at a contradiction, we then have shown that the conjecture is true.

But note what I said above: this is an open question! Nobody knows if it is true or false. So you cannot claim that my logic is invalid because I have a priori assumed something that I already know not to be the case!

Now, if I were to desire to disprove the conjecture, it would suffice to find just such an instance of $m^*$ as I have described above. But an extensive computer search has turned up no such counterexample. This leads many to believe the conjecture is true, but no constructive method to substantiate that belief. Mathematics--and number theory in particular--contains many examples of claims that appear true but have their smallest known counterexamples for very large numbers.

So, there is my "informal" explanation of proof by contradiction. The essence is that we don't presume to know the truth or falsity of a given claim or statement at the outset of the proof, so we cannot be accused of assuming that which is false. The falsity is established once the contradiction is shown.

Answer 2

Step 0. Use truth tables to convince him that $A \rightarrow \bot$ is equivalent to $\neg A$. Deduce that to prove $\neg P$, we can assume $P$ and attempt to derive $\bot$, since this allows us to infer $P \rightarrow \bot$, which is the same as $\neg P$.

Step 1. Use truth tables to convince him that $A \rightarrow B$ is equivalent to $\neg(A \wedge \neg B).$ Conclude that to prove $A \rightarrow B$, we may assume $A \wedge \neg B$ and attempt to deduce $\bot$.

---

Edit. My original answer (above) focuses on the logic of proof by contradiction, but there is also a pedagogical issue here that deserves to be addressed. The following material is taken from the user Keen and from Steve Jessop's excellent answer.

Unfortunately, assume is one of those words where the mathematical definition differs from its popular English definition. In English, assume S means believe S. In mathematics, it means only imagine if S were true. So when we say, "assume $3p^2=q^2$", we are not asserting that there exists an ordered pair $(p,q)$ with this property. Rather, we are considering the hypothetical properties that such a pair would have, if it did exist.

Answer 3

For me, the real issue here appears to be that the student is expecting you to teach them "right answers", rather than provide them with tools.

The point of teaching them proof by contradiction is not to show them how to prove that hypothesis, it's to show them how to prove other hypotheses that are far more complex, where there isn't an obvious alternate proof they can rattle off.

One way you could start is:

This is a simple example you can easily prove another way, as you've just shown. But I'm not trying to prove this fact, someone's already done that about 1000 years ago. I'm demonstrating this tool for future use, in problems that you don't have another way to solve, or where this tool is simpler to use than many others.

As an analogy, it's useful to be able to know how to ride a bike even if you have a car, for the day when the car breaks down.

Answer 4

There is always something confusing about contradiction in that it postulates one absurd statement and reduces it to another absurd statement. The difference lies in how obvious the absurdities of the respective statements are. In your example $$ A:\ \text{"}\sqrt3\text{ is rational"} $$ is re-phrased as the equivalent statement $$ B:\ 3p^2=q^2 $$ and then reduced to $$ C:\ \text{"both }p\text{ and }q\text{ are infinitely often divisible by }3\text{ "} $$ All three statements are absurd. But if you knew that $A,B$ were already obviously absurd from the beginning i.e. $\sqrt 3$ is obviously irrational, you would not need to pursue any proof either direct or by contradiction in the first place.

---

So if your students acknowledge that $A,B$ are not that obviously absurd before a proof of it is given, the reasoning makes sense as follows: $$ A\iff B\implies C $$ Now since $C$ is obviously absurd, since no natural numbers contain the factor $3$ infinitely often, thus by contraposition $A,B$ cannot have been true either.

Answer 5

I think at this level (university?) it's required that the student begins to grasp the precise meaning of "implies", that is "$p\Rightarrow q$ is the same as $\neg p\lor q$, and an implication may be true if the premise $p$ may be false (it's obviously true if $p$ is actually false)

When it comes to rules of inference I think it's important that one can agree to these and not accept them just because you claim them to be valid. I don't think reductio ad absurdum need to be among the basic inference rules, but it should be able to be proven to hold if not accepted as an basic inference rule. Which inference rules you can get accepted affects the way you prove reduction ad absurdum. I think you have to get to get deduction theorem/conditional introduction (that is if we assume $p$ and then can prove $q$ then we can conclude $p\Rightarrow q$) since a normal proof by contradiction is phrased that way, also modus ponens (being the reverse) should be accepted. Then it's a matter of proving that an proved contradiction leads to anything and therefore the assumtption $\neg p$ in a proof by contradiction leads to $\neg p\Rightarrow p$, that is $\neg\neg p\lor p$.

Answer 6

When we say, "assume $3p^2 = q^2$", we are not asserting that there exist $p$ and $q$ with that property. So the fact that the student happens to know by an independent proof that no such $p$ and $q$ exist in the integers is irrelevant to this proof. We can write more than one proof of the same result, but we won't produce different proofs if all the other proofs we write after the first one just go ahead and use the result.

Rather, we are considering the hypothetical properties that such $p$ and $q$ would have, if they did exist. We may or may not later conclude (by contradiction) that they don't exist, but all we're really doing is using a logic in which it is legitimate to construct and use formulae like $A \rightarrow B$ even if $A$ turns out to false. (Actually, to be strict, we're doing more than that, we're actually using the fact $A \vdash B$ to deduce $\vdash A \rightarrow B$, and from this and $\vdash \neg B$ we conclude $\vdash \neg A$. If these are all things that the student understands in first-order logic, then that's a way to explain it, but I suspect this student doesn't yet).

In English, when we say "suppose X", or "assume X", we are not saying "X is true". We are introducing a perhaps very long chunk of work in which everything is implicitly preceded by "If X is true, then". In these terms, proof by contradiction is a rule of procedure that says that once we reach "If X is true, then contraction", we may deduce "not X".

This claim would not satisfy possible philosophical objections against reasoning about the properties of things that don't exist. So your student might still not be satisfied about this notion of reasoning in a conditional mode about something whose existence we wish to investigate. But ultimately all you're doing is saying, "all unicorns have horns". For most users of logic this statement is still (vacuously) true even once one notes that no unicorns exist. You are not saying, "there exists a unicorn with a horn".

Practically speaking, you might be able to satisfy the student's objection by finding a proof by contradiction where he doesn't just so happen to already know the result by an independent proof. If he doesn't mind reasoning about the properties of things when he doesn't know whether they exist or not, he might be persuaded not to mind reasoning about the properties of things that he happens to know don't exist, but whose non-existence has not yet been established by the proof at hand.

You might also be able to drill into his proof using prime factorisation and identify a point at which he reasons about a situation which he then proves not to be the case. If so then you're doing "the same thing", it's just that in your example the falsehood takes longer to establish.

Answer 7

I can't be sure about your question in hand, but I have an easy way to understand how proof by contradiction works:

Proof by contradiction is usually having the following "walking paths":

a statement $S$ has only two possible out comes, asy, $A$ and $B$. ($S$=it is rational; $A$=true, $B$=false)

Now, we don't know about that statement $S$, but with one of the outcome, it leads to a false conclusion shown by facts.

$S(A)\rightarrow C$

(Assuming it is rational, but it shows ridiculous result.)

assuming how you get to C is right (if-then logic value is true).

if we look up the truth table, we will find $S(A)$ must be false. therefore, the only possible result is $S(B)$ is true.

Answer 8

You could try and start with a short discussion based around a logic puzzle that involves a contradiction (for example: "A prussian officer, Colonel Maximilian orders Private Hans to shave all the soldiers under Maximilian's command who don't shave themselves. Can Hans obey this order?"), familiarizing them with the simple mechanics involved, before moving on to mathematics with the numbers and the symbols and all the other things that seem to intimidate some young minds.

Answer 9

I think it is useful to take a step back from math when dealing with logic, and take examples from the real world. My favorite implication example is "If it rains, Bob comes to the office with an umbrella". Another even cleare is "If you are standing right in front of me, then I see you".

There are two issues that I think you're raising:

1. How to prove that this implication actually exists, that is, prove that in EVERY rainy situation Bob comes to the office with an umbrella. Or to prove that EVERY time you're standing right in front of me, I can see you.
2. Use the implication (which we know to be true) to infer something (either about the weather or Bob bringing an umbrella to the office).

Let's focus on 2 (which helps for 1).

If we know that an implication exist, then the easiest way to use (the so called "modus ponens") is: "Hey, it's raining. Then I'm sure that Bob is coming with an umbrella, I don't even need to check, cause I know that this fact is GUARANTEED by the fact that is raining". No sweat. The countrapositive, or "modus tollens" is less intuitive, but not hard to grasp with an example: "Hey, Bob does not have an umbrella today. Could it be raining outside? Of course not, otherwise he would have brought an umbrella". In terms of the other example: "Hey, I don't see you. Could you be standing right in front of me? Well, no, otherwise I'd see you". Of course, we are not assuming invisibility or other kind of esoteric stuff here...

Now that we know how to use an existing implication, let's think about 1. How can I decide that an implication between two facts actually exists? Well, in math we can use logic (which uses previous results, probably based on previous implications). In real life we "trust" our intuition, or trust a large number of experiments showing the same result. Unfortunately there's no universal SURE law in real life, only "strongly" believed ones. But if we focus only on the observed past, then sure laws exist, based on the collection of all experiments.

Back to Bob. How can we prove that the implication "it rains-> he brings an umbrella" exists? Well, we stalk Bob and observe him through all his work days. But that's expensive. So we can cut down the costs a bit. Two ways:

1. We stalk Bob only when it rains, and check whether he's bringing an umbrella (pass) or not (fail).
2. We don't stalk Bob. We just see him at the office and check whether or not he has an umberlla. If he does, we don't do anything. If he does not, we check if it's raining (fail) or not (pass).

Now, 1. seems the most obvious way, and it clearly looks correct. On the other hand, 2. seems weird. How can a pass support the implication? After all, we only checked that he never has an umbrella when it's not raining, but we do not have any guarantee that he did bring an umbrella when it was raining. Or do we? Well, we actually do! In fact, there are two possibilities:

a) It never rained. In this special scenario, Bob never brought the umbrella, we always checked (every day). It is a not so interesting scenario since the implication is probably going to be useless. All the days were the same (it never rains!), so there's no distinction to make. We may assume that the implication is true, since we have no grounds to reject it.

b) It rained at least some days. Well, it certainly did not rain when he did not bring the umbrella, cause we checked. Then it must have rained when we did not check. But that's precisely when he brought the umbrella. Therefore the implication DOES prove right.

Well, I'm getting long here, so I will stop. In short, I think real world examples are easier to grasp. Also, regarding what your student said ("you are giving me one false statement, and asking me to prove another false statement, I don't understand") it could help him to mention that a "false" statement can be seen as another statement that is "true": the statement where I affirm the opposite thing.

Answer 10

Start with a really simple proof by contradiction.

Now flip it.

A proof by contradiction relies on the fact that if a->b, then ~b->~a. We assume a, and derive false. This is a->false. We then flip it and get true->~a, from which we derive ~a.

We do this flipping "after the fact", but every proof by contradiction can be manually flipped. Every derivation can be reversed, assuming the proof is valid.

Such manual flipping (if done mechanically) looks really artificial, but you can then clean the proof up.

Practice before you show it to your student, as it takes a bit of work to get your head around it, and you'll probably screw it up the first times you try. Start with a really simple case (like a silly logical tautology) before trying even a short "real" proof.

Once they have constructed really simple cases, and they get the trick used, using it "on faith" without doing the flipping themselves might be practical.

Answer 11

Suppose we can prove that $P\implies Q \land \neg Q$.

In no "universe" can $ Q \land \neg Q$ be true. Therefore, in no "universe" can $P$ be true.

Answer 12

If I were to dig deep into the philosophy of mathematics, it eventually finds its way to the age old question of semantics vs. syntax. Mathematics does a remarkably large amount of its work in pure syntactic manipulation, such as "add 3 to both sides." These techniques work because, within the confines of mathematics, it has been deemed valid to simply adjust these symbols on the page in well defined ways to change one problem into another (and hopefully turn the problem into a solution!)

Semantics is a different beast, looking into the meaning behind the math. Mathematics has a powerful ability to hide the semantics deep under layers of syntax, but it never quite goes away. If it did, the philosophers would argue that math would have lost its meaning.

A sentence such as $A \to B$ is syntactically correct in the language of First Order Logic. The symbols are in the correct form such that you are allowed to manipulate them within the rules of First Order Logic. However, if you know a-priori that A is false, the phrase has no semantic meaning. It is as meaningful as "If wishes were fishes..."

Others have pointed out that you are providing a tool, and that is absolutely correct. You are showing that it is valid to do the syntactic manipulations, even when the semantic meanings are missing. This gives you great power as a mathematician. You can manipulate the strings of symbols on the page without worrying about whether the semantic meanings are valid, pushing the semantics towards the beginning (in the form of axioms) and the end (in the form of results, or contradictions). In this case, the whole point is to use syntax to show that First Order Logic finds a contradiction if we make the initial assumption, thus the initial assumption was probably a poor choice for a First Order Logic theory.

(As a meta argument, consider that the rules of First Order Logic have been chosen because they have a tendency to lead from statements which are semantically true to other statements which are semantically true without leading to statements which are semantically false, using nothing but syntactic manipulation to do it. Some, such as Godel and Tarski, even tug at these strings, questioning whether we can actually get away with this substitution of syntax for semantics as much as we think we can!)

The value of this is not in making a simple proof. It's in giving the student tools in the future that they can use when they are less clear in the semantic issues. The issue of healthcare may be a terribly complicated issue, full of all sorts of meanings on both sides of the table, but one only has to engage in syntactic manipulation to test whether a healthcare plan is properly funded.

I like to argue this is the difference between one who goes to school and a student. Anyone can go to school to learn how to get the answers that are in the back of the book (at least the odd numbered ones!). A student knows that no one will pay them to solve problems that are in the back of the book, they will be paid to solve the problems that aren't there, and they will need tools to do it.