Ch1 Sets, Relations & Functions

Sets

Basic Concepts

• 集合 (set)：无序的元素聚集。
• $\varnothing$：空集。
• $\subseteq$（子集）：$S\subseteq T$ 意味着 $S$ 里所有元素都在 $T$ 里。
• $\subset$（真子集）：$S\subset T$ 且 $S\ne T$。
• 相等：两个集合相等 $\Leftrightarrow$ 它们互为子集。

Warning

$\subset$ 是真子集 (proper subset) 的符号，这种时候两个集合不能相同。

Set Operations

• 并 (union)：$A\cup B$，属于 $A$ 或 $B$ 的元素集合。
• 交 (intersection)：$A\cap B$，同时属于 $A$ 和 $B$ 的元素集合。
• 差 (difference)：$B-A$，在 $B$ 中但不在 $A$ 中的元素集合。
• 补 (complement)：$\bar A$，相对某个全集 (universal set) $U$ 而言，不在 $A$ 的元素。
• 对称差 (symmetric difference)：$A\mathbin{\triangle}B$，属于 $A$ 或 $B$ 但不属于二者交集的元素集合。

Set Identities

• 幂等律 (idempotent law)：$A\cup A=A$，$A\cap A=A$。
• 交换律 (commutative law)：$A\cup B=B\cup A$，$A\cap B=B\cap A$。
• 结合律 (associative law)：$(A\cup B)\cup C=A\cup(B\cup C)$（交同理）。
• 分配律 (distributive law)：$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$（并对交也成立）。
• 吸收律 (absorption)：$A\cup(A\cap B)=A$，$A\cap(A\cup B)=A$。
• De Morgan’s Law（用来交换 $\cap$ 与 $\cup$）：

$$A-(B\cup C)=(A-B)\cap(A-C),\qquad A-(B\cap C)=(A-B)\cup(A-C)$$

Power Set

• 幂集 (power set)：$\mathcal P(A)$ 或 $2^A$，$A$ 的所有子集构成的集合。若 $A$ 有 $n$ 个元素，则 $|2^A|=2^n$。
• $|2^A|=2^{|A|}$。

Partition

对非空集合 $A$，分割是一个子集族 $\Pi\subseteq 2^A$，满足：

1. $\Pi\ne\varnothing$（至少有一块）。
2. 对任意 $S,T\in\Pi$，$S\ne T$，有 $S\cap T=\varnothing$（每个元素只属于一块）。
3. $\displaystyle\bigcup_{S\in\Pi}S=A$（所有块加起来刚好是整个 $A$）。

Example

【占位：Partition example】

Relations & Functions

Ordered Pair

• A pair $(a,b)$ is an ordered pair.
• $(a,b)=(c,d)\Longleftrightarrow a=c\land b=d$。
• 在 ordered pair $(a,b)$ 中，第一个元素称为第一分量 (first component)，第二个元素称为第二分量 (second component)。
• 对于 relation 中的 ordered pair，前者又称为 input value，后者又称为 output value。

Binary Relation

给定两个集合 $A,B$，定义它们的笛卡尔积 (Cartesian product) 为：

$$A\times B=\{(a,b)\mid a\in A,b\in B\}$$

也就是所有“从 $A$ 取一个元素，从 $B$ 取一个元素”组成的有序对集合。

一个二元关系 (binary relation) $R$ 是某两个集合之间的“配对规则”。形式上，

$$R\subseteq A\times B$$

Relation Operations

若 $R\subseteq A\times B$，定义它的逆关系 (inverse relation) 为：

$$R^{-1}=\{(b,a)\mid(a,b)\in R\}\subseteq B\times A$$

复合关系 (composition relation)：如果 $a$ 通过 $R$ 连到 $b$，$b$ 通过 $S$ 连到 $c$，那么 $a$ 通过 $R\circ S$ 连到 $c$。

$$R\circ S=\{(a,c)\mid\exists b\in B,(a,b)\in R\text{ and }(b,c)\in S\}$$

Domain & Range

• 定义域 (domain)：关系中所有第一分量的集合：

$$\operatorname{Dom}(R)=\{a\mid\exists b,(a,b)\in R\}$$

• 值域 (range)：关系中所有第二分量的集合：

$$\operatorname{Ran}(R)=\{b\mid\exists a,(a,b)\in R\}$$

Function

一个函数 (function) $f:A\to B$ 必须满足：

• $f\subseteq A\times B$。
• 对任意 $a\in A$，存在 exactly one $b\in B$ with $(a,b)\in f$。

1. 单射 (injective / one-to-one)

   $$a_1\ne a_2\Longrightarrow f(a_1)\ne f(a_2)$$

   不同输入不会映射到同一输出。

2. 满射 (surjective / onto)

   $$\forall b\in B,\exists a\in A\text{ 使 }f(a)=b$$

   即值域覆盖整个 $B$。

3. 双射 (bijective / one-to-one correspondence)

   同时满足单射与满射。

二元关系的特殊类型

有向图

• 对任意集合 $A$，关系 $R\subseteq A\times A$ 都可以用有向图 (directed graph) 表示。
  • 节点用小圆圈表示，每个节点对应 $A$ 中的一个元素。
  • 箭头是图中的边。当且仅当 $(a,b)\in R$ 时，存在一条从 $a$ 指向 $b$ 的箭头。
  • 从一个节点到另一个节点，要么没有边，要么只有一条边。

【占位：有向图示例】

矩阵

• 若 $R$ 是集合 $X$ 与 $Y$ 之间的二元关系，则 $R\subseteq X\times Y$。
• $R$ 可以用逻辑矩阵 (logical matrix) $M$ 表示，其中行标和列标分别对应 $X$ 和 $Y$ 中的元素。
• 矩阵 $M$ 的元素定义为

$$m_{i,j}=\begin{cases} 1 & (x_i,y_j)\in R,\\ 0 & (x_i,y_j)\notin R. \end{cases}$$