離散數學-代數系統-半群

author: o-jules

Description:

這是關於離散數學的相關筆記，本篇介紹代數系統中的半群

半群

設 $S$ 是定義了一個運算的非空集合，若該運算是可結合的，則稱 $S$ 為半群；若該運算還有一個單位元，則稱 $S$ 為幺半群。

自由半群，自由幺半群

設 $F = F(A)$ 表示 $A$ 上所有字符串在連接運算下的集合，顯然對於任意串 $u，v，w$，串$(uv)w$ 和 $u(vw)$是一樣的；它們都是由$u，v，w$一個接一個地寫成的。因此 $F$ 是一個半群，稱為 $A$ 上的自由半群；$A$ 的元素，稱為 $F$ 的生成元。

空序列記為 $\lambda$，也看做 $A$ 上的一個串，但我們不能認為$\lambda$屬於 自由半群 $F = F(A)$。 $A$ 上所有的串包括 $\lambda$ 記為$ A *$。於是 $A *$ 是連接下的一個幺半群，稱為 $A$ 上的自由幺半群。

子半群

設 $A$ 是半群 $S$ 的一個非空子集，如果 $A$ 本身對於 $S$ 上的運算是一個半群，則稱 $A$ 為 $S$ 的一個子半群。因為 $A$ 中的元素也是 $S$ 的元素，$A$ 中的元素自然滿足結合行。

因此 $A$ 是一個子半群當且僅當 其在 $S$ 的運算下封閉。

同余關系和商結構

設 $S$ 是一個半群，$~$ 是 $S$ 上的一個等價關系。回顧等價關系，可以把集合 $S$ 分成等價類，且用$[a]$表示含有集合 $S$ 中的元素 $a$ 的等價類，等價類的集合記為：$S/~$。

假設 $S$ 上的等價關系有下面的性質： \(a ~ a', b ~ b' \implies ab ~ a'b'\)

那麼 ~ 稱為 $S$ 上的同余關系。而且可以定義等價類上的一個運算： \([a] * [b] = [a * b], [a] [b] = [ab]\)

並且這個 $S/~$ 上的運算是可結合的，因此，$S/~$ 是一個半群。

定理 設 $~$ 是半群 $S$ 上的一個同余關系，那麼 $~$ 的等價類 $S/~$ 關於運算 \([a] [b] = [ab]\) 構成一個半群。這個半群 $S/~$ 稱為由 $~$生成的商群。

半群的同態

考慮兩個半群$(S, *)$ 和 $(S’, *’)$，函數 $f: S\to S’$，稱為半群同態，或簡稱同態，如果： \(f(a * b) = f(a) *' f(b) 或 f(ab) = f(a)f(b)\) 假設 $f$ 是單射的，滿射的，則 $f$ 稱為 $S$ 與 $S’$ 之間的一個同構，$S$ 和 $S’$ 稱為同構半群，記作： \(S\cong S'\)

半群同態的基本定理

定理 設 $f: S\to S’$ 是一個半群同態，如果 $f(a) = f(b)$，今 $a ~ b$，則

1. $~$ 是$S$ 上的同余關系;
2. $S/~$ 同構於 $f(S)$；

半群的積

設 $(S_1, *1)$ 和 $(S_2, *2)$ 是兩個半群，我們構造一個新半群 $S = S_1 \otimes S_2$，稱為 $S1$ 和 $S2$ 的直積，如下：

1. $S$ 中的元素來自 $S_1\times S_2$，即 $S$ 中的元素是有序偶 $(a,b), a\in S_1, b\in S_2$；
2. $S$ 中的運算 $*$ 定義為分量兩兩相乘，即： \((a, b) * (a', b') = (a *_1 a', b *_2 b')\) 或簡記為： \((a, b)(a', b') = (aa', bb')\) （可證明，上面的運算是可結合的。）