§2.1　关系及其表示

定义2.1.1　设A，B为任意两个集合，称笛卡儿积A×B的子集R为集合A到B的一个二元关系.若<x，y>∈R，则称x与y有关系R，记为xRy；否则称x与y没有关系R，记为.特别地，若A=B=C，则称R为集合A上的二元关系.

例如，设A={2，3，4，5，6}，则定义在A上的整除关系如下：

定义2.1.2　设R是定义在集合A上的二元关系.

（1）若对每个x∈A，均有xRx，则称R为自反的（reflexive）；

（2）若对每个x∈A，均有，则称R为反自反的（irreflexive）；

（3）若对任意x，y∈A，由xRy，可得出yRx，则称R是对称的（symmetric）；

（4）若对任意x，y∈A，由xRy且yRx，可得出x=y，则称R是反对称的（antisymmetric）；

（5）若对任意x，y，z∈A，由xRy且yRz，可得出xRz，则称R是传递的（transitive）.

例如，数值之间的相等关系“=”是自反的、对称的、反对称的和传递的，而小于关系“<”则是反自反的、反对称的和传递的；集合之间的含于关系“⊆”是自反的、反对称的和传递的.

【例2.1】　设Z+是正整数集，定义Z+上的整除关系为R={<x，y>|x，y∈Z+，x|y}.证明R是自反的、反对称的、传递的.

证明：对于任意的x∈Z+，均存在1∈Z+，使得x=1×x，于是x|x，所以R是自反的；又对于任意的x，y∈Z+，如果x|y并且y|x，则存在t，u∈Z+，使得y=tx，x=uy，将y=tx代入x=uy得x=utx，因t，u是正整数，故必有t=u=1，于是x=y，所以R是反对称的；最后，对于任意的x，y，z∈Z+，如果x|y并且y|z，则存在t，u∈Z+，使得y=tx，z=uy，于是z=utx，即x|z，所以R是传递的.

两个有限集合之间的二元关系除了用序偶的集合，即笛卡儿积的子集表示之外，还可以用关更为直观.

定义2.1.3　设A={x1，x2，…，xm}，B={y1，y2，…，yn}，R是A到B的二元关系.定义R的关系矩阵（matrix of R）MR=（rij）m×n如下：

例如，设A={1，2，3，4}，则定义在A上的小于关系R为：

R={<1，2>，<1，3>，<1，4>，<2，3>，<2，4>，<3，4>}

从而，其关系矩阵为

定义2.1.4　设A={x1，x2，…，xm}，B={y1，y2，…，yn}，R是A到B的二元关系.以A∪B中的每个元素x为平面上的一个结点（仍用x表示），对每个<x，y>∈R，均画一条从x到y的有向弧，其箭头指向y.称此图为R的关系图（digraph of R），记为GR.

例如，设A={1，2，3，4，5}，定义在A上的二元关系

R={<1，1>，<1，2>，<3，2>，<1，4>，<5，4>，<5，1>}

于是R的关系图GR如图2.1所示.