离散数学偏序关系：自反、反自反、反对称和传递性

偏序关系：设对集合A上的二元关系R，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系.偏序关系R通常记作≤.当xRy时，可记作x≤y.

偏序集：集合A与A上的偏序关系R一起称为一个偏序结构，或称偏序集，记作＜A，R＞.

小于与可比：设R为A上的偏序关系，定义

（1）∀x、y∈A，x＜y⇔x≤y∧x≠y，其中x＜y读作x“小于”y.

（2）∀x、y∈A，x与y可比⇔x≤y∨y≤x.

全序关系：设R为A上的偏序关系，如对任意的x、y∈A，x与y都是可比的，则称R为A上的全序关系.

盖住：对偏序集＜A，≤＞，如果x、y∈A，x＜y，且不存在元素z∈A使得x＜z＜y，则称y盖住x.

哈斯图：偏序集＜A，≤＞的关系图.

偏序集中的特殊元素：设＜A，≤＞为偏序集，且B⊆A，y∈B，

（1）若∀x（x∈B→y≤x），则称y为B的最小元.

（2）若∀x（x∈B→x≤y），则称y为B的最大元.

（3）若∀x（x∈B∧x≤y→x=y），则称y为B的极小元.

（4）若∀x（x∈B∧y≤x→x=y），则称y为B的极大元.

定理4.13　设＜A，≤＞为偏序集，且B⊆A，若B有最大元，则必是唯一的.

偏序集中的上（下）界、上（下）确界：设＜A，≤＞为偏序集，且B⊆A，y∈A，

（1）若∀x（x∈B→x≤y），则称y为B的上界.

（2）若∀x（x∈B→y≤x），则称y为B的下界.

（3）若集合C=｛y|y为B的上界｝，则C的最小元称为B的上确界.

（4）若集合D=｛y|y为B的下界｝，则D的最大元称为B的下确界.

良序集：任一偏序集，假设它的每一个非空子集存在最小元素，这种偏序集称为良序的.

定理4.14　每个良序集一定是全序集.

定理4.15　每个有限的全序集一定是良序集.

重点和难点

1.关系的表示，关系性质的判断，特别是传递性的判断能力.

2.复合关系的计算.

3.等价关系的证明及与划分的关系.

4.偏序关系的证明，偏序集中的特殊元素.

例题解析

例4.1　设A=｛1，2，3｝，R1=｛＜1，1＞，＜2，2＞｝、R2=｛＜1，1＞，＜1，2＞，＜2，1＞｝、R3=｛＜1，2＞，＜1，3＞｝和R4=｛＜1，2＞，＜2，1＞，＜1，3＞｝都是A上的关系，说明R1、R2、R3和R4具有什么性质.

【分析】可以根据关系的性质的定义进行判断；也可以根据关系矩阵或关系图判断关系的性质.如关系是自反关系，则关系矩阵的主对角线都是1且关系图的每个结点都有自回路；关系是反自反关系，则关系矩阵的主对角线都是0且关系图的每个结点都没有自回路；关系是对称关系，则关系矩阵是对称矩阵且关系图的每对结点之间的有向边都成对出现；关系是反对称的，则关系矩阵和它的转置矩阵的对应位置的非主对角线元素不能都是1且关系图的每对结点之间的有向边不能成对出现；对传递关系，需要借助R和R2的比较.

解：(www.xing528.com)

R1是对称的、反对称的和传递的.

R2只是对称的.

R3是反自反的，反对称的和传递的.

R4是反自反的.

例4.2　设R是集合A上的等价关系，则R2也是A上的等价关系.

【分析】对于关系各种不同性质的证明，一般地，总是这样开始证明的：

自反性：∀x∈X，∵…，∴＜x，x＞∈R，即R是自反的.

反自反性：∀x∈X，∵…，∴＜x，x＞∉R，即R是反自反的.

对称性：∀x，y∈X，若＜x，y＞∈R…，∴＜y，x＞∈R，即R是对称的.

反对称性：∀x，y∈X，若＜x，y＞∈R且＜y，x＞∈R…，∴y=x，即R是反对称的.

传递性：∀x，y，z∈X，若＜x，y＞∈R且＜y，z＞∈R…，∴＜x，z＞∈R，即R是传递的.

证明：

因为R是集合A上的等价关系，所以R是自反的、对称的和传递的.

∀x∈X，∵R是自反的，∴＜x，x＞∈R且＜x，x＞∈R，故＜x，x＞∈R2，即R2是自反的.

∀x，y∈X，若＜x，y＞∈R2，故存在z∈A，＜x，z＞∈R且＜z，y＞∈R.因为R是对称的，所以＜y，z＞∈R且＜z，x＞∈R，∴＜y，x＞∈R2，即R2是对称的.

∀x，y，z∈X，若＜x，y＞∈R2且＜y，z＞∈R2，故存在u，v∈A，＜x，u＞∈R，＜u，y＞∈R，＜y，v＞∈R且＜v，z＞∈R.由于R是传递的，∴＜x，y＞∈R且＜y，z＞∈R，从而＜x，z＞∈R2，即R2是传递的.

综上所述，R2是A上的等价关系.

例4.3　设集合A=｛2，3，6，8，12，16，24，32，48｝，A上的偏序关系是整除.求集合｛6，8，12｝的极大元、极小元、最大元、最小元、上界，下界，上确界和下确界（如果有的话）.

【分析】求偏序集中一个集合B的特殊元素，要注意B的极大（小元）、最大（小元）一定在B中，极大（小元）一定有且不一定唯一，但最大（小元）可能不存在，若有的话，则一定唯一.B的上（下）界不一定在B中，上（下）确界也不一定在B中，且它们不一定存在.上（下）界不一定存在，即使存在上（下）界也不一定唯一，但上（下）确界有的话，则一定唯一.

解：

集合｛6，8，12｝的极大元是8和12；极小元是6和8.

最大元和最小元无.

上界是24和48；下界是2.

上确界是24；下确界是2.

例4.4　设集合A=｛a，b，c，d，e｝，R是A上的二元关系，且R=｛＜a，a＞，＜a，b＞，＜a，c＞，＜a，d＞，＜a，e＞，＜b，b＞，＜b，c＞，＜b，e＞，＜c，c＞，＜c，e＞，＜d，d＞，＜d，e＞，＜e，e＞｝，验证＜A，R＞为偏序集，并画出其哈斯图.

【分析】验证偏序关系的自反性、反对称性和传递性，和例4.2中的证明一样.在画偏序的哈斯图时，要注意如果x≤y，x应该画在y的上方，如y盖住x，则x到y画一条边，否则x到y之间不应该有边.各个结点上的自回路应该省略，边的方向也应该省略.

解：

易证R是自反的、反对称的和传递的，因此R是偏序关系.

R的哈斯图如下图所示.