半順序集合と束 ― 順序構造の組合せ論

posetの定義，ハッセ図，鎖と反鎖，Dilworthの定理，Mirskyの定理，束の定義，メビウス関数（incidence algebra）を証明付きで解説する．

2026年2月27日

1 半順序集合の基本

定義 1 (半順序集合).

集合

P

上の二項関係

\leq

が以下の3条件を満たすとき，

(P, \leq)

を半順序集合（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$ ．

定義 2 (被覆関係).

x < y

かつ

x < z \leq y

ならば

z = y

であるとき，

y

は

x

を被覆する（cover）といい，

x ⋖ y

と書く．

定義 3 (ハッセ図).

有限 poset

(P, \leq)

のハッセ図（Hasse diagram）とは，

P

の元を頂点とし，被覆関係

x ⋖ y

を

x

から

y

へ向かう上向きの辺で表した図のことである．

例 4.

P = {1, 2, 3, 6, 12}

を整除順序

a ∣ b

で半順序集合とする．被覆関係は

1 ⋖ 2

，

1 ⋖ 3

，

2 ⋖ 6

，

3 ⋖ 6

，

6 ⋖ 12

である．

2 鎖と反鎖

定義 5 (鎖と反鎖).

poset

P

の部分集合

C

が鎖（chain）であるとは，

C

の任意の2元が比較可能（

x \leq y

または

y \leq x

）であることをいう．

A

が反鎖（antichain）であるとは，

A

の任意の異なる2元が比較不能であることをいう．

定義 6.

poset

P

の最長鎖の長さ（元の個数

- 1

）を

P

の高さ（height）という．最大の反鎖のサイズを

P

の幅（width）という．

3 Dilworth の定理

定理 7 (Dilworth の定理).

有限 poset

P

の幅（最大反鎖のサイズ）を

w

とする．

P

はちょうど

w

個の鎖に分割できる（

w - 1

個以下では不可能）．

証明.

P

が

w

個の鎖に分割できることを

∣ P ∣

に関する帰納法で示す．まず

w

個未満の鎖では分割できないことは明らかである（サイズ

w

の反鎖の各元は互いに異なる鎖に属さなければならない）から，

w

個の鎖で

P

を被覆できることを示せばよい．

基底：

∣ P ∣ = 1

のとき

w = 1

であり，

P

自身が1つの鎖なので成立．

帰納段階：

∣ P ∣ \geq 2

とし，

∣ P ∣

未満のサイズの有限 poset に対して定理が成立すると仮定する．

P

の最大反鎖

A = {a_{1}, \dots, a_{w}}

を1つ固定し，

P^{+} = {x \in P ∣ \exists a \in A, x \geq a}, P^{-} = {x \in P ∣ \exists a \in A, x \leq a}

とおく．

（i） $P = P^{+} \cup P^{-}$ ：各

a \in A

は

a \geq a

かつ

a \leq a

を満たすので

A \subseteq P^{+} \cap P^{-}

である．

x \in P ∖ (P^{+} \cup P^{-})

が存在すれば，

x

は

A

のどの元とも比較不能であるから

A \cup {x}

がサイズ

w + 1

の反鎖となり

A

の最大性に矛盾する．

（ii） $P^{+} ⊊ P$ かつ $P^{-} ⊊ P$ ：

P

の極小元

m

を1つとる（有限 poset には極小元が存在する）．

m \in P^{+}

と仮定すると，ある

a \in A

で

m \geq a

が成り立つが，

m

の極小性より

m = a \in A

でなければならない．一方

m \in P^{-}

は

m \leq m

より自明に成り立つ．ここで

m \in / P^{+}

なる極小元が存在すれば

m \in P^{-} ∖ P^{+}

となり

P^{+} ⊊ P

が従う．すべての極小元が

P^{+}

に属する（すなわちすべての極小元が

A

に属する）場合を考える．

∣ P ∣ \geq 2

であり

A

は反鎖であるから，

P ∖ A \neq = \emptyset

（

P = A

なら

P

は反鎖で

∣ P ∣ = w

だが，

w \geq 1

であり

∣ P ∣ \geq 2

のとき

P

のすべての元が極小元であるためには

P

自身が反鎖でなければならない；このとき

P = A

で

w = ∣ P ∣

であり

∣ P ∣

個の1元鎖に分割すればよい）．

P \neq = A

の場合，

x \in P ∖ A

をとると

x

は極小元でないから

x

より真に小さい元が存在し，その元は仮定よりある

a \in A

に等しい．よって

a < x

なので

x \in P^{+}

である．一方

x \in / A

であるから，

x \in P^{-}

であればある

a^{'} \in A

で

x \leq a^{'}

，つまり

a < x \leq a^{'}

であるが

A

が反鎖であるから

a \neq = a^{'}

のとき

a < a^{'}

が矛盾となり，

a = a^{'}

なら

x = a^{'} \in A

で矛盾．よって

x \in / P^{-}

であり，

P^{-} ⊊ P

．双対的な議論（

P

の極大元に着目）により

P^{+} ⊊ P

も得られる．

（iii）鎖分割の構成：

∣ P^{+} ∣ < ∣ P ∣

かつ

∣ P^{-} ∣ < ∣ P ∣

である．

P^{+}

と

P^{-}

の幅はそれぞれ

w

に等しい（

A

がそれぞれの中でサイズ

w

の反鎖であるから

w

以上であり，

P

の部分 poset であるから

w

以下）．帰納法の仮定より

P^{+}

は

w

個の鎖

C_{1}^{+}, \dots, C_{w}^{+}

に分割できる．

A

の各元

a_{i}

はいずれかの鎖に属し，

A

は反鎖であるから同一の鎖に2元以上入ることはなく，各鎖にちょうど1つの

a_{i}

が属する．再ラベルして

a_{i} \in C_{i}^{+}

とする．同様に

P^{-}

は

w

個の鎖

C_{1}^{-}, \dots, C_{w}^{-}

に分割でき，

a_{i} \in C_{i}^{-}

となるように再ラベルする．

C_{i} = C_{i}^{+} \cup C_{i}^{-}

（

i = 1, \dots, w

）とおく．

C_{i}^{+}

の元はすべて

a_{i}

以上，

C_{i}^{-}

の元はすべて

a_{i}

以下であるから，

C_{i}

の任意の2元は

a_{i}

を介して比較可能であり

C_{i}

は鎖である．

C_{i}^{+} \cap C_{i}^{-} = {a_{i}}

であり

P = P^{+} \cup P^{-}

であるから，

C_{1}, \dots, C_{w}

は

P

の互いに素な

w

個の鎖への分割を与える． □

4 Mirsky の定理

定理 8 (Mirsky の定理).

有限 poset

P

の最長鎖の長さ（元の個数）を

ℓ

とする．

P

はちょうど

ℓ

個の反鎖に分割できる．

証明.

各

x \in P

に対して

h (x)

を「

x

で終わる最長鎖の長さ」と定める．

A_{k} = {x \in P ∣ h (x) = k}

（

k = 1, \dots, ℓ

）とおけば

{A_{1}, \dots, A_{ℓ}}

は

P

の分割であり，各

A_{k}

は反鎖である．実際，

x, y \in A_{k}

で

x < y

ならば

h (y) \geq h (x) + 1 > k

となり矛盾． □

5 束

定義 9 (束).

poset

(L, \leq)

が束（lattice）であるとは，

L

の任意の2元

x, y

に対して上限（join）

x \lor y

と下限（meet）

x \land y

が存在することをいう．

例 10.

正整数の集合を整除順序で考えると，

a \lor b = lcm (a, b)

，

a \land b = g cd (a, b)

で束をなす．集合

S

のべき集合

2^{S}

は包含順序で束をなし，

A \lor B = A \cup B

，

A \land B = A \cap B

である．

定義 11 (分配束).

束

L

が分配束（distributive lattice）であるとは，

x \land (y \lor z) = (x \land y) \lor (x \land z)

が任意の

x, y, z \in L

に対して成り立つことをいう．

6 メビウス関数と接続代数

定義 12 (接続代数のメビウス関数).

有限 poset

P

のメビウス関数

μ : P \times P \to Z

を以下で帰納的に定める：

μ (x, x) = 1, x \leq z \leq y \sum μ (x, z) = 0 (x < y)

すなわち

μ (x, y) = - \sum_{x \leq z < y} μ (x, z)

（

x < y

）である．

x \neq \leq y

のときは

μ (x, y) = 0

と定める．

定理 13 (poset 上のメビウス反転公式).

P

を局所有限 poset とし，

f, g : P \to R

とする．

g (x) = y \leq x \sum f (y) ⟺ f (x) = y \leq x \sum μ (y, x) g (y)

証明.

右辺に

g (y) = \sum_{z \leq y} f (z)

を代入すると

y \leq x \sum μ (y, x) z \leq y \sum f (z) = z \leq x \sum f (z) z \leq y \leq x \sum μ (y, x)

z < x

のとき内側の和は

\sum_{z \leq y \leq x} μ (y, x) = 0

（メビウス関数の定義），

z = x

のとき

μ (x, x) = 1

であるから，全体は

f (x)

に等しい． □

例 14.

P = (Z_{> 0}, ∣)

（正整数の整除順序）のとき，

μ (d, n) = μ_{M \overset{o}{¨} bius} (n / d)

（古典的メビウス関数）であり，数論的メビウス反転公式が poset 上の一般論の特殊な場合であることがわかる．

組合せ論離散数学教科書半順序集合束

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

半順序集合と束 ― 順序構造の組合せ論

1 半順序集合の基本

2 鎖と反鎖

3 Dilworth の定理

4 Mirsky の定理

5 束

6 メビウス関数と接続代数

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ