本页使用了标题或全文手工转换

幺半群

维基百科,自由的百科全书
跳转至: 导航搜索
群论
Rubik's cube.svg

抽象代數此一數學分支中,幺半群是指一個帶有可結合二元運算單位元代數結構。么半群在許多的數學分支中都會出現。在幾何學中,么半群捉取了函數複合的概念;更確切地,此一概念是從範疇論中抽象出來的,之中的么半群是個帶有一個物件的範疇。么半群也常被用來當做電腦科學的堅固代數基礎;在此,變換么半群語法么半群被用來描述有限狀態自動機,而跡么半群歷史么半群則是做為進程演算並行計算的基礎。么半群的研究中一些較重要的結論有克羅恩-羅德斯定理星高問題

定義[编辑]

么半群是一個帶有二元運算 *: M × MM 的集合 M ,其符合下列公理:

  • 結合律:對任何在 M 內的abc , (a*b)*c = a*(b*c) 。
  • 單位元:存在一在 M 內的元素e,使得任一於 M 內的 a 都會符合 a*e = e*a = a

通常也會多加上另一個公理:

  • 封閉性:對任何在 M 內的 aba*b 也會在 M 內。

但這不是必要的,因為在二元運算中即內含了此一公理。

另外,么半群也可以說是帶有單位元半群

么半群除了沒有逆元素之外,滿足其他所有的公理。因此,一個帶有逆元素的么半群和群是一樣的。

生成元和子么半群[编辑]

么半群 M子么半群是指一個在 M 內包含著單位元且具封閉性(即若x,yN ,則 x*yN )的子集 N。很明顯地, N 自身會是個么半群,在導自 M 的二元運算之下。等價地說,子么半群是一個子集 N ,其中 N=N* ,且上標 * 為克萊尼星號。對任一於 M 內的子集 N 而言,子么半群 N* 會是包含著 N 的最小么半群。

子集 N 被稱之為 M生成元,若且唯若 M=N*。若 N 是有限的, M 即被稱為是有限生成的。

可交換么半群[编辑]

運算為可交換的么半群稱之為可交換么半群(或較少地,稱之為阿貝爾么半群)。可交換么半群經常會將運算寫成加號。每個可交換么半群都自然會有一個它自身的代數預序 ≤ ,定義為下: x ≤ y 若且唯若存在 z 使得 x+z=y 。可交換么半群 M序單位是一個在 M 內的元素 u ,其中對任一在 M 內的元素 x 而言,總會存在一個正整數 n 使得 x ≤ nu。这经常用在 M偏序阿贝尔群 G正锥体的情况,在这种情况下我们称 uG 的序-单位。有接受任何交换幺半群,并把它变成全资格阿贝尔群的代数构造;这个构造叫做格羅滕迪克群

部分可交換么半群[编辑]

运算只对某些元素而不是所有元素是交换性的的幺半群是跡么半群;跡幺半群通常出现在并发计算理论中。

例子[编辑]

  • 每一個單元素集合 {x}都可給出一個單元素(當然)么半群。對定固的x,其么半群是唯一的,當其么半群公理在此例子必須滿足x*x=x時。
  • 每一個都是么半群,且每一個阿貝爾群都是可交換么半群。
  • 每一半格都是等冪可交換么半群。
  • 任一個半群S都可以變成么半群,簡單地加上一不在S內的元素e,並定義ee=e和對任一在S內的ses=s=se
  • 自然數N是加法及乘法上的可交換么半群。
  • 以加法或乘法為運算,任何單作的元素
  • 矩陣加法矩陣乘法為運算,所有於一環內n×n矩陣所組成的集合

某些固定字母Σ的有限字元串所組成的集合,會是個以字元串串接為運算的么半群。空字元串當成單位元。這個么半群標記為Σ*,並稱為在Σ內的自由么半群

  • 給定一么半群M,並考慮包含其所有子集冪集P(M)。這些子集的二元運算可以定義成S * T = {s * t : sS內且 tT內}。這使得P(M)變成了具有單位元{e}的么半群。依同樣的方法,一個群的冪集是一在群子集的乘積下的么半群。
  • S為一集合。由所有函數SS所組成的集合會是在複合函數下的么半群。其單位元為恆等函數。若S為有限的且有n個元素,其么半群也會是有限的,且有nn個元素。
  • 廣義化上述的例子,設C為一範疇XC內的一對象。由X所有自同態組成的集合,標記為EndC(X),是一在態射複合下的么半群。更多有關範疇論和么半群的關係請見下述。
  • 連通和下的閉流形同態所組成的集合,其單位元為一般二維球面類。此外,當a標記為環面類且b標記為射影平面類,此一么半群的每一個元素c都會有一唯一的表示式c=na+mb,其中n是大於等於零的整數,m為0、1或2,且會有3b=a+b
  • <f>是一個數為n的循環么半群,亦即<f> = \{f^0,f^1,..,f^{n-1}\}。然後,f^n = f^k,其中0 \le k \le n。事實上,不同的k會給出不同的么半群,且每個么半群都會和另一個同構

此外,f也可以想成在點{0,1,2,..,n-1}上的函數,給定如下

\begin{bmatrix} 
0 & 1 & 2 & ... & n-2 & n-1 \\ 
1 & 2 & 3 & ... & n-1 & k\end{bmatrix}

或等價地表示成

f(i) := \begin{cases} i+1, & \mbox{if }  0 \le i < n-1  \\ k,  & \mbox{if } i = n-1. \end{cases}

<f>元素間的乘法即由複合函數給定。

注意當k=0時,函數f\{0,1,2,..,n-1\}的置換,並給出個數為n的唯一循環群

性質[编辑]

在一么半群內,可以定義一元素x的正整數冪:x1=xxn=x*...*x (乘上n次),其中n>1。冪的規則xn+p=xn*xp則是很明顯的。

由定義可以證明其單位元e是唯一的。然後,對任一x,可以設x0e,則其冪的規則在非負冪中依然會是成立的。

逆元素:一元素x稱為可逆,若存在一元素y,使得x*y = ey*x = e。此一元素y便稱做x的逆元素。結合律使得其逆元素(若存在)是唯一的。

yx的逆元素,則可以定義x的負冪,以x−1=yx−n=y*...*y (乘上n次),其中n>1。如此冪的規則在所有整數就都成立了,這也是為什麼x的逆元素通常會寫做x−1。所有在么半群M內的可逆元素,和其自身的運算可組成一個。在這意思之下,每個么半群都含有一個群。

但並不是每個么半群都包含在一個群內的。例如,絕對可能有一個么半群,其兩個元素ab會有a*b=a的關係,即使b不是單位元。如此的么半群是不可能包含於一個群內的, 因為在群裡,兩邊一同乘a的逆元素,就會得到b = e的結果,但這不是真的。一個么半群(M,*)若具有消去性,即表示對任何在M內的abca*b = a*c永遠意指b = cb*a = c*a也永遠意指b = c。一具有消去性的可交換么半群總是可以包含於一個群內。這是為什麼整數(加法運算下的群)可以由自然數(具有消去性的加法運算下的可交換么半群)建立。但一具有消去性的不可交換么半群則一定不可能包含於一個群之中。

若一么半群有消去性且是有限的,它會是一個群。

一可逆么半群為一么半群,其任一在M內的a,總存在一唯一在M內的a-1,使得a=aa-1a且a-1=a-1aa-1

一么半群G的子么半群是G的子集H,其包含有單位元,且若xy屬於H,則xy屬於H。很清楚地,H本身也是個么半群,在G的二元運算之下。

作用和算子幺半群[编辑]

算子么半群是一作用在集合X上的么半群M。亦即,存在一運算$ : M × XX符合么半群的運算。

  • 對任一在X內的xe$x=x
  • 對任何在M內的ab及在X內的xa $ (b $ x) = (a * b) $ x。) = (a * b) • x.

運算子幺半群也叫做作用(因为它们类似于群作用), 转移系统, 半自动机或变换半群。

么半群同態[编辑]

兩個么半群(M, *)和(M′, @)之間的同態是一個函數f : MM′,會有如下兩個性質:

  • f(x*y) = f(x)@f(y) 對所有在M內的xy
  • f(e) = e

其中ee′分別是MM′的單位元。

不是每一個群胚同態都會是個么半群同態,因為它不一定會維持單位元。和上述不同,群同態的情況則會成立:群論的公理確保每一兩群之間的群胚同態都會維持住單位元。對於么半群,這不是永遠成立的,而必須有另外的要求。

雙射么半群同態稱做么半群同構

幺半群同余和商幺半群[编辑]

幺半群同余是相容于幺半群乘积的等价关系。就是说它是子集

\sim\;\subseteq M\times M

使得它是自反的、对称的和传递的(如同所有等价关系必须的那样),还要有如果 x\sim y\,u\sim v\, 对于所有 M 中的 x,y,uv,则有 x*u\sim y*v\, 的性质。

幺半群同余引发同余类

[m] = \{x\in M\vert\; x\sim m\}

而幺半群运算 * 引发在同余类上的二元运算 \circ:

[u]\circ [v] = [u*v]

它是幺半群同态。它明显的也是结合的,所以所有同余类的集合也是幺半群。这个幺半群叫做商幺半群,可以写为

M/\sim\; = \{[m]\,\vert\; m\in M\}

一些额外的符号是公用的。给定子集 L\subseteq M,写

[L] = \{[m] \,\vert\; m\in L\}

对于引发自 L 的同余类的集合。在这个表示法中,明显的 [M]=M/\sim \,。但是一般的说,[L] \, 不是幺半群。走相反的方向,如果 X\subseteq [M] 是商幺半群的子集,写

\bigcup X = \{m \,\vert\; [m]\in X\}

当然这只是 X 的成员的并集。一般的说,\bigcup X 不是幺半群。

明显的有 L\subseteq \bigcup[L]\left[\bigcup X\right]=X

和範疇論的關係[编辑]

類似群的結構
完全性 結合律 單位元 除法
1 1 1 1
幺半群 1 1 1 0
半群 1 1 0 0
環群 1 0 1 1
擬群 1 0 0 1
原群 1 0 0 0
廣群 0 1 1 1
范疇 0 1 1 0

么半群可視之為一類特殊的範疇。么半群運算滿足的公理同於範疇中從一個對象到自身的態射。換言之:

么半群實質上是只有單個對象的範疇。

精確地說,給定一個么半群 (M,*),可構造一個只有單個對象的小範疇,使得其態射由 M 的元素給出,而其合成則由 么半群的運算 * 給出。

同理,么半群之間的同態不外是這些範疇間的函子。就此意義來說,範疇論可視為是么半群概念的延伸。許多關於么半群的定義及定理皆可推廣至小範疇。

么半群一如其它代數結構,本身也形成一個範疇,記作 Mon,其對象是么半群而態射是么半群的同態。

範疇論中也有么半對象的概念,它抽象地定義了何謂一個範疇中的么半群。

参考文献[编辑]