3.  空集合,合併集合,共通集合

集合を定義するのにいつもいつも make-instance ではタイプ入力の効率が悪いので,set とset-of という関数を次のように定義しましょう.

(defun set (members)
  (make-instance 'set :elements members))

(defun set-of (&rest members)
  (make-instance 'set :elements members))

また,いつもいつも slot-value では見栄えが悪いので,次のようにして,elements スロットのアクセッサを定義します.

(defclass set ()
  ((elements :initarg :elements :accessor member-of))
  )

いかなる要素も含まない集合のことを空集合と言いますが,空集合の公理とは,空集合が存在するという公理です.それをここではこんな風に定義してみました.

(defparameter +empty+ (set-of))

(defun empty-p (set)
  (null (member-of set)))

もし二つの集合 a と b が共に空集合なら,両者は(集合として)等しい.すなわち,

zf(17): (equals (set-of) (set-of))
t

たった一つの要素を持つ集合を特別にシングルトンと呼びます.

(defun singleton-of (element)
  (set-of element))

(defun singleton-p (set)
  (length=1 (member-of set)))

空集合と空集合のシングルトンは異なるものです.

zf(18): (equals +empty+ (singleton-of +empty+))
nil

非順序対の存在公理とは,任意の二つの集合について,それらを要素として含みそれら以外を含まないような集合がある,というものです.

(defun unordered-set-of (e1 e2)
  (if (equals e1 e2) (singleton-of e1)
    (set-of e1 e2)))

非順序ですから,二つの要素を入れ替えても結果は(集合として)同じです.

zf(19): (equals (unordered-set-of 1 2) (unordered-set-of 2 1))
t

合併集合はCommon Lisp のunion を使えばmap と reduce で簡単に定義できます.

(defun union-of (&rest sets)
  (set (reduce #'(lambda (e1 e2) (union e1 e2 :test #'equals))
               (mapcar #'member-of sets)
               :initial-value '())))

cl:union は2変数の関数ですが,こうすれば任意個の集合について合併集合を定義できます.

zf(55): (equals +empty+ (union-of))
t
zf(56): (equals +empty+ (union-of +empty+))
t
zf(57): (equals (set-of 1 2) (union-of (set-of 1 2)))
t
zf(58): (equals (set-of 1 2 3) (union-of (set-of 1 2) (set-of 2 3)))
t

共通集合は次のように定義できます.

(defun intersection-of (&rest sets)
  (cond ((null sets) +empty+)
        ((length=1 sets) (car sets))
        (t (set (reduce #'(lambda (e1 e2) (intersection e1 e2 :test #'equals))
                        (mapcar #'member-of sets))))))
zf(70): (equals +empty+ (intersection-of))
t
zf(71): (equals (set-of 1 2) (intersection-of (set-of 1 2)))
t
zf(72): (equals (set-of 2) (intersection-of (set-of 1 2) (set-of 2 3)))
t