
Re: Double Induction  A brief note that may help
Posted:
Jul 16, 2013 4:48 AM


On Mon, 15 Jul 2013, David N Melik wrote:
> > 1. Base case: > > Ordinary induction: Prove P(1) > > Double induction: Prove P(1,1) > > > > 2. Inductive step: > > Ordinary induction: For x in N, assume P(x) and prove P(x+1) > > Double induction: For x, y in N, assume P(x,y) and prove P(x+1,y) > > and P(x,y+1). > > Sounds like an interesting idea... is there an example proof somewhere? > Proof is simple. Let S be a set of interger pairs with (1,1) in S and for all n,m in N, If (n,m) in S, then (n+1,m) and (n,m+1) in S.
Assume (a,b) not in S and let let c be the smallest c in N for which (c,b) not in S. Next let d be the smallest d in N for which (c,d) not in S.
Case c = 1. Then (1,d) not in S and 1 < d. Thus (1,d1) in S and by hypthesis, (1,d) = (1, (d1)+1) in S, a contradiction.
Case 1 < c. Then (c1,d) in S. Thus by hypothesis, (c,d) = ((c1)+1,d) in S a contradiction.
Exercise. State and prove the base and induction steps of nfold induction. Can there be an aleph_0fold induction?

