The premise of 'proof by contradiction' is that a true statement can never imply a false statement.
In my lectures (intro to logic), this has been brushed aside as 'obvious', but is there a formal proof for this fact?
Asked
Active
Viewed 1,560 times
3 Answers
6
Most mainstream logical systems have a deduction rule called modus ponens, meaning that if $p$ is true and $p \to q$ is true then $q$ is true. Thus if $p$ is true and $q$ is false, then $p \to q$ cannot be true, otherwise $q$ would be true. (And it wouldn't make much sense for $q$ to be simultaneously true and false!)
Clive Newstead
- 64,925
2
If $p$ is true and $q$ is false, then $p\implies q$ is equivalent to $\neg p\vee q$, and since $\neg p$ is false and $q$ is false, $\neg p \vee q$ is also false...
5xum
- 123,496
- 6
- 128
- 204
-
Nitpick: be careful, in some common logical systems (such as intuitionistic logic), $\to$ is not definable in terms of $\neg$ and $\vee$ and has to be taken as primitive. – Clive Newstead Aug 15 '14 at 19:43
-
@Clive: Does that mean that $\to$ in intuitionistic logic hasn't invented the wheel yet? :-D – Asaf Karagila Aug 15 '14 at 19:51
1
This is an assumption, that first-order logic (or propositional calculus if you will) is sound, and that our inference rules do not prove a contradiction.
Now write down the truth table for $p\implies q$, and since we assume that the basic rules of our game are "correct", this means that we have to obey this truth table when we have $p\implies q$. In particular if $p$ is true and $q$ is false then the implication itself is false.
The reason this is usually brushed aside in introductory courses is that we don't want to burden the student. We work in a mathematical system "so obviously this system is consistent". There's no need to worry about this. Later, in intermediate logic courses you will often meet a proof that first-order logic is sound.
beep-boop
- 11,595
Asaf Karagila
- 393,674