多重帰納法

質問

任意の自然数k,n1,…,nkに対して命題P(n1,…,nk)を証明する方法は次のようにしたらよいでしょうか？それとももっと合理的な方法があるでしょうか？類似の質問などがあればそれも教えて下さい.

∀k∈N,Q(k)≡(∀n1,…,nk∈N,P(n1,…,nk))とし
(1) Q(1)(⇔P(n1))を完全帰納法で示す
(2) Q(k)⇒Q(k+1)を示す
(2-1) Q(k)⇒P(n1,…,nk,1)を示す
(2-1) Q(k),P(n1,…,nk,i)⇒P(n1,…,nk,i+1)を示す

回答No.3

betagamma · ベストアンサー

あー、確かに誤解してましたね。
私がやったのは、ある固定されたｋにたいして、ｋ個の変数をとる命題P(n1,n2,...,nk)があるとき、これを、ｋ変数の場合から１変数の場合に向かって崩して証明する方法ですね。
これは、これであっていると思いますが、今は、ｋを無限大にしようと思っているので、使えませんね。

そこで、考えてみたところ、余り自信がないのですが、次のような、かなりとっぴなことを思いついたので、書いてみます。

まず、ちょっと記法を変えます。
証明したいのは、
P(n1),P(n1,n2),P(n1,n2,n3),...
ですが、nkは自然数ですから、n1>=1,n2>=1,n3>=1,...ですよね。0は使われていないわけですから、Pを次のように、形式的に拡張できます。
P(n1)→P(n1,0,0,0,0,...)
P(n1,n2)→P(n1,n2,0,0,0...)
P(n1,n2,n3)→P(n1,n2,n3,0,0,...)

こう書くことにすると、問題は、
n1,n2,n3,...は、非負の整数（０を含む）のとき、
P(n1,n2,n3,...,nk,...)が成り立つことを証明せよ。
ただし、P(0,0,0,...)は、常に成り立つと定義する。
とかけますね。

こうすると、形式的に、Pは、無限次元非負整数ベクトルとしてあらわせます。ただし、演算は、まだ定義されていませんので、今の段階では、単なる集合です。無限次元非負整数ベクトル全体の集合を、Aとします。
次のように考えます。まず、Aの部分集合Sを定義域とします。このSの元については、逐一証明するとします。次に、Sの元の間に次のように二項演算子＋を導入します。a,b∈S,c∈Aのとき、a+b=cを、「aかつbが真⇒cが真」をあらわすと形式的に定義します。すると、P(0,0,0,....)は、常に真と定義しましたから、任意のa∈Sに対して、「aかつP(0,0,0,...)が真⇒aが真」がなりたつので、a+P(0,0,0,...)=aが成り立ちます。
つまり、P(0,0,0,...)は、単位元になります。任意の元が真ということは、単位元は真なのですから、任意の元が単位元に一致してしまうような演算+を定義し、その演算＋を証明すれば、全部が証明されたことになります。

まず、質問者さんの方法があっていますので、質問者さんの方法を、この表記で書いてみます。
(1)
P(n1,0,0,0,....)が真
P(n1,0,0,0,...)=P(0,0,0,0,...)
(2-1)
P(n1,n2,...,nk,0,0,0,...)+P(0,0,0,...)
=P(n1,n2,...,nk,1)
(2-2)
P(n1,n2,...,nk,i,0,0,0,...)+P(n1,n2,...,nk,0,0,...)
=P(n1,n2,...,nk,i+1,0,0,0,...)

と、形式的に書き換えられるわけです。

さて、ここまで書いて思ったのは、もし、
P(n1,n2,n3,...,nk,...)+P(m1,m2,m3,...,mk,...)
=P(n1+m1,n2+m2,n3+m3,....,nk+mk,...)
が成り立つような線形の世界であれば、このルールと
P(1,0,0,0,...),P(0,1,0,0,...),...
といった基底を証明するだけで終わりです。

そこまで強くなくても、任意のnkについて、
P(n1,n2,...,nk,...)+P(0,0,0,...)=P(n1,n2,...,(nk)+1,...)
が示せれば、やっぱり、同じ基底で証明できてしまいます。

結局、この非負整数ベクトルの集合の中で、いかにうまい基底をとるか、という話になっていくのではないでしょうか。

お礼

ありがとうございます．
線形空間の問題として取り扱おうとする発想が素晴らしいと思いました.スカラー倍が特に必要なければ、ベクトル空間でなく群でもいいんでしょうね.ですが証明したい事柄によっては、スカラ倍も導入してもいいかもしれません.

回答No.2

betagamma

No.1です。

任意のk個の自然数について、二次元のカントールの対角線論法と、添え字の振りなおしの繰り返しで、できますね。
とりあえず、３次元のバージョンで、書いてみました。k個の場合も、これと同じです。

P(n1,n2,n3)
P(1,1,1)を示す。
P(n1,(1,1))で成り立つと仮定。
P(n1,(n,n))のとき、P(n1,(1,n+1))が成り立つことを示す。
P(n1,(k,n))のとき(1<=k<=n-1)、P(n1,(k+1,n))を示す。
これで、P(n1,(1,1))で成り立つならば、任意のn2,n3∈Nに対して、P(n1,(n2,n3))が成り立つことが示された。
Q(1,1)=P(1,1,1)
Q(1,2)=P(1,1,2)
Q(1,3)=P(1,2,2)
Q(1,4)=P(1,1,3)
Q(1,5)=P(1,2,3)
...
とQ(n1,n2)を定義。

Q(1,1)=P(1,1,1)は示された。
Q(n,n)のとき、Q(1,n+1)を示す。
Q(k,n)のとき(1<=k<=n-1)、Q(k+1,n)を示す。

これで、任意の自然数、n1,n2に対して、Q(n1,n2)が成り立つ。
だから、任意の自然数、n1,n2,n3に対して、P(n1,n2,n3)が成り立つ。

お礼

ありがとうございます．
ご回答を読んだ限りではちょっとハッキリしませんが
もしかしたら、少し質問の意味を誤解されているかもしれないので質問内容についてもう少し説明させて下さい.

実はkは固定していないのです.
つまり
∀n1∈N,P(n1)を示す
∀n1,n2∈N,P(n1,n2)を示す
…
∀n1,n2,…,nk∈N,P(n1,n2,…,nk)を示す
…
という事全部を証明したいのです.

因みにこのようなことを知りたい発端は
部分分数の分解の証明を書き直すことです.
f,g∈R[x] (実数係数の一変数多項式)とし
deg(f)>deg(g),
f=Π[i=1～k](x-ai)^mi*Π[j=1～l]((x-aj)^2+bj^2)^njと因数分解されるとき、このfで部分分数の形を与える命題をP(m1,m2,…mk,n1,…,nl)とします.
全てのm1,m2,…mk,n1,…,nlについてPが真であることを示すのに質問のような帰納法を使う必要があります.

回答No.1

betagamma

k個の自然数についてであれば、それが、一番妥当なやり方ですかね。

ただ、２次元ぐらいであれば、（P(n1,n2)であれば）、カントールの対角線論法が使えます。つまり・・・
P(1,1)を示す
P(1,2)を示す
P(2,2)を示す
P(1,3)を示す
P(2,3)を示す
P(3,3)を示す
P(1,4)を示す・・・

すなわち、
P(1,1)を示す。
P(n,n)を仮定したとき、P(1,n+1)を示す。
P(k,n)を仮定したとき(1<=k<=n-1)、P(k+1,n)を示す。
の手順でできます。

P(k,n)を行列と思って書いてみればわかりますが、表を右上から左下に、斜めに番号付けすることで、一列にしてしまおう、という考え方です。

以下は、あまり自信がないのですが、可算個（自然数の濃度）×可算個は、可算個になるので、何次元でも使えるはずです。例えば、３次元では、
P(1,1,1)を示す
P(1,1,2)を示す
P(1,2,2)を示す
P(2,1,2)を示す
P(2,2,2)を示す
P(1,1,3)を示す...

とやっていけば、同じことができるはずです。