10.7 集合の包含関係を使った半順序の表現

数学的オブジェクトの重要な性質を抽象化・議論する上で公理化は非常に有用な手法である。一方で、公理を満たす概念の具体的な例を考えることでも理解は深められる。例えば DAG は半順序を視覚的に表現する手段を与える。本節では、異なる数学的オブジェクトを使った半順序の表現を見る: 任意の半順序は集合族とそれらの包含関係として表現できる。つまり、任意の半順序と「同じ形」をした集合族が存在する。この「同じ形」は数学的な言葉で同型 (isomorphic) と呼ばれる:

定義 10.7.1

集合 \(A\) 上の二項関係 \(R\) と集合 \(B\) 上の二項関係 \(S\) が同型 (isomorphic) とは、\(A\) から \(B\) への関係を保存する全単射が存在することを言う。言い換えれば、全ての \(a, a^{\prime} \in A\) で次の関係が成り立つ全単射 \(f\colon A \to B\) が存在するとき \(R\) と \(S\) は同型である:

\[ a \mathrel{R} a^{\prime} \ \ \longleftrightarrow \ \ f(a) \mathrel{S} f(a^{\prime}) \]

集合 \(A\) 上の半順序 \(\preceq\) と同型な包含関係を持つ集合族は、\(A\) の各要素に対してそれと \(\preceq\) 関係にある要素全体の集合を構築すると得られる。つまり、次の対応関係は二項関係 \(\preceq\) を保存する全単射を定める:

\[ a\ \longleftrightarrow\ \left\{ b \in A \; | \; b \preceq a \right\} \]

例として整数の集合 \(\left\{ 1, 3, 4, 6, 8, 12 \right\}\) 上の整除関係を考えると、それぞれの整数は \(A\) に属する正約数の集合に対応付く:

\[ \begin{aligned} 1 \ &\longleftrightarrow\ \left\{ 1 \right\} \\ 3 \ &\longleftrightarrow\ \left\{ 1, 3 \right\} \\ 4 \ &\longleftrightarrow\ \left\{ 1, 4 \right\} \\ 6 \ &\longleftrightarrow\ \left\{ 1, 3, 6 \right\} \\ 8 \ &\longleftrightarrow\ \left\{ 1, 4, 8 \right\} \\ 12\ &\longleftrightarrow\ \left\{ 1, 3, 4, 6, 12 \right\} \\ \end{aligned} \]

例えば \(3 \; | \; 12\) は \(\left\{ 1, 3 \right\} \subseteq \left\{ 1, 3, 4, 6, 12 \right\}\) に対応する。

この構築が示すのは、任意の弱半順序が対応する集合族の包含関係で捉えられる事実である。正確に言えば、次の補題が成り立つ:

補題 10.7.2

\(\preceq\) を集合 \(A\) 上の弱半順序とする。\(A\) の各要素の \(\preceq\) による逆像からなる集合族の包含関係は \(\preceq\) と同型である。

証明は練習問題 (問題 10.37) とする。本質的に同じ構築を使えば、任意の狭義半順序が対応する集合族の真の包含関係で表せることも示せる。以上の事実を次の定理にまとめる:

定理 10.7.3

任意の弱半順序 \(\preceq\) に対して、包含関係が \(\preceq\) と同型な集合族が存在する。
任意の狭義半順序 \(\prec\) に対して、真の包含関係が \(\prec\) と同型な集合族が存在する。