半順序

概要

集合 $P$ とその上の二項関係 $\le$ の組 $(P, \le)$ が半順序集合（Partially Ordered Set, Poset）であるとは、$\le$ が以下の3つの公理を満たすことをいう。

半順序の公理

任意の $a, b, c \in P$ に対して、

反射律 (Reflexivity):
$a \le a$
（自分自身と比較可能である）
反対称律 (Antisymmetry):
$a \le b$ かつ $b \le a$ ならば、$a = b$
（互いに相手以下ならば、それらは同一である。順序のループが存在しない）
推移律 (Transitivity):
$a \le b$ かつ $b \le c$ ならば、$a \le c$
（$a$ が $b$ より小さく、$b$ が $c$ より小さいなら、$a$ は $c$ より小さい）

もし $a \le b$ かつ $a \neq b$ であるときは、$a < b$ と表記する。

「半（Partial）」という言葉は、「比較不能（incomparable）なペアが存在してもよい」ということを意味している。

全順序: 任意の2元 $a, b$ について、$a \le b$ または $b \le a$ が必ず成り立つ（一直線に並ぶ）。
半順序: $a \le b$ でも $b \le a$ でもない状態（$a$ と $b$ は無関係）があり得る（分岐や並列がある）。
半順序集合の構造は、ハッセ図（Hasse diagram）と呼ばれるグラフを用いて視覚化されることが多い。要素を点で表し、$a < b$ のとき $b$ を $a$ の上方に配置して線で結ぶ（推移律により自明な線は省略する）。

半順序は、数の大小以外にも、構造的な「強弱」や「包含」を表す場面で現れる。

代表的な例

集合の包含関係:
ある集合 $S$ の冪集合 $\mathcal{P}(S)$ において、包含関係 $\subseteq$ は半順序である。
- $S = \{a, b\}$ のとき、$\{a\} \subseteq \{a, b\}$ だが、$\{a\}$ と $\{b\}$ は互いに包含関係にない（比較不能）。
自然数の整除関係:
自然数 $\mathbb{N}$ において、「$x$ が $y$ を割り切る（$x \mid y$）」という関係は半順序である。
- $2 \mid 6$ だが、$2$ と $3$ は比較不能である。
タスクの依存関係:
プロジェクト管理において、「タスクAが終わらないとタスクBが始まらない」という関係は半順序をなす。並行して実行可能なタスクは比較不能な元に対応する。

半順序集合において最も注意を要するのが、「一番大きい（Greatest）」と「これ以上大きくない（Maximal）」の区別である。全順序ではこれらは一致するが、半順序では明確に異なる概念となる。

特殊な元

部分集合 $A \subseteq P$ について：

最大元 (Greatest / Maximum):
$A$ のすべての元 $x$ に対して $x \le g$ となる $g \in A$。存在すればただ一つである。
極大元 (Maximal):
$A$ の元 $m$ であって、「$m$ より大きい元が $A$ の中に存在しない」もの（$m \le x \implies m = x$）。複数存在しうる。

具体例での違い

集合 $A = \{2, 3, 4, 6\}$ に整除関係（$x \mid y$）を入れる。ハッセ図を描くと、$2$ と $3$ が底にあり、$4$ は $2$ の上、$6$ は $2$ と $3$ の上にある。

極大元: $4$ と $6$
- $4$ の倍数は $A$ 内に存在しない（$4 \mid 6$ ではない）。$6$ の倍数も存在しない。よって両方とも極大である。
最大元: 存在しない
- 全ての元から割り切られる数（例えば $12$ など）が $A$ に含まれていないため。

Zornの補題: 「任意の鎖が上界を持つような半順序集合には、極大元が存在する」という定理。選択公理と同値であり、現代数学の存在定理の証明に不可欠である。
Dilworthの定理: 有限半順序集合において、最小の鎖分解のサイズは、最大の反鎖のサイズに等しい。