2007年10月17日 星期三

偏序集(Partially ordered sets)

現時,香港政府的架構以「三司十二局」為骨幹,每個決策局均設一名局長和一名常任秘書長,之下再設副秘書長和助理秘書長多名,再之下還設有更多職級。基本上,這些「高級」的職位有著緊密的從屬關係:局長是常任秘書長的直屬上司、常任秘書長是副秘書長的直屬上司、副秘書長是助理秘書長的直屬上司。這就好像是數學上的全序集(totally ordered sets)-- 集合裏任何兩個元素都可以比較大小。

今天,政府公佈擴闊政治委任制的建議,在局長下增設副局長和政治助理,兩者與常任秘書長之間沒有從屬關係(詳見 http://www.news.gov.hk/tc/category/administration/071017/html/071017tc01006.htm)。這就「破壞」了之前提及的全序集,因為常任秘書長和副局長兩者的職級不能比較高低。數學上,這是一個偏序集(partially ordered set)-- 集合中有些元素可以比較大小,但亦有可能有些不能比較(incomparable -- 注意讀音)的元素。

偏序集的「大小關係」(通常以「≥」表示)需滿足以下三個條件:
(1) 對偏序集中的任意元素 x,皆有 x ≥ x。
(2) 若 x ≥ y 且 y ≥ x,則 x = y。
(3) 若 x ≥ y 且 y ≥ z,則 x ≥ z。
全序集則需同時滿足「對偏序集中的任意元素 x 和 y,皆有 x ≥ y 或 y ≥ x」,即「任何兩個元素都可以比較大小」。全序集的例子很多,如實數集、所有英文字的集合(以字母順序比較大小)等。

有沒有些不是全序集的偏序集呢?也有很多,例如,若 S 是有兩個或以上的元素的集合,P(S) 為 S 的冪集(power set),即 S 的所有子集(subsets)的集合,並對 P(S) 中的元素 X、Y 定義 Y ≥ X 當且僅當 X 是 Y 的子集,那麼 P(S) 便是偏序集,然而它是不全序集。(例如:若 S = {1,2},那麼 P(S) = {Φ, {1}. {2}. {1,2}},其中 {1, 2} ≥ Φ、{1,2} ≥ {1}、{1,2} ≥ {2}、{1} ≥ Φ、{2} ≥ Φ,但 {1} 和 {2} 不能比較大小。)

值得注意的一點是全序集和偏序集包括本身和比較大小的關係「≥」。改變「≥」的定義後所得的會被視為另一個全序集或偏序集。在以上例子中,若對 P(S) 中的元素 X、Y 改為定義 Y ≥ X 當且僅當 Y 的元素之和不小於 X 的元素之和,則 P(S) 會變成一個全序集呢!

1 則留言:

wu yan 提到...

375nice..

thx and god bless..

^___^