关于幺半群与交换幺半群二元余积差异的证明问询

背景 #

以下内容摘自Arbib和Manes的《Algebraic approaches to program semantics》，以及Roy L.Crole的《Categories for Types》。

来自Crole的《Categories for Types》 #

定义1： 范畴$\mathcal{C}$中对象$A$和$B$的二元余积由以下部分确定：

• $\mathcal{C}$中的对象$A+B$，
• 两个插入态射$i_A:A\to A+B$和$i_B:B\to A+B$，
  满足：对任意态射$f:A\to C$、$g:B\to C$，存在唯一的态射$[f,g]:A+B\to C$，使得$[f,g]\circ i_A = f$且$[f,g]\circ i_B = g$。

我们可以将这个定义推广到集合索引对象族的余积：给定范畴$\mathcal{C}$中的对象族$(A_i\mid i\in I)$（其中$I$是集合），余积由以下数据确定：

• $\mathcal{C}$中的对象$\sum_{i\in I}A_i$，
• 对每个$j\in I$，态射$i_j:A_j\to \sum_{i\in I}A_i$（称为第$j$个余积插入态射），
  满足：对任意对象$C$和任意态射族$(f_i:A_i\to C\mid i\in I)$，存在唯一的态射$[f_i\mid i\in I]:\sum_{i\in I}A_i\to C$，使得对任意$j\in I$，有$[f_i\mid i\in I]\circ i_j = f_j$。

来自Arbib和Manes的相关内容 #

定义2： Mon（幺半群范畴）或Grp（群范畴）中的余积

• 单元素幺半群/群${e}$显然是两个范畴中的初始对象（即空余积）。
• 设${X_i\mid i\in I}$是非空的幺半群族，令$A$（字母表）为集合$X_i$的不交并，$W$为$A$上所有字构成的集合$A^$。一个字$(a_1,\ldots,a_n)$是约化的*，当且仅当：对所有$j<n$，$i_j\neq i_{j+1}$；且对所有$j\leq n$，$x_j\neq e_j$（其中$a_j=(x_j,i_j)$，$e_j$是$X_{i_j}$的单位元）。若一个字不是约化的，可通过反复应用以下规则进行约化：
  • (a) 合并具有相同$i$标记的相邻元素：$(a_1,\ldots,a_j=(x_j,i),a_{j+1}=(x_{j+1},i),\ldots,a_n)\mapsto (a_1,\ldots,\hat{a}j=(x_jx{j+1},i),a_{j+2},\ldots,a_n)$
  • (b) 删除单位元项：$(a_1,\ldots,a_j=(e_j,i_j),\ldots,a_n)\mapsto (a_1,\ldots,a_{j-1},a_{j+1},\ldots,a_n)$

预设习题 #

预设习题1 #

若幺半群$X$满足对所有$x,y\in X$，$xy=yx$，则称$X$是交换的。令Abm为交换幺半群与幺半群同态构成的范畴。证明：Abm中的积、等化子、余等化子可通过模仿Mon或Grp中的构造得到；模仿Vect（向量空间范畴）的构造来构造Abm中的余积。

预设习题2 #

验证：在Abm中构造的半格的积仍然是半格。陈述并证明关于等化子、余等化子、余积的类似结论。

目标习题 #

将预设习题2中的（交换幺半群，半格）替换为（幺半群，交换幺半群），证明：积、等化子、余等化子的结论仍然成立，但二元余积的结论不成立。

用户问题 #

在上述目标习题中，替换后的表述可理解为：“验证在Mon中构造的交换幺半群的积仍然是幺半群；而对于定义1中的二元余积，结论不成立，因为Mon中的余积与Abm中的余积并不相同。我之前查询过交换幺半群与幺半群的余积相关内容，若二者确实不同构，该如何从数学上证明？或许可以证明它们不同构，但我不确定如何构建证明框架并完成证明。

感谢您的帮助！

解答 #

别担心，我们可以通过具体的例子和矛盾法来清晰证明这个差异：

第一步：选两个简单的交换幺半群 #

咱们取最常见的非平凡交换幺半群——整数加法幺半群$\mathbb{Z} = (\mathbb{Z}, +, 0)$，来对比它和自身在两个范畴里的余积：

• 在Mon（幺半群范畴）中，根据前面的构造，$\mathbb{Z} +{\textbf{Mon}} \mathbb{Z}$是由$\mathbb{Z}$与自身的不交并生成的“约化字幺半群”。简单说，这里的元素是交替来自第一个$\mathbb{Z}$和第二个$\mathbb{Z}$的非零整数串，比如$(1{\text{第一个}\mathbb{Z}}, 2_{\text{第二个}\mathbb{Z}})$，运算就是把串拼接后合并同来源的相邻元素。这个幺半群是非交换的：比如取第一个$\mathbb{Z}$里的$1$和第二个$\mathbb{Z}$里的$1$，把它们相乘（对应幺半群的串拼接运算），得到的$(1,1)$和反过来的$(1,1)$是不同的约化字，没法合并，所以二者不相等。
• 在Abm（交换幺半群范畴）中，按照预设习题的提示（模仿向量空间直和），$\mathbb{Z} +_{\textbf{Abm}} \mathbb{Z}$其实就是$\mathbb{Z}\times\mathbb{Z}$（配逐点加法），这是个交换幺半群，任意两个元素交换运算后结果都一样。

第二步：用矛盾法证明不同构 #

假设这两个余积是同构的，也就是存在一个幺半群同构$\phi: \mathbb{Z} +{\textbf{Mon}} \mathbb{Z} \to \mathbb{Z} +{\textbf{Abm}} \mathbb{Z}$。那$\phi$必须保持运算的交换性：

• 因为$\mathbb{Z} +_{\textbf{Abm}} \mathbb{Z}$是交换的，所以对任意元素$x,y$，$\phi(xy) = \phi(x)\phi(y) = \phi(y)\phi(x) = \phi(yx)$。
• 但$\mathbb{Z} +_{\textbf{Mon}} \mathbb{Z}$里存在不交换的元素对（比如刚才说的两个$1$），也就是$xy \neq yx$，那$\phi(xy) \neq \phi(yx)$，这就和上面的结论矛盾了。

所以这两个余积肯定不同构，也就证明了目标习题里“二元余积结论不成立”的部分。

至于积、等化子、余等化子的结论为啥成立，也很好理解：

• 积：Mon里交换幺半群的积就是集合笛卡尔积配逐点运算，这个积本身既是交换幺半群也是幺半群，在两个范畴里的构造完全一致，所以结论成立。
• 等化子：Mon里两个同态的等化子是原幺半群中满足$f(x)=g(x)$的元素构成的子幺半群，要是原幺半群是交换的，这个子幺半群也必然交换，所以在Abm里也是等化子。
• 余等化子：Mon里的余等化子是原幺半群模掉同余关系后的商，交换幺半群的商还是交换的，所以在Abm里同样是余等化子，构造通用。

这样就完成了整个证明的框架和细节啦～

备注：内容来源于stack exchange，提问作者Seth