完全分配格

i∈I j ∈Ji f∈
i∈I Ji
i∈I
和
(CD2)
i∈I j ∈Ji
aij =
f∈
i∈I Ji
ai,f (i) .
i∈I
则称L是一个完全分配格(completely distributive lattice), 其中(CD1)称为交对 并的完全分配律, (CD2)称为并对交得完全分配律. 在格上的一些等式的证明过程中, 完全分配律(CD1)和(CD2)的作用在于 可以将交并运算交换计算次序. 定理1 完全分配律(CD1)和(CD2)相互等价. 证明 这里我们只证明(CD1)可推出(CD2), (CD2)推出(CD1)可类似证明. 一方面, 对于每一个固定的f ∈ i∈I Ji , 任取i0 ∈ I 都有 ai0 ,j ≤ i∈I ai,f (i) .
Ts
ρ(a).
又显然↓a是上确界大于等于a的下集, 由定义2, ρ(a) ≤ a. 反过来, 设{As | s ∈ S }, As = {xst | t ∈ Ts }是L的一族子集. 令a = s∈S t∈Ts xst , 则对于任意 的s ∈ S, As ≥ a. 于是
xsϕ(s) ≥
ϕ∈
s∈ S
∗ 本文是已发表在 《纺织高校基础科学学报》 2103年第1期上的相应论文的修改版.
1
§1
完全分配格的定义
完全分配格[2, 7]的定义需要借助于选择函数. 设{Ji | i ∈ I }是以I 为指标 集的集族, 记 i∈I Ji = {f | f : I −→ i Ji , ∀i ∈ I, f (i) ∈ Ji }, 其中 i Ji 表 示{Ji | i ∈ I }的不交并. 根据选择公理, 对于任意非空指标集I , 若对于每一 个i ∈ I , Ji = ∅, 则有 i∈I Ji = ∅. 定义1 设L是完备格, 若对于L的任意子集族Xi = {aij | j ∈ Ji } (i ∈ I ), 有 (CD1) aij = ai,f (i)
bf,φ(f ) ≤
φ∈I F f ∈F i j ∈Ji
aij .
因此, (CD2)的右边总是小于等于左边. 例1 (1) 对于任意集合（包括空集）, 其幂集格2X 是完全分配格. (2) 任意完备的全序集, 如单位区间[0,1], 是完全分配格.
2
接下来, 我们将研究完全分配格在集合和集族下的表现形式. 设R是一族 集合, 如果R按照集合的通常的交并关系构成一个完备格, 且称R是一个完备 集环(complete ring of sets). 定理2 L是一个完全分配格当且仅当L完备格同构于某完备集环的同态 像. 证明 由于完备集环作为完备格, 其交并运算分别为通常的集合交并运算, 因此充分性是显然的, 下证必要性. 设S(L)是L的非空下集的全体, 定义f : S(L) −→ L为f (A) = A, 则f 是一个满射. 设L是一个完全分配格, 一方面, 设{As | s ∈ S } ⊆ S(L)且As = {xst | t ∈ Ts }, 显然
ρ(a) = a =
s∈S t∈Ts
xst ,
Ts s∈S
因此 ϕ∈ s∈S Ts s∈S xsϕ(s) = s∈S t∈Ts xst . (3) ρ(a) = ρ( ρ(a)) = x∈ρ(a) ρ(x). 定理5 (1) 一族完全分配格的直积仍然是完全分配格. (2) 完全分配格的完备子格是完全分配格. 证明留给读者. 定理6 设L是一个完备格, 则L是一个完全分配格当且仅当L可以作为完 备子格序嵌入到一些完备链的直积中. 证明 由定理5, 我们只需证必要性. 设L是完全分配格, 在L上定义二元关 系R为xRy ⇐⇒ x ∈ ρ(y ). 第一步 R ◦ R = R. 事实上, 设xRy , 则x ∈ ρ(y ) = z∈ρ(y) ρ(z ), 从而存 在z ∈ L使得x ∈ ρ(z ), z ∈ ρ(y ), 即xRzRy, xR ◦ Ry , 因此R ⊆ R ◦ R. 反过来, 如果xR ◦ Ry , 则存在z ∈ L使得xRzRy , 即x ∈ ρ(z ), z ∈ ρ(y ), 从而x ∈ ρ(y ), 即xRy , 因此R ◦ R ⊆ R. 第二步 令{Ms | s ∈ S }是满足条件“∀x, y ∈ Ms , x = y 或xRy 或者yRx”的L的 极大子集. 事实上, 由Zorn引理知这样的极大子集是存在的, 而且显然0属于 每一个Ms , 因为0 ∈ ρ(x) (∀x ∈ L). 第三步 对于任意的s ∈ S 和任意的x, y ∈ Ms 使得xRy , 存在z ∈ Ms 使得 xRzRy . 事实上, 设s ∈ S, x, y ∈ Ms , 有xRy . 由R ◦ R = R, 存在z ∈ L使得xRzRy . 设u ∈ Ms , u = x, y , 则uRx或者xRu, 且uRy 或者yRu. 如果uRx, 则uRxRz , 从而uRz ; 如果xRu, 则yRu (否则有uRy , 而这可推出xRuRy , 此时结论已得 证), 从而zRyRu, zRu. 因此, 对于每一个u ∈ Ms , u = x, y , 有uRz 或者zRu. 由Ms 的极大性, z ∈ Ms . 第四步 对每一个s ∈ S , 定义映射fs : L −→ 2Ms 为
f(
s∈S
As ) =
s∈S
As =
s∈S
f (As ); xsϕ(s) , 从而 f (As ).
s∈S
另外, x ∈
f(
s∈S
s∈S
As 当且仅当存在ϕ ∈ Πs∈S Ts 使得x = xsϕ(s) =
ϕ∈Πs∈S Ts s∈S s∈S t∈TsBiblioteka s∈SAs ) =
xst =
s∈S
As =
因此f : S(L) −→ L为满的完备格同态. 定义2 设L是一个完备格, a ∈ L, 定义
fs (a) = {x ∈ Ms | 存在y ∈ Ms 使得xRyRa}.
4
令Cs = fs (L), 则Cs 在集合的包含序下是一个完备链, 且fs : L −→ Cs 是 完备格同态. 事实上, (1) 设a, b ∈ L且fs (a) ⊆ fs (b), 则存在x ∈ fs (a) − fs (b), 于是存在y ∈ Ms 使得xRyRa, 但是对于每一个u ∈ Ms , xRuRb都不成立. 设z ∈ fs (b), 则存 在u ∈ Ms 使得zRuRb. 对x, z ∈ Ms 进行分类讨论: 如果xRz , 则xRzRuRb, 从 而xRuRb, 这与假设矛盾; 如果x = z , 则x ∈ fs (b), 这又是一个矛盾; 所以只 有zRx, 从而zRxRyRa, zRyRa, 进而z ∈ fs (a). 因此fs (b) ⊆ fs (a). 故, Cs 是一 个链(由下面的(2,3)知, Cs 是完备的). (2) fs ( T ) = t∈T fs (t). 事实上, 设x ∈ fs ( T ), 则存在y ∈ Ms 使 得xRyR T , 即x ∈ ρ(y ), y ∈ ρ( T ). 由定理4, ρ( T ) = t∈T ρ(t), 从而存 在t0 ∈ T 使得y ∈ ρ(t0 ), 因此xRyRt0 , x ∈ fs (t0 ) ⊆ t∈T fs (t). 以上各步可逆, 因此fs ( T ) = t∈T fs (t). (3) fs ( T ) = t∈T fs (t). 显然左边包含于右边. 下设x ∈ t∈T fs (t). 对于 t∈T fs (t) ∈ Cs , 存在b ∈ L使得fs (b) = t∈T fs (t), 从而存在y ∈ Ms 使 得xRyRb. 由于x, y ∈ Ms , 运用第三步两次得, 存在u, v ∈ Ms 使得xRuRvRyRb. 这可推出v ∈ fs (b) = t∈T fs (t) ⊆ t∈T fs (t). 从而对于任意的t ∈ T 有v ∈ fs (t), 进而存在wt ∈ Ms 使得vRwt Rt, 即v ∈ ρ(wt ), wt ∈ ρ(t). 结合定理4(2)我 们有v ≤ t(∀t ∈ T ), 从而v ≤ T . 故ρ(v ) ⊆ ρ( T ). 又由于uRv , 我们 有u ∈ ρ(v ) ⊆ ρ( T ), 则xRuR T . 由u ∈ Ms 知, x ∈ fs ( T ). 第五步 f : L −→ s∈S Cs , f (a) = (fs (a))s∈S 就是所求的完备格序嵌入 (注意虽然每一个fs 都是满射, 但是f 一般不是满射), 这里我们只需证明f 是单 射. (1) 对于任意的a ∈ L, ρ(a) = s∈S fs (a). 设x ∈ ρ(a), 则xRa, 存在s0 ∈ S 使得{x, a} ∈ Ms0 . 由于R ◦ R = R, 存在y ∈ Ms0 使得xRyRa. 这样有x ∈ fs0 (a) ⊆ s∈S fs (a). 以上各步可逆. 因此, ρ(a) = s∈S fs (a). (2) 设f (a) = f (b), 则对于每一个s ∈ S , fs (a) = fs (b), 从而ρ(a) = ρ(a) = ρ(b) = b. s∈S fs (a) = s∈S fs (b) = ρ(b), 由定理4, a =
ρ(a) = {I ⊆ L| I ≥ a, I 是下集}.
注意很多情况下, ρ(a)都不等于↓a. 定理3 设L是一个完备格, a ∈ L, 则ρ(a)恰是集合{ s∈S xsϕ(s) | ϕ ∈ s∈S Ts }生 成的下集, 其中As = {xst | t ∈ Ts }是所有上确界大于或等于a的L的子集. 证明 设x ∈ ρ(a), 对于每一个s ∈ S , 设Is 是As 生成的下集, 则 Is ≥ a, 从而x ∈ s∈S Is . 于是有ϕ ∈ s∈S Ts 使得x ≤ s∈S xsϕ(s) . 因此x属于集 合{ s∈S xsϕ(s) | ϕ ∈ s∈S Ts }生成的下集. 反过来, 设x属于集合{ s∈S xsϕ(s) | ϕ ∈ s∈S Ts }生成的下集, I 是一个下集且满足 I ≥ a, 则I 是某一个As , 由I 是下 集知, x ∈ I . 由I 的任意性, x ∈ ρ(a). 定理4 设L是一个完备格, 则 (1) ρ : L −→ S(L)保任意并. (2) L是完全分配格当且仅当 ρ(a) = a对任意的a成立. (3) 若L是完全分配格, 则ρ(a) = x∈ρ(a) ρ(x). 证明 (1) 由定义知, ρ保序. 设A ⊆ L, 只需证ρ( A) ⊆ a∈A ρ(a). 设x ∈ a∈A ρ(a)但x ∈ ρ( A), 则x不属于每一个ρ(a). 对于a ∈ A, 由ρ(a)的定义, 存 在下集Ia 满足 Is ≥ a使得x ∈ Ia . 令B = a∈A Ia , 则B 是下集且