Tương đẳng trên các nửa nhóm xyclic
Tương đẳng Nửa nhóm thương
1.1.1 Định nghĩa. i) Giả sử X là một tập hợp tùy ý khác rỗng Khi đó mỗi tập con ρ của tích đề cácX X× được gọi là một quan hệ trên X
Giả sử ρ là một quan hệ trên tập hợp X Nếu (a, b) ∈ ρ, với a và b là các phần tử thuộc X, thì ta có thể viết a bρ Hơn nữa, nếu ρ và δ là các quan hệ trên X, thì hợp thành ρ δo được định nghĩa như sau: (a, b) ∈ ρ δo nếu tồn tại một phần tử x ∈ X sao cho (a, x) ∈ ρ và (x, b) ∈ δ.
Phép toán hai ngôi ( )o trên tập hợp β X bao gồm tất cả các quan hệ trên X kết hợp Nếu ,ρ δ và τ là các quan hệ trên X, thì các khẳng định ( , ) (a b ∈ ρ δ τo o) và ( , )a b ∈ρ δ τo o( ) tương đương với việc tồn tại các phần tử x và y thuộc X sao cho ( , )a x ∈ρ , ( , )x y ∈δ và ( , )y b ∈τ Như vậy, β X cùng với phép toán ( )o tạo thành một nửa nhóm, được gọi là nửa nhóm các quan hệ trên X.
1.1.2 Một số quan hệ hai ngôi đặc biệt Giả sử X là một tập hợp tùy ý.
1) Quan hệ i được gọi là quan hệ bằng nhau nếu ( , )a b ∈i khi và chỉ khi a b= với ,a b X∈
2) Quan hệ ω được gọi là quan hệ phổ dụng nếu ( , )a b ∈ω với mọi ,a b X∈
3) Giả sử ρ β∈ X Khi đó quan hệ ngược ρ − 1 của ρ được định nghĩa như sau : ( , )a b ∈ρ − 1 nếu và chỉ nếu ( , )b a ∈ρ
4) Giả sử ,ρ δ β∈ X Khi đó ρ δ⊆ nếu ρ là tập con của δ , nghĩa là a bρ kéo theo a bδ Vì β X gồm tất cả các tập con của X X× , nên ta có thể thực hiện trong β X các phép toán : hợp, giao và phần bù.
5) Giả sử ρ là một quan hệ trên X Khi đóρ được gọi là đối xứng nếu ρ − 1∈ρ(và do đó ρ − 1 =ρ ).
Quan hệ ρ được gọi là phản xạ nếu i⊆ ρ và được gọi là bắc cầu nếu ρ ρ ρo ⊆
Một quan hệ ρ trên tập hợp X được xem là quan hệ tương đương khi nó thỏa mãn ba tính chất: phản xạ, đối xứng và bắc cầu Khi đó, ρ trở thành một lũy đẳng của nửa nhóm β trên X, tức là ρ^2 = ρ.
1.1.3 Phân hoạch một tập hợp Giả sử ρ là một quan hệ trên X và a X∈ Khi đó ta sẽ ký hiệu:
Nếu ρ là quan hệ tương đương trên X thì hai điều kiện sau đây được thỏa mãn: i) a a∈ ρ với mọi a X∈ ii) aρ∩bρ ≠ φ kéo theo aρ =bρ
Họ các tập con aρ của X là một phân hoạch của X, nghĩa là các tập con này không giao nhau và tổng hợp của chúng tạo thành X.
Lớp tương đương X ρ được xác định bởi mối quan hệ tương đương ρ chứa a Mỗi phân hoạch P của tập X sẽ tạo ra một quan hệ tương đương ρ trên X, với P = X ρ Hai phần tử a và b sẽ thuộc quan hệ tương đương a bρ nếu và chỉ nếu chúng nằm trong cùng một tập con của phân hoạch P Ánh xạ a a a ρ được gọi là ánh xạ tự nhiên hay ánh xạ chính tắc.
X lên X ρ và ký hiệu ánh xạ đó là ρ ∗ Chú ý rằng: ρ ∗ ( )a =aρ với mỗi a X∈
1.1.4 Định nghĩa Giả sử S là một nửa nhóm và ρ là một quan hệ trên S Khi đó ρ được gọi là một tương đẳng trên S nếu hai điều kiện sau được thỏa mãn: i) ρ là quan hệ tương đương trên S. ii) ρ ổn định hai phía, nghĩa là nếu a bρ thì ac bcρ và ca cbρ với mọi c S∈
1.1.5 Bổ đề [5] Một quan hệ tương đương ρ trên nửa nhóm S là một tương đẳng nếu và chỉ nếu với mọi x x y y thuộc 1, , ,2 1 2 S có:
1.1.6.Định nghĩa Giả sử ρ là một tương đẳng trên nửa nhóm S và
Tập hợp các lớp tương đẳng của S theo ρ được ký hiệu là Sρ = xρ x S∈ Trong đó, phép toán hai ngôi (xρ ρ, y )a xyρ được xác định trên Sρ, theo Bổ đề 1.1.5, giúp Sρ trở thành một nửa nhóm Nửa nhóm này được gọi là nửa nhóm thương (của S theo modρ) Để chứng minh Định nghĩa 1.1.6 là hợp lý, cần chứng minh phép toán hai ngôi trên Sρ có tính chất kết hợp Cụ thể, với mọi x, y, z thuộc S, ta có tính chất kết hợp này.
1.1.7 Định nghĩa Giả sử S và T là các nửa nhóm Ánh xạ :ϕ S →T được gọi là một đồng cấu (nửa nhóm) nếu ( )ϕ ab =ϕ( ) ( ),a ϕ b ∀a b S, ∈ Đồng cấu ϕ được gọi là đơn cấu, toàn cấu hay đẳng cấu nếu ϕ tương ứng là đơn ánh, toàn ánh hay song ánh.
1.1.8 Định nghĩa Giả sử ρ là một tương đẳng trên nửa nhóm S Khi đó, ánh xạ tự nhiên ρ ∗ : S → S ρcho bởi ρ ∗ ( )a =aρ là một toàn cấu và được gọi là toàn cấu chính tắc.
Vì ρ ∗ là một toàn ánh, nên để chứng tỏ Định nghĩa 1.1.8 hợp lý ta chỉ cần chứng minh ρ ∗ là một đồng cấu Thật vậy, với mọi ,x y S∈ ta có:
( ) ( )xy xy x y ( ) ( )x y ρ ∗ = ρ = ρ ρ ρ= ∗ ρ ∗ ⇒ ρ ∗ là một đồng cấu.
1.1.9 Định nghĩa Giả sử :ϕ S →T là một đồng cấu nửa nhóm Khi đó quan hệKer ( )ϕ trên S cho bởi ( , )x y ∈ Ker ( )ϕ nếu và chỉ nếu ( )ϕ x =ϕ( )y là một tương đẳng trên S và được gọi là tương đẳng hạt nhân của ϕ
Rõ ràng Ker ( )ϕ là một quan hệ tương đương trên S Tính ổn định của Ker ( )ϕ suy ra từ điều kiện ϕ là đồng cấu.
1) Nếu { ρ ∈ i i I } là một họ tương đẳng trên S, thế thì : i i I ρ ρ
= I cũng là một tương đẳng trên S
Giả sử δ là một quan hệ trên tập hợp S Khi đó, δ = C : I {ρ | ρ là một tương đẳng trên S, ρ ⊇ δ} được xác định là tương đẳng bé nhất trên S chứa δ Tương đẳng này, được gọi là tương đẳng sinh bởi δ, đóng vai trò quan trọng trong việc mở rộng quan hệ δ.
Nửa nhóm xyclic
1.2.1 Định nghĩa Giả sử S là một nửa nhóm và a là một phần tử tùy ý của S
Khi đó nửa nhóm con a của S gồm tất cả các lũy thừa nguyên dương của a :
{ , , , 2 3 } a = a a a được gọi là nửa nhóm con xyclic của S sinh bởi a Trong trường hợp S = a thì
S được gọi là nửa nhóm xyclic sinh bởi a và a được gọi là phần tử sinh
Cấp của a được định nghĩa là cấp của nửa nhóm con xyclic a Với mỗi a S∈ chỉ có hai khả năng xảy ra:
1) Hoặc mỗi lũy thừa của a đều khác nhau, khi đó a có cấp vô hạn (đếm được).
2) Hoặc tồn tại các số nguyên dương r s, với r s< sao cho a r =a s Khi đó a có cấp hữu hạn.
Giả sử \( s \) là số nguyên dương nhỏ nhất sao cho \( a^r \) là lũy thừa của phần tử \( a \) với \( r \) nhỏ hơn \( s \) (với \( r \) là số nguyên dương nhỏ nhất có tính chất này) Khi đó, ta có \( a^s = a^r \) và đặt \( m = s - r \), thì \( a^r = a^{m+r} \) Trong trường hợp này, \( m \) được gọi là chu kỳ, còn \( r \) được gọi là chỉ số của phần tử \( a \) hay của nửa nhóm cyclic \( a \).
1.2.2 Mệnh đề Giả sử a là một phần tử của nửa nhóm S và a là nửa nhóm con xyclic sinh bởi a Nếu a là nửa nhóm con xyclic vô hạn thì mọi lũy thừa của a đều khác nhau Nếu a là nửa nhóm xyclic hữu hạn với chỉ số r và chu kỳ m thì a m r + =a r và a = { a a , 2 , , a m r + − 1 } Khi đó cấp của nửa nhóm con a bằng
Tập hợp K a = { a a r , r + 1 , , a r + m − 1 } là nhóm con xyclic cấp m của nửa nhóm S.
+ Nếu a là nửa nhóm xyclic vô hạn, từ Định nghĩa 1.2.1 suy ra số phần tử của nửa nhóm a là vô hạn và mọi lũy thừa của a đều khác nhau.
+ Nếu a là nửa nhóm xyclic hữu hạn với chu kỳ m và chỉ số r thì theo Định nghĩa 1.2.1, tồn tại hai số nguyên dương r và s sao cho a r = a s
Do m là chu kỳ nên m s r= − ; khi đó a r = a m r + và vì các phần tử
, , , s a a a − đôi một khác nhau nên suy ra :
+ Tập hợp K a = { a a r , r + 1 , , a r + m − 1 } là nhóm con xyclic cấp m của S.
Thật vậy, hiển nhiên K a là nửa nhóm con của S Ta đặt a n ∈K a với
Xét ánh xạ ϕ : a n a ( ) m + n trong đó ( ) m + n là lớp thặng dư các số nguyên theo modm chứa n Thế thì ϕ là một đẳng cấu từ K a lên nhóm cộng
Z ( ) m tất cả các lớp thặng dư theo modm Từ đó, K a là nhóm con xyclic cấp m của nửa nhóm S.
1.2.3 Mệnh đề Giả sử S = a là nửa nhóm xyclic hữu hạn với chu kỳ m và chỉ số r ; n là số tự nhiên thỏa mãn r ≤ ≤ +n m r và n≡0(mod m ) Khi đó a n là đơn vị của nhóm con tối đại K a = { a a r , r + 1 , , a r m + − 1 }
Chứng minh Xét ánh xạ ϕ: K a →¢ m a h a h
Khi đó ϕ là một đồng cấu nhóm và ϕ ( ) a h = ⇔ = ⇔ ≡ 0 h 0 h 0 mod ( m ) với r h m r≤ ≤ + □
1) Từ đây trở đi, ta sẽ ký hiệu nhóm cộng tất cả các số nguyên là ¢, nửa nhóm cộng tất cả các số nguyên dương là ¢ + và vị nhóm cộng các số nguyên không âm là ¥.Từ định nghĩa suy ra mọi nửa nhóm xyclic vô hạn đều đẳng cấu với ¢ + và mọi vị nhóm xyclic vô hạn đẳng cấu với ¥
2) Đối với hai số nguyên dương tùy ý cho trước r và m, có thể xây dựng nửa nhóm xyclic a mà chỉ số bằng r và chu kỳ bằng m; chẳng hạn nửa nhóm sinh bởi phép biến đổi
=ỗỗỗố + + - ữữữứ của tập {0,1, 2, , ,r r+1,r+2, ,r m+ −1} Hiển nhiên hai nửa nhóm xyclic đẳng cấu với nhau khi và chỉ khi chúng có cùng chỉ số và cùng chu kỳ
1.2.5 Định nghĩa Giả sử A là một tập con khác rỗng của nửa nhóm ¢ + Khi đó
A được gọi là cô lập nếu từ đẳng thức a b c= + với a A b A c∈ , ∈ , ∈¢ + kéo theo c A∈
1.2.6 Mệnh đề Giả sử A là nửa nhóm con của nửa nhóm xyclic vô hạn ¢ + Khi đó A là nửa nhóm con xyclic khi và chỉ khi A cô lập trong ¢ +
+) Điều kiện cần Giả sử A là nửa nhóm xyclic, khi đó A m= ¢ + với m∈¢ +
Từ a b c= + với a A b A ∈ , ∈ suy ra tồn tại a'∈¢ + , 'b ∈¢ + sao cho ', ' a m a b m b= = Vì a b c= + nên a b> , do đó 'a >b' Khi đó, từ 'm a =m b c '+ suy ra c m a b = ( ' − ') ∈ A Vậy A cô lập trong ¢ +
+) Điều kiện đủ Giả sử A cô lập trong ¢ + Gọi k : min = { a a A ∈ } và
- Nếu q = 0 thì n r k= < mâu thuẫn với cách chọn k.
- Nếu q ≤ − 1 thì k q ≤ − k , do đó k q r r k + ≤ − suy ra n