半順序集合

概要

「半順序集合」「順序集合」「半順序」という三つの語は、いずれも反射律・反対称律・推移律を満たす順序関係を扱う点で重なり合うが、指す対象のレベルが異なる。「半順序」は関係そのもの、「順序集合」は順序関係が定義された集合を指す包括的な語、「半順序集合」はそのうち最も標準的な、反射律・反対称律・推移律の3公理を満たす関係を備えた集合の組 $(P,\leq)$ を指す。本記事では公理そのものの詳細な性質（直積順序・双対順序・順序の階層など）は順序集合に委ね、「半順序集合」という呼称に固有の二つの観点――半順序集合を対象とする圏としての扱いと、有限な場合にハッセ図と完全に対応するという事実――を中心に述べる。

定義

半順序集合（recall）

集合 $P$ とその上の二項関係 $\leq\ \subset P\times P$ の組 $(P,\leq)$ が次の3条件を満たすとき、これを 半順序集合（partially ordered set, poset）と呼ぶ。

反射律: 任意の $x\in P$ に対して $x\leq x$。
反対称律: $x\leq y$ かつ $y\leq x$ ならば $x=y$（反対称律）。
推移律: $x\leq y$ かつ $y\leq z$ ならば $x\leq z$。
この3条件は順序集合の def-partially-ordered-set とまったく同一であり、「半順序集合」はその構造を指す標準的な同義語である。本記事では公理の再証明は行わず、直積順序・双対順序・最大元の一意性など公理そのものから従う基礎的性質は順序集合に委ねる。以下では、半順序集合を圏の対象として捉える視点と、有限半順序集合に特有の性質（ハッセ図との対応）という、この呼称に固有の観点を中心に論じる。

単調写像（作業用）

半順序集合 $(P,\leq_P)$、$(Q,\leq_Q)$ の間の写像 $f\colon P\to Q$ が単調（monotone, order-preserving）であるとは、任意の $x,y\in P$ に対して $x\leq_P y$ ならば $f(x)\leq_Q f(y)$ が成り立つことをいう。この定義は順序同型の def-order-iso-preserving と同一の作業用定義であり、正式な所有権は独立記事「順序を保つ写像」（未着手）に委ねる。

被覆関係（作業用）

半順序集合 $(P,\leq)$ において、$x,y\in P$ に対し $y$ が $x$ を 被覆する（$y$ covers $x$）とは、$x< y$ であり、かつ $x< z< y$ を満たす $z\in P$ が存在しないことをいう。このとき $x\lessdot y$ と書き、$\lessdot$ を $(P,\leq)$ の 被覆関係（covering relation）と呼ぶ。全順序集合における「直後の元」（順序同型の def-order-iso-immediate-successor）を、比較不能な元があってもよい一般の半順序集合へ拡張した概念である。

直感

半順序集合という呼称は、反射律・反対称律・推移律を満たす同じ構造を、それ自体を比較・分類する対象（圏の対象）として、あるいは有限の場合はハッセ図で描ける具体的な組合せ構造として捉える視点を強調する。

例

12の正の約数と整除関係

正の整数 $12$ の正の約数全体 $D_{12}=\{1,2,3,4,6,12\}$ に整除関係 $a\leq b:\iff a\mid b$ を入れると、$(D_{12},\mid)$ は有限な半順序集合である（順序集合の整除関係の例を $12$ の約数に制限したもの）。被覆関係は $1\lessdot2$、$1\lessdot3$、$2\lessdot4$、$2\lessdot6$、$3\lessdot6$、$4\lessdot12$、$6\lessdot12$ の7組である（たとえば $1\mid4$ だが $1\mid2\mid4$ を経由するため $1$ は $4$ を被覆しない）。これら7本の辺を図示したものが $(D_{12},\mid)$ のハッセ図であり、後述の性質により、この被覆関係だけから整除関係全体を（推移閉包を取ることで）完全に復元できる。

冪集合の包含関係（recall）

集合 $X=\{1,2,3\}$ の冪集合 $\mathcal P(X)$ を包含関係 $\subset$ で半順序集合とみると（一般の $X$ での議論は順序集合を参照）、$X$ が有限集合なので $\mathcal P(X)$ 自身も有限半順序集合であり、圏 $\mathbf{Poset}$ の対象の一例を与える。被覆関係は「ちょうど一元を加える」包含 $A\lessdot A\cup\{a\}$（$a\notin A$）で与えられる。

2元集合上の反鎖と鎖

2元集合 $\{a,b\}$ 上には本質的に異なる半順序がちょうど二通り存在する。$a,b$ を比較不能のままにする反鎖（antichain）と、$a< b$（または $b< a$）を課す鎖（chain、全順序）である。反鎖では $a\leq b$ が成り立たないが鎖では成り立つため、恒等的な対応 $a\mapsto a,\ b\mapsto b$ は順序同型写像にならない。実際、任意の全単射 $f\colon\{a,b\}\to\{a,b\}$ について、反鎖側では相異なる二元は比較不能なままだが鎖側では常に比較可能な対になるので、両者の間に順序同型写像は存在しない。半順序集合を圏 $\mathbf{Poset}$ の対象として捉える視点は、こうした「同じ台集合の大きさでも異なる半順序」を区別して扱う枠組みを与える。

反例：前順序だが半順序集合でない例（年齢による前順序）

人の集合 $X$ 上で $x\leq y:\iff（x\text{ の年齢}）\leq（y\text{ の年齢，実数として}）$ と定める。この関係は反射律（自分自身は自分と同年齢）と推移律（実数の大小関係の推移律から従う）を満たすので前順序（preorder）ではあるが、一般には反対称律を満たさない。実際、$x\neq y$ であっても同い年の二人がいれば $x\leq y$ かつ $y\leq x$ が成り立つのに $x\neq y$ である。したがって $(X,\leq)$ は半順序集合ではない。半順序集合であるためには反射律・推移律だけでなく反対称律まで満たす必要があることを、この反例は具体的に示している（同種の反例として、正の整数の整除関係を整数全体 $\mathbb Z$ に広げた場合が反対称律に挙げられている）。

性質

半順序集合と単調写像は圏をなす

半順序集合を対象とし、半順序集合の間の単調写像を射とし、写像の合成を射の合成、恒等写像を各対象の恒等射とする構造を $\mathbf{Poset}$ と呼ぶ。このとき次が成り立つ。

任意の半順序集合 $(P,\leq_P)$ に対し、恒等写像 $\mathrm{id}_P\colon P\to P$ は単調である。
$(P,\leq_P)$、$(Q,\leq_Q)$、$(R,\leq_R)$ を半順序集合とし、$f\colon P\to Q$、$g\colon Q\to R$ をともに単調写像とすると、合成 $g\circ f\colon P\to R$ も単調写像である。
したがって $\mathbf{Poset}$ は圏をなす。

半順序集合と単調写像は圏をなすことの証明

1. 任意の $x,y\in P$ に対し $x\leq_P y$ ならば、$\mathrm{id}_P(x)=x$、$\mathrm{id}_P(y)=y$ であるから $\mathrm{id}_P(x)\leq_P\mathrm{id}_P(y)$ が直ちに成り立つ。よって $\mathrm{id}_P$ は単調である。
2. $x,y\in P$ を $x\leq_P y$ とする。$f$ が単調であることから $f(x)\leq_Q f(y)$。さらに $g$ が単調であることから $g(f(x))\leq_R g(f(y))$、すなわち $(g\circ f)(x)\leq_R(g\circ f)(y)$ を得る。よって $g\circ f$ は単調である。
写像の合成が結合的であること、恒等写像が合成の両側単位元であることは、順序を保つという条件と無関係に写像一般について成り立つ事実である。1・2とあわせて、$\mathbf{Poset}$ は対象・射・合成・恒等射の組として圏の公理をすべて満たす。

有限半順序集合における被覆関係からの復元

$(P,\leq)$ を有限な半順序集合とし、$\lessdot$ をその被覆関係（def-poset-covering-relation）とする。$x,y\in P$ とするとき、次は同値である。

$x\leq y$。
$x=y$、または $x=x_0\lessdot x_1\lessdot\cdots\lessdot x_n=y$（$n\geq1$）を満たす $P$ の元の列（被覆鎖）が存在する。

有限半順序集合における被覆関係からの復元の証明

(2$\Rightarrow$1)。 $x=y$ なら反射律より $x\leq y$。被覆鎖 $x=x_0\lessdot x_1\lessdot\cdots\lessdot x_n=y$ があるとき、各 $x_{i-1}\lessdot x_i$ は特に $x_{i-1}< x_i$（したがって $x_{i-1}\leq x_i$）を含意するので、推移律を繰り返し用いれば $x\leq y$ を得る。
(1$\Rightarrow$2)。 $x\leq y$ とする。$x=y$ の場合は自明なので、$x< y$（$x\neq y$）の場合を示せばよい。区間 $I(x,y):=\{z\in P\mid x\leq z\leq y\}$ は $P$ の部分集合で $P$ が有限だから有限集合であり、$x,y\in I(x,y)$ かつ $x\neq y$ なので $|I(x,y)|\geq2$ である。$n:=|I(x,y)|$ についての強い帰納法で、$x$ から $y$ への被覆鎖が存在することを示す。
基礎段階（$n=2$）。 $I(x,y)=\{x,y\}$ である。もし $x< z< y$ を満たす $z\in P$ が存在すれば、$x\leq z\leq y$ より $z\in I(x,y)$ であり、$z\neq x$（$x< z$ より）かつ $z\neq y$（$z< y$ より）となって $|I(x,y)|\geq3$ に矛盾する。したがってそのような $z$ は存在せず、定義より $x\lessdot y$。これは長さ $1$ の被覆鎖である。
帰納段階（$n>2$）。 $|I(x,y)|< n$ を満たすすべての組について主張が成り立つと仮定する。$n>2=|\{x,y\}|$ より $I(x,y)\neq\{x,y\}$ であるから、$x< z< y$ を満たす $z\in P$ が存在する（存在しなければ基礎段階と同じ議論で $I(x,y)=\{x,y\}$ となり矛盾）。
$I(x,z)\subset I(x,y)$ であり、$y\in I(x,y)$ だが $y\notin I(x,z)$（$z< y$ より、もし $y\leq z$ なら $z\leq y$ とあわせて反対称律から $y=z$ となり $z< y$ に矛盾するので $y\notin I(x,z)$）だから $I(x,z)\subsetneq I(x,y)$、すなわち $|I(x,z)|< n$。同様に $x\notin I(z,y)$（$x< z$ より、もし $z\leq x$ なら反対称律から $x=z$ となり矛盾するので $x\notin I(z,y)$）だから $|I(z,y)|< n$。
帰納法の仮定より、$x$ から $z$ への被覆鎖 $x=u_0\lessdot u_1\lessdot\cdots\lessdot u_k=z$ と、$z$ から $y$ への被覆鎖 $z=v_0\lessdot v_1\lessdot\cdots\lessdot v_m=y$ がそれぞれ存在する（$x\neq z$、$z\neq y$ よりいずれも長さ $1$ 以上）。これらを $z$ でつなげた
$$ x=u_0\lessdot u_1\lessdot\cdots\lessdot u_k=z=v_0\lessdot v_1\lessdot\cdots\lessdot v_m=y $$
は $x$ から $y$ への被覆鎖である。以上より、すべての $n\geq2$ について主張が成り立つ。

有限性が本質的である理由：稠密な順序との対比

有理数全体 $\mathbb Q$ に通常の大小関係を入れた（無限の）半順序集合では、被覆関係 $\lessdot$ は空である。実際、任意の $p< q\in\mathbb Q$ に対して $z:=(p+q)/2$ とおけば $z\in\mathbb Q$ かつ $p< z< q$ が成り立ち（順序同型の prf-order-iso-Z-not-Q が用いる稠密性の議論と同じ）、$p\lessdot q$ とはならない。したがって「被覆関係の推移閉包として順序を復元する」という prop-poset-finite-hasse-cover は無限な半順序集合には一般化できず、$P$ の有限性が本質的に必要である。

圏 $\mathbf{Poset}$ の始対象と終対象

空集合 $\emptyset$ に空の順序関係を入れた半順序集合 $(\emptyset,\emptyset)$ は $\mathbf{Poset}$ の 始対象 である。すなわち、任意の半順序集合 $(P,\leq_P)$ に対して単調写像 $\emptyset\to P$ はちょうど一つ存在する。また、一元集合 $\{*\}$ に（反射律のみが要求する自明な）順序を入れた半順序集合 $(\{*\},=)$ は $\mathbf{Poset}$ の 終対象 である。すなわち、任意の半順序集合 $(P,\leq_P)$ に対して単調写像 $P\to\{*\}$ はちょうど一つ存在する。

圏 $\mathbf{Poset}$ の始対象と終対象の証明

始対象。 始域が空集合であるような写像は、対応させるべき元が存在しないため常にただ一つ存在する（空写像）。この空写像が単調であるという条件「任意の $x,y\in\emptyset$ に対して……」は、そのような $x,y$ が存在しないので空虚に成り立つ。よって $\emptyset\to P$ なる単調写像はちょうど一つ（空写像）存在し、$(\emptyset,\emptyset)$ は始対象である。
終対象。 任意の写像 $f\colon P\to\{*\}$ は、終域が一元集合であることから $f(x)=*$（すべての $x\in P$ について）と一意に定まる。この $f$ が単調であることを確かめる。任意の $x,y\in P$ に対し $x\leq_P y$ ならば $f(x)=*$、$f(y)=*$ であり、$\{*\}$ 上の自明な順序では $*\leq*$（反射律）が成り立つので $f(x)\leq f(y)$ を得る。よって $f$ は単調であり、$P\to\{*\}$ なる単調写像はちょうど一つ存在するので、$(\{*\},=)$ は終対象である。

分野ごとの使われ方

圏論では、半順序集合を対象・単調写像を射とする圏 $\mathbf{Poset}$ は、順序集合を「薄い圏」（thin category、対象間の射が高々1本の圏）とみなす視点（順序集合の「分野ごとの使われ方」参照）の圏論的な受け皿であり、$\mathbf{Poset}$ の同型対象は、順序同型の意味で順序同型な半順序集合にほかならない。
組合せ論・順序集合論では、有限半順序集合はハッセ図によって具体的に描画・分類される対象であり、上の被覆関係からの復元（prop-poset-finite-hasse-cover）は、この図が半順序集合の情報を過不足なく持つことの数学的根拠を与える。有限半順序集合の数え上げ・分配束との対応（Birkhoffの表現定理）・次元理論・区間順序といった深い分類理論は、専用記事有限半順序集合（未執筆）の担当とする。
前順序 $\subset$ 半順序 $\subset$ 全順序 $\subset$ 整列順序という順序集合一般の階層を一望する比較表は順序集合の記事に既にあるので、本記事では複製せず参照するに留める。

注意

「半順序」「半順序集合」「順序集合」の呼び分け

文献・サイト内でこれら三つの語は密接に関連するが、指す対象のレベルが異なる（型C）。「半順序」は反射律・反対称律・推移律を満たす二項関係そのものを指す語であり、台集合を明示しない。「半順序集合」（本記事）は、そのような関係 $\leq$ を備えた集合の組 $(P,\leq)$ を指す。「順序集合」は、より一般に「順序関係が定義された集合」を指す包括的な語であり、その最も標準的な形が半順序集合である。本サイトでは、構造としての組 $(P,\leq)$ を主題とする記事を「半順序集合」（本記事）と「順序集合」の二本に分け、前者は圏 $\mathbf{Poset}$・有限半順序集合とハッセ図という固有の観点を、後者は順序の公理そのもの・直積順序・双対順序・順序の階層といった一般論を担当する、という役割分担を取る。