Does anyone have some simple examples of theorems in FOL that are most easily proven using proof by contrapostive? Every example that I have found so far involves aspects number theory. Any help would be appreciated.
Dan
Does anyone have some simple examples of theorems in FOL that are most easily proven using proof by contrapostive? Every example that I have found so far involves aspects number theory. Any help would be appreciated.
Dan
Taking Carl's tip, say you want to prove that CpCqp. In one natural deduction system, with proof by contrapositive as a derived rule of inference you can then proceed as follows:
1 | NCqp hypothesis 2 || p hypothesis 3 ||| q hypothesis 4 ||| p 2 repetition 5 || Cqp 3-4 conditional introduction 6 || KCqpNCqp 1, 5 conjunction introduction 7 | Np 2-6 negation introduction 8 CNCqpNp 1-7 conditional introduction 9 CpCqp 8 proof by contrapositive
An even shorter example goes:
1 | p hypothesis 2 Cpp 1-1 conditional introduction 3 CNpNp 2 proof by contrapositive