实用抽代1

参考：Paolo Aluffi, Algebra Chapter 0。以下内容对应原书第一章的前两小节，包含集合论、函数两方面内容。

Set Theory

multiset

多重集即允许元素出现多次的“集合”。严格定义为多重集就是集合+定义在该集合上，值域为正整数的一个函数。这个函数指明了各个元素的“个数”。

singleton

单元集即单元素集合。（注意通过上下文区分“单元集”和“单例模式”）

graph

若$f:A\rightarrow B$是函数，则该函数的图定义为$\Gamma_f=\{(a,b)\in A\times B|b=f(a)\}$

所有$f:A\rightarrow B$的函数的集合记作$B^A$。可以证明：$|B^A|=|B|^{|A|}$

这可以对幂集的记法$2^A$（其实是一个函数集）进行严格的论证。可以将其解释为$2^A=\{f:A\rightarrow \{0,1\}\}$，因此$2^A$中的每一个函数都把$A$中的元素按照取0/取1划分成两部分。因此$2^A$和$A$的幂集同构。

fiber

纤维就是指单点的原象。

inclusion

当$S\sub A$，则可定义一个包含函数$S\rightarrow A$，将自变量映射为自身。

notation for injection/surjection

单射常用$\hookrightarrow$，满射常用$\twoheadrightarrow$。

isomorphism

两个集合$A,B$同构，就是指两个集合之间存在双射，记作$A\cong B$。这个双射可以称为同构映射，记作$f:A\stackrel{\sim}{\rightarrow}B$。

left/right inverse

对$f:A\rightarrow B$而言，若存在函数$g$使得$g\circ f=id_A$（$id_X:X\rightarrow X$指$X$上的恒同映射），则称$g$为$f$的左逆；若$f\circ g=id_B$，则称$g$为$f$的右逆。

注意：左/右指写成“$\circ$”形式的左右。

Prop.2.1 定义域非空的函数$f$有左（右）逆当且仅当它是单（满）射

Pf.

1. 设$g$是$f$的左逆，则$\forall x\neq y$，$g(f(x))=x\neq y=g(f(y))$。由于$g$是函数，因此函数值不等时自变量也不相等，即$f(x)\neq f(y)$，可见$f$是单射。
2. 设$f$是单射。由于定义域非空，则在定义域取一个元素$a$。则构造$g$为：当自变量在$f$的像（值域的一个子集）中时，$g$将其映射到该自变量关于$f$的原像，否则$g$将其映射到$a$。可以验证，$g$是函数，因此是$f$的左逆。
3. 设$g$是$f$的右逆，则对$f$值域中任意$b$，有$f(g(b))=id(b)=b$，因此$f$是满射。
4. 设$f$是满射，则值域中每个元素关于$f$的原像（即“纤维”）非空。因此$g$就定义为将自变量映射到它关于$f$的原像中任意一个元素即可。

Cor.2.2 函数$f$是双射，当且仅当它同时有左逆和右逆。

当函数单射非满射时，左逆一定不止一个；当函数满射非单射时，右逆一定不止一个（这些右逆常被称为sections）

我们此后可以看到，讨论函数双射与否未必要逐个检查集合的各个元素。如果已经有单射/满射的信息，我们就可以在定义“元素”概念的前提下讨论双射等概念。而单射/满射随后可以用更根本的方式加以刻画。

monomorphism（monic）

函数$f$是单态射，若对任意（定义域相同，值域为$f$定义域的）函数$\alpha',\alpha''$，总有：

$f\circ \alpha'=f\circ\alpha''\rightarrow\alpha'=\alpha''$

Prop.2.3 函数$f$是单射，当且仅当其为单态射。

Pf.

1. 若$f$是单射，则其左逆$g$存在，于是$\alpha'=g\circ f\circ \alpha'=g\circ f\circ \alpha''=\alpha''$

2. 若$f$是单态射，则设$\alpha':\{p\}\rightarrow a_1$，$\alpha'':\{p\}\rightarrow a_2$，$a_1,a_2$是$f$定义域中任意两个元素。于是总有$f(a_1)=f(a_2)\rightarrow (\alpha'=\alpha''\leftrightarrow a_1=a_2)$，因此是单射。

epimorphism（epic）

函数$f$​是满态射，若对任意（值域相同，定义域为$f$值域的）函数$\alpha',\alpha''$，总有：

$\alpha'\circ f=\alpha''\circ f\rightarrow\alpha'=\alpha''$

Prop. 函数$f$是满射，当且仅当其为满态射。

Pf.

1. 若$f$是满射，则$f$有右逆$g$，于是$\alpha'=\alpha'\circ f\circ g=\alpha''\circ f\circ g=\alpha''$
2. 若$f$是满态射，假设其不是满射（设值域中有元素$b$不在$f$的像中），则规定$\alpha',\alpha''$的值域为$\{x,y\}$，$\alpha'$把$b$映射到$x$，把其他自变量映射到$y$；$\alpha''$把所有自变量映射到$y$。则虽然$\alpha'\neq\alpha''$，但由于$f$的像中没有$b$，因此复合上$f$后这个差别将被抹去，即$\alpha'\circ f=\alpha'' \circ f$。这与满态射假设矛盾，因此$f$是满射。

以下会给出几个实际的例子。

natural projections

以$A\times B$上定义的自然投影为例：$\pi_A((a,b))=a,\pi_B((a,b))=b$。

自然投影显然是满射。

natural injections

自然单射指$A\rightarrow A\sqcup B$（或$B\rightarrow A\sqcup B$），其将自变量映射到$A\sqcup B$中对应的元素（具体元素的形态要看无交并的定义方式）。

自然单射显然是单射。

canonical projection

设$\sim$是$A$上的一个等价关系，则存在将$A$中元素映射到$A/\sim$相应等价类的满射（记为$A\twoheadrightarrow A/\sim$），这称为标准投影。

canonical decomposition

以下展示如何将任意函数$f:A\rightarrow B$分解为满射、双射和单射的复合。

在$A$定义等价关系$\sim$为”当函数值相等时，相应的自变量等价“。于是：

Thm.2.7（The first isomorphism theorem） $f=f_{cproj}\circ\bar{f}\circ f_{inclu}$，其中$f_{cproj}$就是前面提到的标准投影（满射），$\bar{f}:[a]_{\sim}\mapsto f(a)$是双射，$f_{inclu}$就是包含函数（单射）。用图形表示为（图源原书pp15）：

Pf. 证明的关键是说明这种定义下的$\bar{f}$是函数，而且是双射。

1. 证明$\bar{f}$是函数。根据$\bar{f}:[a]_{\sim}\mapsto f(a)$，只要每个等价类的代表元（即$a$）的选择与$f$的函数值无关，则这个定义就不会把同一个等价类映射为不同的值。由于等价关系$\sim$就是根据$f$函数值相等来定义的，因此代表元选谁都无所谓。因此$\bar{f}$是函数。
2. 设$\bar{f}([a_1]_{\sim})=\bar{f}([a_2]_{\sim})$，则$f(a_1)=f(a_2)$，则$a_1\sim a_2$，因此$[a_1]_{\sim}=[a_2]_{\sim}$，故$\bar{f}$是单射。
3. $\forall b \in im \space f,\exist a\in A,s.t.b=f(a)$，因此$\bar{f}([a]_{\sim})=b$，可见$\bar{f}$是满射。