Coursera离散数学概论笔记（五）：集合论之关系基本概念

1 有序组

1.1 二元有序组

元素的无序性是集合的特征之一，元素的有序组合可以从集合来定义。

二元有序组（或称二元组、序偶）：设 $a,b$ 为任意对象，称集合族 $\{\{a\},\{a,b\}\}$ 为二元有序组，简记为 $<a,b>$ 。其中，称 $a$ 为 $<a,b>$ 的第一分量， $b$ 为第二分量。

1.2 “有序”的含义

定理：对于任意序偶 $<a,b>,<c,d>$ ， $<a,b>=<c,d>$ 当且仅当 $a=c$ 且 $b=d$ 。

证明如下：

当 $a\neq b$ 时， $<a,b>\neq <b,a>$ ，但 $\{a,b\}=\{b,a\}$ 。

有序组利用元素和集合的两个不同层次进行巧妙定义，实现了两个对象 $a,b$ 的有序排列。

1.3 n 元有序组的定义

利用递归定义对 n 元有序组（n-tuple） $<a_1,...,a_n>$ 进行定义：

$n=2$ 时， $<a_1,a_2> = \{\{a_1\},\{a_1,a_2\}\}$

$n \geq 2$ 时， $<a_1,...,a_n> = <<a_1,...,a_{n-1}>,a_n>$

其中， $a_1$ 称为 n 元组的第 i 分量。

定理：对于任意 n 元组 $<a_1,...,a_n> = <b_1,...,a_n>$ 当且仅当 $a_1=b_1,...,a_n=b_n$ 。

2 笛卡尔积

2.1 定义

对任意集合 $A_1,A_2,...,A_n$ ， $A_1 \times A_2$ 称作集合 $A_1,A_2$ 的笛卡尔积，即为一个有序对的集合，定义如下：

$n=2$ 时， $A_1 \times A_2 = \{<u,v>|u \in A_1, v \in A_2\}$

$n \geq 2$ 时， $A_1,A_2,...,A_n = (A_1 \times A_2 \times ... \times A_{n-1}) \times A_n$

2.2 例子

2.3 性质

一般情况下， $A \times B \neq B \times A$ ， $A \times (B \times C) \neq (A \times B) \times C$ ，即笛卡尔积运算不满足交换律和结合律。

笛卡尔积对集合运算的分配律：设 $A,B,C$ 为任意集合，此处用 $\cdot$ 表示 $\cup,\cap,-$ 运算，那么有 $A \times(B \cdot C) = (A\times B) \cdot (A\times C)$ ， $(B \cdot C) \times A = (B \times A) \cdot (C \times A)$ 。

证明如下：

笛卡尔积的基数：对于任意有限集合 $A_1,...,A_n$ ，有 $|A_1 \times...\times A_n|=|A_1|*...*|A_n|$ 。

3 关系定义

3.1 关系的基本概念

关系是各个对象之间的联系和对应，最常见的是两组对象之间的联系和对应（比如“职员-部门”的隶属关系），也有三组或者更多对象之间的联系和对应（比如“供应商-工程-零件“的供应关系）。

采用二元组或多元组的集合来表示关系。

3.2 关系的定义

如果 R 是 $A_1 \times A_2...\times A_n$ 的一个子集，R 称为集合 $A_1,A_2,...,A_{n-1}$ 到 $A_n$ 的 n 元关系。当如果 R 是 $A_1 = A_2...= A_n$ 时，也称 R 为 $A$ 上的 n 元关系。

如果 R 是 $A \times B$ 的一个子集，R 称为集合 $A$ 到 $B$ 的 二元关系。当如果 R 是 $A \times A$ 上的一个子集，也称 R 为 $A$ 上的二元关系。（我们主要研究二元关系）

3.3 关系的例子

Coursera离散数学概论笔记（五）：集合论之关系基本概念

3.4 几个特殊的二元关系

空关系： $\empty$ ， $\empty \subseteq A \times B$ ，称 $\empty$ 为 A 到 B 的空关系。
全关系： $A \times B$ ，笛卡尔积 $A\times B$ 是 A 到 B 的全关系。
相等关系： $E_A = \{<x,x>|x\in A\}$ ，称作 A 上的相等关系。

3.5 关系的几个概念

设 R 为 A 到 B 的二元关系（ $R \subseteq A \times B$ )，xRy 表示 $<x,y> \in R$ ， ¬ xRy 表示 $<x,y> \notin R$ 。

R 的定义域（domain）： $Dom(R) = \{x|x\in A \bigwedge \exist y(<x,y> \in R)\}$

R 的值域（range）: $Ran(R) = \{y|y\in B \bigwedge \exist x(<x,y> \in R)\}$

同时，称 A 为 R 的前域，B 为 R 的陪域。

3.6 关系的表示法

集合表示法： $R = \{<x,y>|P(x,y)\}$ ，适合于表示集合的几种方法均可。
关系图法：前域和陪域都是有限集合，一般的关系图，有向箭头表示元素之间存在关系，也可以表示前域和陪域相同的关系图。

Coursera离散数学概论笔记（五）：集合论之关系基本概念

关系矩阵法：前域和陪域都是有限集合，设关系 $R \subseteq A\times B$ ， $A = {a_1,...,a_m}$ ， $B = {b_1,...,b_n}$ ，关系 R 的关系矩阵 $M_R$ 的定义为： $m_{ij} = 1$ 当且仅当 $a_1Rb_j$ ， $m_{ij} = 0$ 当且仅当 $¬a_1Rb_j$ 。