【離散數學】3. 代數系統

1.數理邏輯

2. 集合論

3. 代數系統

4. 圖論

代數系統：把一些形式上很不相同的代數系統，用統一的方法描述、研究、推理，進而得到反映出他們共性的一些結論，在将結論運用到具體的代數系統中

系統：運算+研究對象

• 運算：具有的共同性質的不同演算抽取成一個運算，根據性質的不同取名群、環域等。
• 研究對象：可以運算的抽象對象

如：集合上的并滿足結合律，實數上的加法也滿足結合律，用一個符号代表具有結合律的運算，而研究對象變為代表實數或者集合等對象的抽象事物

是以代數系統定義為：非空集合和定義在集合上的封閉運算構成的系統

5. 代數系統

5.0 代數學

代數學：研究數的部分

幾何學：研究形的部分

分析學：溝通數與性且設計極限運算的部分

代數：用字母代替具體的數值

發展曆程

1. 算數
2. 初等代數

3. 代數式的運算、方程

   從簡單的一進制一次方程開始

   讨論二進制和三元的一次方程

   研究二進制以上及可以轉換為二進制的方程組

4. 數與方程理論
   • 無理數與有理數的界定
   • 運算符号的創立與無理方程的解法
   • 虛數理論
5. 高等代數

   • 線性代數：讨論任意多個未知數的一進制方程組（線性方程組）

     費馬與笛卡爾引入笛卡爾坐标系，統一了代數與集合，線性代數才出現

     僅涉及線性運算(加法和數乘)的代數學分支，以矩陣為研究工具，以向量空間和線性映射為研究對象

   • 多項式代數：研究更高次的一進制方程組
6. (19世紀以後)抽象代數

系統：将不同演算共有的性質抽取形成系統，根據抽取的性質取名群、環域等。

如：集合上的并有結合律，實數上的加法也有結合律，用一個符号代表具有結合律的運算，而研究對象變為代表實數或者集合等對象的抽象事物

是以代數系統定義為：抽象的研究對象集合和滿足某種性質的運算構成的系統

具體應用：

伽羅瓦用置換群的方法證明一般形式的一進制五次方程沒有通解，給出了可解性的判别原則

格與布爾代數：用于電子線路設計、電子計算機硬體設計和通信系統設計

半群：形式語言，自動機理論

5.1 運算

5.1.1 運算的概念

二進制運算：函數 f : A × A → A f:A\times A\rightarrow A f:A×A→A，則稱f為A上的二進制代數運算

如：

1. 加法與乘法是在 Z + Z^+ Z+ 上的二進制代數運算，運算結果也是 Z + Z^+ Z+ ，是以是封閉的

   f ( < x , y > ) = x + y , x ∈ Z + , y ∈ Z + , x + y ∈ Z + f(<x,y>)=x+y,x\in Z^+,y\in Z^+,x+y\in Z^+ f(<x,y>)=x+y,x∈Z+,y∈Z+,x+y∈Z+

2. 減法不是 Z + Z^+ Z+ 上的二進制運算，因為 x − y ∉ ? Z + x-y\notin^{?} Z^+ x−y∈/?Z+ ，是以是不封閉的
3. 減法在Z上是二進制運算， x − y ∈ Z x-y\in Z x−y∈Z ，是封閉的

5.1.2 運算的性質

二進制運算 A × A → A A\times A\rightarrow A A×A→A 上的性質，以*為運算符

交換律

∀ x , y ∈ A , 有 x ∗ y = y ∗ x ，稱 ∗ 滿足交換律 \forall x,y\in A,有x*y=y*x，稱 *滿足交換律 ∀x,y∈A,有x∗y=y∗x，稱∗滿足交換律

運算表關于主對角線對稱

結合律

∀ x , y , z ∈ A , 有 ( x ∗ y ) ∗ z = x ∗ ( y ∗ z ) ，稱 ∗ 滿足結合律 \begin{aligned} \forall x,y,z\in A,有(x*y)*z=x*(y*z)，稱*滿足結合律 \end{aligned} ∀x,y,z∈A,有(x∗y)∗z=x∗(y∗z)，稱∗滿足結合律​

配置設定律

∀ x , y , z ∈ A , 有 { x ∗ ( y ⋅ z ) = x ∗ y ⋅ x ∗ z ( y ⋅ z ) ∗ x = y ∗ x ⋅ z ∗ x ，則稱 ∗ 滿足配置設定律 \forall x,y,z\in A,有\begin{cases} x*(y·z)=x*y·x*z\\ (y·z)*x=y*x·z*x \end{cases} ，則稱*滿足配置設定律 ∀x,y,z∈A,有{x∗(y⋅z)=x∗y⋅x∗z(y⋅z)∗x=y∗x⋅z∗x​，則稱∗滿足配置設定律

幂等律

∀ x ∈ A , 有 x ∗ x = x ，則稱 ∗ 滿足幂等律 若 ∃ a ∈ A , 且 a ∗ a = a ，則稱 a 是 ∗ 的幂等元 \begin{aligned} &\forall x\in A,有x*x=x，則稱*滿足幂等律\\ &若\exists a\in A,且a*a=a，則稱a是*的幂等元 \end{aligned} ​∀x∈A,有x∗x=x，則稱∗滿足幂等律若∃a∈A,且a∗a=a，則稱a是∗的幂等元​

主對角線元素排列與表頭順序一直

吸收律

∀ x , y ∈ A , 有 { x ∗ ( x ⋅ y ) = x x ⋅ ( x ∗ y ) = x , 則稱 ∗ 和 ⋅ 滿足吸收律 \forall x,y \in A,有 \begin{cases} x*(x·y)=x\\ x·(x*y)=x \end{cases}, 則稱*和·滿足吸收律 ∀x,y∈A,有{x∗(x⋅y)=xx⋅(x∗y)=x​,則稱∗和⋅滿足吸收律

消去律

若滿足兩個關系： { x ∗ y = x ∗ z ( x ≠ 0 ) ，則 y = z y ∗ x = z ∗ x ( x ≠ 0 ) ，則 y = z ， ∗ 滿足消去律 若滿足兩個關系： \begin{cases} x*y=x*z(x\neq 0)，則y=z\\ y*x=z*x(x\neq 0)，則y=z \end{cases} ，*滿足消去律 若滿足兩個關系：{x∗y=x∗z(x=0)，則y=zy∗x=z∗x(x=0)，則y=z​，∗滿足消去律

Z上的加法、乘法滿足消去律

幂集 ρ ( A ) \rho(A) ρ(A) 上的 U 不滿足消去律

• A ∪ B = A ∪ C ⇏ B = C A\cup B=A\cup C \nRightarrow B=C A∪B=A∪C⇏B=C

5.1.3 表示方法

1. 公式
2. 運算表

5.2 代數系統

5.2.1 基本概念

代數系統：非空集合A和A上的k個封閉的運算 f 1 , f 2 , . . . , f k f_1,f_2,...,f_k f1​,f2​,...,fk​ 組成的系統，稱為一個代數系統，記作 < A , f 1 , f 2 , . . . , f k > <A,f_1,f_2,...,f_k> <A,f1​,f2​,...,fk​>

如： < R , + > , < R , ∗ > , < ρ ( A ) , ∪ , ∩ > <R,+>,<R,*>,<\rho(A),\cup,\cap> <R,+>,<R,∗>,<ρ(A),∪,∩>

子代數系統：設 < A , ∗ 1 , ∗ 2 , . . . , ∗ k > <A,*_1,*_2,...,*_k> <A,∗1​,∗2​,...,∗k​> 是代數系統，若 B ⊆ A , B ≠ ∅ B\subseteq A,B\neq ∅ B⊆A,B=∅ ，且運算 ∗ 1 , ∗ 2 , . . . , ∗ k *_1,*_2,...,*_k ∗1​,∗2​,...,∗k​ 對B是封閉的，則 < B , ∗ 1 , ∗ 2 , . . . , ∗ k > <B,*_1,*_2,...,*_k> <B,∗1​,∗2​,...,∗k​> 也是代數系統，稱為 < A , ∗ 1 , ∗ 2 , . . . , ∗ k > <A,*_1,*_2,...,*_k> <A,∗1​,∗2​,...,∗k​> 的子代數系統

若 B ⊂ A B\subset A B⊂A，則稱 < B , ∗ 1 , ∗ 2 , . . . , ∗ k > <B,*_1,*_2,...,*_k> <B,∗1​,∗2​,...,∗k​> 為真子代數系統

如：

對 < R , − > ： < Z , − > 是 < R , − > 的真子代數系統 < N , − > 不是 < R , − > 的真子代數系統 對<R,->： \begin{aligned} &<Z,->是<R,->的真子代數系統\\ &<N,->不是<R,->的真子代數系統 \end{aligned} 對<R,−>：​<Z,−>是<R,−>的真子代數系統<N,−>不是<R,−>的真子代數系統​

5.2.2 特殊元

幺元零元

代數系統的幺元，零元 ，若存在必唯一

左幺元：設*是S上的二進制運算， 1 l 1_l 1l​ 是S中的元素，如果對S中的每一進制素x，有 1 l ∗ x = x 1_l*x=x 1l​∗x=x，則稱 1 l 1_l 1l​ 是對運算 * 的左幺元

左零元：如果對于S中的每個元素x，有 0 l ∗ x = 0 l 0_l*x=0_l 0l​∗x=0l​ ，則稱 0 l 0_l 0l​ 對運算 * 是左零元

設 * 是S上的二進制運算，1是S中的元素，對于S中的每個元素，滿足 1 ∗ x = x ∗ 1 = x 1*x=x*1=x 1∗x=x∗1=x ，則1為對運算 * 的幺元。

如果對于S中的每一進制素x，有 0 ∗ x = x ∗ 0 = 0 0*x=x*0=0 0∗x=x∗0=0 ，則稱0對運算 * 是零元

• 在運算表中
  • 幺元：所在的行與列的元素排列都與表頭一緻
  • 零元：元素的行與列都有鈣元素自身構成

逆元

某個元素的逆元

設 * 是S上的二進制運算，1是對運算 * 的幺元。如果 x*y =1，那麼關于運算 * ，x是y的左逆元，y是x的右逆元

如果 x*y=1和y*x=1都成立，則關于運算 *，x是y的逆元

x的逆元記作 x − 1 x^{-1} x−1 ，存在逆元的元素稱為可逆的

5.3 含一個運算的代數系統

5.3.1 半群

設 V = < S , ∗ > V=<S,*> V=<S,∗> 是代數系統，* 為一個二進制運算符

• 若 * 是可結合的，則稱V是半群

如：乘法，加法，關系的合成， < ρ ( A ) , ∪ > , < ρ ( A ) , ∩ > <\rho(A),\cup>,<\rho(A),\cap> <ρ(A),∪>,<ρ(A),∩> 都是半群

幂等元： ∃ a ∈ S , 使得 a 2 = a \exists a\in S,使得 a^2=a ∃a∈S,使得a2=a 成立，則稱a是幂等元素

• 定理：有限半群必有幂等元

  連續幂等後根據封閉性，結果仍在集合中，是以一定存在幂等元

子半群

在非空子集上的運算是封閉的半群

獨異點(含幺半群)

含幺半群=半群+幺元

半群V中 * 運算符含有幺元，則稱V是含幺半群（獨異點），記作 < S , ∗ , 1 > <S,*,1> <S,∗,1>

如：矩陣乘法

證明獨異點

在R中定義二進制運算 * ， ∀ a , b ∈ R , a ∗ b = a + b + a b \forall a,b \in R,a*b=a+b+ab ∀a,b∈R,a∗b=a+b+ab ，求證 < R , ∗ > <R,*> <R,∗> 構成獨異點

1. ∀ a , b ∈ R , a ∗ b = a + b + a b ∈ R , 是以 ∗ 是封閉的 即 < R , ∗ > 是一個代數系統 2. ( a ∗ b ) ∗ c = ( a ∗ b ) + c + ( a ∗ b ) c = ( a + b + a b ) + c + ( a + b + a b ) c = a + b + c + a b + a c + b c + a b c c ∗ ( a ∗ b ) = c + ( a ∗ b ) + c ( a ∗ b ) = c + ( a + b + a b ) + c ( a + b + a b ) = a + b + c + a b + a c + b c + a b c 是以 ∗ 是可結合的，故 < R , ∗ > 是半群 3. 對 0 ∈ R , ∀ x ∈ R , 有 0 ∗ x = x = x ∗ 0 = x , 是以 0 為幺元 綜上， < R , ∗ > 是獨異點 \begin{aligned} 1.\quad &\forall a,b \in R,a*b=a+b+ab\in R,是以*是封閉的\\&即<R,*>是一個代數系統\\ 2.\quad &(a*b)*c=(a*b)+c+(a*b)c=(a+b+ab)+c+(a+b+ab)c\\&=a+b+c+ab+ac+bc+abc\\ &c*(a*b)=c+(a*b)+c(a*b)=c+(a+b+ab)+c(a+b+ab)\\&=a+b+c+ab+ac+bc+abc\\ &是以 *是可結合的，故<R,*>是半群\\ 3.\quad &對0\in R,\forall x\in R,有0*x=x=x*0=x,是以0為幺元\\ &綜上，<R,*>是獨異點 \end{aligned} 1.2.3.​∀a,b∈R,a∗b=a+b+ab∈R,是以∗是封閉的即<R,∗>是一個代數系統(a∗b)∗c=(a∗b)+c+(a∗b)c=(a+b+ab)+c+(a+b+ab)c=a+b+c+ab+ac+bc+abcc∗(a∗b)=c+(a∗b)+c(a∗b)=c+(a+b+ab)+c(a+b+ab)=a+b+c+ab+ac+bc+abc是以∗是可結合的，故<R,∗>是半群對0∈R,∀x∈R,有0∗x=x=x∗0=x,是以0為幺元綜上，<R,∗>是獨異點​

定理

• x,y都有逆元，則 x*y 有逆元，且 ( x ∗ y ) − 1 = x − 1 ∗ y − 1 (x*y)^{-1}=x^{-1}*y^{-1} (x∗y)−1=x−1∗y−1

可交換半群=半群+滿足交換律

若半群 V = < S , ∗ > V=<S,*> V=<S,∗> 的運算符 * 是可交換的，V是可交換半群

定理

• 在可交換半群 < S , ∗ > <S,*> <S,∗> 中，有 ( a ∗ b ) n = a n ∗ b n (a*b)^n=a^n*b^n (a∗b)n=an∗bn ，其中n是正整數, a , b ∈ S a,b\in S a,b∈S

獨異點 < S , ∗ , 1 > <S,*,1> <S,∗,1> 中的 * 是可交換的，稱V是可交換獨異點

循環半群=半群+生成元

5.3.2 群

群=含幺半群+每個元素有逆元

設 V = < S , ∗ > V=<S,*> V=<S,∗> 是代數系統，* 是二進制運算

若 * 是可結合的，存在幺元 ∃ 1 ∈ S \exists 1 \in S ∃1∈S ，且 ∀ x ∈ S , 有 x − 1 ∈ S \forall x\in S,有x^{-1}\in S ∀x∈S,有x−1∈S ，稱V為群

如：

< N , + > 滿足結合律，是以是半群。幺元是 0 ，是以是含幺半群。但是 < N , + > 不是群，每個元素的逆不在 N 中 \begin{aligned} &<N,+>滿足結合律，是以是半群。幺元是0，是以是含幺半群。但是\\ &<N,+>不是群，每個元素的逆不在N中 \end{aligned} ​<N,+>滿足結合律，是以是半群。幺元是0，是以是含幺半群。但是<N,+>不是群，每個元素的逆不在N中​

證明群的過程

設Z為整數集合，在Z上定義二進制運算*， ∀ x , y ∈ Z \forall x,y\in Z ∀x,y∈Z，x*y=x+y-2，為 < Z , ∗ > <Z,*> <Z,∗> 是否為群

1. ∀ x , y ∈ Z , x ∗ y = x + y − 2 ∈ Z , 是以 ∗ 是封閉的，即 < Z , ∗ > 是代數系統 2. ∀ x , y , z ∈ Z ( x ∗ y ) ∗ z = ( x + y − 2 ) + z − 2 = x + y + z − 4 x ∗ ( y ∗ z ) = x + ( y + z − 2 ) − 2 = x + y + z − 4 即 ∗ 是可結合的，是以 < Z , ∗ > 是半群 3. 設 p 是幺元， p ∗ x = p = p + x − 2 = x ⇒ p = 2 故半群 < R , ∗ > 是獨異點，幺元為 2 4. x ∗ x − 1 = 2    ⟺    x + x − 1 = 4 ⇒ x − 1 = 4 − x ∈ Z 故 < R , ∗ > 是群 \begin{aligned} 1.\quad &\forall x,y\in Z,x*y=x+y-2\in Z,是以*是封閉的，即<Z,*>是代數系統\\ 2.\quad &\forall x,y,z\in Z \\ &(x*y)*z=(x+y-2)+z-2=x+y+z-4\\ &x*(y*z)=x+(y+z-2)-2=x+y+z-4\\ &即*是可結合的，是以<Z,*>是半群\\ 3.\quad &設p是幺元，p*x=p=p+x-2=x\Rightarrow p=2\\ &故半群<R,*>是獨異點，幺元為2\\ 4.\quad &x*x^{-1}=2\iff x+x^{-1}=4\Rightarrow x^{-1}=4-x\in Z\\ &故<R,*>是群 \end{aligned} 1.2.3.4.​∀x,y∈Z,x∗y=x+y−2∈Z,是以∗是封閉的，即<Z,∗>是代數系統∀x,y,z∈Z(x∗y)∗z=(x+y−2)+z−2=x+y+z−4x∗(y∗z)=x+(y+z−2)−2=x+y+z−4即∗是可結合的，是以<Z,∗>是半群設p是幺元，p∗x=p=p+x−2=x⇒p=2故半群<R,∗>是獨異點，幺元為2x∗x−1=2⟺x+x−1=4⇒x−1=4−x∈Z故<R,∗>是群​

有限群&無限群

設 < G , ∗ > <G,*> <G,∗> 是一個群

• 如果G是有限集，則稱 < G , ∗ > <G,*> <G,∗> 是有限群，G中的元素個數稱為群的階，記為 ∣ G ∣ \mid G \mid ∣G∣
• G是無限集，則為無限群，群的階為無限

群的基本性質

二階以上的群無零元

• 一階群一定有零元，零元即幺元， < g , ∗ > <{g},*> <g,∗> g*g=g，是以g是零元

群中每個元素都存在唯一逆元

群中除幺元外無幂等元

群的運算表中，沒有兩行或兩列是相同的

群滿足消去律

滿足消去律的有限半群是群

• 沒有零元的有限半群是群

子群

設 < G , ∗ > <G,*> <G,∗> 為群， H ⊆ G H\subseteq G H⊆G，且 < H , ∗ > <H,*> <H,∗> 為群，則稱H為G的子群，記作 H ≤ G H\le G H≤G

子群判定定理

設 < G , ∗ > <G,*> <G,∗> 為群，H是G的非空子集

< H , ∗ > 是 < G , ∗ > 的非空子群    ⟺    { 封閉： ∀ a , b ∈ H , 有 a ∗ b ∈ H 逆元： ∀ a ∈ H , 有 a − 1 ∈ H    ⟺    ∀ a , b ∈ H , 有 a ∗ b − 1 ∈ H H 是 G 的子集且 H 是有限集    ⟺    ∀ a , b ∈ H , 有 a ∗ b ∈ H \begin{aligned} <H,*>是<G,*>的非空子群 &\iff \begin{cases} 封閉：\forall a,b\in H,有a*b\in H\\ 逆元：\forall a\in H,有a^{-1}\in H \end{cases}\\ &\iff \forall a,b\in H,有a*b^{-1}\in H\\ H是G的子集且H是有限集&\iff \forall a,b\in H,有a*b\in H \end{aligned} <H,∗>是<G,∗>的非空子群H是G的子集且H是有限集​⟺{封閉：∀a,b∈H,有a∗b∈H逆元：∀a∈H,有a−1∈H​⟺∀a,b∈H,有a∗b−1∈H⟺∀a,b∈H,有a∗b∈H​

性質

子群的幺元是群的幺元， ∀ a ∈ H \forall a\in H ∀a∈H ，其逆元 a H − 1 a_H^{-1} aH−1​ 就是a在G中的逆元 a − 1 a^{-1} a−1

二階以上的群 < G , ∗ > <G,*> <G,∗> 一定存在兩個子群，稱為G的平凡子群

• 由幺元組成的子群 < 1 , ∗ > <{1},*> <1,∗> 稱為G的幺子群，其中 1就是 < G , ∗ > <G,*> <G,∗> 的幺元
• < G , ∗ > <G,*> <G,∗> 群本身
• 其餘子群稱為 非平凡子群/真子群

交換群：滿足交換律的群

若群 V = < S , ∗ > V=<S,*> V=<S,∗> 中的 * 滿足交換律，則稱V是可交換的群（阿貝爾群）

循環群：有生成元的交換群

群中的每個元素都可用一個元素的方幂表示，則稱這個群是循環群

群 V = < G , ∗ > V=<G,*> V=<G,∗> 中，如果 ∃ g ∈ G \exists g\in G ∃g∈G，對于每個元素 a ∈ G a\in G a∈G，都有一個相應的 i ∈ I i\in I i∈I ，能把a表示成幂次 g i g^i gi 的形式，則稱 < G , ∗ > <G,*> <G,∗> 是一個循環群。或循環群是由g生成的，g是 < G , ∗ > <G,*> <G,∗> 的生成元

循環群的判别

證明： < Z , + > <Z,+> <Z,+> 是循環群

1. ∀ a , b ∈ Z , a + b ∈ Z ，故 + 是封閉的 < G , + > 是一個代數系統 2. ∀ a , b , c ∈ Z , ( a + b ) + c = a + ( b + c ) = a + b + c 是以 < G , + > 是半群 3. 設幺元為 p , ∀ x ∈ Z , p + x = x , 則 p = 0 幺元 = 0 4. ∀ a ∈ Z , a + a − 1 = 0 ⇒ a − 1 = − a ∈ Z 是以 < G , + > 是群 5. 設 g = 1 ， ∀ n ∈ Z + ， n = 1 + 1 + . . . + 1 = 1 n ∀ n ∈ Z − , n = ( − 1 ) + ( − 1 ) + . . . + ( − 1 ) = ( − 1 ) n = ( 1 − 1 ) n 故 1 是 < G , ∗ > 的生成元，該群為循環群 \begin{aligned} &1. \quad \forall a,b\in Z,a+b\in Z，故+是封閉的\\ & \quad <G,+>是一個代數系統\\ &2.\quad \forall a,b,c \in Z,(a+b)+c=a+(b+c)=a+b+c\\ &\quad 是以<G,+>是半群\\ &3.\quad 設幺元為p,\forall x\in Z,p+x=x,則p=0\\ &\quad 幺元=0\\ &4. \quad \forall a\in Z,a+a^{-1}=0\Rightarrow a^{-1}=-a\in Z\\ &\quad 是以<G,+>是群\\ &5. \quad 設g=1，\forall n\in Z_+，n=1+1+...+1=1^{n}\\ &\quad \forall n\in Z_-,n=(-1)+(-1)+...+(-1)=(-1)^n=(1^{-1})^n\\ &故1是<G,*>的生成元，該群為循環群 \end{aligned} ​1.∀a,b∈Z,a+b∈Z，故+是封閉的<G,+>是一個代數系統2.∀a,b,c∈Z,(a+b)+c=a+(b+c)=a+b+c是以<G,+>是半群3.設幺元為p,∀x∈Z,p+x=x,則p=0幺元=04.∀a∈Z,a+a−1=0⇒a−1=−a∈Z是以<G,+>是群5.設g=1，∀n∈Z+​，n=1+1+...+1=1n∀n∈Z−​,n=(−1)+(−1)+...+(−1)=(−1)n=(1−1)n故1是<G,∗>的生成元，該群為循環群​

循環群的性質

1. 生成元不唯一

   

2. 群的階：設 < G , ∗ > <G,*> <G,∗> 是一個由元素a生成的循環群，且是 有限群，如果G的階是n，即 ∣ G ∣ = n \mid G \mid=n ∣G∣=n ,則 a n = 1 a^n=1 an=1 且 G = { a , a 2 , . . . , a n = 1 } G=\{a,a^2,...,a^n=1\} G={a,a2,...,an=1} ，n是元素 a 的階(使得 a n = 1 a^n=1 an=1 成立的最小正整數)
3. 任意的循環群都是交換群

   

置換群

變換與變換群

變換：在A上的映射/函數

對稱群 < S A , ◇ > <S_A,◇> <SA​,◇>：非空集合A 上的全體 可逆變換(雙射函數)的複合運算 構成集合的A的群

• 代數系統——封閉：集合A上的任意兩個雙射函數複合後仍在集合A中
• 半群——結合律：複合運算具有結合律
• 含幺半群——求幺元：恒等函數，自己到自己的變換
• 群——每個元素逆元都在群中：雙射函數的逆元仍在集合中

對稱群 < S A , ◇ > <S_A,◇> <SA​,◇> 的子群稱為A的一個變換群

• 運算符号滿足結合律，不滿足交換律
• 每個群都同構于一個變換群

G是實數集R上 所有變換 f a , b : R → R f_{a,b}:R\rightarrow R fa,b​:R→R 構成的集合， ∀ x ∈ R , f a , b ( x ) = a x + b \forall x\in R,f_{a,b}(x)=ax+b ∀x∈R,fa,b​(x)=ax+b ， < G , ◇ > <G,◇> <G,◇> G是變換群

置換

置換：在 有限集合 上的可逆變換（雙射函數）

如：集合A={1,2,3,4,5}是有限集合，其上的一個可逆變換(可逆函數/雙射函數)即為一個置換

若 ∣ A ∣ = n \mid A \mid=n ∣A∣=n ，則A上的置換有 n! 個。A上的所有置換的集合記為 S n S_n Sn​

置換群

n元有限集合A上的置換所構成的群，稱為n元置換群；A上所有置換構成的群稱為n次對稱群

• 置換群是在 有限集合 上的變換群
• n次對稱群是n元置換群的特殊情況

• 以符号◇表示右合成運算： p 1 ◇ p 2 p_1◇p_2 p1​◇p2​ 表示先進行 p 1 p_1 p1​ 置換，在進行 p 2 p_2 p2​ 置換
• < S n , ◇ > <S_n,◇> <Sn​,◇> 表示對稱群， < { p 1 , p 2 , . . . } , ◇ > <\{p_1,p_2,...\},◇> <{p1​,p2​,...},◇> 表示置換群
• 任何一個有限群都同構于一個置換群

置換群的幾何意義

5.4 含兩個運算的代數系統

5.4.1 環

具有兩個二進制運算的代數系統

設 < R , + , ∗ > <R,+,*> <R,+,∗> 是代數系統，+,*為二進制運算，若滿足

• < R , + > <R,+> <R,+> 是可交換群
• < R , ∗ > <R,*> <R,∗> 是半群

• *對+滿足配置設定律

  A*(B+C)=A*B+A*C

稱 < G , + , ∗ > <G,+,*> <G,+,∗> 為環

整環

若環 < R , + , − > <R,+,-> <R,+,−> 可交換，含幺元，無零元，稱R為整環

對應可交換半群

除環

若環 < R , + , − > <R,+,-> <R,+,−> 至少存在兩個元素，含幺元，無零元，且(逆元也在環中) ∀ a ∈ R ( a ≠ 0 ) \forall a\in R(a\neq 0) ∀a∈R(a=0) 有 a − 1 ∈ R a^{-1}\in R a−1∈R ，稱R為除環

對應群

5.4.2 域

若環 < R , + , − > <R,+,-> <R,+,−> 既是整環又是除環，則稱R是域

對應可交換群——阿貝爾群

5.5 格

設 < S , ≤ > <S,\le> <S,≤> 是偏序集(自反，反對稱，傳遞)，如果 ∀ x , y ∈ S \forall x,y \in S ∀x,y∈S ，{x,y} 都有最小上界和最大下界，稱S關于 ≤ \le ≤ 構成一個格，記為：

格 < S , ≤ > , 格 < S , ∧ , ∨ > 格<S,\le>,格<S,∧,∨> 格<S,≤>,格<S,∧,∨> ，

其中 ∨表示最小上界，∧表示最大下界

每個全序集都是一個格

5.5.1 格的判斷

1.

設 < S 6 , D > <S_6,D> <S6​,D> ，D表示整除， S n S_n Sn​ 表示整除n的因子集合

其中：

1∨2=2，,1∨3=3，1∨6=6，2∨3=6

1∧2=1，,1∧3=1，1∧6=1，2∧3=1

是以是格

2.

對于 b,d 有最小上界 b∨d=c,e

對于 c,e 有最大下界 c∧e =b,d 但是無最小上界，c與e大小無法判斷

是以不是格

3. < ρ ( B ) , ⊆ > <\rho(B),\subseteq> <ρ(B),⊆>

∀ x , y ∈ ρ ( B ) , x ∨ y = x ∪ y , x ∧ y = x ∩ y \forall x,y\in \rho(B),x∨y=x\cup y,x∧y=x\cap y ∀x,y∈ρ(B),x∨y=x∪y,x∧y=x∩y

是以是格

5.5.2 格的界

全界：

若格 < L , ∧ , ∨ > <L,∧,∨> <L,∧,∨> 中 ∃ a \exists a ∃a，對 ∀ b ∈ L \forall b\in L ∀b∈L ，有 a ≤ b ( b ≤ a ) a\le b(b\le a) a≤b(b≤a) ，則稱a為格L的全下界(全上界)

全下界a是L中的最小值，哈斯圖的最底層一個元素。

全上界a是L中的最大值，哈斯圖的最頂層一個元素

5.5.3 特殊的格

有界格

記為： < L , ∧ , ∨ , 0 , 1 > <L,∧,∨,0,1> <L,∧,∨,0,1> 。界的位置與運算符号位置對應

有補格

每個元素都有補元，為有補格

補元

有界格 < L , ∧ , ∨ , 0 , 1 > <L,∧,∨,0,1> <L,∧,∨,0,1> ， ∀ a ∈ L \forall a\in L ∀a∈L ，若 ∃ b ∈ L \exists b\in L ∃b∈L ，使 a∧b=0,a∨b=1，則稱 b是a的 補元

如：

< S 8 , D > <S_8,D> <S8​,D> ，其哈斯圖為：

1是全下界，8是全上界，即表示為格 < S 8 , D , ∧ , ∨ , 1 , 8 > <S_8,D,∧,∨,1,8> <S8​,D,∧,∨,1,8>。

由于1∧8=1，1∨8=8，是以1和8互為補元

由于1∧2=1，1∨2=2；2∨4=4；2∨8=8，2∧8=2，是以2無補元，同理4無補元

所給哈斯圖是格，a為全上界，d為全下界。a與d互為補元，b,c,e無補元

a為全上界，e為全下界，是以a與e互為補元

對于b,c，b∧c=e，b∨c=a，是以b與c互為補元

同理，c與d，b與d互為補元

有界有補配置設定格

格 < L , ∧ , ∨ , 0 , 1 > <L,∧,∨,0,1> <L,∧,∨,0,1> 是有補配置設定格，稱L為布爾代數

• 有界格
• 有補格

• 求界可配置設定

  ∧對∨可配置設定

  ∨對∧可配置設定

• 0：全下界
• 1：全上界

如：

< B , ∧ , ∨ , ′ , 0 , 1 > <B,∧,∨,',0,1> <B,∧,∨,′,0,1> 是布爾代數

若a’是a的補元，則a∧a’=0,a∨a’=1

a∨0=a,a∧0=0,a∨1=a,a∧1=a

5.6 代數間的關系

用于研究兩個代數系統間的聯系

5.6.1 同構

兩個代數系統 A = < S , ∗ , + , k > A=<S,*,+,k> A=<S,∗,+,k> 和 A ′ = < S ′ , ∗ ′ , + ′ , k ′ > A'=<S',*',+',k'> A′=<S′,∗′,+′,k′> ，其中*是二進制運算，+是一進制運算。若存在一個雙射函數h，使

h: S → S ′ S\rightarrow S' S→S′

h(a*b)=h(a)*'h(b)

h(+a)=+'h(a)

h(k)=k’

則将h為從A到A’的同構

5.6.2 同态