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 n∈N and want to show that ∀x1,x2,...,xn∈N, P(x1,x2,x3,...,xn) is true.
We let x1,x2,x3,...,xn∈N and confirm the base case is true, namely P(1,1,1,...,1).
Inductive step over x1: We let k1∈N 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.
Inductive step over x2: We let k2∈N and assume P(h1,k2,1,...,1) is true for some h1∈N. Our goal here is to show P(h1,k2+1,1,...,1) is true.
Inductive step over x3: We let k3∈N and assume P(h1,h2,k3,...,1) is true for some h1,h2∈N. 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.
- Inductive step over xn: We let kn∈N 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,...,hn∈N, P(h1,h2,h3,...,hn) is true. Therefore, ∀x1,x2,...,xn∈N, 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