7.1-7.2 二元運算、么半群與群

第 7 章開始轉換視角。

集合論讓我們用函數、關係和基數比較集合。但很多數學對象之所以有趣，不只是因為它們包含哪些元素，而是因為那些元素上還帶有額外結構。

例如，只看基數時，集合 {5, dog} 和 {0,1} 都只有兩個元素。但 {0,1} 可以配上熟悉的加法和乘法規則；相反， $5 + dog$ 在未指定額外結構之前沒有明確意義。

本章的目標，就是把這些額外結構說清楚。

帶結構的集合

許多基本例子都符合這個模式：自然數帶有加法與乘法，平面帶有向量加法，置換帶有合成。

共同模式是：

先有一個集合；
在集合上指定某些運算、關係、函數或特殊元素；
寫下這些額外資料要滿足的公理；
只由公理推出定理。

這是現代數學的一個基本習慣。與其在每個例子中重複證明同一類事實，不如先定義一種結構，再證明所有具有該結構的例子都必須滿足甚麼。

二元運算

定義

二元運算

設 $X$ 是集合。 $X$ 上的一個 二元運算 是一個函數

*:X\times X\to X.

對 $a,b\in X$ ，通常寫 $a*b$ ，而不是 $*(a,b)$ 。

這個定義有兩個重點。

第一，運算從 $X$ 中取兩個輸入。第二，輸出仍然必須屬於 $X$ 。第二點常被稱為封閉性；在這門課的寫法中，它已經包含在函數型別 $X\times X\to X$ 裡。

常見錯誤

一條公式不會自動成為每個集合上的二元運算

減法是 $Z$ 上的二元運算，因為 $a-b\in Z$ 對所有 $a,b\in Z$ 都成立。但若要求結果仍留在 $N$ 中，減法就不是 $N$ 上的二元運算，因為 $2-5$ 不是自然數。

Boolean integers

定義

B=\{0,1\}.

在這個集合上，加法規則為

0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0,

乘法規則為

0\cdot 0=0,\qquad 0\cdot 1=0,\qquad 1\cdot 0=0,\qquad 1\cdot 1=1.

定義

Boolean integers

Boolean integers 是三元組

(B,+,\cdot),

其中 $B=\{0,1\}$ ，而 $+$ 與 $\cdot$ 是上面顯示的兩個二元運算。

重點不在名稱，而在於：即使集合很小，只要指定運算，也可以有非平凡結構。

例題

在 $B$ 中解 $x+y=0$

一個有用練習是證明

\forall x\in B,\ \exists y\in B\ (x+y=0).

只需檢查 x 的兩個可能值。

若 $x=0$ ，取 $y=0$ ，因為 $0+0=0$ 。

若 $x=1$ ，取 $y=1$ ，因為 $1+1=0$ 。

所以在這個加法規則下， $B$ 的每個元素都有加法逆元。

么半群

第 7 章首先研究的結構是 monoid。

定義

么半群

一個 么半群 $(M,*)$ 是一個集合 $M$ ，連同一個二元運算

*:M\times M\to M

使得：

對所有 $a,b,c\in M$ ，
$(a*b)*c=a*(b*c)$
（結合律）；
存在 $e\in M$ ，使得對所有 $a\in M$ ，
$a*e=e*a=a$
（單位元存在）。

結合律說明三個元素連乘時括號位置不影響結果。單位元則是一個從左邊或右邊合併也不改變元素的元素。

標準例子包括：

$(N,+)$ 是么半群，單位元為 0；
$(N,\times)$ 是么半群，單位元為 1；
$(Z,+)$ 是么半群，單位元為 0；
$(Z,\times)$ 是么半群，單位元為 1；
對任意集合 $X$ ， $X^X$ 在合成下是么半群，單位元為 $id_X$ ；
$(B,+)$ 是么半群；
$(B,\cdot)$ 是么半群。

例題

檢查 $(N,+)$ 是么半群

$+$ 是 $N$ 上的二元運算。

結合律成立：

(a+b)+c=a+(b+c)

對所有自然數 a,b,c 成立。

單位元是 0，因為

a+0=0+a=a.

所以 $(N,+)$ 是么半群。

例題

檢查函數合成么半群

設 $X$ 是任意集合。 $X^X$ 的元素是函數 $X\to X$ 。

合成滿足結合律：

(h\circ g)\circ f=h\circ(g\circ f).

恆等函數 $id_X$ 滿足

f\circ id_X=f,\qquad id_X\circ f=f.

所以 $X^X$ 在合成下是么半群。

不是么半群的例子

也要看一些失敗例子。

例題

$(Z^+,+)$ 不是么半群

若 $Z^+$ 表示正整數，則加法封閉且滿足結合律。但 $Z^+$ 裡沒有加法單位元。

加法單位元必須是 0，因為 $a+0=a$ 。但 $0\notin Z^+$ 。所以 $(Z^+,+)$ 不是么半群。

例題

$(Z,-)$ 不是么半群

減法是 $Z$ 上的二元運算，但不滿足結合律。例如

(5-3)-1=1,

而

5-(3-1)=3.

結果不同，所以結合律失敗， $(Z,-)$ 不是么半群。

常見錯誤

有單位元仍然不夠

一個運算可能看起來有單位元，但若不滿足結合律，仍然不是么半群。結合律和單位元是兩個獨立要求。

單位元唯一

定理

單位元唯一性

一個么半群恰好只有一個單位元。

證明

這個證明很短，原因是單位元律可以左右兩邊使用。兩個候選單位元必須互相不改變對方，因而被迫相等。

群

么半群很有用，但條件較弱。群額外要求每個元素都可以被「復原」。

定義

群

一個群是一個集合 $G$ ，連同一個元素 $e\in G$ 和一個二元運算

(a,b)\longmapsto a\cdot b

使得：

對所有 $a\in G$ ，
$e\cdot a=a=a\cdot e;$
對所有 $a,b,c\in G$ ，
$(a\cdot b)\cdot c=a\cdot(b\cdot c);$
對每個 $a\in G$ ，存在逆元 $a^{-1}\in G$ ，使得
$a\cdot a^{-1}=e \qquad\text{且}\qquad a^{-1}\cdot a=e.$

群的自然動機之一是形式化對稱性。對稱操作應該可以合成、有一個甚麼都不做的操作，並且可以反向復原。

在這個標準讀法下，每個群在忘記逆元公理之後都是么半群。群更強，不是因為它有另一套結合律或單位元，而是因為每個元素都有逆元。

常見錯誤

群不是任意帶二元運算的集合

運算必須滿足結合律，必須有雙邊單位元，而且每個元素都必須有逆元。任何一條失敗，也不是群。

群的例子

基本例子包括：

$(Z,+)$ ；
$(Q,+)$ ；
$(Q^+,\cdot)$ ，其中 $Q^+$ 表示正有理數。

例題

為甚麼 $(Z,+)$ 是群

單位元是 0。

對每個整數 a，逆元是 $-a$ ，因為

a+(-a)=0=(-a)+a.

加法滿足結合律，所以 $(Z,+)$ 是群。

例題

為甚麼 $(Q^+,\cdot)$ 是群

單位元是 1。

對每個正有理數 q，逆元是 1/q，它仍然是正有理數，且

q\cdot \frac1q=1=\frac1q\cdot q.

乘法滿足結合律，所以 $(Q^+,\cdot)$ 是群。

常見錯誤

$(Z,\times)$ 是么半群，但不是群

$Z$ 上乘法的單位元是 1，且乘法滿足結合律。但大多數整數在 $Z$ 中沒有乘法逆元。例如不存在整數 b 使得 $2b=1$ 。

逆元唯一

定理

逆元唯一性

對每個 $a\in G$ ，逆元 $a^{-1}$ 是唯一的。

證明

這個證明說明了為甚麼逆元記號是合理的：只要逆元存在，它就是唯一的，所以 $a^{-1}$ 不會有歧義。

襪鞋性質

乘積逆元公式常被稱為 socks-shoes property：要復原兩個連續操作，先復原第二個，再復原第一個。

定理

襪鞋性質

對群中元素 a,b，

(a*b)^{-1}=b^{-1}*a^{-1}.

證明

順序反轉是必要的。在非交換群中， $a^{-1}*b^{-1}$ 未必能復原 $a*b$ 。

消去律

定理

消去律

在群中：

若 $a*b=a*c$ ，則 $b=c$ ；
若 $b*a=c*a$ ，則 $b=c$ 。

證明

左消去證明

右消去的證明類似，只是改為右乘 $a^{-1}$ 。

互動檢查運算律

下面的 checker 是定義的輔助工具：可用來測試小型運算表的封閉性、結合律、單位元與逆元行為。真正的數學內容仍然是上面的公理。

比較 monoid 與 group 的公理表

圖示。monoid 與 group 的分別不是名稱，而是除結合律外，單位元與逆元公理是否成立。

邊讀邊試

檢查 monoid 與 group 公理

這個檢查器按 monoid 與 group 所需的精確公理比較二元運算。

這是一個群。

結合律

是

(a+b)+c = a+(b+c)。

單位元

是

0 是單位元。

逆元

是

a 的逆元是 -a。

快速檢查

一條規則 $*$ 要成為集合 $X$ 上的二元運算，必須滿足甚麼輸入與輸出要求？

用函數型別回答。

解答

答案

快速檢查

為甚麼 $(Z,-)$ 不是么半群？

指出失敗的公理，並給一個具體計算。

解答

答案

快速檢查

為甚麼 $(Z,\times)$ 不是群？

集中看逆元。

解答

答案

快速檢查

在群中， $a*b$ 的逆元是甚麼？

留意順序。

解答

答案

練習

快速檢查

直接證明 $(B,+)$ 是么半群，其中 $+$ 是上面的 Boolean 加法。

檢查結合律並指出單位元。

解答

引導解答

快速檢查

證明么半群的單位元唯一。

使用兩個可能的單位元 e 與 e'。

解答

引導解答

快速檢查

證明群中的左消去律：若 $ab=ac$ ，則 $b=c$ 。

使用 a 的逆元。

解答

7.1-7.2 二元運算、么半群與群

MATH1090：集合論

帶結構的集合

二元運算

二元運算

一條公式不會自動成為每個集合上的二元運算

Boolean integers

Boolean integers

在 BBB 中解 x+y=0x+y=0x+y=0

更多二元運算例子

合成作為二元運算

么半群

么半群

檢查 (N,+)(N,+)(N,+) 是么半群

檢查函數合成么半群

不是么半群的例子

(Z+,+)(Z^+,+)(Z+,+) 不是么半群

(Z,−)(Z,-)(Z,−) 不是么半群

有單位元仍然不夠

單位元唯一

單位元唯一性

證明

群

群

群不是任意帶二元運算的集合

群的例子

為甚麼 (Z,+)(Z,+)(Z,+) 是群

為甚麼 (Q+,⋅)(Q^+,\cdot)(Q+,⋅) 是群

(Z,×)(Z,\times)(Z,×) 是么半群，但不是群

逆元唯一

逆元唯一性

證明

襪鞋性質

襪鞋性質

證明

消去律

消去律

左消去證明

互動檢查運算律

檢查 monoid 與 group 公理

快速檢查

一條規則 ∗*∗ 要成為集合 XXX 上的二元運算，必須滿足甚麼輸入與輸出要求？

答案

為甚麼 (Z,−)(Z,-)(Z,−) 不是么半群？

答案

為甚麼 (Z,×)(Z,\times)(Z,×) 不是群？

答案

在群中，a∗ba*ba∗b 的逆元是甚麼？

答案

練習

直接證明 (B,+)(B,+)(B,+) 是么半群，其中 +++ 是 上面的 Boolean 加法。

引導解答

證明么半群的單位元唯一。

引導解答

證明群中的左消去律：若 a∗b=a∗ca*b=a*ca∗b=a∗c，則 b=cb=cb=c。

引導解答

相關筆記

先備知識

本單元重點詞彙

本系列更多筆記

在 $B$ 中解 $x+y=0$

檢查 $(N,+)$ 是么半群

$(Z^+,+)$ 不是么半群

$(Z,-)$ 不是么半群

為甚麼 $(Z,+)$ 是群

為甚麼 $(Q^+,\cdot)$ 是群

$(Z,\times)$ 是么半群，但不是群

一條規則 $*$ 要成為集合 $X$ 上的二元運算，必須滿足甚麼輸入與輸出要求？

為甚麼 $(Z,-)$ 不是么半群？

為甚麼 $(Z,\times)$ 不是群？

在群中， $a*b$ 的逆元是甚麼？

直接證明 $(B,+)$ 是么半群，其中 $+$ 是上面的 Boolean 加法。

證明群中的左消去律：若 $ab=ac$ ，則 $b=c$ 。