离散数学:格的基本概念

回顾

偏序关系

$<A,\le >$是偏序集:$\le \text{是}A\text{上}\text{自}\text{反},\text{反}\text{对}\text{称},\text{和}\text{传}\text{递}\text{关}\text{系}(\text{偏}\text{序}).$

$\text{偏}\text{序}\text{集}\text{中}\text{的}\text{元}\text{素}\text{间}\text{的}\text{次}\text{序}\text{可}\text{以}\text{通}\text{过}\text{它}\text{的}Hasse\text{图}\text{反}\text{映}\text{出}\text{来}.$

$\text{偏}\text{序}\text{集}\text{中}\text{的}\text{重}\text{要}\text{元}\text{素}:\text{极}\text{大}(\text{小})\text{元},\text{最}\text{大}(\text{小})\text{元},\text{上}(\text{下})\text{界},\text{上}(\text{下})\text{确}\text{界}.$

定义

$\begin{array}{l}<A,\le >\text{是}\text{偏}\text{序}\text{集},\text{如}\text{果}\text{任}\text{何}a,b\in A,\text{使}\text{得}\{a,b\}\text{都}\text{有}\\ \text{上}\text{确}\text{界}\text{和}\text{下}\text{确}\text{界},\text{则}\text{称}<A,\le >\text{是}\text{格}\end{array}$

:::tip

平凡格

所有的全序都是格,称之为平凡格.

:::

$$\begin{array}{cc}& \text{由格诱导的代数系统}\\ & \text{设}<𝐀,⪯>\text{是}\text{格}\text{，}\text{在}𝐀\text{上}\text{定}\text{义}\text{二}\text{元}\text{运}\text{算}\vee \text{和}\wedge \text{为}:\forall 𝐚,𝐛\in 𝐀\\ & 𝐚\vee 𝐛=\text{LUB}\{𝐚,𝐛\},\{𝐚,𝐛\}\text{的}\text{最}\text{小}\text{上}\text{界}\text{。}𝐋𝐞𝐚𝐬𝐭𝐔𝐩𝐩𝐞𝐫𝐁𝐨𝐮𝐧𝐝\\ & 𝐚\wedge 𝐛=\text{GLB}\{𝐚,𝐛\},\{𝐚,𝐛\}\text{的}\text{最}\text{大}\text{下}\text{界}\text{。}𝐆𝐫𝐞𝐚𝐭𝐞𝐬𝐭𝐋𝐨𝐰𝐞𝐫𝐁𝐨𝐮𝐧𝐝\\ & \text{称}<𝐀,\vee ,\wedge >\text{是}\text{由}\text{格}<𝐀,⪯>\text{诱}\text{导}\text{的}\text{代}\text{数}\text{系}\text{统}\text{。}(\vee -\text{并},\wedge -\text{交})\end{array}$$

$$\begin{array}{cc}& \text{子格}\\ & \text{设}<𝐀,\vee ,\wedge >\text{是}\text{由}\text{格}<𝐀,⪯>\text{诱}\text{导}\text{的}\text{代}\text{数}\text{系}\text{统}\text{。}𝐁\text{是}𝐀\text{的}\text{非}\text{空}\text{子}\text{集}\text{，}\\ & \text{如}\text{果}\wedge \text{和}\vee \text{在}𝐁\text{上}\text{封}\text{闭}\text{，}\text{则}\text{称}<𝐁,⪯>\text{是}<𝐀,⪯>\text{的}\text{子}\text{格}\text{。}\end{array}$$

$$\begin{array}{cc}& \text{格的对偶}\\ & \text{如}\text{果}\text{将}\text{命}\text{题}(𝐏)\text{中}\text{的}⩽\text{换}\text{成}⩾\text{，}\wedge \text{换}\text{成}\vee \text{，}\vee \text{换}\text{成}\wedge \text{，}\text{得}\text{到}\text{命}\text{题}({𝐏}^{\prime })\text{，}\text{称}({𝐏}^{\prime })\text{为}(𝐏)\text{的}\text{对}\text{偶}\text{命}\text{题}\text{。}\\ & \text{对}\text{偶}\text{原}\text{理}\text{：}\text{如}\text{果}(𝐏)\text{对}\text{任}\text{何}\text{格}\text{为}\text{真}\text{，}\text{则}({𝐏}^{\prime })\text{对}\text{任}\text{何}\text{格}\text{也}\text{为}\text{真}\text{。}\end{array}$$

格的同态与同构

$$\begin{array}{cc}& \text{三. 格的同态与同构}\\ & \text{设}<{𝐀}_{\mathrm{𝟏}},{⩽}_{\mathrm{𝟏}}>\text{ 和 }<{𝐀}_{\mathrm{𝟐}},{⩽}_{\mathrm{𝟐}}>\text{ 是两个格，由它们诱导的代数系统分别是 }\\ & <{𝐀}_{\mathrm{𝟏}},{\vee }_{\mathrm{𝟏}},{\wedge }_{\mathrm{𝟏}}>\text{ 和 }<{𝐀}_{\mathrm{𝟐}},{\vee }_{\mathrm{𝟐}},{\wedge }_{\mathrm{𝟐}}>,\text{ 如果存在映射 }𝐟:{𝐀}_{\mathrm{𝟏}}\to {𝐀}_{\mathrm{𝟐}}\text{ 使得对任何 }𝐚,𝐛\in {𝐀}_{\mathrm{𝟏}},\\ & 𝐟(𝐚{\vee }_{\mathrm{𝟏}}𝐛)=𝐟(𝐚){\vee }_{\mathrm{𝟐}}𝐟(𝐛)\\ & 𝐟(𝐚{\wedge }_{\mathrm{𝟏}}𝐛)=𝐟(𝐚){\wedge }_{\mathrm{𝟐}}𝐟(𝐛)\\ & \text{则称}𝐟\text{ 是 }<{𝐀}_{\mathrm{𝟏}},{\vee }_{\mathrm{𝟏}},{\wedge }_{\mathrm{𝟏}}>\text{ 到 }<{𝐀}_{\mathrm{𝟐}},{\vee }_{\mathrm{𝟐}},{\wedge }_{\mathrm{𝟐}}>\text{ 的同态映射。}\\ & \text{也称 }<𝐟({𝐀}_{\mathrm{𝟏}}),{⩽}_{\mathrm{𝟐}}>\text{ 是 }<{𝐀}_{\mathrm{𝟏}},{⩽}_{\mathrm{𝟏}}>\text{ 的同态像。}\\ & \text{如果 }𝐟\text{ 是双射，就称 }𝐟\text{ 是 }<{𝐀}_{\mathrm{𝟏}},{\vee }_{\mathrm{𝟏}},{\wedge }_{\mathrm{𝟏}}>\text{ 到 }<{𝐀}_{\mathrm{𝟐}},{\vee }_{\mathrm{𝟐}},{\wedge }_{\mathrm{𝟐}}>\text{ 的格同构，}\\ & \text{也称格 }<{𝐀}_{\mathrm{𝟏}},{⩽}_{\mathrm{𝟏}}>\text{ 和 }<{𝐀}_{\mathrm{𝟐}},{⩽}_{\mathrm{𝟐}}>\text{ 同构。}\end{array}$$