この記事は「みゅーもり Advent Calendar 2018」の11日目分となります:

記事を書く時間が十分に取れ無さそう（そもそも現時点で締切を2日超過している）なので, 計画を変更して簡単に書ける内容にしました.

（当初予定していた「banditとcoarse correlated equilibriumの関係性」の記事は（みゅーもりのやる気があれば）後日改めて書こうと思います……）

Jupyter Notebook: http://nbviewer.jupyter.org/github/myuuuuun/blog_contents/blob/master/notebooks/topological_sort.ipynb

定義

$X$ を任意の集合とし, $\succeq$ を $X$ 上で定義された二項関係とします.

このとき $\succeq$ が以下の3つを満たせば, $\succeq$ は 半順序（partial order） であるといいます

反射律: $\forall x \in X,$ \begin{align} x \succeq x \end{align}
推移律: $\forall x, y, z \in X,$ \begin{align} x \succeq y \land y \succeq z \implies x \succeq z \end{align}
歪対称律: $\forall x, y \in X,$ \begin{align} x \succeq y \land y \succeq x \implies x = y \end{align}

また $\succeq$ が以下の3つを満たせば, $\succeq$ は 全順序, または線形順序（total order / linear order） であるといいます

完全律: $\forall x, y \in X,$ \begin{align} x \succeq y \lor y \succeq x \end{align}
推移律: $\forall x, y, z \in X,$ \begin{align} x \succeq y \land y \succeq z \implies x \succeq z \end{align}
歪対称律: $\forall x, y \in X,$ \begin{align} x \succeq y \land y \succeq x \implies x = y \end{align}

$\succeq$ が $X$ 上の半順序である時, $(X, \succeq)$ を 半順序集合（partially ordered set / poset） といいます. 同様に $\succeq$ が $X$ 上の全順序である時, $(X, \succeq)$ を 全順序集合（totally ordered set） といいます.

半順序と全順序の違いは1.のみです. 完全律が成り立てば反射律も自動的に成り立つので, 全順序集合であれば必ず半順序集合になります.

イメージ

順序関係を有向グラフで表現してみます. たとえば $X = \{ a, b, c, d, e \}$ として, $X$ 上の二項関係を \begin{align} \forall x, y \in X, x \succeq y \Longleftrightarrow \ \text{$x = y$, または$x$から$y$へ向かうpathがある} \end{align} と定義します.

f:id:myumori:20181214005655p:plain — 順序の例

例1は半順序ですが, $b \succeq c$ と $c \succeq b$ のいずれも成り立たないため, 全順序ではありません
例2は全順序（したがって半順序）です. 全順序である時, 順序を崩さずに集合の各元を一列に並べることができます（例では $a \to b \to c \to d \to e$ ）
例3は $b \succeq c \land c \succeq b$ ですが $b \neq c$ なので, 歪対称律を満たさず, 半順序ではありません
例4は, 仮に推移律を満たすとすると $c \succeq d \land d \succeq e$ より $c \succeq e$ となります. しかし $e \succeq c$ でもあるので, 歪対称律が成り立ちません. したがって推移律と歪対称律が同時に成り立たないので, これは半順序ではありません

問題設定

半順序集合 $(X, \succeq)$ が与えられた時, この半順序 $\succeq$ を拡張して全順序 $\succeq^{L}$ を構成することはできるでしょうか？

より厳密に書けば \begin{align} \forall x, y \in X, x \succeq y \implies x \succeq^{L} y \end{align} を満たす $X$ 上の全順序 $\succeq^{L}$ は存在するでしょうか？

$X$ が有限の場合

$X$ の要素が有限個の場合は, 以下で具体的に説明するように, 半順序集合を非巡回有向グラフ（Directed Acyclic Graph, DAG）に置き換えてトポロジカルソートを実行することで, 条件を満たす全順序を具体的に構成できます.

Step 1: 半順序集合からDAGを構成する

まず半順序集合 $(X, \succeq)$ を所与として, 次のような有向グラフ $(V, E)$ を構成します（ $V$ は頂点の集合, $E$ が有向辺の集合です）

頂点は $X$ の各元（ $V = X$ ）
頂点 $x \in V$ から頂点 $y \in V$ への有向辺 $(x, y)$ は, \begin{align} (x, y) \in E \iff x \neq y \land x \succeq y \end{align}

このようにして作られた有向グラフ $(V, E)$ には閉路（サイクル）はありません.

（∵）仮にサイクル $x_1 \to x_2 \to \ldots \to x_n \to x_1$ があったとする. グラフの構成から \begin{align} x_1 \succeq x_2, \hspace{0.5em} x_2 \succeq x_3, \hspace{0.5em} \ldots, \hspace{0.5em} x_{n-1} \succeq x_n, \hspace{0.5em} x_n \succeq x_1 \end{align} が成り立つ. $\succeq$ は半順序なので, 推移律から $x_1 \succeq x_n$ が成り立つ. しかし $x_n \succeq x_1$ でもあるので, $x_1 \neq x_n$ よりこれは歪対称律を破り, $\succeq$ が半順序であることに矛盾する.

$(V, E)$ に閉路が無いので, この有向グラフはDAGになっています. よって半順序集合からDAGを構成できました.

Step2: DAGにトポロジカルソートを適用する

トポロジカルソートとは, 以下のルールを満たすようDAGの各点を並び替えることを言います

どの点も, その点から有向パスが伸びている任意の点より前に並んでいる

例

下図の例でトポロジカルソートを実行すると,

$a, b, c, d, e$
$a, c, b, d, e$
$e, a, c, b, d$
$a, e, c, b, d$

などが解になります.

f:id:myumori:20181215054149j:plain — DAGの例

解はユニークではありませんが, 有向グラフに閉路が存在しなければ（DAGであれば）解は必ず1つ以上存在します. このことは次のアルゴリズムの停止条件からわかります.

アルゴリズム

深さ優先探索を応用してトポロジカルソートを実現するアルゴリズムを紹介します. 以下の擬似コードはwikipediaからのコピペです.

L ← トポロジカルソートされた結果の入る空の連結リスト

for each ノード n do
    if n に印が付いていない then
        visit(n)

function visit(Node n)
    if n に「一時的」の印が付いている then
        閉路があり DAG でないので中断
    
    else if n に印が付いていない then
        n に「一時的」の印を付ける
        for each n の出力辺 e とその先のノード m do
            visit(m)
        n に「恒久的」の印を付ける
        n を L の先頭に追加

補足: 深さ優先探索をする過程で「一時的」の印が付いたノードに辿り着いたということは, 探索をしてきたパスの中に閉路が存在するということです. したがってDAGであれば, visit() の最初のifの中身が実行されることはありません.

擬似コードをPythonで書くと以下のようになります

class DiGraph(object):
    false_flag, temp_flag, perm_flag = 0, 1, 2
    
    def __init__(self, nodes, edges):
        self.nodes = nodes
        self.edges = edges
        self.node_size = len(nodes)

    def topological_sort(self):
        self.flags = {node:self.false_flag for node in self.nodes}
        self.sorted_nodes = []
        
        for node in self.nodes:
            if self.flags[node] == self.false_flag:
                self.visit(node)
        
        return self.sorted_nodes[::-1]
            
    def visit(self, node):
        if self.flags[node] == self.temp_flag:
            raise ValueError("DiGraph has a cycle")
            
        elif self.flags[node] == self.false_flag:
            self.flags[node] = self.temp_flag
            for node_to in self.edges[node]:
                self.visit(node_to)
                
            self.flags[node] = self.perm_flag
            self.sorted_nodes.append(node)

上の例を解いてみると

nodes = ["a", "b", "c", "d", "e"]
edges = {
    "a": ["b", "c"], 
    "b": ["d"], 
    "c": ["d"], 
    "d": [], 
    "e": [], 
}

digraph = DiGraph(nodes, edges)
digraph.topological_sort()

>> ['e', 'a', 'c', 'b', 'd']

となりました.

停止条件と計算量

上述のようにDAGであればアルゴリズムが途中でエラーを出力することは無いので,

全ての辺を探索し（ $O(|E|)$ ）
全ての頂点を sorted_nodes (L) に追加した（ $O(|V|)$ ）

時点でアルゴリズムは終了します. したがって計算量は $O(|V| + |E|)$ となります.

Step 3: トポロジカルソートの結果を全順序とする

トポロジカルソートの結果, $X$ の各元の順番が $x_1, x_2, \ldots, x_n$ と定まったら, あとは $X$ 上の二項関係 $\succeq_L$ を \begin{align} x_1 \succeq_L x_2 \succeq_L \ldots \succeq_L x_n \end{align} で定義すれば, これは $\succeq$ を拡張した全順序になっています. なぜならば, 任意の $x, y \in X$ s.t. $x \succeq y$ に対し,

DAGの構成から, $(x, y) \in E$
トポロジカルソートの定義から, $x$ は $y$ よりも前に並んでいる
$\succeq_L$ の構成から, $x \succeq_L y$

となっているためです.

$X$ が無限の場合

$X$ の要素が無限個の場合はトポロジカルソートのアルゴリズムの停止が保証できないため, 上記のような構成的な証明は使えません.

代わりに有名なZornの補題を用いて証明します.

Zornの補題
$S$ を半順序集合とする. $S$ の任意の全順序部分集合が $S$ の中に上界を持つ時, $S$ は少なくとも1つの極大元を持つ

いま $X$ 上で定義された2つの半順序 $(\succeq_1)$ と $(\succeq_2)$ の包含関係 $\subseteq$ を \begin{align} (\succeq_1) \subseteq (\succeq_2) \iff [ \forall x, y \in X, \ x \succeq_1 y \implies x \succeq_2 y ] \end{align} と定義します（つまり $\succeq_2$ は $\succeq_1$ を拡張したものだということです）.

また与えられた半順序集合 $(X, \succeq)$ に対し, 「 $\succeq$ を拡張した $X$ 上の半順序」全体の集合を \begin{align} \mathcal{P} = \left\{ \succeq^{\prime} \mid \text{$\succeq^{\prime}$は$X$上の半順序} \land (\succeq) \subseteq (\succeq^{\prime}) \right\} \end{align} で定義します.

このとき, $(\mathcal{P}, \subseteq)$ は半順序集合になっています.

（∵）半順序集合が満たすべき性質1-3を順にチェックすれば良い. $(\succeq_1), (\succeq_2), (\succeq_3) \in \mathcal{P}$ と $x, y \in X$ を任意に取る.

反射律: $x \succeq_1 y \implies x \succeq_1 y$ が成り立つので, $(\succeq_1) \subseteq (\succeq_1)$
推移律: $(\succeq_1) \subseteq (\succeq_2), \ (\succeq_2) \subseteq (\succeq_3)$ が成り立つとすると, \begin{align} x \succeq_1 y \implies x \succeq_2 y \implies x \succeq_3 y \end{align} が成り立つ. よって $(\succeq_1) \subseteq (\succeq_3)$
歪対称律: $(\succeq_1) \subseteq (\succeq_2) \ \land \ (\succeq_2) \subseteq (\succeq_1)$ が成り立つとすると, \begin{align} x \succeq_1 y \iff x \succeq_2 y \end{align} が成り立つ. よって $(\succeq_1) = (\succeq_2)$

また半順序集合 $(\mathcal{P}, \subseteq)$ はZornの補題の仮定を満たします.

（∵） $(\mathcal{P}, \subseteq)$ の（空でない）全順序部分集合 $(\mathcal{D}, \subseteq)$ を任意に取る.

いま新たな $X$ 上の二項関係 $\succeq_U$ を, \begin{align} \forall x, y \in X, \ x \succeq_U y \iff x \succeq_D y \hspace{0.5em} \text{for some $(\succeq_D) \in \mathcal{D}$} \end{align} で定義する. この時

$(\succeq_U)$ は半順序
$(\succeq_U) \in \mathcal{P}$
$(\succeq_U)$ は $(\mathcal{D}, \subseteq)$ の上界

が成り立つ. まず1.に関しては, 任意の $x, y, z \in X$ に対して

反射律: $\forall (\succeq_D) \in \mathcal{D}, x \succeq_D x$ なので, $x \succeq_U x$
推移律: $x \succeq_U y$ かつ $y \succeq_U z$ だと仮定する. この時 $(\succeq_{D1}), (\succeq_{D2}) \in \mathcal{D}$ が存在して \begin{align} x \succeq_{D1} y, \ y \succeq_{D2} z \end{align} が成り立つ. いま $(\mathcal{D}, \subseteq)$ は全順序集合だから, 完全律より $(\succeq_{D1}) \subseteq (\succeq_{D2})$ または $(\succeq_{D2}) \subseteq (\succeq_{D1})$ の少なくとも一方が成り立つ. 一般性を失わず $(\succeq_{D1}) \subseteq (\succeq_{D2})$ が成り立つとすると, \begin{align} x \succeq_{D1} y \implies x \succeq_{D2} y \end{align} が成り立つ. $(\succeq_{D2})$ が半順序であることから, $y \succeq_{D2} z$ と合わせて推移律より \begin{align} x \succeq_{D2} z \end{align} が成り立つ. よって $x \succeq_{U} z$
歪対称律: $x \succeq_U y$ かつ $y \succeq_U x$ だと仮定する. この時 $(\succeq_{D1}), (\succeq_{D2}) \in \mathcal{D}$ が存在して \begin{align} x \succeq_{D1} y, \ y \succeq_{D2} x \end{align} が成り立つ. よって推移律と全く同様の議論から, $i = 1$ or $2$ に対して \begin{align} x \succeq_{Di} y \land y \succeq_{Di} x \end{align} が成り立つので, $\succeq_{Di}$ の歪対称律から $x = y$ となる

2.に関しては, すでに $(\succeq_U)$ が半順序であることがわかったので, $(\succeq) \subseteq (\succeq_U)$ が成り立つことだけを調べればよい. これは $\forall x, y \in X$ , \begin{align} x \succeq y \implies \forall (\succeq_{D}) \in \mathcal{D}, x \succeq_{D} y \implies x \succeq_{U} y \end{align} より成り立つ.

3.に関しては, $(\succeq_{U})$ の構成から任意の $(\succeq_{D}) \in \mathcal{D}$ に対して, \begin{align} \forall x, y \in X, \ x \succeq_{D} y \implies x \succeq_{U} y \end{align} となり $(\succeq_D) \subseteq (\succeq_U)$ が成り立つので, $(\succeq_{U})$ は確かに $\mathcal{D}$ の上界となる.

したがってZornの補題が適用でき, 半順序集合 $(\mathcal{P}, \subseteq)$ は極大元を持ちます. 極大元の1つを $(\succeq_{M})$ とすると, これは $(\succeq)$ を拡張した $X$ 上の全順序になっています.

（∵） $(\succeq_{M}) \in \mathcal{P}$ なので, $(\succeq)$ を拡張した $X$ 上の半順序であることは明らか. したがって完全律だけを確かめれば良い.

任意の $x, y \in X$ をとる. 背理法の仮定として, $x \succeq_{M} y$ と $y \succeq_{M} x$ のいずれも成り立たないとする. この時 $X$ 上の新しい二項関係 $\succeq_{M^{\prime}}$ を \begin{align} \forall v, w \in X, \ v \succeq_{M^{\prime}} w \iff \begin{cases} v \succeq_{M} w, \ \text{ or } \\ v \succeq_{M} x \land y \succeq_{M} w \end{cases}\tag{1} \end{align} で定義する（つまり $(\succeq_{M})$ に $x \succeq_{M^{\prime}} y$ を加え, 推移律を満たすように拡張したもの）.

この時 $\succeq_{M^{\prime}}$ は半順序になっている. なぜならば任意の $u, v, w \in X$ に対し,

反射律: $\succeq_{M}$ の反射律から $u \succeq_{M} u$ が成り立つので, $u \succeq_{M^{\prime}} u$ もOK
推移律: およびが成り立つと仮定する.
- $(u, v) = (x, y)$ の場合: $x \succeq_{M} x$ かつ $y \succeq_{M} w$ なので, （1）より $x \succeq_{M^{\prime}} w$
- $(v, w) = (x, y)$ の場合: $u \succeq_{M} x$ かつ $y \succeq_{M} y$ なので, （1）より $u \succeq_{M^{\prime}} y$
- その他の場合: $(\succeq_{M})$ が推移律を満たすことからOK
歪対称律: $u \succeq_{M^{\prime}} v$ および $v \succeq_{M^{\prime}} u$ が成り立つと仮定する. 背理法の仮定から $(u, v) \neq (x, y), (y, x)$ なので, $(\succeq_{M})$ が歪対称律を満たすことからOK

加えて $(\succeq) \subseteq (\succeq_{M}) \subseteq (\succeq_{M^\prime})$ なので, $(\succeq_{M^\prime}) \in \mathcal{P}$ . これは $(\succeq_{M})$ が $\mathcal{P}$ の極大元であることに反する.

したがって完全律が成り立ち, $\succeq_{M}$ は $\succeq$ を拡張した $X$ 上の全順序になっています. よって任意の半順序集合 $(X, \succeq)$ に対して, それを拡張した全順序を構成できることがわかりました.

所感

トポロジカルソートのやり方は, 上で紹介したもの以外にもあります
Zornの補題は選択公理と同値なので, 選択公理フリークの方は上記の命題が選択公理と同値なのか/真に弱い命題なのか気になるのだと思いますが, 詳しくないのでわかりません（すみません）
整列可能定理（任意の集合は整列順序付け可能である）は選択公理と同値で, それよりも弱い「任意の集合は全順序で順序付け可能である」という命題は選択公理よりも真に弱いそうですが, 後者の命題よりもちょっと強い今回の命題はどうなんでしょうか

myumori diary

Live like a cat

半順序を全順序に拡張するやつ

定義