[開設 06/29/21=MM/DD/YY]
分割全体からなる束
ここでは，
「分割間の順序」に引き続き，
分割は
空集合を要素に持たないものとする．
（参考：「集合族の例： 分割」
さて，「分割間の順序」で，
( ℙX, ⊑ )
が半順序集合になることを見た．
ただし，
ℙX は
集合 X の分割全体の族，すなわち
ℙX
=
{P ∊2(2X)
|
P は X の分割 }
である．
（ここでは，
空集合∅は分割の構成要素にはならないとしている．
つまり，
P が X の分割ならば
∅∉P ）．
また，
P ⊑ Q
⇔
∀P∊P
∃Q∊Q
( P⊆Q )
であった．
ここでは，
( ℙX, ⊑ )
が束であることを示そう．
P, Q ∊ℙX
のとき，
下の
P ⊓Q
を
P と Q
の交差分割
(cross partition)
という．
P ⊓Q
=
{ P∩Q | P∊P ,
Q∊Q }∖{∅} .
（これが
X
の分割であることの
証明）．
- 例 1
-
X = {
a,
b,
c,
d
}
とするとき，
{
{a,b},
{c,d}
}
⊓
{
{a,c},
{b,d}
}
=
{
{a},
{b},
{c},
{d}
},
{
{a,b},
{c,d}
}
⊓
{
{a,b,c},
{d}
}
=
{
{a,b},
{c},
{d}
}
である．
それぞれを
図に描くと下のようになる
（ブラウザーによっては適切に表示されないことがあります）．
図から，
P ⊓Q
は，
P
の境界線（切れ目）と
Q
の境界線
の両方を
境界線
とする分割になっていることが解る．
- 命題 1
-
P ⊓Q
は，
{ P, Q }
の最大下界である．
- 問 1
-
命題 1 を示せ．
解答
上の命題 1 に
ハンドアウト「半順序関係 (2)」命題 2 の証明を適用することによって，
ℙX
の任意の有限部分集合が下限をもつことがわかる．
しかし，
実は
有限に限らず
ℙX
の任意の部分集合が下限をもつ．
- 命題 2
-
{ P λ | λ∊Λ }⊆ℙX
の下限 ⊓λ∊ΛP λ
は
⊓λ∊ΛP λ
=
{ ∩λ∊ΛPλ |
Pλ∊P λ }∖{∅}
で与えられる．
注：
一般に
順序集合では，
sup {xλ | λ∊Λ }
を
∨λ∊Λ xλ，
inf {xλ | λ∊Λ }
を
∧λ∊Λ xλ
と書くことがある．
⊓λ∊ΛP λ
が X の分割であることの証明は，
P ⊓Q
が X の分割であることの証明と同様だが，
一応 ここ
に示しておく．
また，
⊓λ∊ΛP λ
が
{ P λ | λ∊Λ }
の下限であることの証明も，
P ⊓Q
が
{ P, Q }
の下限であることの証明と同様だが，
一応 ここ
に示しておく．
P, Q ∊ℙX
のとき，
P ⊔Q
を { P, Q }
の上界全体
{ R ∊ℙX |
P ⊑R,
Q ⊑R }
の下限とする．
すなわち，
P ⊔Q
=
⊓{ R ∊ℙX |
P ⊑R,
Q ⊑R } .
なお，
P, Q ∊ℙX
が何であっても，
{X}∊{ R ∊ℙX |
P ⊑R,
Q ⊑R }
である．
- 例 2
-
X = {
a,
b,
c,
d
}
とする．
まず，
{
{a,b},
{c},
{d}
}
⊔
{
{a},
{b},
{c, d}
}
を求めてみよう．
{ {
{a,b},
{c},
{d}
}，
{
{a}, {b},
{c,d}
}
}
の上界は，
{
{
{a,b},
{c,d}
}，
{
{a,b,c,d}
}
}
であるから，
その下限は
{
{a, b},
{c, d}
}
である．
したがって，
{
{a,b},
{c},
{d}
}
⊔
{
{a},
{b},
{c, d}
}
=
{
{a, b},
{c, d}
}
である．
別の例も 1 つ挙げておこう
（考え方はまったく同様）．
{
{a,b},
{c},
{d}
}
⊔
{
{a,c},
{b},
{d}
}
=
{
{a,b,c},
{d}
} .
これらを
図に描くと下のようになる（ブラウザーがOperaの場合，適切に表示されないことがあります）．
図に描くことによって，
P ⊔Q
は，
P
と
Q
の共通の境界線
だけを
境界線
とする分割になっていることが解る．
- 命題 3
-
-
P ⊔Q
は，
{ P, Q }
の最小上界になっている．
-
さらに，
{ P λ | λ∊Λ }⊆ℙX
の上限 ⊔λ∊ΛP λ
は
⊔λ∊ΛP λ
=
⊓{ R ∊ℙX |
∀λ∊Λ；
P λ⊑R } .
で与えられる．
命題 3 は，
上の命題 2
と
次の定理から
直ちに導かれる．
- 定理 1
-
半順序集合 (X, ≤)
において，
X
の任意の部分集合が
下限を持てば，
X
の任意の部分集合は
上限をもつ．
特に，
S⊆X
の上界全体の集合を U(S) とすると，
supS
=
infU(S)
である．
（なお，
任意の部分集合が上限と下限をもつ
半順序集合は 完備
(complete)
であるという．）
- 問 2
-
定理 1 を示せ．
解答
命題 1
と 命題 3
より，
( ℙX, ⊑ )
は束である
（しかも完備である）．
離散構造（室伏）のホームへ
