讲个小故事 III：从集合开始，到抽象代数结构

· · 个人记录

集合

我们今天的故事，从集合开始。

集合是什么？粗略地说，集合就是一堆 确定的 元素所构成的整体。

特别强调「确定的」意味着，给定一个元素，一定能够说出这个元素在不在这个集合里。

比如 1 就在自然数集 \mathbf{N} 中，-1 就不在当中，「乒乓球」也不在当中。

关于集合的严谨定义，可查看 ZFC 公理集合论系统。对于这篇文章来说，没那么重要。

集合常用大写字母表示。单表示集合，没什么其它含义时，通常用字母 S 表示（集合的英文 Set 的首字母）。

看似平平无奇吧？但你可以先提前感叹一下，因为在现代数学的背景下，各种定义几乎全都离不开它！伟大的集合！

不过在那之前，还要再拜访一位大牛：

二元运算

二元运算，就是指接收两个元素，输出一个元素的运算。

四则运算、向量点积、向量数乘、两个元素的 \gcd、两个序列的合并、两种颜色的混合……都可以是二元运算。

二元运算的特性

考虑太多乱七八糟的二元运算有点头昏……还是来点正常点的吧。

封闭性

一个数加上一个数还是一个数，两种颜色混合还是颜色，两个数组合并后还是数组……这就是封闭性。

具体地，若定义在 S 上的二元运算 * 满足对于所有的 s, t \in S, s*t \in S，则称 * 在 S 上满足封闭性。

结合律

小学就学过的加法结合律，乘法结合律……结合律其实就是这么一回事。只是现在，我们有了更通用的解释：

如果 (a * b) * c = a * (b * c)，则称 * 运算满足结合律。

满足结合律就意味着，我们不需要在意先执行哪个运算。上式的括号可以去掉了：a * b * c = (a * b) * c = a * (b * c)。

交换律

小学就学过的加法交换律，乘法交换律……交换律其实也就是这么一回事。只是现在，我们有了更通用的解释：

如果 a * b = b * a，则称 * 运算满足交换律。

分配律

小学就学过乘法分配律……等等，这里面有两个运算，+ 和 \times。所以分配律应该这么表述：

如果 (a + b) \times c = a \times c + b \times c，则称 \times 对于 + 满足分配律。

作为其它扩展思维的例子：+ 对 \max 也满足分配律，即 \max(a, b) + c = \max(a+c, b+c)。当然前提是可以比较。

抽象代数结构

有了集合和二元运算，我们就可以研究更多的东西啦！

群大家族

群的英文是 Group，我们以大写字母 G 来表示相应的集合。

半群

我们来到了第一个神奇的代数结构：半群。

具体的，若代数结构 \left<G, *\right> 满足封闭性和结合律，则称 \left<G, *\right> 是半群。

半群厉害的点在哪？其中一个点是：线段树可以维护它的信息！具体地，给定一个序列 \left< g_1, g_2, \dots, g_n \right> 和任意的区间 [L, R]，线段树就可以在 O(\log n) 的时间里求出 g_L * g_{L + 1} * \cdots * g_R。区间求和，区间求 \max，区间求 \gcd……是不是很熟悉！

幺半群

在半群 \left<G, *\right> 的基础上，如果找得出一个元素 e \in G，使得对于所有的 g \in G, e*g = g*e = g，则称 e 是单位元，或称幺元。称 \left<G, *, e\right> 为幺半群。

比如 \left<\mathbf{N^*}, +\right> 就是半群，而 \left<\mathbf{N}, +, 0\right> 就可以是幺半群，因为 0 的存在。

但即使半群 \left<G, *\right> 不是幺半群，我们也可以强行给集合 G 加入一个元素 e，然后扩展 * 的运算，使得 e*g = g*e = g。这样就给一个半群完成了升级，升级成了幺半群！

群

在幺半群 \left<G, *, e\right> 的基础上，如果对于所有的 g \in G，全都找得出一个元素 g^{-1}，使得 g * g^{-1} = g^{-1} * g = e，则称 g^{-1} 是 g 的逆元，称 \left<G, *\right> 是群。

逆元的存在使得可以定义出运算 * 的逆运算 /：a / b = a * b^{-1}。

举例的话，\left<\mathbf{Z}, +\right> 就是群，每个数的逆元是它的相反数。\left<\mathbf{Z} \setminus \{0\}, \times\right> 也是群，每个数的逆元是它的倒数。\left<\mathbf{R}, \max\right> 定义不出逆元，所以无法构成群。

群更加规整，所有的元素非常和谐，不会有什么元素拥有更高的地位！

阿贝尔群 / 交换群

在群 \left<G, *\right> 的基础上，如果 * 还满足交换律，则称群 \left<G, *\right> 是阿贝尔群，或称交换群。

同样的例子，\left<\mathbf{Z}, +\right> 和 \left<\mathbf{Z} \setminus \{0\}, \times\right> 都是交换群。但矩阵乘法不一定满足交换律，就不好构成交换群。

到了这里，树状数组也有了用武之地！具体的，给定一个序列 \left< g_1, g_2, \dots, g_n \right> 和指定的区间 [1, R]，树状数组也可以在 O(\log n) 的时间里求出 g_1 * g_2 * \cdots * g_R，也可以因此通过计算 (g_1 * g_2 * \cdots * g_R) / (g_1 * g_2 * \cdots * g_L) 求出 g_L * g_{L + 1} * \cdots * g_R，且通常具有比线段树更快的速度！

多个运算的领域

有了很厉害的群大家族，我们可以进一步探索更深的领域——有多个运算的领域！

环

环的英文是 Ring，接下来以首字母大写 R 来表示相应的集合（注意不一定是实数集喔）。

对于一个代数结构 \left<R, +, \times\right>——没错，一个加运算，一个乘运算——如果 \left<R, +\right> 构成交换群，\left<R, \times\right> 构成半群，且 \times 对 + 满足分配律（还记得乘法分配律吗？），则称 \left<R, +, \times\right> 是一个环。

尽管 R 甚至不用非得是数集，为了方便，我们还是用 0 \in R 来表示加运算下的单位元。

为什么叫做环呢？就我个人目前的理解，+ 相当于是给这个环做旋转操作，\times 相当于是以 0 为固定点做缩放操作。

交换环

如果环 \left<R, +, \times\right> 的 \times 也满足交换律，则这个环成为交换环。

我好像说不出什么东西来……

幺环

如果环 \left<R, +, \times\right> 对于 \times 存在单位元 1 \in R 使得 1 \times r = r \times 1 = r，则这个环成为幺环。

我好像还是说不出什么东西来……

除环

如果一个幺环 \left<R, +, \times\right> 对于所有的 r \in R \setminus \{0\} 都有乘法逆元 r^{-1} \in R \setminus \{0\} 使得 r^{-1} \times r = r \times r^{-1} = 1，则这个环升级为除环。

字面意思，可以定义出除法的环：a \div b = a \times b^{-1}。

除了那个 0，它是没有乘法逆元的（

最强最熟悉的环：域

如果如果一个环既是交换环又是除环，则这个环称为域。

因此，域还有一个更简单的表述：能定义出四则运算的代数结构。

这是我们熟悉又陌生的东西，熟悉是因为我们天天都在做四则运算，陌生是因为如果换到一个使用了不那么熟悉的四则运算的域，我们有可能手足无措。

域的英文是 Field，特别强调域时，一般用 F 表示。

加一点新元素！

在数学的发展史上，经常会有给一个代数结构加上点什么东西，会使得更多的东西得到满足。接下来，我们可以一边回顾历史，一边学习一点门道~

复数域的由来

本章假定大家已经大致了解什么是实数域 \mathbf{R}。

TODO……

四则运算的世界

域和四则运算可能比你想象的要强大得多，因为在此基础上可以定义出更多更多的东西。接下来讲的新运算全部基于四则运算。

平方根

TODO……