抽象化で証明できる命題は増えないだろ (52ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
38(1): 02/11(火)02:26 ID:a715F0Tt(1/5) AAS
>>37
ファン・デル・ヴェルデンの定理：
任意の自然数 k, l に対して、自然数 n(k, l) が存在して、
連続する n(k, l) 個の自然数をどのように k 色に塗り分けても、
同色で長さが l の等差数列が存在する。
この定理は帰納法で証明できるが、安直に帰納法を適用するなら、
・ k,l に対する二重帰納法を使う
省3
39: 02/11(火)02:32 ID:a715F0Tt(2/5) AAS
ファン・デル・ヴェルデンの定理の証明は色々あるが、
帰納法が回るように定理の内容を大幅に抽象化しなければならず、
どう抽象化すればいいのかが腕の見せどころになる。
グラフ理論の言葉で書き換えて抽象化した上で帰納法を使ったり、
あるいは Hales–Jewettの定理 のような拡張の仕方もある。
もともとの定理から離れすぎない抽象化の仕方は wiki に載っていて、
もともとのパラメータ「 k, l 」とは異なる方向性からの
省1
40: 02/11(火)02:46 ID:a715F0Tt(3/5) AAS
なぜ>>38の形のままでは帰納法が回らないのか？
それは、定理の内容が具体的すぎて、「変形理論」の構築に失敗するからだ。
なぜ大幅に抽象化すると帰納法が回るようになるのか？
それは、抽象化すると「変形理論」が作りやすいからだ。
41: 02/11(火)02:47 ID:a715F0Tt(4/5) AAS
変形理論の構築に失敗していると、少し変形しただけでも、
変形前のフレームワークから はみ出てしまう。帰納法の場合、
そこで帰納法の前提に帰着できないことになるので、失敗に終わる。
42: 02/11(火)02:49 ID:a715F0Tt(5/5) AAS
変形理論の構築に成功していると、変形したあとでも、
変形前と同じフレームワークに収まる。帰納法の場合、
そこで帰納法の前提に帰着できることになるので、成功する。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.005s