§1.2　经典关系

1.2.1　集合的直积

在日常生活中，有许多事物是成对出现的，且具有一定的顺序。例如，上、下；左、右；平面上点的坐标等。任意两个元素 x 与 y 配成一个有序的对（ x ， y ），称为 x 与 y 的序对或称序偶，有序是指当 x ≠ y 时，（ x ， y ）≠（ y ， x ）；（ x ， y ）=（ x '， y '） x =x'， y = y '。

定义1.6 设 X ， Y 是两个非空集合，由 X 的元素与 Y 的元素搭配成的全体序偶组成一个集合，称为 X 与 Y 的直积（或笛卡尔积），记为 X × Y 。即 X × Y ={（ x ， y ）| x ∈ X ， y ∈ Y }。

例1.1 设 X ={1，2}， Y ={0，2}，则

X × Y ={（1，0），（1，2），（2，0），（2，2）}；

Y × X ={（0，1），（0，2），（2，1），（2，2）}。

一般地， X × Y ≠ Y × X 。即，如果把集合的直积作为集合之间的运算，那么该运算不满足交换律。

两个集合的直积可推广为多个集合的直积。

1.2.2　经典二元关系

关系是一个基本概念。客观世界中的事物之间普遍存在着某种联系，这种联系就称为关系，其中最简单的就是二元关系。在日常生活中有“父子关系”，“朋友关系”、“师生关系”等，在数学上有“大于关系”、“等于关系”等。而序偶又可以表达两个对象之间的关系。于是，引进下面的定义。

定义1.7 设 X ， Y 为非空集合，则 X × Y 的子集 R 称为从 X 到 Y 的二元关系。特别地，当 X = Y 时，称之为 X 上的二元关系，以后把二元关系简称为关系。

若（ x ， y ）∈ R ，则称 x 与 y 有关系，记为 xRy ；若（ x ， y ）∉ R ，则称 x 与 y 没有关系，记为 。 R 的特征函数：

为方便，特征函数 χ _R （ x ， y ）常简记为 R （ x ， y ）。

例1.2 设 X ={1，4，7，8}， Y ={2，3，6}，定义关系 R x < y ，称 R 为“小于”关系。于是 R ={（1，2），（1，3），（1，6），（4，6）}。

例1.3 设 X 为实数集，则子集 R ={（ x ， y ）|（ x ， y ）∈ X × X ， y = x }是实数集上元素间的“相等”关系。

例1.4 X ={1，2，3，4，5，6}， X 上的整除关系定义为：

R ={（ x ， y ）| x | y ， x ， y ∈ X }={（1，1），…，（1，6），（2，4），（2，6），（3，6）}。

1.2.3　关系的运算

定义1.8 设 R ， R ₁ ， R ₂ ∈ P （ X × Y ），定义：

并： R ₁ ∪ R ₂ ={（ x ， y ）|（ x ， y ）∈ R ₁ 或（ x ， y ）∈ R ₂ }；

交： R ₁ ∩ R ₂ ={（ x ， y ）|（ x ， y ）∈ R ₁ 且（ x ， y ）∈ R ₂ }；

余： R ^c ={（ x ， y ）|（ x ， y ）∉ R }；

逆： R ^-1 ={（ y ， x ）|（ x ， y ）∈ R }∈ P （ Y × X ）；

合成：设 R ₁ ∈ P （ X × Y ）， R ₂ ∈ P （ Y × Z ），则 R ₁ 与 R ₂ 的合成 R ₁ ° R ₂ ∈ P （ X × Z ）定义为： R ₁ ° R ₂ ={（ x ， z ）|∃ y ∈ Y ，（ x ， y ）∈ R ₁ 且（ y ， z ）∈ R ₂ }。

例1.5 设 X ={1，2，3}， Y ={ a ， b ， c ， d }， Z ={甲，乙}，若

R ₁ ={（1， a ），（1， c ），（2， b ），（3， a ），（3， d ）}∈ P （ X × Y ），

R ₂ ={（ a ，甲），（ c ，甲），（ b ，乙），（ d ，乙）}∈ P （ Y × Z ），

则 ={（1，甲），（3，甲），（2，乙），（3，乙）}∈ P （ X × Z ）。

1.2.4　特征关系

关系的特征函数称为特征关系。

定义1.9 设 R ∈ P （ X × Y ），则 R 的特征函数

称为 R 的特征关系。 fR （ x ， y ）可理解为 x ， y 具有 R 的程度。

若从特征关系的角度看关系的运算，则有

（ⅰ） （ x ， y ）∈ X × Y ，

（ⅱ） （ x ， y ）∈ X × Y ，

（ⅲ） （ x ， y ）∈ X × Y ， （ x ， y ）=1- fR （ x ， y ）；

（ⅳ） （ x ， y ）∈ X × Y ， （ y ， x ）= fR （ x ， y ）；

（ⅴ） R ₁ ∈ P （ X × Y ）， R ₂ ∈ P （ Y × Z ），则 （ x ， z ）∈ X × Z ，

（ⅵ） R ₁ R ₂ （ x ， y ）∈ X × Y ， 1 2；

（ⅶ） R ₁ = R ₂ （ x ， y ）∈ X × Y ， 1 2 。

1.2.5　关系的矩阵表示

关系的表示方法很多，除了用直积的子集表示外，对于有限论域情形，用矩阵表示在运算上更为方便。有限集之间的关系可用矩阵表示。设

X ={ x ₁ ， x ₂ ，…， x _n }， Y ={ y 1， y ₂ ，…， y _m }， R ∈ P （ X × Y ）　　（1.3）

令

将 R 写成矩阵，有

矩阵的行数 n 为 X 中元素的个数，列数 m 为 Y 中元素的个数， r _ij =1 x _i Ry _j 。关系矩阵中的元素或是0或是1，在数学上把诸元素只是0或1的矩阵称为布尔（Boole）矩阵。因此，任何普通二元关系的矩阵都是布尔矩阵。

例1.6 X ={2，3}， Y ={1，2，3，4}，从 X 到 Y 的小于关系为

则 R 可写成矩阵形式 。

R ={（ x ， y ）| x < y ， x ∈ X ， y ∈ Y }={（2，3），（3，4），（2，4）}　　（1.5）

关系的各种运算可在矩阵中进行。

若 R ₁ =（ r _ij ） _n×m ， R ₂ =（ s _ij ） _n×m ，则

R ₁ ∪ R ₂ =（m ax（ r _ij ， s _ij ）） _{n × m} ， R ₁ ∩ R ₂ =（min（ r _ij ， s _ij ）） _{n × m} ， =（1- r _ij ） _{n × m} ， R ^-1 是 R 的转置。

如果两关系均用矩阵表示，则复合关系可用类似于矩阵乘法的方法得到，“乘”换成“取小”，“加”换成“取大”。

例1.8 设 X ={ x ₁ ， x ₂ ， x ₃ ， x ₄ }， Y ={ y 1， y ₂ ， y ₃ }， Z ={ z ₁ ， z ₂ ， z ₃ }，从 X 到 Y 的关系 R ={（ x ₂ ， y ₃ ），（ x ₃ ， y ₁ ），（ x ₄ ， y ₃ ）}， Y 到 Z 的关系 Q ={（ y ₂ ， z ₃ ），（ y ₃ ， z ₁ ）}，求 。

解：

从而， ={（ x ₂ ， z ₁ ），（ x ₄ ， z ₁ ）}。与定义式直接运算的结果一致。

1.2.6　等价关系与划分

定义1.10 设 R 是 X 上的关系，若 x ∈ X ，有 xRx ，即 χ _R （ x ， x ）=1，则称 R 是自反的。

x ， y ∈ X ，若 xRy ⇒ yRx ，即 χ _R （ x ， y ）= χ _R （ y ， x ），则称R是对称的。

x ， y ， z ∈ X ，若 xRy ， yRz ⇒ xRz ，即 χ _R （ x ， y ）=1， χ _R （ y ， z ）=1， χ _R （ x ， z ）=1，则称 R 是传递的。

设N为自然数集，N上的关系“<”具有传递性，但不具有自反性和对称性。

设 P （ X ）为 X 的幂集， P （ X ）上的关系“ ”具有自反性和传递性，但不具有对称性。

为了将集合的元素进行分类，下面引进一个重要的关系——等价关系。

定义1.11 设集合 X 上的二元关系 R 具有自反性、对称性和传递性，则称 R 是 X 上的等价关系，此时 xRy 又称为 x 等价于 y ，记为 x ≅ y 。

比如，“同龄关系”，数学上的“=”都是等价关系，而朋友关系不是等价关系，因为它不具有传递性。

集合 X 上的等价关系的重要性在于可以将集合 X 分成适当的子集（实际上就是将集合 X 进行分类），为此又引进下面的定义。

定义1.12 设 X 是非空集， X _i 是 X 的一些非空子集，若∪ X _i = X ，且 X _i ∩ X _j =∅（ i ≠ j ），则称集合族 {…， X _i …}为 X 的一个划分，称集 X _i 为这个划分的一个类（ i ∈ I ， I 为指标集），以∏表示划分，即为∏= { X _i | X _i X ，且 x ∈ X 恰属于 X _i }。

划分∏的每一个元素称为一个块，也称为划分的一个类。

当划分的块数为有限时，划分∏也可表示为∏={ X ₁ ， X ₂ ，…， X _n }， n 为块数。

显然，对有限集而言，它的划分块数一定是有限的。

例1.9 设 X ={1，2，3，4}，则∏ ₁ ={{1}，{2}，{3}，{4}}，∏ ₂ ={{1，2}，{3}，{4}}，∏3={{1，2，3}，{4}}，∏4={{1，2}，{3，4}}，∏5={{1，2，3，4}}等都是 X 的划分，但∏'={{1}，{2，3}}，∏″={{1}，{2，3}，{2，4}}等不是 X 的划分。

下面的定理说明了集合 X 上的等价关系与划分（即分类）之间的联系。

定理 集合 X 上的任一等价关系可以确定 X 的一个划分（即分类）；反过来，集合 X 的任一划分（即分类）可以确定 X 上的一个等价关系。

例1.10 设论域 X = {某高校全体本科生（四年制）}，在 X 上定义了 R ₁ =“同年级关系”，显然“同年级关系”是一个等价关系。因此，关系 R ₁ 把 X 划分为四个不同的年级： X ={ X ₁ ， X _2， X ₃ ， X ₄ }，其中 X _i 表示 i 年级， i =1，2，3，4。这就表明，论域 X 上的等价关系 R ₁ （同年级关系）可以确定一个划分（分类）： X ={ X ₁ ， X _2， X ₃ ， X ₄ }。

例1.11 设论域 X = {某高校学生}，在论域 X 上有一个划分（分类）： X ={男生，女生}={ Y ₁ ， Y ₂ }，因为这个划分是按性别划的，所以这个划分可以确定 X 上的一个关系 R ₂ =“同性别关系”。显然，“同性别关系”= R ₂ 是一个等价关系。

定义1.13 设 R 是集合 X 上的关系，若关系 R 是自反的、对称的，则称 R 是相似关系。

例如朋友关系、同学关系都是相似关系。

与等价关系一样，相似关系的应用也是非常广泛的。 HFsgx9LY5jekbP1nDDBoHAReoecrEptUbNE0AHVgIjkBfkNYefKC97hUFXdP/squ