Tuesday, February 5, 2019

Multidimensional Induction for n Variables




I am wanting to use a proof technique known as multidimensional induction, and I am having a hard time finding a situation that explains how to use this technique clearly for three or more variables. I want to use this technique properly and have listed the steps below which would make sense to me, but they could be wrong. Please, feel free to copy the code as it is a lot of typing and post answers as to how to conduct this proof technique properly.



Let us say I have a statement that is P(x1,x2,x3,...,xn) for some nN and want to show that x1,x2,...,xnN, P(x1,x2,x3,...,xn) is true.





  1. We let x1,x2,x3,...,xnN and confirm the base case is true, namely P(1,1,1,...,1).


  2. Inductive step over x1: We let k1N and assume the statement P(k1,1,1,...,1) is true. Our goal here is to show P(k1+1,1,1,...,1) is true.


  3. Inductive step over x2: We let k2N and assume P(h1,k2,1,...,1) is true for some h1N. Our goal here is to show P(h1,k2+1,1,...,1) is true.



  4. Inductive step over x3: We let k3N and assume P(h1,h2,k3,...,1) is true for some h1,h2N. Our goal here is to show P(h1,h2,k3+1,...,1) is true.





We continue our inductive steps until we have expended all variables through our inductive steps except xn.





  1. Inductive step over xn: We let knN and assume P(h1,h2,h3,...,kn) is true for some h1,h2,...N. Our goal here is to show P(h1,h2,h3,...,kn+1) is true.





We have shown h1,h2,...,hnN, P(h1,h2,h3,...,hn) is true. Therefore, x1,x2,...,xnN, P(x1,x2,x3,...,xn) is true.




Answer



In practice I would hope that the statement P(x1,,xn) would be highly symmetrical, and then it would suffice just prove the ith case and be done with it.



In principle, however, without any symmetry assumptions, I agree that induction will need to be done separately in each variable.




Perhaps you should also consider doing induction in the number of variables: I have an inductive proof of x1P(x1,,1), and if I have an inductive proof of x1,,xiP(x1,,xi,1,,1), then I can derive a proof of x1,,xi,xi+1P(x1,,xi,xi+1,1,,1), for $i

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...