覆盖
设(A,≺ )是一个偏序集, A是一个有限集,|A|=n。 对于任意的x,y∊A,且x≠y, 假设(x, y) ∊≺,即 x ≺ y。 如果对于∀z∊A,
由x ≺ z,且 z ≺ y,一定能够推出x=z或y=z, 那么我们说 y覆盖x。
例
A={1, 2, 3, 4} ≺={(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4)}
⋯⋯⋯
({ e }, ≺)
反链? 链?
全序集
设(A,≺)是一个偏序集, 如果它本身就是一条链, 那么称之为全序集,并称≺ 为全序关系。
例 A={ a, b, c, d, e}
d c
e b
a
d
c e
b a
≺={ (a,a), (b,b), (c,c), (d,d), (e,e), (a,b), (a,c), (a,d), (a,e), (b,c), (b,d), (c,d), (e,d) }
✘✔ ✘ ✔
d
j
k
h
4
c
e
h
i
e
f
g
2
3b
f
g
b
c
d
1
a
bc de
a
a
图7.3(a)
(b)
(c)
(d)
命题 一个有限格,一定有最小元和最大元。
(1) 用数学归纳法证明一定有最小元如下: 设(A,≺)是一个有限格,记|A|=n。 当n=1时,结论显然成立。 归纳假设当n=k时,结论成立。考察n=k+1的情况: 不妨记 A={a1,…,ak, ak+1}=A’∪{ak+1} , 这里A’={a1,…,ak}, |A’|=k。 显然,(A’,≺)也是一个有限格 由归纳假设知道, (A’,≺)有最小元,不妨记之为d。 因为(A,≺)是一个格, 则A中存在d与ak+1的最大下界glb(d,ak+1), 可以说明它即为(A,≺)的最小元。