劉維娜

中央民族大學(xué)，北京 100081

0 引言

格是隨著經(jīng)典邏輯的代數(shù)化與泛代數(shù)的發(fā)展而引進的一個新的代數(shù)系統(tǒng)。近年來，偏序集與格的理論在組合數(shù)學(xué)、Fuzzy數(shù)學(xué)、理論計算機科學(xué)，甚至社會科學(xué)中都得到了廣泛的應(yīng)用，極大地推動了該學(xué)科自身的發(fā)展，也使之成為數(shù)學(xué)和理論計算機科學(xué)中的重要研究對象[4]。

作為格的特殊實例，完備格出現(xiàn)于數(shù)學(xué)和計算機科學(xué)的很多應(yīng)用中，在次序論和泛代數(shù)中也都有所研究。

1 預(yù)備知識

定義2.1 設(shè)P是一集合，≤是P上的二元關(guān)系，如果對?x，y，z∈P，有：

1）x≤x（自反性）

2）x≤y，y≤x ?x≤y（反對稱性）

3）x≤y，y≤z?x≤z（傳遞性）

則稱≤為P上的一個偏序（關(guān)系），一個集合P及其上的偏序≤形成的有序二元組（P，≤）稱為偏序集。

在不至混淆的情況下，對（P；≤）可簡記為P。

定義2.2 設(shè)（P，≤）是偏序集，X ?P，a ∈P。

1）若?x ∈X，x ≤（aa ≤x），則稱a為A的一個上界（下界）；

2）若?x ∈P，x ≤a（a ≤x），則a稱為P的最大元（最小元）；

3）若 ?x ∈P，a ≤x ?x = a（x ≤a ?x=a），則稱 a是 P中的一個極大元（極小元）；

4）若a是A的全體上界（下界）的集合中的最小元（最大元），則稱a為A的上確界（下確界）；A的上確界記為supA，A的下確界記為infA。

定義2.3 設(shè)（P，≤）是偏序集，S是P的非空子集。

1）若S中任意兩個元在S中都有上界，則稱S是定向的，或稱為P的定向子集；

2）若S中任意兩個元在S中都有下界，則稱S是余定向的，或稱為P的余定向子集.

定義2.4 設(shè)（P，≤）是偏序集，若P任意有上界子集均有上確界，那么稱偏序集（P，≤）是有界完備的。

顯然，有界完備偏序集是有最小元0的，即是空集的最小上界。

定義2.5 設(shè)（P，≤）是偏序集，若P關(guān)于有限并封閉，即P的任意有限子集均有上確界，則稱偏序集（P，≤）為上半格；若P關(guān)于有限交封閉，即P的任意有限子集均有下確界，則稱偏序集（P，≤）為下半格。

定義2.6 設(shè)（P，≤）是偏序集，若P關(guān)于有限并與有限交均封閉，則稱偏序集（P，≤）為格。

下面介紹一下對偶原理。給定一個偏序集（P，≤），我們可以通過定義x≤y（在P中）?y ≤x（在P?中）生成一個新的偏序集（P?，≤）。給定一個關(guān)于偏序集（P，≤）的命題Φ，我們可以通過改變偏序的方向，得到對偶命題Φ?。

定理2.7（ 對偶原理）給定一個命題Φ，如果關(guān)于所有偏序集均成立，那么其對偶命題Φ?亦成立。

2 完備格

定義3.1 設(shè)（P，≤）是偏序集，若P關(guān)于任意并封閉，即P的任意子集均有上確界，則稱偏序集（P，≤）為完備∨半格；若P關(guān)于任意交封閉，即P的任意子集均有下確界，則稱偏序集（P，≤）為完備∨半格。

定義3.2 設(shè)（P，≤）是偏序集，若P關(guān)于任意并與任意交均封閉，則稱（P，≤）是完備格。

例3.3

1）有限格是完備格。

2）由集合X的冪集及集合的包含關(guān)系構(gòu)成的偏序集是一個完備格。

引理3.4 設(shè)（P，≤）是偏序集，則（P，≤）是完備∨半格當(dāng)且僅當(dāng)（P，≤）是完備∨半格.

證明：設(shè)偏序集（P，≤）是完備∧半格，對于S ?P，記T為S的全體上界之集，并記a=∧T。因為?s ∈S，s是T的下界，于是s≤a，從而a是S的上界。但是a =∧T，即a是S的最小上界，所以a =∨S.這就證明了偏序集（P，≤）是完備∨半格。

由對偶原理易知，若偏序集（P，≤）是完備∨半格，則它必是完備∧半格。

推論3.5 完備∨半格或完備∧半格必是完備格。

證明：可由引理2.2的直接推出。

思考3.6 對一個偏序集（ P，≤），如果其任意非空子集均有下確界，那么只需添加一個單位元1（1?P, 且對?x ∈P，有 x ≤1），得到P'=P∪{1}，那么（P'，≤）即是一個完備格。

定理3.7 設(shè)（P，≤）是有界完備偏序集，且有最大元1，則P是一個完備格。

證明一：偏序集P是有界完備的，則P有最小元，又P有最大元，故P的任意子集均有上下界。?≠A ?P，那么對A的下界B，最小元0∈B，A中任一元素均是B的上界，故B有最小上界，亦是A的最大下界-下確界，即P的任意非空子集有下確界，由思考2.6可知，最大元1存在，可推出P是完備格。

證明二：對?A ?P，最大元1是A一個上界，又P是有界完備的，故A有上確界，即P是完備∨半格，由推論2.5知P是完備格。

顯然，如果偏序集（P，≤）是一個完備格，則必是有界完備的，且有最大元和最小元，所以事實上這是一個等價定理。

定理3.8 設(shè)（P，≤）是偏序集，則（P，≤）是完備格當(dāng)且僅當(dāng)（P，≤）是有最大元1的下半格，且P的任意余定向子集均有下確界。

證明：對P的任意子集X，若X是空集，則inf X=inf?=1。若X是非空集合，由P是下半格可知，X的任意有限子集A有下確界。令D是所有這些下確界的集合，則X的下界是A的下界（P是下半格，則P是一個余定向子集，從而存在下確界，于是P的任意子集均有下界），故也是D的下界。又因為單點集{*}的下確界是*，所以X ?D，故D的下界亦是X的下界.于是X與D有相同的下界集。下面證明D的下確界存在.?a, b ∈D, a = inf A,b = inf B , A,B是X的有限子集。令c = inf（A∪B），則 c ∈D,且c ≤a, c ≤b.故D是余定向的，從而D有下確界，于是X的下確界亦存在，inf X = inf D.于是我們得到P的任意子集均存在下確界，是完備∧半格，由推論2.5知P是完備格。

反之，顯然成立。

[1]G.Gierz，K.H.Hofmann，K.Keimel，J.D.Lawson，M.Mislove，D.S.Scott，Continuous Lattices and Domains，Cambridge，2002.

[2]B.A.Davey，H.A.Priestly，Introduction to Lattices and Order(second editon)，Cambridge，2002.

[3]G.Brikhoff，Lattice Theory(3rd ed)，American Mathematical Society Colloquium Publications，Vol.25，Providence，R.I，1979.

[4]鄭崇友，樊磊，崔宏斌，F(xiàn)RAME與連續(xù)格[M].2版.首都師范大學(xué)出版社，2000.