前回の記事は本当は,この記事の前振りにあたります.混乱しそうですが,バックグラウンドの理解ということで,よろしくお願いします.

さて,カントールは集合論の創始者で,数論の議論に道を開いたわけですが,同時にゲーデルの不完全性定理に至る,今日では超数学と呼ばれる分野にもつながるパラドックスも明らかにしてしまいました.前々から展開してきたように,集合の内包的表記では,{ x | φ(x) } という形式で集合を表します.ここでその意味は φ(x) という性質を持つ要素 x のすべての集合,という意味です.このような表記をベースとする集合論で内部にパラドックスを含む集合論を素朴集合論と言います.素朴集合論に含まれるパラドックスを限りなく単純な形で明らかにしたのがラッセルのパラドックスであり,それを解決(回避)するように,個物としては空集合のみのZermelo-Fraenkel (通称ZF)集合論,一般の個物を許すvon Neumann–Bernays–Godel 集合論が創出されていきます.

この集合論ブログの最初に,x = x という同一性の話をして,集合における外延性公理を紹介しました.x = x は真というのは,どんな場合でも成り立つことですから,これを内包とするような集合の定義は,すべての個物やすべての集合についてあてはまる定義です.このような集合を今からuniversal class と呼ぶことにします.universal class を実現するために,satisfies ではありませんが,1変数の述語 φ(x) を許すようにこれまでの in と subset-p を拡張します.ちょっとコード量が多くなりますので,今日時点での最新のコードを ここここに置きました(コメントをいただいたg000001さん,どうもありがとうございました).興味のあるかたは二つのファイルをダウンロードしてみて,議論につきあってください.ダウンロードしなくても要点はわかるはずですが.

universal-p という述語を次のように定義すれば,ユニバーサルクラス +RR+ は次のようになります.

(defun universal-p (x)
  (equals x x))
(defparameter +RR+ (set-by :type #'universal-p))

すると,すべてのものはこのクラスに所属することができます.数でも,自然数の集合でも,なんでも.

zf(2): (in 1 +RR+)
t
t
zf(3): (in +NN+ +RR+)
t
t
zf(4): (in "This is a string." +RR+)
t
t
zf(5): (in 'aSymbol +RR+)
t
t

コードを見ていただければ分かりますが,新しく拡張された in では,集合の type スロットの値が関数の場合にはその述語を与えられた要素かもしれない引数に適応します.universal-p はどんな x がきてもそれが x = x であるかを見るだけですから,その時々の文脈で well-formed formula であれば常に真ですね.だからこれは type スロットの値を t とするユニバーサルクラスと意味的に同一です.記述論理ではこれを T と書いて top と読みます.

(defparameter +TOP+ (set-by :type 't))

+TOP+ はCommon Lisp の型階層における t と同様に,集合の包含関係における最上位の集合になります.反対に nil を type に持つような集合は最下位の集合になって,それを記述論理では ⊥ と書いて bottom と読みます.実は bottom は空集合と同等なので,その意味で以下のようにしました.

(defparameter +BOTTOM+ (set-by :type 'nil))
(setf (member-of +BOTTOM+) nil)
(finalize +BOTTOM+) ; define rank
zf(12): (equals +RR+ +TOP+)
t
t
zf(13): (equals +empty+ +BOTTOM+)
t
t

実はちょっとズルをして,equals のコード中にもし type が universal-p の述語だったら,というコードを埋め込んでいますが,はっはっ,このくらいは許してください.エージェントがLisp コードの意味を理解できるようになればいいんですけどね.

さて,ここからが本題です.この実装では見かけ上,+RR+ や +TOP+ はその要素としてそれ自身に所属することができます.

zf(14): (in +RR+ +RR+)
t
t
zf(15): (in +TOP+ +TOP+)
t
t

何故でしょうか?前にも書いたように,集合が自分自身に所属することはありません.実装としてはたとえば (universal-p +RR+) が起動されるだけですから,<t, t> が返ります.

zf(17): (in +RR+ +RR+)
 0[6]: (universal-p {x | #<Function universal-p>})
 0[6]: returned t t
t
t

集合にまつわるパラドックスには,カントールのパラドックス,ブラリ・フォルティのパラドックスがありますが,これらの「すべての集合」みたいな集合に関するパラドックスだけでなく,自分自身を要素としない集合についてもパラドックスが含まれます.それがRussell 集合と呼ばれる集合のパラドックスでラッセルのパラドックスと呼ばれます.今,自分自身を要素としないという述語を次のように定義して,ラッセル集合を定義します.

(defun russell-p (x)
  (multiple-value-bind (val1 val2) (in x x)
    (if val1 (values nil t)
      (if val2 (values t t)
        (values nil nil)))))
(defparameter +Russell+ (set-by :type #'russell-p))

分かりにくいかもしれませんが,このコードは(not (inx x))であると理解願います.すると,次のように一見よさそうに見えるのですが,これを自分自身に適応すると矛盾が露呈します.

zf(18): (in +NN+ +Russell+)
t
t
zf(19): (in +INT+ +Russell+)
t
t
zf(20): (in +RR+ +Russell+)
nil
t
zf(21): (in +Russell+ +Russell+)
Error: Stack overflow (signal 1000)
[condition type: synchronous-operating-system-signal]

ここで (in +RR+ +Russell+) が一見もっともらしく動いたのは,russell-p の働きの中で universal-p が動いて,これが真となり,その否定で偽となったものであり,(in +Russell+ +Russell+) のスタックオーバーフローは in の呼び出しが再帰になったがためです.

zf(23): (trace russell-p universal-p)
(universal-p russell-p)
zf(24): (in +RR+ +Russell+)
 0[6]: (russell-p {x | #<Function universal-p>})
   1[6]: (universal-p {x | #<Function universal-p>})
   1[6]: returned t t
 0[6]: returned nil t
nil
t

Lisper の常識から言わせれば,(in +Russell+ +Russell+) についてはあっそんなことしちゃだめだめ,ということになるのですが,(in +RR+ +RR+) はきちんと動くのに対して (in +Russell+ +Russell+) は駄目というところをどう解釈するのかというのが集合論的な問題なのです.ちなみに,Russell 集合 { x | x ∉ x } ではなく,自分自身を含む集合 { x | x ∈ x } についてもパラドックスは全く同様です.ユニバーサルクラス { x | x = x } は問題ないのにですよ.

カントールまでの素朴集合論では,{ x | φ(x) } のような形で集合を定義できると考えられていました.この φ(x) にはどんな形の式がきてもよいと.これを(今では)無制限の包括原理と呼びます.ここで,α = { x | φ(x) } は∀x [ (x ∈ α) ⇔ φ(x) ] と書けることを指摘しておきます.すなわち,φ(x) を満足する x は α の要素であり,その逆も真.ところが今ラッセル集合 R =  { x | x ∉ x } について考えると,任意の x の一つとして R をとれば,R = R ⇔ R ∉ R と矛盾が簡単に導かれます.どこがいけなかったのか分かりますか?結論として,今日では α = { x | φ(x) } と書けるようなものをクラスと呼び,クラスには集合もあるが集合となりえないものもあり,それを特別に本来のクラス(proper class) と呼んでいます.ですからRussell 集合は本当はRussell クラスと呼ばなければならず,実際にそう呼んでいる教科書もあります.ユニバーサルクラス { x | x = x } も,本当の意味では集合ではなく,それはクラスである,というわけです.ちなみに,あれこれの予備知識を前提としないで,集合論を教えるブルバキの数学原論では,集合を作り得る関係なるものを教えて,関係 x ∈ y (x と y は異なる記号)は集合を作り得るが,x ∉ x は集合を作りえない,と述べています.ですから,ユニバーサルクラスは集合ではなく,集合みたいな顔をした(この実装での)しかけなのですよ.では,ラッセルクラスも何かしかけることができるかって?いやー,多分駄目でしょうね.なんか根源的にだめなもののような気がします.Lisp の再帰では,このブログで説明したように,複雑なものを一つブレークダウンして,簡単なものに分解し,そのそれぞれに対して再帰させます.そしてその再帰が停止する終了条件を書くことが重要です.集合においても同様な基礎の公理(正則性の公理)というものがあって,∈の階梯を下って行ったら必ず最後は空集合で停止する,というものがあります.ユニバーサルクラスにせよ,ラッセルクラスにせよ,それだけの条件ではこの正則性の公理を満たすことはできませんね.基礎の公理を満たす集合であれば,何とかしかけられそうですが.

このラッセルのパラドックスをきっかけとして,Zermelo は無制限の包括原理のかわりに,分出原理というものを置きました.

∀z∃α∀x [ (x ∈ α) ⇔ (x ∈ z) ∧ φ(x) ]

ここでは,集合は任意の公式 φ(x) からだけでは,作ることができず,その集合の要素は必ず何か別の集合かクラス z を必要とし,その要素として存在しなければなりません.CLOS でいけば,すべてのクラスは,cl:standard-class の実現であるみたいなことですね.上の式ではどんな z でもいいと言っていますけどね.

Zermeloはいくつかの集合の公理を明らかにしましたが,それに加えてFraenkel の公理による集合論が今日一つの標準となっている Zermelo-Fraenkel の集合論です.しかし,オントロジーやオブジェクト指向の観点からは,Zermelo-Fraenkel の集合論ではすべての実現は集合しかありません.線とか四角とか円とか,Cat とかAnimal とかはないのです.そこで個物として集合以外のものも認めようとする集合論があります.次はそういう話ができるといいですね.