ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

ペアノの公理と特殊な数学的帰納法

今回は、あんまり深く考えないで数学について記事にしようということで、以前の記事で数学的帰納法を使ったときに思ったことを書きます。

あんまり考えて書いていないので、特に新たな発見をしたわけではないのですが、ちょっとしたアイデアとして。


数学的帰納法は、なにも0や1(自然数の最初の数)から始まって1つ後ろの数、その1つ後ろの数というふうにドミノ倒しされるとは限らず、

0や1でない自然数から始まって、1つ後ろでないところの数へとドミノ倒しされることがあります。

数学的帰納法の応用ですね。
我らがWikipediaにも書いてあります。

数学的帰納法 - Wikipedia
https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95


そんでもって、数学的帰納法は形式論理で扱うときにどのようになるかというと、自然数に関する公理のひとつとなります。

ペアノの公理というやつで、それの一番最後の公理が数学的帰納法を正当化するための公理となります。

ペアノの公理 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%A2%E3%83%8E%E3%81%AE%E5%85%AC%E7%90%86


余談ですが、こういうふうに自然数はどんな性質なんだろうと突き詰めて公理を発見するのではなく、自然数とはこういうものなんだという性質を、神ではない我々が定義することができるというのは、なんか数学の面白さのひとつですよね~。

まあ、私が定義できるほど実力はないのですが…。
ただ、こういう公理主義的な考えの上での数学は、自分で作れるという意味でプログラミングと似ていると思います。




さて、ペアノの公理で数学的帰納法を正当化するためにある公理は論理式で書くと

∀x(P(x)→P(suc(x)))∧P(0)→∀xP(x)

になると思います。
ここで0は自然数の一番最初の数で、suc(x)はxの次の数を示す関数です。

これらが存在することもペアノの公理で要請されています。
正確にはsucという関数が存在することを一階述語論理で述べることはできないので、すべての個体xについてsuc(x)という個体が存在することを述べています。

そしてつまり、この論理式は、すべてのxにおいてxが性質Pを満たすなら、xの次の数も性質Pを満たす、そして一番最初の数が性質Pを満たすなら、すべてのxにおいて性質Pを満たすということを表しています。


これで確かに最初の自然数が性質を満たすことと、任意の自然数が性質を満たすならその1つ後ろの自然数も性質を満たすことから、すべての自然数で性質を満たすことをいうタイプの数学的帰納法なら公理から成立すると思うのですが、

前述した応用的な数学的帰納法は成立しないのではないか!!


これはちょっとペアノの公理、欠陥品ではないでしょうか。
まあ私はペアノの公理について詳しく勉強したことはないので、見当違いなことを言ってるのかもしれませんが…。


というわけで、どうすれば応用的な数学的帰納法も成立させられる公理を作れるか、無い知恵を絞り出してみます。
すごくプログラミング的な頭の使い方をします。

問題は、スタートとなる数、次の数、最終的に性質Pを満たす数の集合がそれぞれ、0、suc(x)、すべてのxとして固定されていることです。

ここを取り替えられるようにしたいということになります。


まずスタートの数、適当な自然数nにしてしまいましょう。

次にsuc(x)ですが、自然数の性質としてsucという関数が存在しなければならないのはいいとして、それとは別に数学的帰納法のためのドミノ倒しの次のドミノを表す関数が要ります。

next(x)とします。

ただ、その関数の定義域と値域を表す集合は自然数全体ではなく自然数の部分集合になるはずです。
その集合Aを定義するには

1. A∋0
2. ∀x(A∋x→A∋next(x))

を満たすという条件が必要になって、関数nextの定義と循環してしまいます。


で、どうするかというと、ひとつはnextの定義域と値域を自然数全体にしてしまって、任意の自然数aにおける合成関数next^a(0)の値以外は適当な値にしてしまうか、

それか集合Aを頑張ってnext関数を使わずに定義するかになります。


今回は後者の手段、つまり集合Aを先に定義することを試みます。

感覚的に最初の数nと、その次の数、その次の数、その次の数…を集めた集合とします。
次の数というのは結局next(x)なので、ようはnext(x)を形式的に扱えないからフィーリングの世界に移しただけになります。

結局は前者の手段を使っていると言えるでしょう。


これで材料が揃いました。
最初の数n、次の数を表す関数next(x)、性質Pを満たす数の集合Aです。

まず、これらの材料が存在することを条件φとします。

数学的帰納法の応用的な使い方もカバーできる公理は

φ→(∀x(P(x)→P(next(x)))∧P(n)→∀x(A∋x→P(x)))

となります。


以上の議論にツッコミするならば、まずフィーリングとかなんとか、ぜんぜん形式的じゃねえだろというのと、

もうひとつ重大な欠陥を書いてから発見しました。


next(x) = x - 1とかでは、最終的に0や1になって終わりますから、Aが有限集合の場合があるということになります。

その場合、next関数の定義域と値域が一致しません。
値域の最後の数の1つ前の数までの集合が定義域となるからです。

そのとき上の論理式の∀x(P(x)→P(next(x)))は絶対に成り立たなくなります。

next(x)が存在するかどうか、お伺いを立てる論理式が必要となりますが、next(x)と書いた時点でnext(x)が存在してないといけないので、そのような論理式は思いつきませんでした。

だれか知恵をください!!!!


というわけで、また壮大な企画倒れを作ってしまいました。
どうすればいいんですかね~。

tag: 数学 論理学 論理式 自然数 考察 命題 形式 帰納法

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/508-7f9dd9ce
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。