半順序

数のリストを小さい順に並べるとき、そこには「順序」という概念が使われている。でも順序の考え方はもっと広い。集合を包含関係で並べたり、タスクを依存関係で並べたり、整数を整除関係で並べたりもできる。こういったすべての背後にある抽象的な構造が半順序（はんじゅんじょ、partial order）だ — 「以下またはイコール」という数学的な概念を厳密に定式化したもので、比較できない元のペアが存在してもかまわない。

二項関係

順序を定義する前に、集合の元どうしの関係を語る方法が必要だ。その核心となるのが直積（ちょくせき、Cartesian product）だ。

集合 $A$ と $B$ に対して、その直積 $A \times B$ は $a \in A$、$b \in B$ なる順序対 $(a, b)$ をすべて集めた集合だ：

$$A \times B \;\coloneqq\; \{(a, b) \mid a \in A,\; b \in B\}$$

例えば、$\{1, 2\} \times \{x, y\} = \{(1,x),\,(1,y),\,(2,x),\,(2,y)\}$。

集合 $S$ 上の二項関係（にこうかんけい、binary relation）とは、$S \times S$ の任意の部分集合 $R \subseteq S \times S$ のことだ。$(a, b) \in R$ のとき「$a$ は $b$ に関係する」と言い、$a \mathbin{R} b$ と書く。この関係は $R$ が表すルールによって「関係する」順序対を記述している。

身近な例：

• $\mathbb{Z}$ 上の通常の $\leq$：$2 \leq 5$ なので、順序対 $(2, 5)$ はこの関係に属する。
• $\mathbb{N}$ 上の整除関係：$a \mid b$ は $\exists\, k \in \mathbb{N}$ で $b = k \cdot a$ を意味する。
• 冪集合上の集合の包含関係：$\{1\} \subseteq \{1, 2\}$ なので、順序対 $(\{1\}, \{1, 2\})$ はこの関係に属する。

3つの重要な性質

すべての二項関係が順序であるわけではない。順序関係を成り立たせるには、3つの構造的な条件を満たす必要がある。

反射性（はんしゃせい、reflexivity）。 すべての元は自分自身と関係する：

$$\forall a \in S,\quad a \leq a$$

反対称性（はんたいしょうせい、antisymmetry）。 $a \leq b$ かつ $b \leq a$ ならば、$a$ と $b$ は等しい：

$$\forall a, b \in S,\quad a \leq b \;\text{ かつ }\; b \leq a \;\Longrightarrow\; a = b$$

これにより循環が排除される：異なる2つの元が互いに「下」になることはできない。

推移性（すいいせい、transitivity）。 $a \leq b$ かつ $b \leq c$ ならば $a \leq c$：

$$\forall a, b, c \in S,\quad a \leq b \;\text{ かつ }\; b \leq c \;\Longrightarrow\; a \leq c$$

順序が比較の連鎖を通じて「伝播する」という考え方を捉えている。

半順序の定義

$S$ 上の半順序とは、反射的・反対称的・推移的な $S$ 上の二項関係 $\leq$ のことだ。組 $(S, \leq)$ を半順序集合（はんじゅんじょしゅうごう、partially ordered set）、またはポセット（poset）と呼ぶ。

記号 $\leq$ は慣例的なものだが、この3つの公理を満たす二項関係であれば、どんな記号を使っていても半順序と呼べる。

狭義半順序

任意の半順序 $\leq$ から、付随する狭義半順序（きょうぎはんじゅんじょ、strict partial order）$<$ が次のように定義される：

$$a < b \;\coloneqq\; a \leq b \;\text{ かつ }\; a \neq b$$

狭義版は非反射的（すべての $a$ に対して $a \not< a$）かつ非対称的（$a < b \Rightarrow b \not< a$）だ。どちらか一方からもう一方が決まるので、$\leq$ か $<$ のどちらを与えても半順序を指定できる。

例

$\leq$ による整数の順序

$(\mathbb{Z}, \leq)$ は最もなじみ深い半順序だ。反射性（$n \leq n$）、反対称性（$m \leq n$ かつ $n \leq m$ なら $m = n$）、推移性（$m \leq n$ かつ $n \leq p$ なら $m \leq p$）がすべて成り立つ。この例では、任意の整数のペアが比較可能だ：任意の $m, n \in \mathbb{Z}$ に対して、$m \leq n$ または $n \leq m$ のどちらかが成り立つ。

包含関係による冪集合

$A$ を任意の集合とし、$\mathcal{P}(A)$ を $A$ の冪集合 — $A$ のすべての部分集合からなる集合 — とする。すると $(\mathcal{P}(A), \subseteq)$ は半順序になる。

$A = \{1, 2, 3\}$ のとき、部分集合 $\{1, 2\}$ と $\{2, 3\}$ を考えると、どちらももう一方を含まないので、$\subseteq$ のもとで比較不能だ。これは $(\mathbb{Z}, \leq)$ では起こらない。

正の整数上の整除関係

$b = k \cdot a$ となる $k \in \mathbb{N}$ が存在するとき $a \mid b$（「$a$ は $b$ を割り切る」）と定義する。すると $(\mathbb{Z}_{>0},\; \mid)$ は半順序になる：

• 反射性： $a = 1 \cdot a$ なので $a \mid a$。✓
• 反対称性： 正の整数で $a \mid b$ かつ $b \mid a$ ならば $a = b$。✓
• 推移性： $a \mid b$ かつ $b \mid c$ のとき、$b = j \cdot a$、$c = k \cdot b$ と書けば $c = (kj) \cdot a$ となり $a \mid c$。✓

しかし $2$ と $3$ は比較不能だ：$2 \nmid 3$ かつ $3 \nmid 2$。

ハッセ図

有限ポセットに対しては、ハッセ図（Hasse diagram）を使うと簡潔に視覚化できる：

• 各元をラベル付きの点として描く。
• $a < b$ のとき $b$ を $a$ より高い位置に配置する。
• $a < b$ かつ $a < c < b$ となる $c$ が存在しない場合（これを被覆関係と呼ぶ）にのみ、$a$ から $b$ へ上向きの線を引く。
• 推移性から導かれる線は省略する。

$\{1, 2, 3, 6\}$ 上の整除順序のハッセ図は、$1$ が一番下にあり、$2$ と $3$ が中段（それぞれ $1$ と線でつながる）、$6$ が一番上（$2$ と $3$ とつながる）になる。$1$ から $6$ への線は、$1 < 2 < 6$ という推移性から導かれるので省略される。

比較可能な元と比較不能な元

$S$ の2つの元 $a, b$ が比較可能（ひかくかのう、comparable）とは、$a \leq b$ または $b \leq a$ が成り立つことだ。どちらも成り立たない場合は比較不能（ひかくふのう、incomparable）といい、$a \parallel b$ と書くこともある。

$(\mathbb{Z}, \leq)$ ではすべてのペアが比較可能だ。$(\mathcal{P}(\{1,2\}), \subseteq)$ では、1元集合 $\{1\}$ と $\{2\}$ は比較不能だ。「半」順序の「半」はまさにここを指している：すべての元のペアが比較可能である必要はない。すべてのペアが比較可能になると、より強い概念 — 全順序（ぜんじゅんじょ、total order） — になり、次のチェックポイントで学ぶ。

極小・極大・最小・最大元

この4つの用語は混同しやすいので、それぞれの正確な意味を確認しよう。

元 $m \in S$ が極小元（きょくしょうげん、minimal element）であるとは、$S$ の中に $m$ より真に小さいものが存在しないことだ：

$$\nexists\, a \in S \text{ s.t. } a < m$$

元 $M \in S$ が極大元（きょくだいげん、maximal element）であるとは、$S$ の中に $M$ より真に大きいものが存在しないことだ：

$$\nexists\, a \in S \text{ s.t. } M < a$$

$S$ の最小元（さいしょうげん、least element / minimum）とは、他のすべての元以下である元 $m_0$ のことだ：

$$\forall a \in S,\quad m_0 \leq a$$

$S$ の最大元（さいだいげん、greatest element / maximum）とは、他のすべての元以上である元 $M_0$ のことだ：

$$\forall a \in S,\quad a \leq M_0$$

重要な違い。 最小元は自動的に極小元でもあるが、極小元が最小元とは限らない。ポセットは複数の極小元を持ちつつ、最小元を持たないこともある。

例。 $S = \{2, 3, 6\}$ 上の整除関係を考えよう。$2$ と $3$ はどちらも極小元だ（$S$ の中にそれらを真に割り切る元がない）。しかし最小元は存在しない — $2$ と $3$ は比較不能で、どちらももう一方以下ではないからだ。$6$ は極大元であり、また唯一の最大元でもある。なぜなら $2 \mid 6$ かつ $3 \mid 6$ だからだ。

最小元が存在する場合、それは反対称性によって一意だ。最大元についても同様だ。

まとめ

• 直積 $A \times B = \{(a, b) \mid a \in A, b \in B\}$ は順序対をまとめる。$S$ 上の二項関係は $S \times S$ の任意の部分集合だ。
• $S$ 上の半順序 $\leq$ は反射的・反対称的・推移的な関係であり、組 $(S, \leq)$ をポセットと呼ぶ。
• 付随する狭義半順序 $<$ は $a < b \coloneqq a \leq b$ かつ $a \neq b$ で定義される。
• 主要な例：$(\mathbb{Z}, \leq)$、$(\mathcal{P}(A), \subseteq)$、正の整数上の整除関係。
• 元のペアは比較可能（一方が他方以下）または比較不能（どちらでもない）のいずれかだ。
• 最小（最大）元は $S$ のすべての元以下（以上）であり一意に定まる。極小（極大）元は単に真に下（上）にあるものが存在しないだけで、一意とは限らない。