4.1 关系概述

4.1.1 有序对和有序 n 元组

定义4.1.1 由两个元素 a 和 b 按一定的顺序排列成的二元组叫作 有序对 （或 有序偶 ），记作（ a ， b ），其中 a 称为 第一元素 ， b 称为 第二元素 。

有序对可以表示有一定次序关系成对出现的事物，如平面直角坐标系中点的坐标就是有序对，（1，2）、（2，1）、（3，3）、（0，-1）代表平面直角坐标系中不同的点。在有序对中两个元素的次序是十分重要的。

一般说来有序对具有以下特点。

1）当 a ≠ b 时，（ a ， b ）和（ b ， a ）是两个不同的有序对。

2）两个有序对相等，即（ a ， b ）=（ c ， d ）的充分必要条件是 a = c 且 b = d 。

注意，（ a ， b ）和（ b ， a ）是不同的。除非 a = b ，否则（ a ， b ）和（ b ， a ）是不等的。但是集合{ a ， b }和集合{ b ， a }是相等的，即{ a ， b }={ b ， a }，因为集合中的元素是无顺序的。

定义4.1.2 由 n 个元素 a ₁ ， a ₂ ，…， a _n 按一定的顺序排列成的一个序列（ a ₁ ， a ₂ ，…， a _n ），称为 有序 n 元组 ，其中 a ₁ 为第一元素， a ₂ 为第二元素，…， a _n 为第 n 元素。

例如， n 维空间中点的坐标或 n 维向量都是有序 n 元组，（1，2，5）、（-1，-2，3）等是三维空间直角坐标系中点的坐标。

当且仅当两个有序 n 元组中的每一对对应的元素都相等时，它们才相等。也就是说

（ a ₁ ， a ₂ ，…， a _n ）=（ b ₁ ， b ₂ ，…， b _n ），当且仅当 a _i = b _i ， i =1，2，…， n

4.1.2 笛卡儿积

定义4.1.3 设 A 、 B 为集合，取 A 中的元素作为第一元素，取 B 中的元素作为第二元素，构成有序对，所有这样的有序对组成的集合称为 A 和 B 的 笛卡儿积（直积） ，表示为 A × B 。于是

A × B ={（ x ， y ）| x ∈ A ∧ y ∈ B }

例4.1.1 已知 A ={ a ， b ， c }、 B ={1，3}，求 A × B ， B × A ， A ×∅，∅× B 。

解 A × B ={（ a ，1），（ a ，3），（ b ，1），（ b ，3），（ c ，1），（ c ，3）}

B × A ={（1， a ），（1， b ），（1， c ），（3， a ），（3， b ），（3， c ）}

A ×∅=∅

∅× B =∅

◀

例4.1.2 已知 A ={ a ， b ， c }、 B ={1，3}， C ={ x }，求（ A × B ）× C ， A ×（ B × C ）。

解 （ A × B ）× C ={（（ a ，1）， x ），（（ a ，3）， x ），（（ b ，1）， x ），（（ b ，3）， x ），（（ c ，1）， x ），（（ c ，3）， x ）}

A ×（ B × C ）={（ a ，（1， x ）），（ a ，（3， x ）），（ b ，（1， x ）），（ b ，（3， x ）），（ c ，（1， x ）），（ c ，（3， x ））}

◀

根据上面的两个例题，可以看出：

1）当 A 、 B 为非空集合且 A ≠ B 时，笛卡儿积运算不满足交换律，即

A × B ≠ B × A

2） A × B =∅，当且仅当 A =∅或 B =∅。

3）当 A 、 B 、 C 均为非空集合时，笛卡儿积运算不满足结合律，即

（ A × B ）× C ≠ A ×（ B × C ）

4）当集合 A 和 B 都是有限集时，根据乘法原理，有| A × B |=| A |×| B |。

例4.1.3 设 A 、 B 、 C 为任意集合，证明 A ×（ B ∪ C ）=（ A × B ）∪（ A × C ）。

证明 对于任意有序对（ x ， y ），有

（ x ， y ）∈ A ×（ B ∪ C ）

⇔ x ∈ A ∧ y ∈（ B ∪ C ）

⇔ x ∈ A ∧（ y ∈ B ∨ y ∈ C ）

⇔（ x ∈ A ∧ y ∈ B ）∨（ x ∈ A ∧ y ∈ C ）

⇔（ x ， y ）∈（ A × B ）∨（ x ， y ）∈（ A × C ）

⇔（ x ， y ）∈（ A × B ）∪（ A × C ）

所以有 A ×（ B ∪ C ）=（ A × B ）∪（ A × C ）。

◀

由此可见，集合的笛卡儿积对并运算满足分配律。同理可以证明，集合的笛卡儿积对交运算，以及交、并运算均满足分配律，即有如下定理。

定理4.1.1 设 A 、 B 、 C 为任意集合，则

A ×（ B ∪ C ）=（ A × B ）∪（ A × C ）

A ×（ B ∩ C ）=（ A × B ）∩（ A × C ）

（ A ∪ B ）× C =（ A × C ）∪（ B × C ）

（ A ∩ B ）× C =（ A × C ）∩（ B × C ）

对两个以上的集合也可以定义笛卡儿积， n 个集合的笛卡儿积的定义如下。

定义4.1.4 设 A ₁ ， A ₂ ，…， A _n 为任意 n 个集合，它们的笛卡儿积（又称 n 阶直积）为

A ₁ × A ₂ ×…× A _n ={（ a ₁ , a ₂ ,…, a _n ）| a _i ∈ A _i ， i =1,2,…, n }

当 A ₁ = A ₂ =…= A _n = A 时， A ₁ × A ₂ ×…× A _n = A ⁿ 。

若| A ₁ |= n ₁ ，| A ₂ |= n ₂ ，…，| A _n |= n _n ，则 n 个集合的笛卡儿积中的元素个数为

| A ₁ × A ₂ ×…× A _n |=| A ₁ |×| A ₂ |×…×| A _n |= n ₁ × n ₂ ×…× n _n

例4.1.4 证明 A ×（ B-C ）=（ A × B ）-（ A × C ）。

证明 对于任意有序对（ x ， y ），有

（ x , y ）∈ A ×（ B-C ）

⇔ x ∈ A ∧ y ∈（ B-C ）

⇔ x ∈ A ∧（ y ∈ B ∧ y ∉ C ）

⇔ x ∈ A ∧ y ∈ B ∧（ x ∈ A ∧ y ∉ C ）

⇔（ x ， y ）∈ A × B ∧（ x ， y ）∉ A × C

⇔（ x ， y ）∈ A × B-A × C

◀

例4.1.5 设 A 、 B 、 C 、 D 是任意集合，判断下列命题是否为真。

1） A ⊆ C ∧ B ⊆ D ⇔ A × B ⊆ C × D

2）（ A ∩ B ）×（ C ∩ D ）=（ A × C ）∩（ B × D ）

3）（ A ∪ B ）×（ C ∪ D ）=（ A × C ）∪（ B × D ）

解 1）不一定为真。当 A = B =∅或 A ≠∅且 B ≠∅时，命题成立。但当 A 和 B 之一为∅时，命题不成立。例如，令 A =∅、 B ={1}、 C ={2}、 D ={3}，则 A × B ⊆ C × D 为真，而 A ⊆ C ∧ B ⊆ D 为假。

2）为真。证明方法类似于例4.1.4。

3）不一定为真。例如，令 A = D =∅、 B = C ={1}，则（ A ∪ B ）×（ C ∪ D ）={1}×{1}={（1，1）}，而（ A × C ）∪（ B × D ）=∅，这时（ A ∪ B ）×（ C ∪ D ）≠（ A × C ）∪（ B × D ）。

◀

4.1.3 关系的概念

无论在日常生活中还是在数学上，关系都是一个基本的概念，如日常生活中的父子关系、朋友关系、同学关系、上下级关系，以及数学中的相等关系、大小关系和整除关系等。

可以看出，关系描述的是集合的元素间的相关性。实际上，集合的元素间的相关性是指在一定规则下的相关性，如3和2有大小关系、10和5有整除关系和大小关系等。描述两个元素间的相关性称为二元关系，描述多个元素间的相关性称为多元关系。

集合的元素间的相关性也可以用集合来表示。如有三个学生：小王、小张、小李。小王选修英语，小张选修法语，小李选修德语。三个学生的选课情况可以表示为{（小王，英语），（小张，法语），（小李，德语）}，其中（ x ， y ）表示 x 选修 y 。集合{（小王，英语）、（小张，法语）、（小李，德语）}表示了学生的集合{小王，小张，小李}和课程的集合{英语，法语，德语}的元素间的关系。因此，可以定义关系为有序对的集合，其中有序对中的第一元素和第二元素相关。下面给出关系的定义。

定义4.1.5 如果一个集合非空且它的元素都是有序对，或集合为空，则称该集合为一个 二元关系 ，记作 R 。二元关系也可简称为 关系 。对于二元关系 R ，如果有序对（ a ， b ）∈ R ，称 a 与 b 有 R 关系 ，记作 aRb ；当（ a ， b ）∉ R 时，称 a 与 b 没有 R 关系 ，记作 aR / b 。

例如， R ={（0， a ），（0， b ），（1， a ），（2， b ）}是一个二元关系，其中，0 Ra 、1 Ra 、0 Rb 、2 Rb ，而1 R / b 、2 R / a 。而 R ={（1，2），（1，3），2，3}不是一个二元关系。

对任意两个集合 A 、 B ， A 和 B 的笛卡儿积 A × B 的元素是有序对，因而关系还有如下的定义。

定义4.1.6 设 A 、 B 为集合， A × B 的任意一个子集是集合 A 到 B 的一个二元关系。当 A = B 时称为 A 上的 二元关系 。

例如，集合 A ={0，1，2}、 B ={ a ， b }，则 R ₁ ={（0， a ），（1， b ），（1， a ），（2， b ）}是从 A 到 B 的一个二元关系， R ₂ ={（0，1），（1，2），（0，2）}是 A 上的一个二元关系。空集∅是 A × B 的子集，称∅为集合 A 到集合 B 的 空关系 ，表示集合 A 到 B 不存在某种关系； A × B 称为集合 A 到 B 的 全域关系 ，即集合 A 的每个元素和集合 B 的每个元素之间均具有某种关系。在集合 A 上， E _A = A × A 称为 A 上的 全域关系 ， I _A ={（ x ， x ）| x ∈ A }称为 A 上的 恒等关系 。

对于集合 A 、 B ，如果| A |= n 、| B |= m ，则| A × B |= nm ， A × B 的子集有2 ^nm 个，所以集合 A 到集合 B 有2 ^nm 个不同的二元关系。如果 B = A ，则| A × A |= n ² ， A × A 的子集有 个，所以 A 上有 个不同的二元关系。

例4.1.6 设集合 A ={0，1}、 B ={ a ， b }，写出集合 A 到集合 B 的所有二元关系。

解 因为 A ={0，1}、 B ={ a ， b }，所以 A × B ={（0， a ），（0， b ），（1， a ），（1， b ）}。 A × B 的所有不同子集如下。

0元子集：∅。

1元子集：{（0， a ）}，{（0， b ）}，{（1， a ）}，{（1， b ）}。

2元子集：{（0， a ），（0， b ）}，{（0， a ），（1， a ）}，{（0， a ），（1， b ）}，{（0， b ），（1， a ）}，{（0， b ），（1， b ）}，{（1， a ），（1， b ）}。

3元子集：{（0， a ），（0， b ），（1， a ）}，{（0， a ），（0， b ），（1， b ）}，{（0， a ），（1， a ），（1， b ）}，{（0， b ），（1， a ），（1， b ）}。

4元子集：{（0， a ），（0， b ），（1， a ），（1， b ）}。

由定义4.1.6知，上面的16个不同的子集就是集合 A 到集合 B 的所有二元关系。

◀

例4.1.7 设 A ={ a ， b }，写出集合 A 上的全域关系 E _A 和恒等关系 I _A 。

解 A 上的全域关系

E _A ={（ a ， a ），（ a ， b ），（ b ， a ），（ b ， b ）}

A 上的恒等关系

I _A ={（ a ， a ），（ b ， b ）}

◀

对于任何集合 A ， A 上有空关系、全域关系和恒等关系，除了这三种特殊关系以外，还有一些常用的关系，如在实数集上的大于关系、小于关系、整除关系等。

例4.1.8 已知集合 A ={0，1，2}，写出集合 A 上的整除关系 D _A 和小于或等于关系 L _A 。

解 集合 A 上的整除关系为

D _A ={（1，1），（1，2），（2，2）}

集合 A 上的小于或等于关系为

L _A ={（0，0），（0，1），（0，2），（1，1），（1，2），（2，2）}

◀

定义4.1.7 设 A 、 B 是两个集合， R 是从 A 到 B 的二元关系。 R 的所有有序对的第一个元素构成的集合称为 R 的 定义域 （或 前域 ），记为dom R ； R 的所有有序对的第二个元素构成的集合称为 R 的 值域 （或 后域 ），记为ran R ； R 的定义域和值域的并集称为 R 的 域 ，记为 f ld R 。

二元关系 R 的定义域dom R 和值域ran R 又可表示为

dom R ={ x |∃ y （ x ， y ）∈ R ）}

ran R ={ y |∃ x （ x ， y ）∈ R ）}

f ld R =dom R ∪ran R

例4.1.9 A ={甲，乙，丙，丁}， B ={ a ， b ， c }。 R ={（甲， a ），（乙， b ），（丁， c ）}是从 A 到 B 的二元关系，写出 R 的定义域和值域。

解 R 的定义域dom R ={甲，乙，丁}，值域ran R ={ a ， b ， c }。

◀

例4.1.10 设 ℤ是整数集合，ℤ上的关系 R ={（ x ， y ）| x ， y ∈ℤ∧（ y = x ² ）}，写出 R 的定义域和值域。

解 R 的定义域dom R =ℤ，值域ran R ={ y | x ， y ∈ℤ∧（ y = x ² ）}。

◀

可以看出，集合 A 到 B 的二元关系 R 的定义域dom R ⊆ A ，值域ran R ⊆ B 。

上述概念可以推广到 n 个集合的笛卡儿积的子集，即 n 元关系。

定义4.1.8 设 A ₁ ， A ₂ ，…， A _n 是 n 个集合。 A ₁ × A ₂ ×…× A _n 的任一子集，称为 A ₁ ， A ₂ ，…， A _n 间的一个 n 元关系 。

在计算机领域，关系的概念随处可见，如数据结构中的线性关系和非线性关系。在关系数据库中数据按二维表的形式存放，如表4.1.1所示。

一个二维表可有 m 行 n 列，二维表的每一行叫 元组 ，代表一个完整的数据。一个元组有 n 个分量，因此这个元组又叫 n 元元组 。二维表的每一列表示数据的分量，这种二维表叫 n 元关系 。表4.1.1表示学号、姓名、课程、成绩间的关系，这个表还可以用有序4元组的集合来表示：{（02001，张明，物理，优秀），（02002，李强，数学，良好），（02008，王华，英语，优秀），（02010，李力，数学，良好）}。 XfruYH8ChcqHuniqjNcV+zU2O3sXOFiS6kMsb93YkNxYwsZ0UlXiWgYAzBe/4t/D