数学对象可以用不同的结构来表示

1、5.1 格数学对象可以用不同的结构来表示。格就是一种可以用代数或关系来表示的数学对象。我们先用代数结构来定义格。5.1.1 定义 格 L是非空集合，和是L上两个二元运算。称为一个格（按习惯将(x, y)记为xy，将(x, y)记为xy，称为交，称为并），如果L满足以下条件：(1) 幂等律 任给xL，都有xx = x，xx = x。(2) 结合律 任给x, y, zB，都有(xy)z = x(yz)，(xy)z = x(yz)。(3) 交换律 任给x, yB，都有xy = yx，xy = yx。(4) 吸收律 任给x, yB，都有(xy)y = y，(xy)y = y。当, 是已知或不必指出时，

2、简称L是一个格。由结合律，多个元素作交或并时可以省略括号。吸收律刻画了两种运算和的关系，由吸收律还能得到以下重要关系5.1.2 定理 L是格，任给x, yL，都有xy = x当且仅当xy = y。证 如果xy = x，则y = (xy)y = (xy)(yy) = xy。如果xy = y，则x = (xy)x = (xx)(yx) = xy。以下是格的一些例子。5.1.3 例 幂集P(s)的对于和封闭的子集是格，称为集格。5.1.4 例 在单元集a上定义和如下：aa = a，aa = a，则是格，称为单元格。单元格上的和是唯一的。5.1.5 例 正逻辑系统Pm的公理是：(1) |- a(ba)

3、。(2) |- (a(bg)(ab)(ag)。(3) |- aba。(4) |- abb。(5) |- (ab)(ag)(abg)。(6) |- aab。(7) |- bab。(8) |-(ag)(bg)(abg)。推演规则是分离规则：从a和ab得到b。的定义是：abab =df (ab)(ba)。令Form是Pm的所有公式的集合，因为在Pm中有：(1) |- aa；(2) 如果|- ab，则|- ba；(3) 如果|- ab且|- bg，则|- ag。所以可以在Form上定义等价关系如下：ab =df |-ab。公式a在等价关系下的等价类记为a，取L是Form在等价关系下的商集Form /

4、。因为在Pm中有：如果 |-aa且 |-bb，则|-abab，|-abab，所以可以在L上定义和如下：ab = ab，ab = ab是格，相应的Pm逻辑等值式如下：(1) |-aaa，|-aaa。(2) |-(ab)ga(bg)，|-(ab)ga(bg)。(3) |-abba，|-abba。(4) |-(ab)bb，|-(ab)bb。更一般地，对于Pm的任何扩充系统，都可以用同样的方法定义这样的格。5.1.6 定理 L是格，定义L上二元关系如下：xy =df xy = x，则是L上偏序关系。证 (1) 自返性。任给xL，都有xx = x，因此xx。(2) 反对称性。任给x, yL，如果xy且y

5、x，则xy = x且yx = y，因此x = xy = yx = y。(3) 传递性。任给x, y, zL，如果xy且yz，则xy = x且yz = y，所以xz = (xy)z = x(yz) = xy = x，因此xz。由定理，xy 当且仅当 xy = y。5.1.7 定理 L是格，是如上定义的偏序关系。(1) 任给x, yL，都有xyx且xyy。(2) 任给x, y, zL，如果zx且zy，则zxy。(3) 任给x, yL，都有xxy且yxy。(4) 任给x, y, zL，如果xz且yz，则xyz。证 (1) 因为(xy)x = (yx)x = y(xx) = xy，(xy)y = (x

6、y)y = x(yy) = xy，。(2) 如果zx且zy，则zx = z且zy = z，所以z(xy) = (zx)(zy) = zz = z，因此zxy。(3)(4) 类似于(1)(2)，使用xy 当且仅当 xy = y。由定理可知，在这个偏序关系下，xy就是x, y的上确界，xy就是x, y的下确界。设L是偏序结构，如果L的任何两个元素都有上确界和下确界，在L上定义和如下：xy = x, y的下确界，xy = x, y的上确界，则是格。因此，也可以用任何两个元素都有上确界和下确界的偏序结构来定义格。详细定义如下：是关系结构，称为一个格，如果满足以下条件：(1) (xL)(xx)。(2)

7、(x, yL)(xyyxx = y)。(3) (x, y, zL)(xyyzxz)。(4) (x, yL)($aL)(xaya(zL)(xzyzaz)。(5) (x, yL)($bL)(bxby(zL)(zxzyzb)。(1)(2)(3)是说是偏序结构，(4)是说任何两个元素都有上确界，(5)是说任何两个元素都有下确界。可以证明：(4)中a和(5)中b都是唯一的，所以可以在这样定义的格中引进两个二元运算：LLL (x, y) = a (由(4)确定的唯一的a)，：LLL (x, y) = a (由(5)确定的唯一的b)，则就是用代数定义的格。以下讨论中仍用格的代数定义，但同时使用偏序关系。5.

8、1.8 例 全序集的任何两个元素都有上确界和下确界，所以任何非空全序集都可以形成格。5.1.9 例 G是群，L = H | H是G的子群， L在集合的包含关系下是一个偏序集，两个子群H和K的下确界是HK，上确界是HK生成的子群，所以如果在L上定义和如下：HK = HK，HK = HK生成的子群，则是格。5.1.10 定义 子格 是一个格，S L，如果是一个格，则称S是L的子格。S L，S是L的子格的充要条件是：任给x, yS，都有xyS且xyS。5.1.11 例 L是L的子格，不等于L的子格称为真子格。5.1.12 例 L是格，a, bL，ab，令a, b = x | axb，因为任给x, y

9、a, b，都有axb且ayb，由定理得axyb且axyb，所以xy, xya, b。因此a, b是L的子格，称为由a和b确定的闭子格。a, a就是单元格a。类似地可定义由a确定的上开子格a)= x | ax和由b确定的下开子格。(b = x | xb，5.1.13 定理 L是格，G是L的子格的集合，即任给SG，S都是L的子格，则：(1) G是L的子格。(2) 如果G单调的，则G是L的子格。由定理(1)，可定义由X所生成的子格G，其中G = S | X S且S是L的子格。格的同态和同构就是一般代数结构的同态和同构，格的同态基本定理就是一般代数结构的同态基本定理，简单重述如下：5.1.14 定理

10、同态基本定理 、是两个格，s是到的满同态。取等价关系如下：ab 当且仅当 s(a) = s(b)，则是正规的等价关系，因此可以构造商格（和是商集L1/上的二元运算），使得。成立分配律的格称为分配格。分配律是指：任给x, y, zL，都有x(yz) = (xy)(xz)，x(yz) = (xy)(xz)。5.1.15 例 分配格的子格是分配格5.1.16 例 全序集形成的格是分配格。5.1.17 定理 L是分配格，x, yL。如果存在aL，使得ax = ay，ax = ay，则x = y。证 x = x(ax) = x(ay) = (xa)(xy)= (ya)(xy) = y(ax) = y(a

11、y) = y。集格都是分配格。在同构的意义上，分配格都是集格。8 定义 滤 L是格，F是L的非空子集。如果F满足：(1) 任给x, yL，如果xF且yF，则xyF；(2) 任给x, yL，如果xF且xy，则yF。则称F是L的滤。5.1.19 定理 L是格，G是L的滤的集合，即任给FG，F都是L的滤，则：(1) G是L的滤。(2) 如果G单调的，则G是L的滤。如果X，则由定理的(1)，可以定义由X所生成的滤G，其中G = F | F且F是L的滤，可以证明由X所生成的滤是y | 存在x1, xnX，使得x1xny。aL，由a生成的滤就是上开子格a)。F是L的滤，aL，由Fa生成的滤是x | 存在u

12、I，使得uax。5.1.20 定义 素滤 L是格，P是L的真滤。如果任给x, yL，都能从xyF推出xF或yF，则称F是素滤。素滤有以下基本性质。5.1.21 定理 L是格，P是L的素滤，则：(1) 任给x, yL，都有xyP当且仅当xP且yP。(2) 任给x, yL，都有xyP当且仅当xP或yP。证 (1) 如果xP且yP，则xyP。如果xyP，则由xyx得xP，由xyy得yP。(2) 如果xyP，则xP或yP。如果xP或yP，则由xxy和yxy得xyP。5.1.22 定理 L是分配格，F是滤，bF，xyF。令F1是由Fx生成的滤，F2是由Fy生成的滤，则bF1或bF2。证 反证法。设bF1

13、且bF2，则存在uF，vF，使得uxb且vyb，所以uvxb且uvyb，uvF所以(uvx)(uvy)b，由分配律得(uv)(xy)b，因此bF，矛盾。5.1.23 定理 素滤存在定理 L是一个分配格，任给a, bL，如果ba，则存在素滤P，使得aP且bP。证 令G = F | F是滤，aF且bF，由a生成的滤a)G，所以G非空，任给S G是单调的，则F = S是滤，并有aF且bF，所以FG。由Zorn引理，G有极大元P，证明P是素滤。任给xyP，令F1是由Px生成的滤，F2是由Py生成的滤，则由定理5.1.22得bF1或bF2，所以F1G或F2G，由P是极大元得F1 = P或F2 = P，因

14、此xP或yP。5.1.24 定理 L是格，令s = P | P是L的素滤，任给xL，令x* = P | Ps且xP，则：(1) 任给x, yL，都有(xy)* = x*y*。(2) 任给x, yL，都有(xy)* = x*y*。证 首先由x*的定义得Px*当且仅当xP。(1) P(xy)* 当且仅当 xyP当且仅当 (xP且yP)当且仅当 (Px*且Py*)当且仅当Px*y*。所以(xy)* = x*y*。(2) P(xy)* 当且仅当 xyP当且仅当 (xP或yP)当且仅当 (Px*或Py*)当且仅当Px*y*。所以(xy)* = x*y*。 定理 分配格表示定理 任何分配格都同构于集格。证 设分配格为，令s = P | P是L的素滤，取L到P(s)的映射如下：l：L P(s) s(x) = x*，先证明l是单射，任给x, yL，如果x y，则xyxy，由定理5.1.23得存在素滤P，使得xyP且xyP，所以Px且Py，或Py且Px，因此x* y*，即l(x) l(y)。取集格，则l是L到lL的双射，再证明l是L到lL的同构。l(xy) = (xy)* = x*y* = l(x)l(y)，l(xy) = (xy)* = x*y*