2
$\begingroup$

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(x_1, x_2, x_3, ..., x_n)$ for some $n\in \mathbb{N}$ and want to show that $\forall x_1, x_2,..., x_n\in \mathbb{N}$, $P(x_1, x_2, x_3, ..., x_n)$ is true.

  1. We let $x_1, x_2, x_3, ..., x_n\in \mathbb{N}$ and confirm the base case is true, namely $P(1, 1, 1, ..., 1)$.

  2. Inductive step over $x_1$: We let $k_1\in \mathbb{N}$ and assume the statement $P(k_1, 1,1,...,1)$ is true. Our goal here is to show $P(k_1+1, 1, 1, ..., 1)$ is true.

  3. Inductive step over $x_2$: We let $k_2\in \mathbb{N}$ and assume $P(h_1, k_2, 1, ..., 1)$ is true for some $h_1\in \mathbb{N}$. Our goal here is to show $P(h_1, k_2+1, 1, ..., 1)$ is true.

  4. Inductive step over $x_3$: We let $k_3\in \mathbb{N}$ and assume $P(h_1, h_2, k_3, ..., 1)$ is true for some $h_1, h_2\in \mathbb{N}$. Our goal here is to show $P(h_1, h_2, k_3+1, ..., 1)$ is true.

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

  1. Inductive step over $x_n$: We let $k_n\in \mathbb{N}$ and assume $P(h_1, h_2, h_3, ..., k_n)$ is true for some $h_1, h_2, ... \in \mathbb{N}$. Our goal here is to show $P(h_1, h_2, h_3, ..., k_n+1)$ is true.

We have shown $\forall h_1, h_2, ..., h_n\in \mathbb{N}$, $P(h_1, h_2, h_3, ..., h_n)$ is true. Therefore, $\forall x_1, x_2,..., x_n\in \mathbb{N}$, $P(x_1, x_2, x_3, ..., x_n)$ is true.

$\endgroup$
3
$\begingroup$

In practice I would hope that the statement $P(x_1,\dotsc,x_n)$ would be highly symmetrical, and then it would suffice just prove the $i$th 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 $\forall x_1 P(x_1,\cdots,1)$, and if I have an inductive proof of $\forall x_1,\cdots,x_i\,P(x_1,\cdots,x_i,1,\cdots,1),$ then I can derive a proof of $\forall x_1,\cdots,x_i,x_{i+1}\,P(x_1,\cdots,x_i,x_{i+1},1,\cdots,1),$ for $i<n$, then I have induction over all multiindices of length $n$. As above, this only works if the structure of the proposition $P$ allows it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.