by Brian Bosse, Copyright May 01, 2010, all rights reserved. 622 views
In the last post we looked at a direct derivation (DD) in the propositional calculus. In this post we will consider an indirect derivation (ID). ID is based on the idea that if φ leads to a contradiction, then φ cannot be, and if φ cannot be, then ¬φ is the case. It is rooted in the law of non-contradiction and the law of excluded middle, which are as follows…
Law of Non-Contradiction (LCN): Something cannot be both A and not-A at the same time and in the same relationship.
Law of Excluded Middle (LEM): You either have A or not-A.
So, here is the reasoning:
If B leads to both A and not-A, and you cannot have both A and not-A (LCN), then you cannot have B. If you cannot have B, then by LEM you have not-B. As such, this line of reasoning can be used to establish not-B indirectly by assuming B, and from this deriving a contradiction. In other words, if one assumes B and arrives at a contradiction, then not-B has been established. Let’s visit again the following argument…
Premise 1: If Socrates did not die of old age, then the Athenians condemned Socrates to death.
Premise 2: The Athenians did not condemn Socrates to death.
Show: Socrates did die of old age.
To begin, we need to translate this argument into symbolic sentences. Here is the translation…
P: Socrates did die of old age.
Q: The Athenians condemned Socrates to death.
Premise 1: ¬P → Q
Premise 2: ¬Q
Show: P
Now, in our previous post we proved this very argument directly by using MT. This time we are not going to use MT, but rather we will use ID.
1. Show P [ID]
Since we want to prove P by the ID method, we will assume ¬P and attempt to derive a contradiction. Since our assumption is not a premise or does not follow directly from an inference rule, but only is being assumed “for the sake of the argument,” we will indicate this by indenting the line.
2. Assume ¬P [Assumption for ID]
At this point we introduce our first premise…
3. ¬P → Q [Premise 1]
(Technically, 3 does not need to be indented as our assumption was. However, I want to use 3 within the framework of our assumption, and as such have indented it. The same can be said for 5 below.)
From here we can now apply an instance of MP on 2 and 3…
4. Q [MP – 2 and 3]
We now introduce our second premise…
5. ¬Q [Premise 2]
We have derived our contradiction (lines 4 and 5), and by the reasoning of ID we have established what we set out to prove. We can now cross through ‘Show’ in line 1. Here is the full proof…
1.ShowP [ID] 2. Assume ¬P [Assumption for ID] 3. ¬P → Q [Premise 1] 4. Q [MP – 2 and 3] 5. ¬Q [Premise 2] Q.E.D.