1

In slides: http://www.mathdb.org/notes_download/elementary/algebra/ae_A2.pdf I read the scheme for 2-dimensional induction, but Exists an scheme for n-dimensional induction? Thanks in advance!

mle
  • 2,287

1 Answers1

2

According to this slides we can construct $k$-dimensional scheme this way:

Let $S(n_1, n_2, \cdots, n_k)$ denote a statement involving $k$ variables $n_1,n_2, \cdots, n_k$. Suppose:

(i) $S(1,1,\cdots, 1)$ is true.

(ii) $S(1,n_2, \cdots, n_k)$ is true for all positive integers $n_2,\cdots, n_k$.

(iii) If $S(n_1,n_2,\cdots, n_k)$ holds for some positive $n_1,n_2,\cdots, n_k$, then $S(n_1+1,n_2, \cdots, n_k)$ is also true.

Then $S(n_1, n_2, \cdots, n_k)$ is true for all positive integers $n_1,n_2, \cdots, n_k$.

Note that sometimes you can prove (ii) using $(k-1)$-dimensional induction putting $T(n_2,\cdots, n_k)=S(1,n_2,\cdots, n_k)$ and prove that $T$ is true for all positive integers by induction(it's an idea in $2$-dimensional scheme).

agha
  • 10,038
  • iii) is $\exists n_1,n_2,....,n_k \in \Bbb{N}(S(n_1,n_2,\cdots, n_k) \Rightarrow S(n_1+1,n_2, \cdots, n_k))$!? – mle Jul 14 '14 at 10:43
  • 1
    No, (iii) is $\forall n_1,n_2,\cdots, n_k(S(n_1,n_2,\cdots, n_k) \Rightarrow S(n_1+1,n_2,\cdots,n_k))$. – agha Jul 14 '14 at 18:26
  • I am thinking, Can I use the following scheme: $$\text{if}$$$$S(1,1,\cdots, 1)$$$$\forall n_1,n_2,\cdots, n_k(S(n_1,n_2,\cdots, n_k) \Rightarrow S(n_1+1,n_2,\cdots,n_k))$$$$\forall n_1,n_2,\cdots, n_k(S(n_1,n_2,\cdots, n_k) \Rightarrow S(n_1,n_2+1,\cdots,n_k))$$$$\cdots \cdots \cdots$$$$\forall n_1,n_2,\cdots, n_k(S(n_1,n_2,\cdots, n_k) \Rightarrow S(n_1,n_2,\cdots,n_k+1))$$$$\text{then}$$$$\forall n_1,n_2,\cdots, n_k(S(n_1,n_2,\cdots, n_k))$$ ??? Thanks in advance! :) – mle Jul 14 '14 at 18:37
  • 1
    Yes, you can. Note that using first line and $s(1,1,\cdots,1)$ you can prove that $S(n,1,1,\cdots,1)$ for all $n$, using second you and $S(n,1,1,\cdots,1)$ you can prove $S(n,m,1,1,\cdots,1)$ for all $n,m$ and in the same way you get $S(n_1,n_2,\cdots,n_k)$. – agha Jul 14 '14 at 21:09