Lecture 7: Relations

Definition and Examples
Binary Relations
Properties of Binary Relations
Functions

定义与例子 Definition and Examples

关系 Relations

n元关系（n-ary relation）是n个集合的笛卡尔积的子集，记作：

R \subseteq S_1 \times S_2 \times ... \times S_n

特殊地，当 $n=2$ 时，我们称之为二元关系（binary relation），记作：

R \subseteq S \times T

并且展示相关联的数对时，写作：

(x,y) \in R \ \ \ \ \ or \ \ \ \ \ R(x,y) \ \ \ \ \ or \ \ \ \ \ xRy

笛卡尔积的结果集合 $U=S_1 \times S_2 \times ... \times S_n$ ，称之为 $R$ 的定义域（domain）。如果关系 $R$ 定义域在 $U$ 上，我们就说 $R$ 是 $U$ 上的关系。

例子

在这个关系中，enrolment显然是学生与课程的对（pair），但应当不是笛卡尔积的全集（因为不太可能每一名学生都会修掉所有的课）。

定义关系 Defining Relations

有以下几种方式定义一个关系 $R$ ：

通过明确地列举相关的k元组来定义：这里的k元组指的是在二元关系的情况下的有序对。
通过识别大的笛卡尔积内部的相关元组的属性来定义：这意味着关系可以通过满足特定关系的元组的等式/不等式/关系式等描述。
通过其他关系构建定义：例如通过交集，并集，补集等。

二元关系 Binary relations

在集合S和T之间的二元关系是 $S \times T$ 的子集，即有序对的集合。

特殊的二元关系例子：

恒等关系（Identity）：这是对角线关系，也称等价琯溪，定义为 $I = \{(x,x)|x \in S\}$ ，其中每个元素与自身形成对。
空关系（Empty）：不包含任何元素的关系，记作 $\empty$ 。
全域关系（Universal）：包含所有可能有序对的关系，定义为 $U=S \times T$ 。

定义二元关系的方法 Definition binary relations

基于集合定义 Set-based definitions

参考：定义关系部分。

矩阵描绘 Matrix representation

图像描述 Graphical representation

集合图表示

有向图表示

二元关系操作 Operations for binary relations

逆关系 Converse

如果有一个关系 $R \subseteq S \times T$ ，那么它的逆关系 $R^←$ 定义为：

R^←=\{(t,s) \in T \times S: (s,t) \in R\}

这意味着在逆关系中，每个有序对的元素顺序会被反转。并且，显然有：

(R^←)^←=R

复合关系 Composition

如果 $R_1 \subseteq S \times T$ 并且 $R_2 \subseteq T \times U$ ，那么它们的符合关系 $R_1 ; R_2$ 定义为：

R_1 ; R_2 = \{ (s,u) \in S \times U: \exist t \in T \text{ such that } (s,t) \in R_1,(t,u) \in R_2 \}

复合关系意味着从集合S到U存在一个通过集合T中介的关系路径。

关系映像 Relational images

想象一下你在学校的学生和他们参加的俱乐部之间有一个列表，这个列表就是一个关系，它告诉你哪个学生参加了哪个俱乐部。

现在，如果你想知道某个特定学生参加了哪些俱乐部，你就会查找与这个学生相关的所有俱乐部，这就是关系映像。就像你拿着学生的名字去映射找出他们参加的所有俱乐部。

反过来，如果你手头有一个俱乐部的名单，你想找出所有参加这个特定俱乐部的学生，你就会查找与这个俱乐部相关的所有学生，这就是关系预映像。这就像是你从俱乐部的角度出发，反向映射回去找到所有相关的学生。

简单来说，关系映像就是从一个集合（比如学生）出发，找到与它们相关联的另一个集合（比如俱乐部）中的成员。而关系预映像则是反过来的操作。

给定关系 $R \subseteq S \times T$ ， $A \subseteq S$ ，并且 $B \subseteq T$ 。

关系映像 Relational image

关系映像 $R(A)$ 被定义为：

R(A)=\{ t \in T: (s,t) \in R \text{ for some } s \in A \}

简而言之， $R(A)$ 包含了所有与集合A中的元素通过关系R相关联的T中的元素。

关系预映像 Relational pre-image

关系预映像 $R^←(B)$ 被定义为：

R^←(B)=\{ s \in S: (s,t) \in R \text{ for some } t \in B \}

简而言之， $R^←(B)$ 包含了所有能够通过关系R找到与B中元素相对应的S中的元素。

二元关系的性质 Properties of Binary Relations

函数式（Fun） functional：对于每个 $S$ 中的元素 $s$ ，在关系 $R$ 中至多与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至多映射到一个 $t$ 。
全域性（Tot） total：对于每个 $S$ 中的元素 $s$ ，在关系 $R$ 中至少与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至少映射到一个 $t$ 。
单射（Inj） injective：对于每个 $T$ 中的元素 $t$ ，在关系 $R$ 中至多与一个 $S$ 中的元素 $s$ 关联。也就是说不同的 $s$ 映射到不同的 $t$ 。
满射（Sur） surjective：对于每个 $T$ 中的元素 $t$ ，在关系 $R$ 中至少与一个 $S$ 中的元素 $s$ 关联。也就是说 $T$ 中的每个元素都是某个 $s$ 的映射。
双射（Bij） bijective：关系 $R$ 同时满足单射和满射。也就是说， $S$ 到 $T$ 的映射是一对一的（每个 $s$ 只能映射到一个独特的 $t$ ），并且是覆盖的（ $T$ 中的每一个 $t$ 都被 $S$ 中的某个 $s$ 映射到）。

同一集合上的二元关系性质 Properties of Binary Relations $R \subseteq S \times S$

自反性（R）reflexive：对于集合 $S$ 中的所有元素 $x$ ，都有 $(x,x) \in R$ 。也就是说，每个元素都与自己本身在关系 $R$ 中有关联。
反自反性（AR）antireflexive：对于集合 $S$ 中的所有元素 $x$ ，都有 $(x,x) \notin R$ 。也就是说，没有任何元素与自己本身在关系 $R$ 中有关联。
对称性（S）symmetric：如果有序对 $(x,y) \in R$ ，且 $(y,x) \in R$ 。
反对称性（AS）antisymmetric：如果有序对 $(x,y)$ 和 $(y,x)$ 都在 $R$ 中，必须有 $x=y$ 。
传递性（T）transitive：如果有序对 $(x,y)$ 和 $(y,z)$ 都属于关系 $R$ ，那么 $(x,z) \in R$ 。

如果某关系具有该性质，意味着这些性质是对关系中的所有元素都成立的。

其中，S，AS，T是条件语句，如果没有任何元素满足“如果”部分的条件，那么属性被认为是成立的。例如，如果在关系中不存在任何两个不同元素 $x, y$ 使得 $(x,y)$ 和 $(y,x)$ 同时存在，那么该关系就被视为反对称的。

性质的交互 Interaction of Properties

一个关系可以同时是对称的和反对称的。这种情况发生在关系 $R$ 仅由形如 $(x,x)$ 的有序对组成时，也就是说，除了自反元素之外没有其他元素。在这种情况下，每个元素与自己相关联，但没有不同的元素 $x,y$ 使得 $(x,y)$ 和 $(y,x)$ 同时在 $R$ 中。

关系不能同时是自反的和反自反的，除非集合 $S$ 是空集。这是因为自反性要求集合 $S$ 中每个元素与自己相关联，而反自反性要求没有任何元素与自己相关联，这两个定义是相互矛盾的。

不具有自反性（nonreflexive）或不具有对称性（nonsymmetric）的关系，不等同于反自反的（antireflexive/irreflexive）或反对称的（antisymmetric）关系。这是关系属性的一个重要区别，因为“不具有某属性”（如不自反或不对称）并不一定意味着它具有对应的“反属性”（如反自反或反对称）。

例如，一个关系，如果它对某些元素是自反的，而对其他元素则不是自反的，那么该关系既不是自反的也不是反自反的。

数学函数 Functions

一个函数 $f:S→T$ ，是从集合 $S$ 到集合 $T$ 的一个二元关系 $f \subseteq S \times T$ ，且满足函数式（Fun）和全域性（Tot）两个属性。也就是说，对于集合 $S$ 中的每一个元素 $s$ ，都有且只有一个元素 $t$ 在集合 $T$ 中与之关联。

如果 $s$ 唯一关联 $t$ ，我们用 $f(s)$ 来表示这个唯一关联的 $t$ 。

我们用函数集 $T^S$ 表示从 $S$ 到 $T$ 的所有可能的函数的集合。

术语

定义域（domain），包含所有可能的输入，即集合 $S$ 。
上域（co-domain），包含所有可能的输出，即集合 $T$ 。
像（image），即值域（range），是函数 $f$ 的实际所有输出，为 $T$ 的子集。

符号

定义域： $Dom(f)$
上域： $Codom(f)$
像： $Im(f)$ ，也可写作 $\{ f(x): x \in Dom(f) \}$

要点

定义域，上域，方法，三者完全相同的，才能认为是相同的函数。不同的定义域/上域，会影响函数的性质和应用。

当函数 $f$ 同时满足单射和满射（即双射，或称一一对应函数）时，关系 $f^←$ 才能也是一个函数。

双射的性质 Properties of bijections

如果 $f: S → T$ 和 $g: T → U$ 是双射，那么它们的逆函数也是双射的。
函数 $f$ 和 $g$ 的复合 $(f;g): S → U$ 也是双射。
函数 $f$ 与它的逆函数 $f^←$ 的复合等于在 $S$ 上的恒等关系，记作 $f;f^←=I_S$ ，它包含所有形如 $(x,x)$ 的元素对，其中 $x \in S$ 。
逆函数 $f^←$ 与函数 $f$ 的符合等于在 $T$ 上的恒等关系，记作 $f^←;f=I_T$ ，它包含所有形如 $(x,x)$ 的元素对，其中 $x \in T$ 。

最后两个性质实际上定义了双射函数的逆函数关系，也就是说，你可以通过 $f$ 找到 $T$ 中的每个元素的原像，反过来通过 $g$ 找到 $S$ 中的每个元素的原像，没有遗漏也没有重复。

目录