自由幺半群
| 自由幺半群 | |
|---|---|
| 术语名称 | 自由幺半群 |
| 英语名称 | free monoid |
| 自由半群 | |
|---|---|
| 术语名称 | 自由半群 |
| 英语名称 | free semigroup |
集合上的自由幺半群(free group)/自由半群(free semigroup)指由给定集合生成，此外没有任何额外约束的幺半群/半群。 也说一个可以看作这样生成的幺半群/半群是自由的(free)。
“自由(free)”是指不假定任何关系，对这个集合，使用一个“无关”的运算，并增加元素使运算保证对应公理，（不再附加任何其他条件），此时得到的就是其上的自由幺半群或自由半群。“无关”的运算指集合中没有任何几个元素之间有运算关系，因此没有任何特殊结构。
自然数加法半群同构于单元素集上的自由幺半群，正整数加法半群则是自由半群，因此自由群对应可以看作其推广。
定义
泛性质
对集合 [math]\displaystyle{ A }[/math] ，有范畴 [math]\displaystyle{ \mathcal{F}^A }[/math] 满足：
- 范畴中的对象是幺半群/半群与从 [math]\displaystyle{ A }[/math] 到这个幺半群/半群的映射所构成的有序对 [math]\displaystyle{ (j,G) }[/math] ，
- 范畴中的态射是满足以下交换图的幺半群同态/半群同态 [math]\displaystyle{ \varphi }[/math] ，
[math]\displaystyle{ \begin{array}{rcl} G_1 & \xrightarrow{\varphi} & G_2 \\ {\small j_1} \uparrow & \nearrow & {\small j_2} \\ A && \\ \end{array} }[/math]
其中可以认为 [math]\displaystyle{ A,j_1,G_1,j_2,G_2 }[/math] 是集合范畴中的对象和态射， [math]\displaystyle{ G_1,G_2,\varphi }[/math] 是幺半群范畴（半群范畴）中的对象和态射。
则范畴 [math]\displaystyle{ \mathcal{F}^A }[/math] 中必然存在一个始对象，称为集合 [math]\displaystyle{ A }[/math] 上的自由幺半群(free monoid over/on [math]\displaystyle{ A }[/math] )/自由半群(free semigoup over/on [math]\displaystyle{ A }[/math] )。
其存在性由下述构造保证。
构造定义
注：这一定义中出现的中间术语不是固定名称，不同的材料中有不同的名称选取。
对集合 [math]\displaystyle{ A }[/math] ，称 [math]\displaystyle{ A }[/math] 为字母表(alphabet)，将 [math]\displaystyle{ A }[/math] 中的每一个元素称为一个字母(letter)，并称字母的连接 [math]\displaystyle{ a_1 a_2 \cdots a_n }[/math] 为一个字/词(word)，其中 [math]\displaystyle{ a_i \in A }[/math] 。其中字母的个数 [math]\displaystyle{ n }[/math] 称为字的长度(length)。特别地， 0 个字母的连接也是一个字，称为空字(empty word)。将所有的字构成的集合记作 [math]\displaystyle{ A^* }[/math] ，在形式语言理论中也称为集合 [math]\displaystyle{ A }[/math] 的 Kleene 闭包。所有非空字构成的集合记作 [math]\displaystyle{ A^+ }[/math] ，在形式语言理论中也称为集合 [math]\displaystyle{ A }[/math] 的 Kleene+ 闭包。
对字 [math]\displaystyle{ a_1 a_2 \cdots a_m \in A^* }[/math] 和 [math]\displaystyle{ b_1 b_2 \cdots b_n \in A^* }[/math] ，将 [math]\displaystyle{ a_1 a_2 \cdots a_m b_1 b_2 \cdots b_n \in A^* }[/math] 定义为 [math]\displaystyle{ A^* }[/math] 上的连接(concatenation)。类似定义 [math]\displaystyle{ A^+ }[/math] 上的连接。
则可以证明 [math]\displaystyle{ A^* }[/math] 关于 [math]\displaystyle{ A^* }[/math] 上的连接构成一个幺半群。 且此时可证明其由 [math]\displaystyle{ A }[/math] 生成，且 [math]\displaystyle{ A }[/math] 是一个自由生成元集，即不能由这个集合中的元素运算出运算的幺元，即空字。 这样构造出来的群满足以上始对象的要求。
同时，可证明 [math]\displaystyle{ A^+ }[/math] 关于 [math]\displaystyle{ A^+ }[/math] 上的连接是以上幺半群去除幺元后的半群。
相关定义
集合 [math]\displaystyle{ A }[/math] 称为自由幺半群 [math]\displaystyle{ A^* }[/math] /自由半群 [math]\displaystyle{ A^+ }[/math] 的一组基/基底(base)，其元素称为自由幺半群/自由半群的生成元(generator)，这组基底的势即生成元的个数称为自由幺半群/自由半群的秩(rank)。
如果一个幺半群/半群可以看作由其中一部分元素生成，称这个幺半群/半群是自由的(free)。