順序集合

概要

一般に「順序集合」という場合、半順序集合（Partially Ordered Set, poset）を指すことが一般的である。

半順序集合 (Poset)

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

この関係 $\le$ を $X$ 上の順序（order）または半順序（partial order）と呼ぶ。$x \le y$ かつ $x \neq y$ のとき、$x < y$ と書く。

順序関係には、満たす公理の強さに応じていくつかの段階がある。

名称	公理	特徴	具体例
前順序 (Preorder)	反射律 + 推移律	区別できない異なる元が存在しうる（$x \le y \land y \le x$ でも $x=y$ とは限らない）。	命題論理における「ならば（含意）」関係
半順序 (Partial order)	前順序 + 反対称律	順序のループがない。比較不能なペアがあってもよい。	集合の包含関係 $\subseteq$
全順序 (Total order)	半順序 + 比較可能性	任意の2元が比較可能（$x \le y$ または $y \le x$）。一直線に並ぶ。	実数の大小関係 $\le$
整列順序 (Well-order)	全順序 + 最小元の存在	任意の空でない部分集合が最小元を持つ。	自然数 $\mathbb{N}$

比較可能性

$x, y \in X$ が比較可能（comparable）であるとは、$x \le y$ または $y \le x$ が成り立つことをいう。
半順序集合においては、比較可能でないペア（$x \not\le y$ かつ $y \not\le x$）が存在してもよい。

順序集合の概念は、数の大小だけでなく、構造的な「強さ」や「大きさ」を比較する場面で広く現れる。

具体例

数の大小:
自然数 $\mathbb{N}$、整数 $\mathbb{Z}$、実数 $\mathbb{R}$ などは、通常の大小関係 $\le$ により全順序集合である。
包含関係:
集合 $S$ の冪集合 $\mathcal{P}(S)$ において、包含関係 $\subseteq$ は順序関係である。
$S = \{a, b\}$ のとき、$\{a\}$ と $\{b\}$ は互いに包含関係にないため、比較不能である。したがって、これは半順序だが全順序ではない。
整除関係:
自然数 $\mathbb{N}$ において、「$x$ が $y$ を割り切る（$x \mid y$）」という関係は順序となる。
例: $2 \mid 6$ だが、$2$ と $3$ は整除関係にない。
辞書式順序:
単語の並び順のように、複数の順序集合の直積上に定義される標準的な順序。

順序集合においては、「一番大きい」という概念が複数に分岐する。ここが初学者が混同しやすいポイントである。
部分集合 $A \subseteq X$ を考える。

最大元と極大元

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

最大と極大の違い

集合 $A = \{2, 3, 4, 5, 6\}$ に整除関係（$x \mid y$）を入れる。

極大元: $4, 5, 6$ （これらを割り切る $A$ の元は自身のみ）
最大元: 存在しない（すべての元から割り切られる元が存在しないため）
もし $A$ に $12$ を加えれば、$12$ が最大元となる（2, 3, 4, 6 すべての倍数であるため）。

さらに、順序集合論で最も重要な概念の一つに上界と上限がある。

上界と上限

順序集合は、集合論における高度な議論の土台となる。

順序集合に関する定理

Zornの補題:
帰納的順序集合（任意の全順序部分集合が上界を持つような半順序集合）には、少なくとも一つの極大元が存在する。
（ベクトル空間の基底の存在証明などに不可欠）
整列可能定理:
任意の集合には、整列順序を入れることができる（選択公理と同値）。
Knaster-Tarskiの不動点定理:
完備束上の単調写像は不動点を持つ。