4. 集合的关系

关系 Relation

定义

对于子集 $R\subset A\times B$ 称为 a relation from A to B
domain: $\text{domain}(R) := \{x|\exists y（xRy)\}$ 定义域是使得 R 成立的第一个元素的集合
range: $\text{image}(R):=\{y|\exists x(xRy)\}$ 值域表示 R 成立的第二个元素的集合

符号表述法 notation

$(x,y)\in R \Leftrightarrow xRy$
$(x,y)\not\in R\Leftrightarrow x\not R y$
如果 $A = B$ 我们称 $R$ 是一个 relation on A

还原关系 identity relation

$\text{id}_A = \{(a,a)| a\in A\}$

identity relation 将每个元素联系到其自身上，注意 $\text{domain}(id_A) =\text{image}(id_A) = A$

函数 Function

函数 $F : A\to B$ 是一个 triple 三元数据结构 $(A,F,B)$, 其中 $F\subset A\times B$ 是一个关联，要求在一个数据范围内对任意 $x$ 有且只有唯一的 $y$ 与之对应

逻辑语句定义

$(\forall x\in A)(\exists ! y(xFy))$

注意这里 $\exists !y$ 表示存在唯一的 $y$

评论

1. 唯一映射的逻辑表述 $(\forall x,y\in A)(x = y\to F(x) = F(y))$
2. 对于 $x\in \text{domain}(F)$, 存在唯一的 y 使得 $xFy$, 我们称之为 $F$ 在 $x$ 的 value
3. 函数 $F$ 的集合我们表述为 $B^A = \{f : A\to B\}$

局部函数 Partial Function

定义

我们称呼一个关系 $F\subset A\times B$ 是 functional, (right-unique) 前提是 $(\forall x\in A)(\exists_{\le 1}y(xFy))$
其中 $\exists_{\le 1}y$ 表示最多存在1个 y
从上面的定义我们可以看出定义域有些会被定义，有些则可能没有定义
partial function: 我们称呼 $F\subset A\times B$ 是一个 functional
total function: 要求 $\text{dom} F = A$

字符串摘取函数

我们定义局部函数 $[\ell]\to \Sigma$ 其中 $[\ell]$ 表示长度为 $\ell$ 的字符串，那么我们有 $v(i) = v_i$ 表示字符串的第 $i$ 个字符

多重集 multiset

对于任意集合 $S$, 我们有 多集合 $M$ over $S$ 表示任意函数 $M: S\to \mathbb{N}$
有限多集合: $M(a) \not = 0$ 对有限个 a 成立
multiplicity: 我们称呼 $M(a) = k > 0$ 我们称 $a$ 是multiplicity k
empty multiset: 常函数 $M = 0$
简单的说，多重集就是一个可以出现重复元素的集合，其配套的 $M$ 函数表示了元素在集合中的出现的次数,或者说 M 的数据结构是 $(a,2)$ 表示在集合 $M$ 中元素 $a$ 出现了两次
多重集往往会搭配原一般集合出现，也就是说，我们常常会用 $[d]$ 的多重集进行描述一个新的集合，这个新的多重集至少有原集合下的一个元素且可以重复多次出现，多重集的尺寸不是原集合的尺寸，是多重集自身元素的总数

关系与函数的运算

1. 逆运算 inverse: $F^\top = F^{-1} = \{(y,x)| xFy\}$
2. 组合运算 compose: $G ; F = F \circ G = \{(x,z)|\exists y(xGy\land yFz)\}$
3. 限制 restriction: $F|A = \{(x,y)|(xFy)\land (x\in A\}$ 限制了定义域
4. 像空间 image: $F(A) = \text{im}(F|A) = \{y|(\exists x\in A)(xFy)\}$

关系和幺半群

$(P(A\times A), \circ, id_A)$ 构成幺半群
注：这个定理说明了，关系是一种集合，它和 $P(A\times A)$ 同构

用矩阵表示一个关系

我们很多时候使用的是逻辑矩阵进行表示

$m_{ij} = \begin{cases} 1,\text{if }(a_i,b_j) \in R\\ 0,\text{if }(a_i,b_j) \not\in R\end{cases}$

例如我们对于集合 $A = \{1,2,3\}, B=\{r,s\}$,我们有关系 $R = \{(1,r),(2,s),(3,r)\}$ 那么我们就会有 矩阵

$M_R = \begin{bmatrix}1 & 0 \\ 0 & 1 \\1 & 0\end{bmatrix}$

关系矩阵的运算

矩阵运算最常见的操作就是组合 Composing: $M_R M_S = M_{R;S}= M_{S\circ R}$

映射关系

单射 injective / injection

$(\forall x,y\in A)(F(x) = F(y)\to x = y)$

满射 surjective / surjection

$\text{im}(F) = B$

双射 bijective

同时满足 单射 和 满射

左逆 left inverse

对于映射 $F : A\to B$ 存在映射 $G : B\to A$ 使得 $G\circ F = \text{id}_A$
这个性质等价于 injective

右逆 right inverse

存在 $G: B\to A$ 使得 $F\circ G = \text{id}_B$
这个性质等价于 surjective

单射传递性

如果 $g\circ f$ 是单射的，那么 $f$ 是单射的

满射传递性

如果 $g\circ f$ 是满射的，那么 $g$ 是满射的

关系的性质

1. 自反性 reflxive: $(\forall x\in A)(xRx)$
   1. $R$ reflexive iff $id_A\subset R$
2. 非自反性 irreflexive: $(\forall x\in A)(xRx\to \bot)$
3. 强连通性 strongly connected / total$^2$: $(\forall x, y \in A)(xRy\lor yRx)$ 这是一个图论常用概念
4. 传递性 transitive: $(\forall x,y,z\in A)(xRy\to yRz \to xRz)$
   1. $R$ 传递性 iff $R\circ R \subset R$
   2. 前提是 $(x,y), (y,z)$ 都在集合中
5. 对称性 symmetric: $(\forall x ,y \in A)(xRy \to yRx)$
   1. $R$ symmetric iff $R = R^{-1}$
6. 反对称性 anti-symmetric $(\forall x,y \in A)(xRy\to yRx \to x = y)$
   1. $R$ 是反对称 iff $R\cap R^{-1}\subset id_A$
   2. 前提是“若(x,y), (y,x)都在关系R的集合中” 所以要么关系 R 是单方向的，要么就是自映射
7. 不对称性 asymmetric $(\forall x, y\in A )(xRy\to yRx \to \bot)$
   1. antisymmetric $\not =$ non-symmetric: 前者表示完全没有逆映射，后者表示缺少某些逆映射

偏序关系 partial order

1. reflexive: 有自映射
2. antisymmetric: 不存在任何的逆映射
3. transitive: 可传递
   最常见的例子就是整数集合的 $\le$ 关系，我们一般将偏序关系保存的数据结构记为 有顺序的二元集合

等价关系 equivalence relation

1. reflexive: 有自映射
2. symmetric: 有逆映射
3. transitive: 可传递
   最常见的例子就是整数集合的等于号
   当然这个概念很容易让我们联想到 集合论 的等号三律

等价类 Equivalence Classes

定义

对于 A 上的 equivalence relation R,我们有

$[x]_R := \{t\in A |xRt\}$

该集合就是包含 $x$ 的等价类

解释

这就相当于表示了和 x 具有等价性质的所有 A 中元素的集合

等价类传递性

对于等价关系 $R$

$[x]_R = [y]_R \Leftrightarrow xRy$

划分 partition

非空子集，互斥，取并可以获得总集合

等价类与划分

对于等价关系 R, 集合 $\{[x]_R | x\in A \}$ 是 A 的一个partition

商集 quotient set

对于等价关系 $R$, $A/ R := \{[x]_R | x\in A\}$ 念作 “A modulo R”

幺半群 同态 monoid homomorphism

1. $f(x* y) = f(x)\cdot f(y)$
2. $f(e_M) = e_N$

像 kernel

定义 $\ker f:=\{(m,m')\in M \times M | f(m) = f(m')\}$ , 其中 $f : M\to N$
也就是说 $\ker$ 是一个 equivalence 算符
我们可以称之为 congruence 全等算符

全等类 congruence class

$[a] := \{x\in M|(x,a)\in \ker f\}$

表示的是同ker的元素集合，也是原集合 M 的一种partition,是一种特殊的尚集

商幺半群

在此基础上，我们称 $(M / \ker f, \circ , [e_M])$ 是一个幺半群，其中 算符 $\circ$ 满足 $[a]\circ [b] = [ab]$
注意这里 $[e_M]$ 对应的是像空间 (对于特定 f 的像空间) 的内容，由幺半群的定义我们也可以得到 $ab$ 就是常见的 char 的连接
$M / \ker f$ 表示的是子集的集合，元素就是各个子集 ，或者说各个同等类 [x]