运算与关系 • CoderXL's Blog

集合#

不给出严格定义，但是一个给定元素是否属于该集合是确定的。

直积#

两个集合可以进行直积。集合 $A$ 与 $B$ 的直积定义为 $A \times B = \{(a,b) \mid a \in A, b \in B\}$ ，其中 $(a,b)$ 是有序数对。

嵌入映射#

如果 $A_0 \subseteq A$ ，定义

i: A_0 \to A,\ i(x)=x,\ \forall x \in A_0

为 $A_0$ 到 $A$ 的嵌入映射。

嵌入映射看起来有些“废话”，但是作为一种记号有时能很方便地展现集合和映射的关系。

开拓与限制#

如果 $A_0 \subseteq A$ ，且

f: A \to B,\ g: A_0 \to B,\ g(x)=f(x),\ \forall x\in A_0

那么称 $f$ 为 $g$ 的开拓， $g$ 为 $f$ （在 $A_0$ 上）的限制，记作 $g = f\mid_{A_0}$ .

交换图#

通过图表示集合之间的映射关系。节点代表集合，有向边代表映射。

比如存在如下集合与映射的关系：

\begin{array}{l} f_1: A_1 \to A_2& & g_1: A_1 \to B\\ f_2: A_2 \to A_3& & g_2: B \to C\\ f_3: A_3 \to C\\ \end{array}

且

f_3f_2f_1 = g_2g_1

那么可以使用交换图表示为：

flowchart LR
A1(("A₁")) -- "𝑓₁" --> A2(("A₂")) -- "𝑓₂" --> A3(("A₃")) -- "𝑓₃" --> C((C))

A1 -- "g₁" --> B((B)) -- "g₂" --> C

交换图在表示复杂的集合映射关系时，比列出所有关系式来得更简便。

“交换”的含义就是复合映射的等价性。

使用交换图与嵌入映射 $i$ 可以将开拓与限制表示为：

flowchart LR
A0(("A₀")) -- "g" --> B((B))
A0 -- "𝑖" --> A((A)) -- "𝑓" --> B

运算#

设 $A,B,D$ 为三个非空集合，称映射 $f: A \times B \to D$ 为 $A$ 与 $B$ 到 $D$ 的一个代数运算。

如果上述 $A,B,D$ 都相等，则称 $f$ 为 $A$ 上的一个二元运算。

性质#

运算可以具有的性质有交换律，结合律，分配律（左分配率和右分配率）。

当满足结合律时，可以定义 $a^n$ ；当同时满足结合律和交换律时，有 $(ab)^n = a^n b^n$ .

注意交换律推不出结合律。譬如一个交换但不结合的运算 $\cdot$ ，那么只保证成立 $a \cdot b \cdot c = b \cdot a \cdot c = c \cdot (a \cdot b) = c \cdot (b \cdot a)$ ，而不保证 $a \cdot c \cdot b$ 与它们相等。也即一定永远是先进行 $a,\ b$ 之间的运算，再与 $c$ 进行运算。

本课程主要研究满足结合律的代数。非结合代数是一门更新的学科。

关系#

设 $A$ 为非空集合，定义“关系”为一种针对 $A$ 中两个元素的性质，使得任意两个元素，或者具有该性质，或者不具有，二者必居其一。

设 $a,\ b \in A$ ，若 $a,\ b$ 具有关系 $\mathrm{R}$ ，记作 $a\mathrm{R}b$ .

记集合 $R = \{~(a,b) \mid a \mathrm{R} b~\} \subseteq A \times A$ ，那么集合 $R$ 和关系 $\mathrm{R}$ 互相唯一确定，今后可以混用。

性质#

关系可以具有的性质有自反性（反身性），对称性，传递性。

自反性： $\forall a \in A,\ a \mathrm R a$
对称性： $a \mathrm R b \Rightarrow b \mathrm{R} a$
传递性： $a \mathrm{R} b,\ b\mathrm{R} c\ \Rightarrow a \mathrm{R} c$

请注意，对称性和传递性不能推出自反性，因为不能假设 $\forall a \in A,\ \exists b \in A,\ a \mathrm{R} b$ .

同时满足这三条性质的关系称为等价关系。

划分#

设 $A$ 为非空集合，如果存在集合的集合 $\mathscr{A} = \{~A_i~\}$ ，使得 $\forall A_i \in \mathscr{A},\ A_i \subseteq A,\ A_i \ne \varnothing$ 且 $\bigcup_i A_i = A$ 且 $\forall i\ne j,\ A_i \cap A_j = \varnothing$ ，则称 $\mathscr{A}$ 为 $A$ 的一个划分。划分也称分类。

定理： $A$ 的一个划分 $\mathscr{A}$ 与 $A$ 上的一个等价关系 $\mathrm{R}$ 互相唯一确定。

由 $\mathscr{A}$ 唯一确定 $\mathrm{R}$ 的证明是简单的，只需要给出一种确定性的 $\mathrm{R}$ 的构造方式，并验证其符合等价关系的性质。

由 $\mathrm{R}$ 唯一确定 $\mathscr{A}$ 的证明需要引入更多概念以阐明。

等价类、商集合、自然映射#

等价类#

设 $A$ 是非空集合， $\mathrm{R}$ 为其上一等价关系，那么对于 $a \in A$ ，定义 $a$ 所在的等价类为集合 $\overline{a} = \{~b \in A \mid a \mathrm{R} b~\}$ ，亦可以记作 $[a]$ .

商集合#

定义 $A$ 对 $\mathrm{R}$ 的商集合为 $A/\mathrm{R} = \{~\overline{a} \mid a \in A~\}$ .

此处由集合的互异性，自动保证了重复的等价类只记一次。

自然映射#

定义 $A$ 到 $A/\mathrm{R}$ 的自然映射为 $\pi : A \to A/\mathrm{R},\ \pi(a)=\overline{a}$ .

此时，利用 $\mathrm{R}$ 的三个性质，可以证明 $A/\mathrm{R}$ 就是 $A$ 的一个划分，从而完成刚才定理的证明。

同余关系#

设 $A$ 是非空集合， $\circ$ 为其上一二元运算， $\mathrm{R}$ 为其上一等价关系，如果满足：

a_1 \mathrm{R} a_2,\ b_1 \mathrm{R} b_2 \Rightarrow a_1 \circ b_1 \ \mathrm{R}\ a_2 \circ b_2

则称 $\mathrm{R}$ 为 $\circ$ 的同余关系。

同余关系给出了一种将 $A$ 上的二元运算延伸到 $A/\mathrm{R}$ 上的一种方法。

定义 $A/\mathrm{R}$ 上的一个二元运算 $\overline{\circ}$ 为 $\overline{a} \overline{\circ} \overline{b} = \overline{a \circ b}$ .

可以把 $\mathrm{R}$ 看作一种“除数”，用来“分类” $A$ ，分类依据就是“余数”，同一个等价类中的元素“余数”相同。这里的“余数”是针对不同的同余元素在二元运算 $\circ$ 之后“余数”相同而言的。

同余关系可以拆分为左同余和右同余。