過去の質問「1+1=2の証明って?」
http://oshiete1.goo.ne.jp/kotaeru.php3?q=217225
を精読しました。
過去の質問では、小さい自然数の定義した上で、プラスの定義を3変数関数fを使って、
●f(n,m,m)=n
●m≠kのとき、f(n,m,k) = f(s(n),m,s(k))
そして
●+(n,m)=f(n,m,0)
とされていました。
ここでは少し違って考えます。
まず、自然数(ここでは0も含める)の定義ですが、Peano's Axioms
http://mathworld.wolfram.com/PeanosAxioms.html
をみていただくとして、
自然数 a の 後者を suc(a) と書くことにします。
小さい自然数では、
0 := {}
1 := suc(0)
2 := suc(1)
3 := suc(2)
などとします。
次に+の定義ですが、帰納的に、
a+0:=a
a+suc(b):=suc(a+b)
で定義します。
すると、
1+1=1+suc(0)=suc(1+0)=suc(1)=2
と証明できたことになります。
×の定義を、帰納的に、
a×0:=0
a×suc(b):=(a×b)+a
で定義します。
すると、
2×3=2×suc(2)
=(2×2)+2
=(2×suc(1))+2
=((2×1)+2)+2
=((2×suc(0))+2)+2
=(((2×0)+2)+2)+2
=((0+2)+2)+2
=((0+suc(1))+2)+2
=((suc(0+1))+2)+2
=((suc(0+suc(0)))+2)+2
=((suc(suc(0+0)))+2)+2
=((suc(suc(0)))+2)+2
=((suc(1))+2)+2
=(2+2)+2
=(2+suc(1))+2
=(suc(2+1))+2
=(suc(2+suc(0)))+2
=(suc(suc(2+0)))+2
=(suc(suc(2)))+2
=suc(3)+2
=4+2
=4+suc(1)
=suc(4+1)
=suc(4+suc(0))
=suc(suc(4+0))
=suc(suc(4))
=suc(5)
=6
と証明できたことになります。
上記のプラスの3変数関数fでの定義と、今回のプラスやカケルの帰納的定義は同値ですか?
違いがあるとしたらそれは何ですか?
ちなみに、s(n)=suc(n)です。
No.2ベストアンサー
- 回答日時:
No.1へのコメントについてです。
> 3変数関数fでの定義は、数え上げ、かつ、記述が複雑な傾向がありそうです。
> 再帰的定義は、数え下げ、かつ、記述が簡易な傾向がありそうです。
手続き型のプログラミングに慣れていると、再帰的な定義は分かりにくくて困るようです。手順に沿って順番にやっていくループによる操作の方がイメージしやすい。これはひとつには、「この関数は結局何をやってるのか」を知っているかどうかの違いだと思います。実際、fjfsghさんの+が足し算を意味していると分かっていて定義を見るのと、予備知識なしに意味を知るために定義を読むのとでは難しさが全く違います。 後者の場合、再帰が複数箇所に現れるともっと大変で、例えば、Ackermann関数
A(0,n) = n+1 (n≧0のとき)
A(m,0) = A(m-1,1) (m≧1のとき)
A(m,n) = A(m-1,A(m,n-1)) (m≧1, n≧1のとき)
が何をやるものか、定義だけ見てもなかなか分からないでしょう。
手続き型であるfの方は、補助変数が沢山あるので、操作に従ってナニがどう変わって行くか、ナニが変化しないかが見つけやすく、意味を(直感による帰納を使って)推測しやすいのだろうと思います。
ですから、過去の質問「1+1=2の証明って?」において、「どういう演算を表しているか」を先に言わずに、しかも分かりやすく説明する、という目的には、fの方が適していた訳です。
しかし、数学の対象として扱う場合には、fは冗長な補助変数を抱えているのが邪魔ですし、定義が長いので大変。再帰的な定義は数学的帰納法に素直に乗る(数学的帰納法と再帰的定義は表裏一体なのだから当たり前)。だから、再帰的定義の方が大抵便利です。
計算可能性(計算不可能な関数とはどんなものか。真偽を決定できない命題はあるか)を論じるために、算術を手続き型のプロセスとして構築し直したのがアラン・チューリング、再帰的な関数(原始帰納関数、帰納関数)として構築し直したのがクルト・ゲーデルでしょう。
結局、両者の方法は同等であることが示されました。これらは情報工学の基礎理論である「計算の理論(計算論、アルゴリズム理論)」と呼ばれる分野の話であり、同時に、ヒルベルトの形式主義(数学を記号の操作とみなすことによって、あらゆる定理を自動的に導く方法を構築できないか?)の(否定的な)研究、という意味を持っていて、20世紀の数学の重要な流れのひとつと言えます。
なお、チューリングの考えた「チューリングマシン」は、あるプログラムの出力を別のブログラムに入力として与える、というやり方で複雑な計算を構成します。ゲーデルの帰納関数では、同じ事をやるのに、関数の変数に別の関数を代入する、というやり方で実現します。それぞれ手続き型のプログラミング言語と再帰型のプログラミング言語(LISP, PROLOGなど。もちろんC言語でも再帰は書けますが)の基礎になっています。
No.1
- 回答日時:
命題:任意の自然数a,bについてf(a,b,0)=a+b (右辺はfjfsghさんが定義した+)
が証明できるでしょう。
自然数の定義を与えたことによって、証明に帰納法が使えるようになった、という事がポイントだろうと思います。
> 違いがあるとしたらそれは何ですか?
指の出し入れ、という操作論的な解釈ができるfですら技巧的と言われてしまうような文脈において、fjfsghさんの+を持ち出しても質問者には理解できなかっただろう、という事でしょうか。
ありがとうございます。
ここらへんは情報工学的、プログラミング的分野なのですね。僕には未知の分野です。
3変数関数fでの定義は、数え上げ、かつ、記述が複雑な傾向がありそうです。
再帰的定義は、数え下げ、かつ、記述が簡易な傾向がありそうです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 【高1 数学Ⅰ 二次関数】 二次関数 f(x)=x^2-4ax+8a がある。ただし、aは正の定数と 3 2022/07/23 15:46
- 高校 合成関数の定義域につきまして 1 2022/05/18 17:26
- 数学 関数の極値と微分係数の関係について 6 2023/04/23 14:35
- 数学 「違います 質問11 n≦-2ではz≠π/2で g(z)=tan(z)/(z-π/2)^(n+1) 3 2022/07/16 18:12
- 数学 2次関数y=f(x)=−x^2+2ax+1(−1≦x≦1)の最大値を求めよ。 参考書は a<-1 - 3 2023/02/06 20:31
- 数学 モデルのパラメータの定義がいまいちわかりません。 3 2022/10/11 15:16
- 数学 変数と範囲について、(空集合について)質問です。 数学苦手です。よくわからないところで引っかかりがち 4 2022/09/27 13:16
- 高校 数学Ⅰの一次関数について。 6 2023/08/15 02:15
- 数学 『0⁰=1・□』か? 5 2022/10/03 03:34
- Visual Basic(VBA) Excel のユーザー定義関数でソルバーが動作しない 1 2022/09/05 19:51
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
なにしてるかわからない。。
-
皆さん定義を教えてください 「...
-
自然数 整数 有理数 実数 加法 ...
-
無限から無限を引いたら何にな...
-
べき乗
-
「logx^2=2logx」が間違って...
-
1未満と1以下の違い
-
ACCESS VBAでインポート定義の場所
-
ネットストーカーの定義 最近SN...
-
「互いに素」の定義…「1と2は互...
-
定義付けできない言葉について
-
マイナス7は素数ですか?
-
普通の人は人を激しい責めます...
-
環の乗法に関して左(右)逆元...
-
2進数の符号ビットの入った数...
-
集合間演算に関する質問
-
日本語 ことば ひとまわり ふた...
-
三角関数(たとえばf(x)=sinxと...
-
ACCESS IIF関数 複数条件の設...
-
数学の「無定義」での理論の展開
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
皆さん定義を教えてください 「...
-
べき乗
-
無限から無限を引いたら何にな...
-
1未満と1以下の違い
-
p⇒q=(¬p)∨qについて
-
「logx^2=2logx」が間違って...
-
数字の1とは何なのか?
-
「互いに素」の定義…「1と2は互...
-
変数の宣言の名称を教えてくだ...
-
ACCESS VBAでインポート定義の場所
-
日本語 ことば ひとまわり ふた...
-
ACCESS IIF関数 複数条件の設...
-
Excelファイルの「数式」タブ→...
-
e<3の証明を教えてください。
-
なぜ小数は自然数ではないので...
-
ヘシアンが0の場合どうやって極...
-
2進数の符号ビットの入った数...
-
最大元と極大元の定義の違いが...
-
eの0乗は1ってどういう原理です...
-
フーリエ級数展開の初項はなぜa...
おすすめ情報