プログラマのための集合論入門

DWSの道下です。

集合論という数学の分野があります。
集合論は現代数学の標準言語などと言われることもあり、集合論の上で様々な数学の概念を定式化することができます。
プログラマにも無縁ではなく、例えばSQLのベースとなっているリレーショナルモデルに現れる多くの概念が集合を用いて定義されます。

自分は学生時代から集合論に何度も入門を繰り返しているのですが、プログラミングの概念を通して集合をイメージすることで、集合論を初めて学んだ時に起こりがちな混乱を解消しやすくなることがあるのではないかと思っています。
そこで今回の記事では、集合論で扱う対象を、Pythonのコードを添えて解説してみたいと思います。

集合

集合と要素

集合とはものの集まりです。
集合の例をいくつか挙げます。
以下のAという集合は1,2,3という数字の集まりです。
$$A = \lbrace1, 2, 3\rbrace $$
以下のBという集合はa,b,cという文字の集まりです。
$$B = \lbrace a,b,c \rbrace $$
多くのプログラミング言語で set 型が用意されており、これはまさに集合を表現した型です。
Python では以下のように、中括弧{}を使って set 型の変数を生成することができます。

>>> A = {1,2,3}
>>> type(A)
<class 'set'>

集合の中にはいっているひとつひとつのものをその集合の要素と言います。
また、このように要素を書き並べて集合を表す書き方を、外延的記法と言います。

ある集合Aと、なんらかのものaについて、aがAの要素であるか要素でないか、どちらか一方だけが必ず成り立たなければなりません。

あるもの a が集合 A の要素であることを、
$$a \in A$$
と書きます。

逆に、aが集合Aの要素でないことを、
$$a \notin A$$
と書きます。

例えば、
$$１ \in \lbrace1, 2, 3\rbrace$$
$$\lbrace１\rbrace \notin \lbrace1, 2, 3\rbrace$$
が成り立ちます。つまり、1は\( \lbrace1, 2, 3\rbrace\)の要素ですが、\(\lbrace1\rbrace\)は\( \lbrace1, 2, 3\rbrace\)の要素ではありません。
既に少しわかりにくいかもしれませんが、同じ状況を表す次のPythonのコードで見ればどうでしょうか。

>>> 1 in {1,2,3}
True
>>> {1} not in {1,2,3}
True

intの値1は{1,2,3}の要素ですが、1を要素に持つ{1}というsetはそうではありません。プログラマにとってはこちらのほうがわかりやすいのではないでしょうか。

集合は何を要素に持つかのみによって決まります。
そのため、
$$\lbrace1, 2\rbrace　= \lbrace1,1, 2\rbrace $$
$$\lbrace1, 2\rbrace　= \lbrace2,1\rbrace $$
などが成り立ちます。
Pythonのset型でも、以下の通りです。

>>> {1,2} == {1,1,2}
True
>>> {1,2} == {2,1}
True

いずれの集合も1 と 2 を要素に持ちますが他にはどんな要素も持たないため、何を要素に持つかという観点だけで見れば同じものであると言えます。そのため同一の集合となります。
集合には順序や重複といった情報はありません。

空集合

要素を何も持たない集合、つまり
$$ \lbrace \rbrace $$
を空集合と言います。
空集合は\(\emptyset \)という記号で表すことが多いです。

集合論の学び始めで混乱しがちなことの一つとして、\(\emptyset \)と\(\lbrace \emptyset \rbrace \)の区別があります。これらは異なるものです。
要素を持たない集合と、要素を持たない集合の集合・・・結局空なのだから同じなのではないか？と思ってしまいそうですが、プログラミングで考えると多少わかりやすいのではないでしょうか。

# 空集合
>>> a = frozenset([])
# 空集合だけを要素に持つ集合
>>> b = frozenset([frozenset([])])
>>> a == b
False

set型がset型を要素に持てないため、frozensetというsetをイミュータブルにした型を使っています。
空の1次元配列と、空の1次元配列だけを要素に持つ2次元配列が別のものなのと同じことです。

順序対

先程、集合には順序がないと言いました。
しかし、集合を使って順序を伴ったものの集まりを定義することは可能です。
順序を伴った2つのものの組を
$$\langle x,y \rangle = \lbrace\lbrace x \rbrace,\lbrace x,y \rbrace\rbrace$$
と定義し、これを順序対と呼びます。
集合については
$$ \lbrace1, 2\rbrace = \lbrace2, 1\rbrace$$
が成り立ちましたが、順序対については
$$ \langle 1,2 \rangle \neq \langle 2,1 \rangle$$
となります。
定義から
$$\langle 1,2 \rangle = \lbrace\lbrace 1 \rbrace,\lbrace 1,2 \rbrace\rbrace$$
$$\langle 2,1 \rangle = \lbrace\lbrace 2 \rbrace,\lbrace 2,1 \rbrace\rbrace$$
であり、この２つの集合は明らかに異なるものです。
このようにして順序を持たない集合から、順序をもった順序対というものを定義できます。

順序対を表すクラスを作成してみました。

from dataclasses import dataclass, field

@dataclass(frozen=True)
class OrderedPair:
    a:any
    b:any
    orderedPair:frozenset = field(init=False)
    def __post_init__(self):
        left = frozenset([self.a])
        right = frozenset([self.a,self.b])
        object.__setattr__(self, 'orderedPair', frozenset([left,right]))
    def __repr__(self):
        return f"<{self.a},{self.b}>"
    def printAsSets(self):
        print(self.orderedPair)

>>> o1 = OrderedPair(1,2)
>>> o2 = OrderedPair(2,1)
>>> o1
<1,2>
>>> o2
<2,1>
>>> o1.printAsSets()
frozenset({frozenset({1}), frozenset({1, 2})})
>>> o1 == o2
False
>>> o3 = OrderedPair(1,2)
>>> o1 == o3

プログラミングにおいては、配列やlistという順序を伴ったデータ構造が最初から用意されているのだから、こんなものを作る必要はないと思われるかもしれません。しかしここでは、集合という順序を持たないシンプルな対象から、順序を持ったものを作ることができるということを実感していただきたいので、数学的な定義の順番に従ってこのように実装しました。

関係

なぜ順序対を定義したのかというと、順序対を使って関係を定義したかったからです。
そして、関係を定義することができれば、関係の特殊な例として関数を定義できます。

関係は非常にシンプルに、単に順序対の集合として定義できます。
例えば、以下は関係です。
$$ \lbrace\langle北海道, オホーツク海\rangle,\langle北海道, 日本海\rangle, \newline \langle北海道, 太平洋\rangle, \langle青森県, 日本海\rangle, \newline \langle青森県, 太平洋\rangle,\langle秋田県,日本海\rangle, \newline ...,\langle沖縄県, 太平洋\rangle,\langle沖縄県, 東シナ海\rangle\rbrace $$
順序対の集合に関係という名前がついているのは、「x と y は ○○ という関係にある」という状況を表すことができるからです。上記の例は、「x は y に面している」という関係を表しています(x としては日本の都道府県だけを考えています)。

順序対が集合を使って定義されていたことを思い出すと、関係もその気になれば全て集合だけで書き下すことができます。
先程の「xはyに面している」という関係であれば、
$$ \lbrace \lbrace 北海道 \rbrace, \lbrace 北海道, オホーツク海 \rbrace \rbrace ,\newline
\lbrace \lbrace 北海道 \rbrace, \lbrace 北海道, 日本海 \rbrace \rbrace ,\newline
\lbrace \lbrace 北海道 \rbrace, \lbrace 北海道, 太平洋 \rbrace \rbrace, \newline
\lbrace \lbrace 青森県 \rbrace, \lbrace 青森県, 日本海 \rbrace \rbrace, \newline
\lbrace \lbrace 青森県 \rbrace, \lbrace 青森県, 太平洋 \rbrace \rbrace, \newline
\lbrace \lbrace 秋田県 \rbrace, \lbrace 秋田県, 日本海 \rbrace \rbrace
\newline...,
\lbrace \lbrace 沖縄県 \rbrace, \lbrace 沖縄県, 太平洋 \rbrace \rbrace, \newline
\lbrace \lbrace 沖縄県 \rbrace, \lbrace 沖縄県, 東シナ海 \rbrace \rbrace $$
と同じことです。長すぎて見づらいですが・・・
この記事で定義している概念が、全て実体としては集合であることを実感してもらえたでしょうか。

ある関係について、その要素となる順序対\(\langle x, y\rangle \)の x が全て属するような集合を、その関係の定義域といいます。
先程の例で言えば、都道府県全体の集合\(\lbrace北海道, 青森県,秋田県,...,沖縄県\rbrace\)が定義域の一つであると言えます。都道府県全体の集合から群馬県などの内陸県を取り除いた集合は、先程の関係の最小の定義域です。逆に、都道府県全体とアメリカ合衆国の州全てを集めた集合も先程の関係の定義域です。

また、ある関係について、その要素となる順序対\(\langle x, y \rangle \)の y が全て属するような集合を、その関係の値域といいます。

関係は以下のように実装してみました。

@dataclass(frozen=True)
class Relation:
    relation:frozenset[OrderedPair]
    # 最小の定義域
    domain:frozenset = field(init=False)
    # 最小の値域
    range:frozenset = field(init=False)
    def __post_init__(self):
        object.__setattr__(self, 'domain', frozenset([o.a for o in self.relation]))
        object.__setattr__(self, 'range', frozenset([o.a for o in self.relation]))
    def __repr__(self):
        return str(self.relation)

>>> o1 = OrderedPair('北海道','オホーツク海')
>>> o2 = OrderedPair('北海道','日本海')
>>> o3 = OrderedPair('北海道','太平洋')
>>> o4 = OrderedPair('青森県','日本海')
>>> o5 = OrderedPair('青森県','太平洋')
>>> r = Relation(frozenset([o1,o2,o3,o4,o5]))
>>> r
frozenset({<北海道,オホーツク海>, <青森県,太平洋>, <北海道,日本海>, <北海道,太平洋>, <青森県,日本海>})
>>> r.domain
frozenset({'青森県', '北海道'})
>>> r.range
frozenset({'太平洋', 'オホーツク海', '日本海'})

関数

関数は、「要素である各順序対<x,y>について、x が同一なら y も同一である」という条件を満たすような関係です。
先程挙げた都道府県と面する海の関係は、関係ではあるものの関数ではありません。\(\langle北海道, オホーツク海\rangle,\langle北海道, 日本海\rangle\)などの要素が関数の条件を満たさないためです。

他方で、以下は関数です。
$$ \lbrace \langle0,0\rangle, \langle1,2\rangle, \langle2,4\rangle,\langle3,6\rangle \rbrace $$
これは、xを0,1,2,3に限定した場合の f(x)=2x です。
今回は有限の例しか扱いませんでしたが、集合の要素は無限個あっても構わないので、実数上のf(x)=2xでも集合で表すことができます。
（ただし、ここでは要素を全て書き並べて表す外延的記法しか導入していないため、無限集合を正確に書き表すことはできません。）

プログラミングにおいても関数を定義できますが、プログラミングにおける関数はここで定義した数学的な関数の条件を満たすとは限りません。
プログラミングにおいては、異なる引数に対して同じ値を返す関数を作れますし、グローバル変数やランダムな値を用いれば同じ引数に対しても異なる値を返す関数が作れてしまいます。

関数についても、関係と同じように定義域・値域が定義されます。

関数の実装例です。

@dataclass(frozen=True)
class Function:
    function:frozenset[OrderedPair]
    # 最小の定義域
    domain:frozenset = field(init=False)
    # 最小の値域
    range:frozenset = field(init=False)
    def __post_init__(self):
        # 関数の条件を満たすかチェック
        for o1 in self.function:
            for o2 in self.function:
                if o1.a == o2.a and o1.b != o2.b:
                    raise ValueError(f'{self.function} is not a function')
        object.__setattr__(self, 'domain', frozenset([o.a for o in self.function]))
        object.__setattr__(self, 'range', frozenset([o.a for o in self.function]))
    def __repr__(self):
        return str(self.function)
    def value(self,x):
        for o in self.function:
            if o.a == x:
                return o.b

>>> o1 = OrderedPair(0,0)
>>> o2 = OrderedPair(1,2)
>>> o3 = OrderedPair(2,4)
>>> o4 = OrderedPair(3,6)
>>> f = Function((frozenset([o1,o2,o3,o4])))
>>> f
frozenset({<2,4>, <0,0>, <1,2>, <3,6>})
>>> f.domain
frozenset({0, 1, 2, 3})
>>> f.range
frozenset({0, 2, 4, 6})

まとめ

関数という比較的馴染みの有りそうな概念が集合によって定義できるということを感じていただきたかったので、通常の集合論の入門書などであればもっと先に導入するであろう概念を無視して最短で関数の定義を行いました。

他の集合論の概念も同じ方法で紹介してみたいですし、集合論の準備が充分にできたら、その上でリレーショナルモデルの解説もしてみたいと思っています。しかしリレーショナルモデルについて筆者がまだ理解できていないので、これから頑張っていきます。。。

mitchy

SIerで物流システムの保守運用に従事した後、2022年1月にDWSに入社。最近は主にGoでバックエンドの開発をしています。趣味はゲームと散歩。