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
Cube(c) | Dodec(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)
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.