How to understand a proof by contradiction in minute detail?

Question

I am following the course "Language, Proof, and Logic" from Stanford on EdX. I am trying to understand proof by contradiction specifically. I understand the gist of this type of proof, and I have done many proofs using this method in math. But when I really drill down into the details of each individual step and try to understand how and why this method of proof works, I get a bit boggled down in the logical concepts and nomenclature.

I am looking for a verification that the reasoning below is correct down to the minute details.

Consider a world containing objects that can be exactly one of either cubes, tetrahedrons, or dodecahedrons.

Consider predicates Cube(x), Tet(x), and Dodec(x).

For example, Cube(x) is an atomic sentence that we can translate as "x is a cube". The other two predicates are translated analogously.

Consider the argument

Premises

Cube(c) | Dodec(c)

Tet(b)

Conclusion

~(b=c)

Let us try to prove the conclusion using a proof by contradiction.

First let me note that since Cube(c) | Dodec(c) and only one of Cube(c), Dodec(c), and Tet(c) can be true, it follows that ~Tet(c).

Assume b=c is true.

Using identity elimination we can infer that Tet(c) is true.

This means that

• Tet(c) follows from b=c and Tet(b).
• In other words, Tet(c) is a logical consequence of b=c and Tet(b)
• If b=c and Tet(b) are true, then Tet(c) must be true.
• we can write this as: (b=c) & Tet(b) implies Tet(c)

At this point we have two premises that are assumed true, one statement that we assumed true for the proof, and two statements that are intermediary steps of our proof, that we've shown to be true:

Cube(c) | Dodec(c)

Tet(b)

b=c

~Tet(c)

Tet(c)

But now we see that these statements are inconsistent (aka contradictory). This means

• they cannot all be true simultaneously
• their conjunction is always false, ie a contradiction

Question 1: When we write a proof, we start with true premises, and we derive true statements, eventually reaching a statement which is true and which is the conclusion we are trying to prove. We essentially prove that the premises, plus the intermediary steps, plus the conclusion are all true simultaneously, ie their conjunction is true. Is this interpretation of proof correct and generally applicable?

Back to the proof: in particular, if the first premise is true, then the statement Tet(c) must be false.

But if Tet(c) is false, then from the statement (b=c) & Tet(b) implies Tet(c) we know that at least one of b=c or Tet(b) must be false.

We believe our premise to be true, so it must be the statement b=c that is false.

Therefore ~(b=c) is true.

At this point, we have concluded that our conclusion must be true.

But now I would like to show another angle that I am trying to view this from, to try to understand why exactly we can justify concluding that the conclusion must be true.

If b=c is true, and Tet(b) is true then Tet(c) must be true. If Cube(c) | Dodec(c) is true, then ~Tet(c) is true.

If b=c, Tet(b), Cube(c) | Dodec(c) are true, then by conjunction introduction (b=c) & Tet(b) & Tet(c) & ~Tet(c) is true. This statement is a logical impossibility.

At this point, I assume because we give more weight to the premise, we conclude that ~Tet(c) is true, Tet(c) is false, and thus b=c must be false because b=c & Tet(b) implies Tet(c) is a true statement, and we believe Tet(b) to be true.

So our conjunction (b=c) & Tet(b) & Tet(c) & ~Tet(c) which is false, becomes ~(b=c) & Tet(b) & ~Tet(c), which is now true. Also, (b=c) & Tet(b) & Cube(c) | Dodec(c) is true.

Question 3: I am struggling to see how it is actually proved that this is always true, in every logically possible case. This third question is not specific; I am merely expressing my confusion, and if someone could provide an alternative sort of walkthrough of interpreting the final steps of a proof by contradiction in an intuitive way, I would appreciate it.

Answer 1

Question 1: No, a proof with premises A, B, and C doesn't prove that A, B, and C are true. The conclusion of a proof is guaranteed to be true if you started with true premises and used only valid methods of reasoning. You need to look elsewhere for justification of the premises and the methods of reasoning.

As to whether the intermediate statements are true, that depends on what they are. Generally intermediate statements are conclusions from the premises and previous intermediate statements. In this case, you have a shorter proof for the intermediate statement. For example, suppose the proof is the following (where capital letters represent propositions):

1. A   (premise)
2. B   (premise)
3. C   (premise)
4. D   (from 1 and 2)
therefore
E   (from 3 and 4)

In this case, steps 1, 2, and 4 represent a proof for D.

The exception (when an intermediate proposition is not true) is in a proof by contradiction. In this case, neither the hypothesis introduced to get a contradiction, nor any statement inferred with the help of that hypothesis has been proven. The hypothesis was introduced without proof, so anything concluded from it has no proof.

I wonder if part of your concern is the phrase "assumed to be true for the proof". I think that's a poor way to describe the hypothesis that is introduced in a proof by contradiction. I'd say rather that the hypothesis is introduced to see what we could prove if it were true. That is, we don't assume it's true, we just see what could be proven if it were. If it turns out that we can prove a contradiction, then obviously, it can't be true (at least, assuming the premises are true and the rules of inference are valid).

In your example, once you prove that ~(b=c), you must drop the hypothesis (b=c) and everything that you concluded from that. None of them are considered true or proven.

You also write just before Question 3:

So our conjunction (b=c) & Tet(b) & Tet(c) & ~Tet(c) which is false, becomes ~(b=c) & Tet(b) & Tet(c), which is now true. Also, (b=c) & Tet(b) & Cube(c) | Dodec(c) is true.

I don't see how you justify this. (b=c) & Tet(b) & Tet(c) & ~Tet(c) doesn't "become" anything. There is no rule of inference to lead from the falsehood of that statement to the truth of ~(b=c) & Tet(b) & Tet(c) or to the truth of (b=c) & Tet(b) & Cube(c) | Dodec(c). The entire proof from the introduction of the hypothesis to Tet(c) & ~Tet(c) has only one consequence, and that consequence is ~(b=c).

Question 3: if you are asking about the justification of your inferences in the last paragraph before Question 3, then the answer is that you can't draw those conclusions. More generally, proof by contradiction sounds a lot more complicated in mathematical form than it does in real life (like everything else).

It's just normal hypothetical reasoning:

Q. Do you think a bear knocked over the trash cans?

A. If a bear had knocked over the trash cans then we would see bear tracks in the mud. There are no bear tracks, so it must have been the wind.

Here is the same argument a bit more formally. First, we have a rule of inference: BTM: if a bear knocks over the trash cans, there will be bear tracks in the mud. Then we have the argument:

1. Either a bear or the wind knocked over the trash cans. (premise)
2. There are no bear tracks in the mud. (premise)
3a. A bear knocked over the trash cans. (hypothesis for contradiction)
3b. There are bear tracks in the mud. (BTM from 3)
4. A bear did not knock over the trash cans. (contradiction from 2 and 3b defeating 3a)
5. The wind knocked over the trash cans (disjunction 1, 4)

Addendum:

A final question is how you know that you should drop the hypothesis and not one of the other steps or rules of inference used to derive the contradiction. In formal logic, the decision is made for you because only one statement is questionable. The premises and rules of inference are all assumed to be true/valid.

However in real-life reasoning, things are seldom this clear cut, and there are often alternatives to rejecting the hypothesis. For example, maybe the bear knocked over the trash cans before it rained. Then you wouldn't expect to find bear prints in the mud, so that rule of inference was wrong. Or maybe it isn't the case that the trash cans could only be knocked down by the wind or a bear. Maybe some kids threw rocks at them from a distance to knock them down without leaving tracks.

However, these issues don't apply just to proofs by contradiction. In real life, there are always uncertainties about your premises and often uncertainties about rules of inference. The topic of whether and how much we can trust our premises and rules of logic is a large topic all on its own. Formal logic is an idealization of real reasoning. It is greatly simplified from the way real reasoning works.

The only thing are logical argument really proves is that if your premises are true and your rules of inference are valid, then your conclusion is true.

Answer 2

Here is one more way of looking at this:

Consider the argument

Premises

Cube(c) | Dodec(c)

Tet(b)

Conclusion

~(b=c)

This argument has a general form of

Premises: A, B

Conclusion: C

If this argument is valid then it is impossible for A^B to be true and C to be false. The argument can be represented with the connective "material conditional": A & B → C.

If we construct a proof of this argument by contradiction, we include a subproof that makes a temporary assumption ~C. In this subproof, we show that another statement E is a logical consequence of A & B & ~C. However, we know that ~E is a logical consequence of A & B, and so ~E is true.

This means that E is false given our premises. Under our assumption of ~C being true, E would have to be true, but it is actually false, and this means that our assumption of ~C being true is false.

Therefore, we can conclude from the subproof that C is true.

Another way to see this is that A & B & ~C & E → C is not tautologically valid. For any combination of truth values of the antecedent, the consequent can be either true or false, and this is because the antecedent is a set of inconsistent statements.

A tautologically valid statement is A & B & C & ~E → C. If we build a truth table for this sentence, we see that the final column is always true: it is never the case that the conjunction is true and C is false.