Here is a special case of how we use proof by induction:
We want to prove P->Q by induction on n.
base case: n=0, P always false. Then P->Q is a tautology.
step case: show that (P->Q)(n-1) => (P->Q)(n)
Then is it still a constructive proof?
If we consider to prove (P->Q)(0) => (P->Q)(1), which we actually need to prove
(P->Q)(1) without any helps because (P->Q)(0)tell us nothing. Then it may has two situation, one is P(0) is also false, that makes (P->Q)(1) a tautology. So Now let's consider n=j, where P(j) is true, and P(j-1) is false. Then if we want to prove
(P->Q)(j),without any help from (P->Q)(j-1). Once we successfully prove (P->Q)(j), we can prove (P->Q)(n), where n>j, with the help of induction hypothesis,that is if P(n-1) is true, we can get Q(n-1), with the help of Q(n-1), we try to prove (P->Q)(n).
The thing is,if the j above doesn't exist(and we know that), then of course it's easy to explain. If j does exist, we still need to show (P->Q)(j) is true, then we can go on to use induction hypothesis. But Am I right?
Monday, February 1, 2010
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment