密码学数学基础 笔记 10：从集合与映射出发，理解等价关系、商集和映射的典范分解，再用范畴与泛性质统一描述商、积和余积

集合、范畴与泛性质

前面讨论模运算时，整数按照同余关系被分成剩余类；讨论离散对数时，又用到了循环群之间的同构。这些概念都在处理两个问题：哪些差别可以忽略，哪些结构需要保留？

现在从集合与映射开始，把这些问题表述得更精确。先看怎样合并元素、组合集合和分解映射，再逐步转向一种只使用对象、箭头与复合的语言——范畴。其中的核心是泛性质：通过一个对象与其他对象之间的映射关系，刻画它所满足的数学要求

集合的三种构造

并集 $A\cup B$、交集 $A\cap B$ 和差集 $A\setminus B$ 都可以直接用元素的归属来描述。后面更关心三种构造：不交并、笛卡尔积，以及按等价关系取商

不交并：保留元素的来源

设

$$A=\{1,2\},\qquad B=\{2,3\}$$

普通并集为 $A\cup B=\{1,2,3\}$，其中的 $2$ 不再区分来自哪个集合。如果要保留来源，就为两部分添加不同标签，定义不交并

$$\boxed{A\amalg B=(\{0\}\times A)\cup(\{1\}\times B)}$$

这个例子得到

$$A\amalg B=\{(0,1),(0,2),(1,2),(1,3)\}$$

虽然 $(0,2)$ 和 $(1,2)$ 的第二个分量相同，它们仍是不同元素。不交并同时带有两个自然映射

$$i_A:A\to A\amalg B,\quad a\mapsto(0,a)$$

$$i_B:B\to A\amalg B,\quad b\mapsto(1,b)$$

这两个映射都是单射，像彼此不交，并且合起来覆盖整个不交并。对于有限集合，$|A\amalg B|=|A|+|B|$

标签可以换成其他两个不同的符号。所得集合的具体元素会改变，但两部分之间的对应关系仍然明确，后面会用泛性质解释这种构造为什么“在同构意义下唯一”

笛卡尔积：同时记录两个分量

笛卡尔积定义为

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

它同时带有两个自然投影

$$\pi_A:A\times B\to A,\quad\pi_A(a,b)=a$$

$$\pi_B:A\times B\to B,\quad\pi_B(a,b)=b$$

每个投影保留一个坐标。若 $A,B$ 都非空，两个投影都是满射；若 $A\neq\varnothing$ 而 $B=\varnothing$，则 $A\times B=\varnothing$，投影到 $A$ 就不是满射

对于有限集合，$|A\times B|=|A|\,|B|$。不交并中的一个元素选择一个来源，积中的一个元素则同时指定两个分量

相等与同构的区别

三重积可以用不同方式实现，例如

$$(A\times B)\times C,\qquad A\times(B\times C)$$

前者的元素写成 $((a,b),c)$，后者写成 $(a,(b,c))$。它们具有不同的括号结构，但存在自然的双射

$$((a,b),c)\longmapsto(a,(b,c))$$

因此可以写

$$(A\times B)\times C\cong A\times(B\times C)$$

这里的 $\cong$ 表示存在双射。把这些集合视为同一个数学构造时，依据的是明确的对应关系

等价关系、划分与商集

从关系到等价类

集合 $A$ 上的一个二元关系就是 $A\times A$ 的一个子集 $R$。记号 $aRb$ 表示 $(a,b)\in R$

关系 $\sim$ 称为等价关系，如果它满足：

元素 $a$ 的等价类是

$$[a]_{\sim}=\{b\in A:b\sim a\}$$

等价类有一个关键性质：两个等价类要么相等，要么不相交。若 $c\in[a]_{\sim}\cap[b]_{\sim}$，就有 $c\sim a$ 和 $c\sim b$，由对称性与传递性得到 $a\sim b$，进而 $[a]_{\sim}=[b]_{\sim}$

所以全部等价类构成 $A$ 的一个划分：每一块非空，各块两两不交，它们的并为 $A$。反过来，给定一个划分，规定“处于同一块的元素等价”，便得到等价关系

$$\boxed{\text{等价关系}\quad\longleftrightarrow\quad\text{集合的划分}}$$

商集把等价变成相等

把每个等价类当作一个新元素，就得到商集

$$\boxed{A/{\sim}=\{[a]_{\sim}:a\in A\}}$$

商集带有一个典范投影

$$\pi:A\twoheadrightarrow A/{\sim},\qquad a\mapsto[a]_{\sim}$$

它总是满射，而且

$$\boxed{\pi(a)=\pi(b)\quad\Longleftrightarrow\quad a\sim b}$$

因此，取商的作用是把指定的等价关系变成新集合中的相等关系

例如固定 $n\geq2$，在整数集上定义

$$a\sim b\quad\Longleftrightarrow\quad n\mid(a-b)$$

得到的商集就是

$$\mathbb Z/n\mathbb Z=\{[0]_n,[1]_n,\ldots,[n-1]_n\}$$

这里的 $[2]_5$ 是整个集合 $\{2+5k:k\in\mathbb Z\}$，整数 $2$ 只是它的一个代表元。$2$、$7$ 和 $-3$ 都代表同一个商集元素

为什么要检查良定义

若想用代表元定义一个函数

$$F:A/{\sim}\to B,\qquad F([a]_{\sim})=\varphi(a)$$

就必须验证

$$\boxed{a\sim a'\quad\Longrightarrow\quad\varphi(a)=\varphi(a')}$$

同一个输入等价类可以用不同代表元书写，输出必须与这种选择无关。这称为良定义

例如 $F:\mathbb Z/5\mathbb Z\to\mathbb Z$、$F([a]_5)=a$ 就不良定义，因为 $[0]_5=[5]_5$，公式却分别给出 $0$ 和 $5$。若定义 $F([a]_5)$ 为该类中唯一的 $0$ 到 $4$ 之间的整数，才得到一个函数

映射、复合与纤维

函数包含定义域和陪域

一个函数 $f:A\to B$ 为每个 $a\in A$ 指定唯一的 $f(a)\in B$。它可以用图像

$$\Gamma_f=\{(a,f(a)):a\in A\}\subseteq A\times B$$

来记录，但定义域 $A$ 和陪域 $B$ 也是函数的数据。例如

$$f:\mathbb R\to\mathbb R,\quad x\mapsto x^2$$

与

$$g:\mathbb R\to[0,\infty),\quad x\mapsto x^2$$

虽然计算公式相同，满射性却不同：$g$ 是满射，$f$ 不是

对 $S\subseteq A$，定义

$$f(S)=\{f(s):s\in S\},\qquad\operatorname{im}f=f(A)$$

其中 $\operatorname{im}f$ 是函数的像，它可能只是陪域的一个真子集。限制映射 $f|_S:S\to B$ 使用同一规则，并满足 $f|_S=f\circ i$，这里 $i:S\hookrightarrow A$ 是包含映射

复合与交换图

给定 $f:A\to B$ 和 $g:B\to C$，定义

$$(g\circ f)(a)=g(f(a))$$

复合从右向左计算，先执行 $f$，再执行 $g$。它满足结合律和恒等律

$$h\circ(g\circ f)=(h\circ g)\circ f$$

$$f\circ\operatorname{id}_A=f=\operatorname{id}_B\circ f$$

若另有 $k:A\to C$，说下面的图交换，就是要求沿两条路径得到相同的函数，即 $k=g\circ f$

$$\begin{array}{ccc} A&\xrightarrow{f}&B\\ {\scriptstyle k}\downarrow&&\downarrow{\scriptstyle g}\\ C&\xrightarrow{\operatorname{id}_C}&C \end{array}$$

一般地，交换图要求同一起点、同一终点之间的路径复合相等。这里的“交换”描述路径之间的关系，复合运算本身通常不满足交换律

原像与纤维

对任意 $T\subseteq B$，定义原像

$$f^{-1}(T)=\{a\in A:f(a)\in T\}$$

这个记号对所有函数都有意义，不要求 $f$ 存在逆函数。特别地，$f^{-1}(\{b\})$ 称为 $b$ 上的纤维，记录所有产生输出 $b$ 的输入

用纤维可以统一描述三种性质：

所有非空纤维构成定义域的一个划分，这很快就会给出映射的典范分解

用逆映射理解单射、满射和双射

设 $f:A\to B$，$g:B\to A$。根据复合的方向，可以区分：

$$g\circ f=\operatorname{id}_A\qquad\text{左逆}$$

$$f\circ g=\operatorname{id}_B\qquad\text{右逆}$$

左逆与单射

如果 $g\circ f=\operatorname{id}_A$，那么

$$f(a)=f(a')\quad\Longrightarrow\quad g(f(a))=g(f(a'))\quad\Longrightarrow\quad a=a'$$

所以有左逆的函数必为单射

反过来，若 $f$ 是单射且 $A\neq\varnothing$，固定 $a_0\in A$，定义

$$g(b)= \begin{cases} a,&b=f(a)\text{ 对某个 }a\in A\\ a_0,&b\notin\operatorname{im}f \end{cases}$$

单射性保证第一种情形中的 $a$ 唯一，因而 $g$ 良定义，并且 $g(f(a))=a$

这里的非空条件有实际作用：$\varnothing\to\{0\}$ 是单射，但不存在 $\{0\}\to\varnothing$，所以它没有左逆

右逆与满射

如果 $f\circ g=\operatorname{id}_B$，那么每个 $b\in B$ 都满足 $b=f(g(b))$，因此 $f$ 为满射

反过来，若 $f$ 是满射，从每条非空纤维 $f^{-1}(\{b\})$ 中选择一个元素 $g(b)$，就得到右逆。对任意集合上的满射统一作出这种选择，需要选择公理；有限集合的情形只需要有限次选择

右逆也称为截面。它为每个输出挑选一个输入，通常有多种选法

双侧逆必然唯一

双射的每条纤维都只有一个元素，所以可以直接定义逆函数。反过来，若函数有双侧逆，它同时具有单射性与满射性

$$\boxed{f\text{ 是双射}\quad\Longleftrightarrow\quad f\text{ 有双侧逆}}$$

如果 $g_1$ 是左逆，$g_2$ 是右逆，那么

$$\boxed{g_1=g_1\circ(f\circ g_2)=(g_1\circ f)\circ g_2=g_2}$$

因此，只要左逆与右逆同时存在，它们就必然相同，成为唯一的双侧逆。这个证明只用了复合、结合律与恒等映射，完全可以移到更一般的环境中

任意映射的典范分解

给定任意函数 $f:A\to B$，定义

$$a\sim_f a'\quad\Longleftrightarrow\quad f(a)=f(a')$$

等号的自反性、对称性与传递性保证 $\sim_f$ 是等价关系，它的等价类恰好是 $f$ 的非空纤维

现在定义

$$\widetilde f:A/{\sim_f}\to\operatorname{im}f,\qquad \widetilde f([a]_{\sim_f})=f(a)$$

这个映射满足：

1. 良定义：$[a]_{\sim_f}=[a']_{\sim_f}$ 意味着 $f(a)=f(a')$
2. 单射：$\widetilde f([a])=\widetilde f([a'])$ 意味着 $f(a)=f(a')$，进而 $[a]=[a']$
3. 满射：任意 $b\in\operatorname{im}f$ 都可以写成 $f(a)=\widetilde f([a])$

于是得到典范分解

$$\boxed{ A\xrightarrow{\pi}A/{\sim_f} \xrightarrow{\widetilde f}\operatorname{im}f \xrightarrow{\iota}B }$$

其中 $\pi$ 是满射，$\widetilde f$ 是双射，$\iota$ 是包含单射，并且

$$\boxed{f=\iota\circ\widetilde f\circ\pi,\qquad A/{\sim_f}\cong\operatorname{im}f}$$

这三个步骤分别是：合并产生同一输出的输入，把每个等价类对应到它的输出，再将像包含到陪域中。“典范”强调这些映射由 $f$ 本身确定，不需要任意挑选代表元

例如取 $f:\mathbb Z\to\mathbb Z$、$f(a)=a^2$。此时 $a\sim_f b$ 当且仅当 $a=b$ 或 $a=-b$，商集的元素为

$$\{0\},\ \{-1,1\},\ \{-2,2\},\ldots$$

它们分别对应像中的 $0,1,4,\ldots$。这个分解也是以后群与环的第一同构定理的集合层面原型

范畴：对象、态射与复合

函数的复合满足结合律，恒等函数充当单位元。保留这些规则，就得到范畴的基本定义

一个范畴 $\mathsf C$ 包含：

1. 一类对象，记为 $\operatorname{Obj}(\mathsf C)$
2. 对每对对象 $A,B$，一组从 $A$ 到 $B$ 的态射，记为 $\operatorname{Hom}_{\mathsf C}(A,B)$
3. 每个对象上的恒等态射 $1_A:A\to A$
4. 对可衔接的态射 $f:A\to B$、$g:B\to C$，指定复合 $g\circ f:A\to C$

这些数据满足

$$\boxed{h\circ(g\circ f)=(h\circ g)\circ f,\qquad f\circ1_A=f=1_B\circ f}$$

每个态射都有确定的起点和终点。对象不一定是集合，态射也不一定是函数；只要上述数据与规则成立，就可以构成范畴

这里考虑的范畴中，每个 $\operatorname{Hom}$ 都是集合，称为局部小范畴。对象整体则允许构成一个类，因为“所有集合”不能组成一个集合；若对象和态射的全体也都是集合，就称为小范畴

集合范畴与带结构的范畴

最直接的例子是集合范畴 $\mathsf{Set}$：对象为集合，态射为函数，复合为函数复合。若用 $B^A$ 表示从 $A$ 到 $B$ 的全部函数，则

$$\operatorname{Hom}_{\mathsf{Set}}(A,B)=B^A$$

类似地，可以让对象携带更多结构，并要求态射保持这些结构：

例如群同态 $f:G\to H$ 必须满足 $f(xy)=f(x)f(y)$。同一批对象如果允许不同的态射，就可能得到不同的范畴，因此判断性质时需要先明确箭头是什么

预序也能构成范畴

设集合 $P$ 上的关系 $\preceq$ 具有自反性和传递性，即为一个预序。把 $P$ 的元素作为对象，并规定

$$\operatorname{Hom}(a,b)= \begin{cases} \{(a,b)\},&a\preceq b\\ \varnothing,&a\npreceq b \end{cases}$$

自反性提供恒等态射 $(a,a)$，传递性允许定义

$$(b,c)\circ(a,b)=(a,c)$$

任意两个固定对象之间至多有一条箭头，因此，只要两条路径的起点与终点相同，复合就必然相同。结合律、恒等律以及所有已画出的图的交换性都随之成立

三个具体例子是：

• 相等关系给出离散范畴，它只有恒等态射
• $(\mathbb Z,\leq)$ 中，存在箭头 $a\to b$ 当且仅当 $a\leq b$
• 固定集合 $S$ 的幂集 $\mathcal P(S)$ 配上包含关系，得到箭头 $A\to B$ 当且仅当 $A\subseteq B$ 的范畴

这类例子把“箭头”解释为关系成立的记录，说明范畴的定义确实不依赖元素之间的函数

同构、自同构与群胚

同构就是可逆的态射

态射 $f:A\to B$ 称为同构，如果存在态射 $g:B\to A$ 满足

$$\boxed{g\circ f=1_A,\qquad f\circ g=1_B}$$

前面证明双侧逆唯一时，只用了范畴公理，所以在这里依然成立。可以将唯一的逆记为 $f^{-1}$，并且

$$1_A^{-1}=1_A,\qquad(f^{-1})^{-1}=f,\qquad (g\circ f)^{-1}=f^{-1}\circ g^{-1}$$

恒等态射、取逆和复合分别保证同构关系具有自反性、对称性和传递性。存在某个同构 $A\to B$ 时，记 $A\cong B$

“同构”总是相对于某个范畴而言。在 $\mathsf{Set}$ 中，同构就是双射；在 $\mathsf{Grp}$ 中，同构还必须保持群运算；在 $(\mathbb Z,\leq)$ 中，同时存在 $a\to b$ 与 $b\to a$ 意味着 $a\leq b$ 且 $b\leq a$，所以只有恒等态射可逆

自同构自然组成群

从对象 $A$ 到自身的态射称为自态射，全体记为

$$\operatorname{End}_{\mathsf C}(A)=\operatorname{Hom}_{\mathsf C}(A,A)$$

它们在复合下封闭，满足结合律，并含有单位元 $1_A$，因此组成一个幺半群。可逆的自态射称为自同构，全体记为

$$\operatorname{Aut}_{\mathsf C}(A)\subseteq\operatorname{End}_{\mathsf C}(A)$$

自同构对复合与取逆都封闭，因此 $\operatorname{Aut}_{\mathsf C}(A)$ 在复合下组成群。例如，有限集合的自同构就是它的所有置换，向量空间的自同构就是可逆线性变换

如果一个范畴中的每条态射都可逆，就称为群胚。等价关系给出的范畴就是群胚：对称性为每条箭头提供反向箭头。只有一个对象的群胚，则可以直接把它的态射看成一个群的元素

单态与满态：用消去律描述映射

同构可以用逆来定义。对于单射和满射，还可以找到只使用复合的描述

单态是左消去

态射 $f:A\to B$ 称为单态（monomorphism），如果对任意对象 $Z$ 和任意两条态射 $\alpha,\alpha':Z\to A$，都有

$$\boxed{f\circ\alpha=f\circ\alpha'\quad\Longrightarrow\quad\alpha=\alpha'}$$

即在复合表达式中，可以从左边消去 $f$

在 $\mathsf{Set}$ 中，单射显然满足此性质：对每个 $z\in Z$，由 $f(\alpha(z))=f(\alpha'(z))$ 得到 $\alpha(z)=\alpha'(z)$

反过来，假设 $f$ 是单态且 $f(a)=f(a')$。取单点集 $Z=\{*\}$，定义 $\alpha(*)=a$、$\alpha'(*)=a'$，则 $f\circ\alpha=f\circ\alpha'$。消去 $f$ 得到 $\alpha=\alpha'$，所以 $a=a'$

因此

$$\boxed{\mathsf{Set}\text{ 中：单态}\quad\Longleftrightarrow\quad\text{单射}}$$

这个证明也说明，集合中的一个元素可以用一条从单点集出发的箭头来表示

满态是右消去

态射 $f:A\to B$ 称为满态（epimorphism），如果对任意对象 $Z$ 和任意 $\beta,\beta':B\to Z$，都有

$$\boxed{\beta\circ f=\beta'\circ f\quad\Longrightarrow\quad\beta=\beta'}$$

在 $\mathsf{Set}$ 中，满射满足此性质，因为每个 $b\in B$ 都能写成 $f(a)$，所以 $\beta(f(a))=\beta'(f(a))$ 足以推出 $\beta(b)=\beta'(b)$

反过来，如果 $f$ 不是满射，取 $b_0\in B\setminus\operatorname{im}f$，定义两个函数 $B\to\{0,1\}$：

$$\beta(b)=0,\qquad \beta'(b)= \begin{cases} 1,&b=b_0\\ 0,&b\neq b_0 \end{cases}$$

它们在 $\operatorname{im}f$ 上相同，所以 $\beta\circ f=\beta'\circ f$，但 $\beta\neq\beta'$，违反满态条件。因此

$$\boxed{\mathsf{Set}\text{ 中：满态}\quad\Longleftrightarrow\quad\text{满射}}$$

这两个消去律的证明都不需要选择公理

一般范畴中的差别

有左逆的态射一定是单态：在等式 $f\circ\alpha=f\circ\alpha'$ 左边复合左逆即可。有右逆的态射一定是满态，证明类似

但消去律不保证逆态射存在。例如在 $(\mathbb Z,\leq)$ 中，任意两个对象之间至多有一条箭头，单态和满态条件中的平行态射本来就相同。因此每条箭头都是单态，也是满态

特别地，$2\to3$ 同时是单态和满态，却没有逆箭头 $3\to2$。所以一般范畴中

$$\boxed{\text{单态且满态}\quad\not\Longrightarrow\quad\text{同构}}$$

即使态射本身是集合函数，也必须检查逆函数是否保持所需结构。群同态

$$\pi:\mathbb Z\twoheadrightarrow\mathbb Z/2\mathbb Z$$

作为集合函数可以有右逆，例如把 $[0]_2,[1]_2$ 分别选回 $0,1$。但它没有群同态右逆：若 $s$ 是这样的右逆，则

$$2s([1]_2)=s(2[1]_2)=s([0]_2)=0$$

在整数加法群中只能有 $s([1]_2)=0$，这与 $\pi(s([1]_2))=[1]_2$ 矛盾

把带有映射的对象组成新范畴

泛性质经常要同时记录一个对象和它附带的映射。切片范畴与余切片范畴提供了直接的组织方式

切片范畴：固定终点

固定 $\mathsf C$ 中的对象 $A$，定义切片范畴 $\mathsf C/A$

• 对象是一条态射 $f:Z\to A$
• 从 $(Z_1,f_1)$ 到 $(Z_2,f_2)$ 的态射，是满足 $f_2\circ\sigma=f_1$ 的 $\sigma:Z_1\to Z_2$

其条件可以画成交换图

$$\begin{array}{ccc} Z_1&\xrightarrow{\sigma}&Z_2\\ {\scriptstyle f_1}\downarrow&&\downarrow{\scriptstyle f_2}\\ A&\xrightarrow{1_A}&A \end{array}$$

若再有 $\tau:Z_2\to Z_3$ 满足 $f_3\circ\tau=f_2$，则

$$f_3\circ(\tau\circ\sigma)=(f_3\circ\tau)\circ\sigma =f_2\circ\sigma=f_1$$

所以复合仍是切片范畴中的态射。恒等态射和结合律也由 $\mathsf C$ 继承

例如 $\mathsf C=(\mathbb Z,\leq)$，固定 $A=3$。对象就是箭头 $n\to3$，即整数 $n\leq3$；对象之间仍按照整数的大小关系连接

余切片范畴：固定起点

固定起点 $A$，得到余切片范畴 $A/\mathsf C$

• 对象是一条态射 $f:A\to Z$
• 从 $(Z_1,f_1)$ 到 $(Z_2,f_2)$ 的态射，是满足 $\sigma\circ f_1=f_2$ 的 $\sigma:Z_1\to Z_2$

取 $\mathsf C=\mathsf{Set}$、$A=\{*\}$，一条函数 $\{*\}\to Z$ 等价于在 $Z$ 中指定一个元素 $z_0$。因此对象可以写成 $(Z,z_0)$，称为带基点集合，态射则是满足

$$\sigma(z_0)=w_0$$

的函数 $\sigma:(Z,z_0)\to(W,w_0)$。这里每个对象都带有一个指定元素，态射必须保持它

始对象、终对象与唯一同构

“存在且唯一”的两个方向

对象 $I$ 称为始对象，如果对每个对象 $X$，恰有一条态射 $I\to X$

对象 $T$ 称为终对象，如果对每个对象 $X$，恰有一条态射 $X\to T$

$$\boxed{ |\operatorname{Hom}(I,X)|=1,\qquad |\operatorname{Hom}(X,T)|=1 }$$

始对象的英文是 initial object，终对象也称 terminal object 或 final object。关键是每个相关的 $\operatorname{Hom}$ 都恰有一个元素，既要求存在，又要求唯一

在 $\mathsf{Set}$ 中，空集是始对象，因为从空集到任意集合恰有一个空函数；任何单点集都是终对象，因为任意集合到单点集的函数都被唯一确定

在偏序范畴中，始对象是最小元素，终对象是最大元素。因此 $(\mathbb Z,\leq)$ 两者都没有；而 $(\mathcal P(S),\subseteq)$ 的始对象为 $\varnothing$，终对象为 $S$

如果一个对象同时为始对象和终对象，就称为零对象。例如群范畴中的平凡群具有此性质

为什么唯一到唯一同构

假设 $I_1,I_2$ 都是始对象。由定义，分别存在唯一的态射

$$f:I_1\to I_2,\qquad g:I_2\to I_1$$

复合 $g\circ f$ 是 $I_1$ 的自态射。由于 $I_1$ 是始对象，它的自态射只有一条，而恒等态射已经存在，所以

$$g\circ f=1_{I_1}$$

同理 $f\circ g=1_{I_2}$，因而 $f$ 是同构。并且从 $I_1$ 到 $I_2$ 本来就只有这一条态射，所以同构也是唯一的

终对象的证明完全对偶，将箭头方向反过来即可。因此

$$\boxed{\text{始对象与终对象若存在，都在唯一同构意义下唯一}}$$

普通的 $A\cong B$ 只保证某个同构存在，可能有很多选择。泛性质给出的唯一性更强，但唯一性始终针对相应范畴中的态射；若对象附带投影、嵌入等结构映射，同构也必须与这些映射相容

泛性质：通过唯一的映射刻画构造

一个构造的泛性质，可以表述为它是某个适当范畴中的始对象或终对象。常见形式是：给定任意满足条件的对象与映射，存在唯一的态射，使指定图交换

读这样的陈述时，需要明确三件事：候选对象携带哪些数据，候选之间的态射满足哪些条件，以及最终寻找的是始对象还是终对象

下面重新考察商集、积与不交并，把它们的元素定义转化为映射性质

商集的泛性质

固定集合 $A$ 上的等价关系 $\sim$，以及典范投影

$$\pi:A\to A/{\sim}$$

考虑任意函数 $\varphi:A\to Z$，要求它对等价的输入给出相同输出：

$$a\sim a'\quad\Longrightarrow\quad\varphi(a)=\varphi(a')$$

商集的泛性质是：存在唯一的函数 $\overline\varphi:A/{\sim}\to Z$，使得

$$\boxed{\varphi=\overline\varphi\circ\pi}$$

对应的图为

$$\begin{array}{ccc} A&\xrightarrow{\pi}&A/{\sim}\\ {\scriptstyle\varphi}\downarrow&&\downarrow{\scriptstyle\overline\varphi}\\ Z&\xrightarrow{\operatorname{id}_Z}&Z \end{array}$$

存在性与唯一性各来自哪里

为了让图交换，$\overline\varphi$ 必须满足

$$\overline\varphi([a]_{\sim})=\varphi(a)$$

如果 $[a]_{\sim}=[a']_{\sim}$，则 $a\sim a'$，由假设得到 $\varphi(a)=\varphi(a')$。因此公式良定义，给出所需的映射，证明了存在性

另一方面，每个等价类都能写成 $\pi(a)$，所以任何满足交换条件的映射都必须采用这个公式，证明了唯一性

这可以理解为：只要 $\varphi$ 已经忽略了等价元素之间的差别，就能先把输入送到商集，再从商集计算输出，而且第二步被唯一确定

它是哪一个范畴中的始对象

构造一个辅助范畴，其对象为满足上述条件的 $(Z,\varphi:A\to Z)$，态射

$$(Z_1,\varphi_1)\to(Z_2,\varphi_2)$$

是满足 $\sigma\circ\varphi_1=\varphi_2$ 的函数 $\sigma:Z_1\to Z_2$。这就是余切片范畴 $A/\mathsf{Set}$ 中，由那些在等价类上取常值的映射组成的部分

泛性质恰好说明 $(A/{\sim},\pi)$ 是这个辅助范畴的始对象。因此完整的商构造需要同时记录商集和投影

用泛性质重新看典范分解

回到函数 $f:A\to B$ 所诱导的等价关系 $\sim_f$。把陪域缩小到像，得到满射

$$q:A\to\operatorname{im}f,\qquad q(a)=f(a)$$

它也满足同一个泛性质。若 $\varphi$ 在 $f$ 的纤维上取常值，就可以定义

$$u:\operatorname{im}f\to Z,\qquad u(f(a))=\varphi(a)$$

当 $f(a)=f(a')$ 时，$a\sim_f a'$，所以 $\varphi(a)=\varphi(a')$，保证良定义；而 $q$ 满射，保证 $u$ 唯一

于是 $(A/{\sim_f},\pi)$ 与 $(\operatorname{im}f,q)$ 都是同一个辅助范畴中的始对象，必有唯一的相容同构

$$\widetilde f:A/{\sim_f}\xrightarrow{\cong}\operatorname{im}f, \qquad\widetilde f\circ\pi=q$$

典范分解中间的双射，由此成为泛性质的直接结果

积的泛性质

给定对象 $A,B$，一个积由对象 $P$ 与两条态射

$$\pi_A:P\to A,\qquad\pi_B:P\to B$$

组成，并满足：对任意对象 $Z$ 和两条态射 $f_A:Z\to A$、$f_B:Z\to B$，存在唯一的 $\sigma:Z\to P$，使

$$\boxed{\pi_A\circ\sigma=f_A,\qquad\pi_B\circ\sigma=f_B}$$

在 $\mathsf{Set}$ 中，$P=A\times B$ 与两个坐标投影满足此性质。所需的函数必定是

$$\boxed{\sigma(z)=(f_A(z),f_B(z))}$$

这个公式显然使两个等式成立；反过来，两个等式分别指定 $\sigma(z)$ 的第一和第二坐标，所以 $\sigma$ 唯一。这个映射通常记为 $\langle f_A,f_B\rangle$

因此，给出一条到积的映射，等价于给出分别到两个因子的映射，可写为

$$\operatorname{Hom}(Z,A\times B) \cong\operatorname{Hom}(Z,A)\times\operatorname{Hom}(Z,B)$$

积是候选范畴中的终对象

考虑所有三元组 $(Z,f_A,f_B)$。从 $(Z,f_A,f_B)$ 到 $(W,g_A,g_B)$ 的态射 $\sigma:Z\to W$ 必须同时满足

$$g_A\circ\sigma=f_A,\qquad g_B\circ\sigma=f_B$$

积的泛性质就是：$(P,\pi_A,\pi_B)$ 是这个范畴中的终对象。因此积是在保持两个投影的唯一同构意义下唯一

例如两个集合积即使有相同的元素个数，也不能任意选择一个双射作为积之间的比较映射；它还必须满足与指定投影的交换条件

偏序中的积是最大下界

在偏序范畴中，设 $p$ 是 $a,b$ 的积。两个投影意味着

$$p\leq a,\qquad p\leq b$$

而任意共同下界 $z$ 都有箭头 $z\to a$、$z\to b$，泛性质要求存在箭头 $z\to p$，即

$$z\leq a\text{ 且 }z\leq b\quad\Longrightarrow\quad z\leq p$$

这正是最大下界的定义。因此在 $(\mathbb Z,\leq)$ 中，积为 $\min(a,b)$；在 $(\mathcal P(S),\subseteq)$ 中，积为 $A\cap B$

余积的泛性质

把积的定义中所有箭头反向，就得到余积。它由对象 $Q$ 与两条态射

$$i_A:A\to Q,\qquad i_B:B\to Q$$

组成，并要求：对任意对象 $Z$ 和态射 $f_A:A\to Z$、$f_B:B\to Z$，存在唯一的 $\sigma:Q\to Z$，满足

$$\boxed{\sigma\circ i_A=f_A,\qquad\sigma\circ i_B=f_B}$$

集合中的余积是不交并

取 $Q=A\amalg B$，使用带标签的构造，定义

$$\sigma(c)= \begin{cases} f_A(a),&c=(0,a)\\ f_B(b),&c=(1,b) \end{cases}$$

两部分不交，所以定义不冲突；两部分覆盖 $A\amalg B$，所以整个函数被唯一确定。于是

$$\operatorname{Hom}(A\amalg B,Z) \cong\operatorname{Hom}(A,Z)\times\operatorname{Hom}(B,Z)$$

即给出一条从余积出发的映射，等价于分别给出从两个分量出发的映射

这也解释了为什么普通并集一般不能充当集合范畴中的余积：如果 $A$ 与 $B$ 有共同元素，而 $f_A$ 与 $f_B$ 在该元素处取值不同，就无法把两者拼成 $A\cup B$ 上的一个函数。不交并的标签保留了两个独立的输入位置

与积的候选范畴对偶，余积是所有 $(Z,f_A:A\to Z,f_B:B\to Z)$ 组成的范畴中的始对象，比较态射需要保持这两条结构映射

不同范畴中的积与余积

在偏序范畴中，把最大下界的推导反向，就得到余积是最小上界。几个例子可以并列比较：

最后一行尤其值得与前面的数论联系起来。最大公因数 $d$ 满足 $d\mid a$、$d\mid b$，且任意共同因子 $c$ 都满足 $c\mid d$，恰好是整除关系中的最大下界。最小公倍数则是同一偏序中的最小上界

同一个“积”的定义可以得到有序对、较小整数、交集或最大公因数，差别来自所处范畴及其箭头的含义

空积与空余积

若把积推广到零个因子，任何对象 $Z$ 都没有分量映射需要指定，泛性质就要求存在唯一的 $Z\to P$。因此空积是终对象

类似地，空余积是始对象。在 $\mathsf{Set}$ 中，空积可以取任意单点集，空余积则为空集

这也说明，“所有二元积都存在”和“所有有限积都存在”之间还差一个终对象。$(\mathbb Z,\leq)$ 有二元积与二元余积，但没有空积和空余积

带相容条件的积：纤维积

积允许同时记录两个分量。如果两个分量还必须在某个共同目标中给出相同结果，就得到纤维积，也称拉回

给定集合映射 $\alpha:A\to C$、$\beta:B\to C$，定义

$$\boxed{A\times_C B=\{(a,b)\in A\times B:\alpha(a)=\beta(b)\}}$$

它带有投影 $p_A:A\times_C B\to A$、$p_B:A\times_C B\to B$，并使下图交换

$$\begin{array}{ccc} A\times_C B&\xrightarrow{p_B}&B\\ {\scriptstyle p_A}\downarrow&&\downarrow{\scriptstyle\beta}\\ A&\xrightarrow{\alpha}&C \end{array}$$

若 $f_A:Z\to A$、$f_B:Z\to B$ 满足 $\alpha\circ f_A=\beta\circ f_B$，那么

$$\sigma(z)=(f_A(z),f_B(z))$$

确实落在 $A\times_C B$ 中，并且是唯一满足 $p_A\circ\sigma=f_A$、$p_B\circ\sigma=f_B$ 的映射。这里，相容条件保证存在性，两个投影保证唯一性

例如取 $A=B=\mathbb Z$、$C=\mathbb Z/2\mathbb Z$，令 $\alpha,\beta$ 都是模 $2$ 投影，则

$$\mathbb Z\times_{\mathbb Z/2\mathbb Z}\mathbb Z =\{(a,b)\in\mathbb Z^2:a\equiv b\pmod2\}$$

普通积记录任意整数对，纤维积记录奇偶性相同的整数对。这是在积的构造中加入交换条件的一个具体例子

回到模运算与密码学中的代数结构

商集上的运算需要与等价关系相容

整数模 $n$ 的加法与乘法定义为

$$[a]_n+[b]_n=[a+b]_n,\qquad [a]_n[b]_n=[ab]_n$$

它们都要通过良定义检查。若 $a\equiv a'\pmod n$、$b\equiv b'\pmod n$，则

$$(a+b)-(a'+b')=(a-a')+(b-b')$$

以及

$$ab-a'b'=a(b-b')+b'(a-a')$$

都被 $n$ 整除，因此更换代表元不会改变结果。这一步让商集进一步成为带有加法与乘法的代数结构，也是以后构造商群、商环时需要解决的问题

循环群是整数按周期取商

设 $G=\langle g\rangle$ 的阶为 $N$，考虑

$$f:\mathbb Z\to G,\qquad k\mapsto g^k$$

因为 $g$ 的阶为 $N$，有

$$g^a=g^b\quad\Longleftrightarrow\quad N\mid(a-b)$$

所以 $f$ 诱导的等价关系正是模 $N$ 同余。典范分解给出

$$\boxed{\mathbb Z/N\mathbb Z\xrightarrow{\cong}G,\qquad[k]_N\mapsto g^k}$$

而 $g^{a+b}=g^ag^b$ 表明这个双射还保持群运算，因此是加法群与乘法群之间的同构。离散对数求的正是它的逆；同构的存在说明结构一致，计算逆映射的成本仍取决于具体表示

CRT 把一个商结构分解成积

若 $m,n$ 互素，中国剩余定理给出双射

$$\Phi:\mathbb Z/(mn)\mathbb Z \longrightarrow\mathbb Z/m\mathbb Z\times\mathbb Z/n\mathbb Z$$

$$[x]_{mn}\longmapsto([x]_m,[x]_n)$$

它把两个模约化映射配成一条到积的映射，并且保持加法与乘法。例如模 $15$ 的一个剩余类，可以通过模 $3$ 和模 $5$ 的两个坐标来描述

积的泛性质保证两个坐标映射唯一确定 $\Phi$；它进一步是双射，则使用了 $m,n$ 互素这一条件和中国剩余定理。由此，模运算中的等价类、指数映射中的周期、CRT 中的局部坐标，都可以放入商、同构与积的统一语言中理解