実務の中の再帰集合
以前、「自己結合の使い方」で、RANK関数を使わず、自己非等値結合でランキングを算出するSQLを紹介しました。あるいは、相関サブクエリを使って累計を求めるクエリでもいいです。それらの記事でも少し書きましたが、クエリのの基礎となっている考え方は、フォン・ノイマンによる、再帰集合を使った自然数の定義です。
多分、初めてこの考え方を見たとき、皆さん、結構驚いたのではないでしょうか。これは、SQL が集合論と密接に結びついていることを示す好例の一つではあるのですが、しかし集合と数を結びつけるというのは、「裏事情」を知らない人間にとっては意外な発想です。「そもそもノイマンは、何で自然数を集合で定義しようなんて突飛なことを考えたんだろう」という素朴な疑問を持った人も多いでしょう。このコラムでは、その辺りの歴史的な話をすることで、皆さんの疑問解消に役立ててもらおうと思います。ノイマン再帰集合のアイデアを提出した背景には、それなりの前史というものがあったのです。
ノイマンの先輩たち
ノイマンが再帰集合による自然数の定義を提案したのは、1923年の論文「超限順序数の導入について」です。これは彼の2番目の論文で、嫌になっちゃう話ですが、書いた当時、彼は高校生でした。タイトルに「順序数」という言葉が出ていることからも分かると思いますが、正確には、ノイマンが提出したのは「自然数の定義」というより「順序数の定義」です。順序数というのは、名前のごとく、0の次が1、1の次が2、2の次が3 …… という順序を意識したときの自然数の呼び名だ、というぐらいに思ってください（反対に、意識しないときの呼び名に「基数」というものもあります）。
実際、ノイマンの定義を見ると、最初に0を定義して、その次に0を使って1を定義して、その次に1を使って2を定義する、という順序がちゃんとあることが分かります。自己結合のときにも出しましたが、もう一回、定義を見てもらいましょう。
| 自然数 | 自然数の順序に注目した場合 | 集合まで還元した場合 |
|---|---|---|
| 0 | Ø | Ø |
| 1 | { 0 } | {Ø} |
| 2 | { 0, 1 } | {Ø, {Ø}} |
| 3 | { 0, 1, 2 } | {Ø, {Ø}, {Ø, {Ø}}} |
| ・ | ・ | ・ |
| ・ | ・ | ・ |
| ・ | ・ | ・ |
定義の手順が順序を持っていることが分かります。あるいはむしろ、大きい数から 0 へ遡って考えた方が分かりやすいかもしれません。3 を定義するには、2 が必要になる。2 を定義するには 1 が必要になる、そして 1 を定義するには、結局、0 が必要になるわけで、ある数を定義しようと思ったら、その「前の」数が事前に用意されている必要があります。この段階的な特徴のため、「帰納的定義（recursive definition）」とも呼ばれます。SQL では、各自然数を定義している集合の要素数をカウントすることで、ランキングの算出に応用していました。
さて、今回の話の核心はここからです。実は、このような自然数の帰納的な定義を考えたのは、彼が最初ではありません。それ以前に、少なくとも二人の人間が同じ発想のアイデアを提出しています。一人はゴットロープ・フレーゲ。関係モデルの基礎の一つ、述語論理をほとんど独力で創始した偉大な哲学者。もう一人は、現代的な集合論の体系を整備し、整列可能定理と選択公理の提出でも知られる数学者エルンスト・ツェルメロ。こちらも数学史に名を刻む大物です。
二人の方法も、やはり、最初に 0 に適当な集合を割り当てて、あるルールで 1, 2, 3 …… と作っていく構造を持ちます。3人のやり方を一覧にして見比べてみましょう。
| 自然数 | ノイマン型 | ツェルメロ型 | フレーゲ型 |
|---|---|---|---|
| 0 | Ø | Ø | {Ø} |
| 1 | {Ø} | {Ø} | {Ø, {Ø}} |
| 2 | {Ø, {Ø}} | {{Ø}} | {{Ø, {Ø}}, {Ø, {Ø}}} |
| 3 | {Ø, {Ø}, {Ø, {Ø}}} | {{{Ø}}} | {{{Ø, {Ø}}, {Ø, {Ø}}}, {{{Ø, {Ø}}, {Ø, {Ø}}}}} |
| ・ | ・ | ・ | ・ |
| ・ | ・ | ・ | ・ |
| ・ | ・ | ・ | ・ |
カッコの多さに眩暈がしそうですが、それはともかく、3人のやり方には、それぞれ似ているところもあれば、独自の特徴もあります。まず目につくのは、ツェルメロ型の簡単さです。0を空集合から始める点はノイマンと同じですが、後はひたすら外側にカッコをつけていくだけというシンプルさ。この調子でカッコが増えると、例えば 30 という数は、
{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{Ø}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
フレーゲ型は、ノイマンのとよく似ていますが、0 に空集合ではなく、空集合を含む単元集合を割り当てているところが違います。歴史的には、このフレーゲの方法が一番古くて1884年、その後、ノイマンが改良した、という順番になります。ノイマンは他人のアイデアを「横取り」してオリジナルよりずっと優れたものに改良してしまう異能の持ち主でしたが、ここでもその才が遺憾なく発揮されています。
ここまでで、ノイマンのアイデアが、どうやらある歴史的な流れの中に位置づけられているようだ、ということが分かってきました。でもこれだけでは、まだ次の二つの疑問が未解決です。
- 自然数の定義がこんなたくさんあっていいのか。定義というのは普通、一つなのでは。
- 何で自然数の定義に「集合」を使おうと思ったのか。
実は、これらの問いを考える中で、図らずも、20世紀初頭の「数学革命の時代」を、ほんの少し覗くことになります。
数とは何か？
私たちは普通、0 や 1 のような「数」の概念を習うとき、具体的な物の数に結びつけて理解します。小学校のころ、算数の教科書にはりんごやみかんの絵が載ってたのを、私自身も覚えています。 でも、数の一般的な定義を考えるなら、こういう具体的な物に結びけて考えるのがまずいことは、すぐ分かります。仮に、1 という数をリンゴを使って定義したら、リンゴを見たことのない人はその定義を理解できないはずです。でも実際には、リンゴを知っている人と知らない人の間でも、1 という数についての共通理解は成立している。つまり、数というのは具体的な物には縛られない、もっと一般的で抽象的な対象として定義しなければならないのです。
自然数の一般的定義に最初に取り組んだ数学者は、イタリアのジュゼッペ・ペアノです。彼は1891年、自然数としてあるべき条件を満たすなら、どんなものであれ自然数として認めたらどうか、というスタンスで、自然数が満たすべき条件を5つ挙げました。それが今日まで「ペアノの公理」として残っている自然数の定義です[1]。これはいわば、「結婚相手としてどんな男性を望みますか？」と聞かれたときに、「営業の田中さん」と具体的な人名を挙げて答えるのではなく、「えーとね、東大卒でね、外資系に勤めててね、年収1千万以上でね……」とその人が満たすべき条件を列挙して答えるスタンスです。この条件を満たす人なら誰でも「好きな人」として認めよう、というのがペアノの態度。ある意味、現代的でドライです。
ペアノが自然数に求める条件の内容はというと、「0 の役割を果たすものがある」とか「0 より前の自然数はない」とか、多くはごく当然のものです。人間なら「暴力を振るわない」とか「ギャンブル狂じゃない」とか、そういうレベルの最低条件です。ただ、その中で今回の話に関わる重要なものが一つあります。それが
任意の自然数 a には、その後者（successor）が存在する。
このように、ある自然数の次の数を与える関数を、後者関数といい、suc(x) と書きます。suc(5) = 6、suc(17) = 18 です。だから、後者関数を使って自然数を作るときは、次のように入れ子で関数を適用していくことになります。
0 = 0
1 = suc(0)
2 = suc(suc(0))
3 = suc(suc(suc(0)))
・
・
・
そしてここが肝心なのですが、ペアノはこの後者関数についても、その具体的な中身については触れていません。中でどういう操作をしてもいいから、とにかく次の数を生み出す関数が存在すればいいよ、という、ゆるい条件です。再度、結婚相手の条件に喩えるなら、「どんな職業に就いているかは問わないから、とにかく年収1千万を超えていること」ということです。手段は問わず、結果しか興味がない。
ノイマンたち三人の考えた自然数にも、この後者関数が存在します。
ノイマンとフレーゲの後者関数：suc(a) = a ∪ { a }
ツェルメロの後者関数：suc(a) = { a }
このように、後者関数の中身が、ノイマン=フレーゲとツェルメロとで異なりますが、特に問題はありません。山梨県から上っても静岡県から上っても同じ富士山の頂上に着くのと同様、どういうルートを辿ろうと同じ後者へ行き着きさえすればいいのです。
つまり、ここで1番の疑問に対して回答を返すと、ノイマンたちがやったことは、自然数の定義というより構成と呼ぶほうがしっくりきます。定義はペアノの挙げた5つの条件で、ノイマンたちは、ペアノの要求に見合う品物を作ったのです。
そしてこのことから、2番目の疑問に対する答えも出てきます。すなわち、自然数を構成する材料として、別に集合を使う必要はないのです。実際、他にも行列を使っても作れますし、コンピュータ・サイエンスと関連の深いところでは、ラムダ計算による関数を使った構成法もあります。ラムダ計算で構成する自然数には、アロンゾ・チャーチからその名をとった「チャーチ数」という名前が付いていますが、「数」とはいうものの、その内実は高階関数です。ノイマンたちが活躍した19世紀末から20世紀初頭には、まだあまり抽象代数が発展していなかったので、こういう抽象性の高い定義に沿った構成を行う材料としては、当時もっとも抽象度の高い概念だった集合が真っ先に候補になったのです。
SQL の魔術と科学
SQL でのランキング算出という実務的な話から、20世紀初頭の数学史へ、遠いところまで話が飛びました。実践と理論のこの意外なほどの距離の近さが、SQL とリレーショナル・データベースのスリリングなところだ、と私などは思います。最初はいったいどういう動作をしているのか分からず、呪文のように見えたランキング算出のクエリも、こうして理論的背景まで俯瞰してみると、一つの科学的体系の一部を成しているのだ、ということが見えてきます。この「魔術から科学へ」至る理解のプロセスは、SE やプログラマという仕事の醍醐味の一つではないでしょうか。
注
[1] ペアノの五つの公理は次の通り:
- 最初の数が存在する。
- 任意の自然数 a にはその後者が存在する。
- 最初の数はいかなる自然数の後者でもない。
- 異なる自然数は異なる後者を持つ
- 最初の数がある性質を満たし、a がある性質を満たせばその後者もその性質を満たすとき、すべての自然数はその性質を満たす。
Copyright (C) ミック
作成日：2007/06/21
最終更新日：2017/06/22
Tweet