半順序集合の定義と重要な例（集合族と包含関係）｜全順序・鎖・極大元

$2$ と $5$ なら $2 < 5$ 、 $- 3$ と $0$ なら $- 3 < 0$ 。数の世界では、どの 2 つを取り出しても必ず大小が決まります。けれど「順序」と呼べるしくみは、数直線の外にも広がっています。ある集合が別の集合を含む、ある整数が別の整数を割り切る、ある作業が別の作業より先でなければならない。どれも順序の一種ですが、数の大小と決定的に違う点があります。「どちらとも言えない」対が出てくるのです。 ${1}$ と ${2}$ は互いに相手を含みません。 $4$ と $6$ はどちらも他方を割り切りません。この「比べられない対があってもよい順序」を正面から定義したものが、半順序集合です。

半順序集合の定義

半順序集合は、集合と「順序」のペアです。集合 $X$ と、その上の二項関係 $\leq$ の組 $(X, \leq)$ が半順序集合であるとは、 $X$ のどんな元 $a, b, c$ に対しても、次の 3 つが成り立つことをいいます。

反射律

どの元も自分自身とは順序がついていて、 $a \leq a$ がつねに成り立ちます。

反対称律

$a \leq b$ と $b \leq a$ が同時に成り立つのは、 $a = b$ のときだけです。向きが両側についたら、それは同じ元だ、ということです。

推移律

$a \leq b$ かつ $b \leq c$ なら $a \leq c$ が成り立ちます。順序は次々につなげられます。

記号 $\leq$ は数の大小とは限りません。「含む」でも「割り切る」でも、この 3 つさえ満たせば順序と呼び、 $(X, \leq)$ を半順序集合（poset）といいます。名前の「半」は、2 つの元が比較できない場合を許す、という意味です。ここが全順序との分かれ目になります。

「比べられない」を認めるのが半順序

2 つの元 $a, b$ について $a \leq b$ か $b \leq a$ の少なくとも一方が成り立つとき、 $a$ と $b$ は比較可能だといいます。どちらも成り立たないときは比較不能です。反射律・反対称律・推移律は「順序がついた対」がどうふるまうかを定めているだけで、「すべての対に順序がつく」ことまでは求めていません。だからこそ、比較不能な対が残ってもかまわないのです。

あとで見る集合の包含では、 ${1}$ と ${2}$ はどちらも他方を含まず、比較不能です。数直線のように一列に並ぶとは限らず、枝分かれや平行が許される。これが半順序の柔らかさであり、応用範囲の広さの源でもあります。

全順序集合

比較不能な対を一切許さない半順序集合を、全順序集合（または線型順序集合）と呼びます。半順序の 3 条件に加えて、どんな $a, b$ をとっても $a \leq b$ または $b \leq a$ の一方が必ず成り立つ、という比較可能性を満たすものです。

いちばん身近な例が数です。実数全体 $R$ 、整数全体 $Z$ 、自然数全体 $N$ は、通常の大小 $\leq$ でどれも全順序集合になります。どの 2 数にも大小がつくので、比較不能な対はありません。 $(R, \leq)$ は半順序集合であると同時に、この全順序という特別なクラスに属しているわけです。全順序は半順序の一種で、逆は成り立ちません。そしてこの記事の主役は、むしろ全順序にならない半順序のほうです。

重要な例：集合族と包含関係

いよいよ主役の登場です。ある集合 $X$ の部分集合を集めた族を考え、包含関係 $\subseteq$ で順序を入れます。 $A \subseteq B$ を「 $A$ は $B$ に含まれる」と読めば、これは 3 条件をすべて満たします。どんな集合も自分自身を含み（反射律）、互いに含み合えば等しく（反対称律）、含む含まれるの関係は連鎖する（推移律）からです。とくに $X$ のすべての部分集合を集めた族を冪集合といい、 $P (X)$ と書きます。 $(P (X), \subseteq)$ は半順序集合の代表選手です。

小さく $X = {1, 2}$ で見ると、部分集合は $\emptyset$ 、 ${1}$ 、 ${2}$ 、 ${1, 2}$ の 4 個です。 $\emptyset$ はすべてに含まれ、 ${1, 2}$ はすべてを含みます。ところが ${1}$ と ${2}$ は、どちらも相手を含みません。ここに比較不能な対が現れます。数の大小ならありえなかった「引き分け」が、包含では自然に起きるのです。

$X = {1, 2, 3}$ なら、部分集合は要素の有無を選ぶぶんだけ増えます。

$∣ P (X) ∣ = 2^{n}$

元が $n$ 個なら冪集合の元は $2^{n}$ 個で、 $n = 3$ では $8$ 個です。大きさごとに並べると、次のようになります。

要素 0 個：

\emptyset

要素 1 個：

{1}

、

{2}

、

{3}

要素 2 個：

{1, 2}

、

{1, 3}

、

{2, 3}

要素 3 個：

{1, 2, 3}

$8$ 個もあると、比較可能な対と比較不能な対が入り混じり、全体像は文章だけでは追いにくくなります。そこで登場するのが、半順序を一枚の絵にするハッセ図です。

ハッセ図で全体像をつかむ

ハッセ図は、半順序集合を点と線で表す図です。かき方の要点は、余分な線を省くことにあります。まず反射律による自分自身へのループは、どの元にもあるので描きません。次に、推移律でたどれる線も省きます。 $\emptyset \subseteq {1} \subseteq {1, 2}$ の $\emptyset$ から ${1, 2}$ への線は、間の ${1}$ を経由できるので引きません。残すのは「 $A \subseteq B$ で、間に何もはさまらない」対、すなわち $B$ が $A$ を直に覆う関係だけです。この覆う関係を、小さいほうを下、大きいほうを上にして線で結びます。

$P ({1, 2, 3})$ をこの流儀でかくと、次の図になります。

HTML

CSS

JavaScript

<div class="hasse">
<svg viewBox="0 0 360 320" xmlns="http://www.w3.org/2000/svg" role="img" aria-label="P({1,2,3}) のハッセ図">
<rect x="0" y="0" width="360" height="320" rx="10" fill="#f7f8fa"/>
<g stroke="#a3a8b0" stroke-width="1.5" stroke-linecap="round">
<line x1="180" y1="284" x2="80" y2="206"/>
<line x1="180" y1="284" x2="180" y2="206"/>
<line x1="180" y1="284" x2="280" y2="206"/>
<line x1="80" y1="206" x2="80" y2="128"/>
<line x1="80" y1="206" x2="180" y2="128"/>
<line x1="180" y1="206" x2="80" y2="128"/>
<line x1="180" y1="206" x2="280" y2="128"/>
<line x1="280" y1="206" x2="180" y2="128"/>
<line x1="280" y1="206" x2="280" y2="128"/>
<line x1="80" y1="128" x2="180" y2="44"/>
<line x1="180" y1="128" x2="180" y2="44"/>
<line x1="280" y1="128" x2="180" y2="44"/>
</g>
<g font-family="ui-sans-serif, system-ui, sans-serif" font-size="13" text-anchor="middle" fill="#1b1d22" stroke="#f7f8fa" stroke-width="4" paint-order="stroke">
<text x="180" y="48">{1,2,3}</text>
<text x="80" y="132">{1,2}</text>
<text x="180" y="132">{1,3}</text>
<text x="280" y="132">{2,3}</text>
<text x="80" y="210">{1}</text>
<text x="180" y="210">{2}</text>
<text x="280" y="210">{3}</text>
<text x="180" y="288">∅</text>
</g>
</svg>
</div>

.hasse { margin: 0; text-align: center; }
.hasse svg { width: 100%; max-width: 340px; height: auto; }

線を 1 本上へたどるたびに、集合の要素がちょうど 1 個増えます。最下段の $\emptyset$ から $1$ か $2$ か $3$ を足して要素 1 個の集合へ、もう 1 個足して要素 2 個の集合へ、最後に全部そろえて ${1, 2, 3}$ へ。上下に線でつながっていれば比較可能、線をたどって行き来できなければ比較不能です。同じ段に並ぶ ${1}$ 、 ${2}$ 、 ${3}$ は互いに比較不能で、これが図の「幅」を生んでいます。冪集合のハッセ図がちょうど $n$ 次元の立方体になるのは、各要素の有無が座標軸の $0$ と $1$ に対応するからです。

割り切れる関係という順序

包含と並んでよく現れるのが、整数の割り切れる関係です。正の整数の上で「 $a$ が $b$ を割り切る」ことを $a ∣ b$ と書き、これを順序とみなします。 $a ∣ a$ は当然成り立ち（反射律）、 $a ∣ b$ かつ $b ∣ a$ なら $a = b$ （反対称律）、 $a ∣ b$ かつ $b ∣ c$ なら $a ∣ c$ （推移律）と、3 条件がそろいます。正の整数の全体は、この割り切れる関係でも半順序集合になるのです。

これも全順序ではありません。 $2 ∣ 6$ は成り立ちますが、 $4$ と $6$ はどちらも他方を割り切らず、比較不能です。 $12$ の約数 $1, 2, 3, 4, 6, 12$ だけを取り出してハッセ図にすると、 $1$ を最下段、 $12$ を最上段に置き、 $2$ と $3$ が同じ段、 $4$ と $6$ が同じ段に並びます。 $2$ から $4$ へ、 $2$ から $6$ へ、 $3$ から $6$ へと、素因数を 1 つかけるぶんだけ線が上へ伸びる。包含関係の冪集合とよく似た枝分かれが、約数の世界にも現れます。

成分ごとに比べる（直積順序）

順序どうしを組み合わせて、新しい半順序を作ることもできます。平面 $R^{2}$ の点 $(a, b)$ と $(c, d)$ を、成分ごとの大小で比べてみます。すなわち $a \leq c$ かつ $b \leq d$ のときに限り $(a, b) \leq (c, d)$ と定めます。これは直積順序と呼ばれ、やはり半順序集合になります。

この順序では $(1, 2) \leq (3, 4)$ が成り立ちます。横も縦も右上の点のほうが大きいからです。ところが $(1, 4)$ と $(3, 2)$ は比較できません。横で見れば $1 < 3$ ですが、縦では $4 > 2$ と勝敗が逆になり、どちらが大きいとも決められないのです。これは経済学でいうパレート優越と同じ考え方で、すべての指標で勝ってはじめて上位と認める、という比べ方にあたります。指標が 1 つなら全順序ですが、2 つ以上を同時に見た瞬間に比較不能が生まれ、半順序へと変わります。

最大元と極大元は違う

半順序ならではの注意点が、「いちばん上」の意味が 2 通りに分かれることです。ある元 $m$ がすべての元より大きい、つまりどの $x$ に対しても $x \leq m$ が成り立つとき、 $m$ を最大元と呼びます。いっぽう、 $m$ より真に大きい元が 1 つもない、つまり $m \leq x$ となる $x$ が $m$ 自身しかないとき、 $m$ を極大元と呼びます。

全順序ではこの 2 つは一致しますが、半順序ではずれることがあります。

最大元

すべての元と比較可能で、そのどれよりも大きい元。存在すればただ 1 つに定まります。

極大元

自分より上がないだけの元。ほかと比較不能でもよく、いくつも共存できます。

具体例を挙げます。 ${1, 2, 3}$ の部分集合のうち、全体集合 ${1, 2, 3}$ そのものを除いた族を、包含で順序づけます。すると ${1, 2}$ 、 ${1, 3}$ 、 ${2, 3}$ は、自分を真に含む集合が族の中にないので、どれも極大元です。しかしこの 3 つは互いに比較不能なので、すべてより大きい最大元は存在しません。極大元は 3 つあるのに最大元はない、という半順序らしい状況です。全順序の直感で「いちばん大きいものが 1 つある」と思い込むと、ここでつまずきます。

鎖と反鎖

半順序の中には、全順序の小島が隠れています。半順序集合の部分集合で、その中のどの 2 元も比較可能になっているものを鎖と呼びます。冪集合 $P ({1, 2, 3})$ でいえば、

$\emptyset \subset {1} \subset {1, 2} \subset {1, 2, 3}$

という 4 つの集合は、一列に包含が続くので鎖です。ハッセ図の上では、下から上へ一本道でたどれる経路がちょうど鎖にあたります。「全順序になる集合族」とは、まさにこの鎖のことです。

逆に、どの 2 元も比較不能な部分集合を反鎖と呼びます。 ${1}$ 、 ${2}$ 、 ${3}$ の 3 つは互いに包含がなく、反鎖の例です。鎖は「もっとも縦に長い並び」、反鎖は「もっとも横に広い並び」と見ると、半順序の骨格がつかめます。鎖は応用でも主役級で、たとえばツォルンの補題は「どの鎖にも上界があれば極大元が存在する」という形で、鎖を手がかりに極大元の存在を保証します。

理解の確認

冪集合 $P ({1, 2, 3})$ を包含 $\subseteq$ で順序づけたとき、次のうち比較可能な（ $\subseteq$ で結べる）対はどれでしょうか。

${1, 2}$ と ${1, 3}$
${2}$ と ${1, 3}$
${2}$ と ${1, 2}$

__RESULT__

${2} \subseteq {1, 2}$ が成り立つので、 ${2}$ と ${1, 2}$ は比較可能です。残る 2 つはいずれも一方が他方を含まず、比較不能です。 ${1, 2}$ と ${1, 3}$ はどちらも相手にない要素をもち、 ${2}$ と ${1, 3}$ は $2 \in / {1, 3}$ なので ${2}$ すら含まれません。同じ冪集合の中でも、比較できる対とできない対が混在しているわけです。

逆順序と、半順序が現れる場所

半順序の見方を、もう一段広げておきます。半順序集合 $(X, \leq)$ の順序をそっくり逆向きにして、 $a \leq b$ を $b \leq a$ と読み替えると、これもまた半順序集合になります。もとの 3 条件は、向きを反転しても保たれるからです。この逆順序に移ると、最大元と最小元、極大元と極小元、鎖のてっぺんと底が、そっくり役割を入れ替えます。片方で証明したことは、もう片方でも自動的に成り立つ。半順序には、こうした上下対称のうまみがあります。

包含・割り切れ・成分ごとの大小と見てきたように、半順序は数学のあちこちに顔を出します。どの 2 元にも上限と下限がそろえば束になり、開集合の全体は包含で順序づいて位相の舞台となり、作業の依存関係をたどるタスクスケジューラやバージョン管理の履歴もまた半順序です。「一列に並ぶとは限らない順序」という一点をゆるめただけで、これだけ広い世界が同じ言葉で語れるようになります。半順序集合は、その共通の足場なのです。

半順序集合を、反射律・反対称律・推移律の定義から具体例中心に解説します。集合族と包含関係、冪集合のハッセ図、割り切れる関係、直積順序（パレート）、全順序との違い、最大元と極大元、鎖と反鎖まで、比べられない対がある順序を図と例で直観的に学べます。