数学とプログラミングについて考察 ~ペアノの公理~

数学ガールって本が好きなんですけど、現在5作出ていて第三弾目の「ゲーデルの不完全性定理」っていう本を読み直しました。

数学ガールゲーデルの不完全性定理 (数学ガールシリーズ 3)

作者: 結城浩
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2009/10/27
メディア: ペーパーバック
購入: 37人クリック: 930回
この商品を含むブログ (155件) を見る

これの2章にペアノの公理の話があるんですが、今回その章を読んだ感想と、プログラミングにその考えを応用してみるとどうなのかって話を考察したので書いていきたいと思います。

ペアノの公理とは
TDDとテストケースについて
ペアノの公理とテストケースの関係
まとめ

このような流れで書いていきます。

ペアノの公理とは

先に示した数学ガールを読んでいただくのが一番手っ取り早いのですが、
Webだと普通にwikipediaがいいですかね。
ペアノの公理 - Wikipedia

数学ガールの文をどこまで引用していいかわからないので簡単にペアノの公理について説明すると、
「自然数を定義する公理」
っていう表現が一番正しいかと。
1 + 1 = 2を証明するための公理です。

※ちなみに数学ガールの場合 1, 2, 3, ...をwikipediaの場合 0, 1, 2, ... を自然数としております。

1 + 1 = 2を証明するという言い方はやや語弊がありますが、ペアノの公理を使うと自然数全体の演算が説明つきます。
wikipediaの公理から
公理1では
0 は自然数であるといえ、
公理2では
0 に続きがあるということがいえる。これを後続数といい 0' と表す。
公理3では
0 の続きになるものは0にはならない。つまり0が一番先頭の自然数であると示す。
公理4では
自然数の2つA, Bがあったとき Aの後続数A'とBの後続数B'は一致しない。
つまり異なる自然数の後続数が同じ数ではあってはいけない。ある自然数とその自然数の後続数はそのペアでしか存在しないことを示している。
違う言い方をすると自然数 A, Bがあったとき、A=Bならば A'=B'である。
公理5では
数学的帰納法の話。プログラマ的にいうと関数 f(x) があったとき、x = 0の時にxに対応するリターンがあるならばx = n(自然数)になっても正しい結果が出る事を示している。(この場合はx = 1の方がわかりやすいと思うが。)

ポイントは0の後続数をいきなり1と言わない事。0以外の自然数はまだわかっていないこととしている。

というわけでざっくりペアノの公理についての説明でした。

TDDとテストケースについて

いきなりプログラミングの話になりますが、開発手法の一つにTDDという方法があります。
なんども書いているのでもう一度解説することはありませんが。
TDD(テスト駆動開発)でハノイの塔の実装をしてみる~TDD超入門~ - nigoblog
このとき重要なのはテストケースです。
厳しすぎても意味がないし、浅すぎてもテストに合格したとは言えません。

というわけでここでペアノの公理とテストケースの関係について考えることで最適なテストケースの洗い出しを考えてみましょう!

ペアノの公理とテストケースの関係

ここでfizzbuzzをTDDで開発することを考えます。
fizzbuzzについてはこちらを参考に
テスト駆動開発でFizzBuzz問題を解く - nigoblog
テストケースを考える前にfizzbuzzをもう一度掘り下げてみます。
1. 3の倍数でfizz
2. 5の倍数でbuzz
3. 3の倍数であり5の倍数であるときはfizzbuzz
をそれぞれ返し、具体的には

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, ... , 13, 14, fizzbuzz, ...

というような数列を作ります。この定義では明示しておりませんが、入力は全て自然数を前提とします。
これをもう少し数学チックに考えてみます。
1. 3nかつ¬5nならばfizzを返す
2. 5nかつ¬3nならばbuzzを返す
3. 15nならばfizzbuzzを返す
4. nは自然数である (n>0)
というわけで入力は自然数であることも明示しました。(¬は否定)
3n, 5n, 15nはそれぞれの係数をスタートとし、その倍数の自然数の集合と見なし、ペアノの公理が満たされているとします。
ここでペアノの公理を利用したテストケースは以下のようになります。
まずは4の自然数以外で例外を出すかどうかのチェック