NỬA NHÓM 0 – ĐƠN HOÀN TOÀN
Nửa nhóm 0 – đơn hoàn toàn
Giả sử E là tập hợp tất cả các lũy đẳng của nửa nhóm S, ta xác định quan hệ trên E với e f nếu và chỉ nếu ef = fe = e Quan hệ này tạo thành một thứ tự bộ phận trên E Nếu S chứa phần tử zero 0, thì 0 e với mọi e thuộc E Lũy đẳng f trong nửa nhóm S được gọi là nguyên thủy nếu f khác 0 và nếu e f thì e phải bằng 0 hoặc e bằng f.
1.1.1 Định nghĩa (i) Nửa nhóm S (không chứa phần tử zero 0) đƣợc gọi là đơn nếu S không chứa iđêan thực sự hai phía
(ii) Nửa nhóm S với phần tử zero 0 đƣợc gọi là nửa nhóm 0 - đơn nếu
S 2 {0} và S chỉ chứa hai iđêan là {0} và S
(iii) Nửa nhóm S với phần tử zero 0 đƣợc gọi là nửa nhóm đơn (0 - đơn) hoàn toàn nếu S là một nửa nhóm đơn (0 - đơn) chứa lũy đẳng nguyên thủy
Từ Định nghĩa 1.1.1 suy ra rằng nửa nhóm đơn (0 - đơn) hữu hạn là đơn (0 - đơn) hoàn toàn Thật vậy, S hữu hạn nên S chứa lũy đẳng, do đó
E = E(S) , và E {0} vì nếu không, mọi phần tử trong S sẽ là lũy linh Do S là hữu hạn, nên S trở thành nửa nhóm lũy linh, tức là tồn tại một số nguyên dương n sao cho S^n = 0, điều này mâu thuẫn với giả thiết S^2 = S Do đó, tập hữu hạn E \ {0} có một phần tử tối thiểu, đó chính là lũy đẳng nguyên thủy.
Từ Định nghĩa 1.1.1 cũng trực tiếp suy ra: Nếu S là một nửa nhóm
0 - đơn thì S\{0} là một nửa nhóm con đơn của S
1.1.2 Định nghĩa (i) Giả sử S là một nửa nhóm không chứa phần tử 0 và M là một iđêan của S Khi đó M đƣợc gọi là iđêan tối tiểu nếu nó không chứa iđêan thực sự của S
(ii) Giả sử S là một nửa nhóm với phần tử 0 và M là một iđêan của S Khi đó
M đƣợc gọi là một iđêan 0 - tối tiểu nếu M {0} và {0} là iđêan thực sự duy nhất của S đƣợc chứa trong M
1.1.3 Mệnh đề [1] Giả sử S là một nửa nhóm 0 - đơn Khi đó S là nửa nhóm
0 - đơn hoàn toàn nếu và chỉ nếu S chứa ít nhất một iđêan trái 0 - tối tiểu và một iđêan phải 0 - tối tiểu
1.1.4 Định nghĩa Giả sử S là một nửa nhóm Ta định nghĩa các quan hệ
L, R, T và H trên S nhƣ sau: a L b S 1 a = S 1 b a R b aS 1 = bS 1 a T b S 1 a S 1 = S 1 b S 1 trong đó S 1 a, aS 1 , S 1 a S 1 là các iđêan chính trái, chính phải và iđêan chính của
S sinh bởi a Khi đó các quan hệ L, R, T là các quan hệ tương đương trên S, hơn nữa L 0 R = R 0 L Thế thì D := L 0 R (= R 0 L ) và H := L R cũng là các quan hệ tương đương trên S
L, R, T, D và H đƣợc gọi là các quan hệ Grin trên nửa nhóm S
1.1.5 Định nghĩa Một nửa nhóm S đƣợc gọi là D – đơn hoặc song đơn nếu
Ta chú ý rằng một nửa nhóm đơn trái (phải) nếu và chỉ nếu nó gồm một
Lớp L (tương ứng với lớp R) và nửa nhóm đơn chỉ tồn tại khi có một T – lớp duy nhất Do D chứa L, nên mọi nửa nhóm song đơn đều là nửa nhóm đơn Hơn nữa, vì R và L đều nằm trong D, nên các nửa nhóm đơn phải và trái cũng là song đơn.
1.1.6 Mệnh đề Mỗi nửa nhóm 0 - đơn hoàn toàn là 0 - song đơn và chính quy
Giả sử S là một nửa nhóm 0 - đơn hoàn toàn, với a và b là các phần tử khác 0 thuộc S Chúng ta cần chứng minh rằng a D b Vì S là hợp của các iđêan trái (phải) 0 - tối tiểu, nên a thuộc một iđêan trái 0 - tối tiểu L nào đó và b thuộc một iđêan phải 0 - tối tiểu R nào đó của S.
L = Sa và R = bS, với La = L\0 và Rb = R\0 Từ việc a thuộc L và b thuộc R, ta suy ra bSa ⊆ R ∩ L Vì S là một nửa nhóm 0 - đơn và a ≠ 0, b ≠ 0, nên SaS = S và SbS = S Do đó, S = S² = SbSSaS ⊆ S(bSa), dẫn đến bSa ≠ 0 Vì Rb ∩ La chứa tập con khác rỗng bSa\0, nên a D b.
Theo định nghĩa của nửa nhóm 0 - đơn hoàn toàn, D - lớp S\0 chứa lũy đẳng (nguyên thủy) Mỗi phần tử của S\0 được xác định là chính quy, và vì 0 cũng là chính quy, nên S được coi là nửa nhóm chính quy.
Ta nhắc lại rằng một nửa nhóm bixyclic là vị nhóm C = C(p,q) sinh bởi hai ký hiệu p, q và cho bởi một hệ thức xác định pq = 1
1.1.7 Định lý Nửa nhóm bixyclic C = C (p,q) là một nửa nhóm ngược song đơn chứa đơn vị Các lũy đẳng của nó là các phần tử e n = q n p n (n = 0,1,2,…) Chúng thỏa mãn bất đẳng thức 1 = e 0 > e 1 > e 2 > … > e n > e n+1 > …, vì vậy
C không chứa lũy đẳng nguyên thủy
Chứng minh Thử đƣợc rằng hai phần tử q k p l và q m p n thuộc nửa nhóm C (k, l, m, n là các số nguyên không âm) nhân với nhau nhƣ sau:
Chú ý rằng i k Do đó i k nếu q i p j thuộc iđêan chính bên phải R(q k p l ) sinh bởi phần tử q k p l Đảo lại, nếu i k thì q i p j R(q k p l ); chỉ cần lấy m = l + i - k, n = j
Nếu ta viết các phần tử thuộc C thành bảng
R(q k p l) có thể được mô tả là tập hợp tất cả các dòng của bảng bắt đầu từ dòng thứ k + 1 trở xuống, cho thấy rằng R - lớp chứa q k p l trùng với dòng thứ k + 1 Tương tự, L - lớp chứa q k p l trùng với cột thứ l + 1 Như vậy, các R - lớp của nửa nhóm C là các dòng, còn các L - lớp của C là các cột của bảng Điều này dẫn đến việc các H - lớp của C là các tập hợp gồm một phần tử Vì mỗi R - lớp đều giao với mỗi L - lớp, D - lớp duy nhất của C là chính C, từ đó kết luận rằng C là song đơn.
Giả sử rằng q m p n là một lũy đẳng, ta có q m p n = q i p j với i = 2m - min(m, n) và j = 2n - min(m, n), dẫn đến m = i và n = j Điều này cho thấy m = min(m, n) và n = min(m, n), tức là m = n Ngược lại, ta dễ dàng nhận thấy rằng en = q n p n cũng là lũy đẳng Nếu m < n, qua tính toán trực tiếp, ta có emen = enem = en, từ đó suy ra em ≥ en Hơn nữa, em ≠ en nếu m ≠ n, do đó m < n dẫn đến em > en, và do đó không chứa lũy đẳng nguyên thủy.
Do C chứa lũy đẳng và chỉ bao gồm một D - lớp, nên C được coi là chính quy Với điều kiện emen enem = en khi m < n, các lũy đẳng của C sẽ giao hoán với nhau, dẫn đến việc C trở thành một nửa nhóm ngược.
Nửa nhóm ma trận trên một nhóm với phần tử không
1.2.1 Định nghĩa Giả sử G là một nhóm, G 0 = G 0 là nhóm với phần tử không thu đƣợc từ G bằng cách ghép thêm phần tử không 0 (0 G ) Giả sử I và là các tập tùy ý Ta định nghĩa I X ma trận Rixơ trên G 0 là ánh xạ
Trong bài viết này, chúng ta xem xét một ma trận Rixơ trên tập hợp G0, với điều kiện rằng mỗi phần tử ai chỉ có tối đa một phần tử khác không Đối với a thuộc G, i thuộc I và λ thuộc Λ, ma trận Rixơ được ký hiệu là (aiλ), trong đó a nằm ở dòng i và cột λ, trong khi tất cả các vị trí khác đều bằng 0 Đối với mỗi i thuộc I và λ thuộc Λ, ký hiệu (0iλ) được sử dụng để biểu thị một ma trận đặc biệt.
I X ma trận không, cũng ký hiệu là 0
Bây giờ giả sử P = p i là một X I ma trận tùy ý nhƣng cố định trên
G 0 Ta dùng P để định nghĩa một phép toán hai ngôi (o) trong tập các I X ma trận Rixơ trên G 0 nhƣ sau:
Nếu A và B là các I X ma trận Rixơ trên G 0 thì Ao cũng vậy
Thật vậy, nếu A = a i , B = b j thì a i o b j = ap b j j , (a, b G; i, j I; , ) (1)
Hơn nữa, phép toán (o) có tính kết hợp:
Ao(BoC) = AP(BPC) = (APB)PC = (AoB)oC
Tập hợp tất cả các ma trận Rixơ trên G 0 tạo thành một nửa nhóm đối với phép toán (o), được gọi là nửa nhóm I X ma trận Rixơ trên nhóm với phần tử không G 0 và ma trận đệm P, ký hiệu là M 0 (G; I, ; P) Trong trường hợp này, G được xem là nhóm cơ sở của M 0.
1.2.2 Mệnh đề Nửa nhóm I X ma trận Rixơ M 0 (G; I, ; P) trên nhóm với phần tử không G 0 với ma trận đệm P là nửa nhóm chính quy khi và chỉ khi mỗi dòng và mỗi cột của P chứa một phần tử khác không
Chứng minh Giả sử P = p i ; a, b G; i, j I; , Khi đó
a i o b j o a i = ap bp a j i i Vế phải bằng a i khi và chỉ khi p bp j i a 1
Với a i đã cho, phần tử b i tồn tại trong M 0 nếu và chỉ nếu p j 0 và p i 0 cho j I và Điều này xảy ra khi dòng thứ và cột thứ i của ma trận P có chứa một phần tử khác không của G 0.
Ma trận P được xác định là không chính quy trên một nhóm nếu và chỉ nếu mỗi dòng và mỗi cột của ma trận P đều có ít nhất một phần tử khác không.
Bây giờ, ta ký hiệu các phần tử của M 0 là a i , trong đó a G 0 , i I,
H i R i L a i |a G Trong [1] đã chứng minh đƣợc kết quả sau
1.2.3 Mệnh đề (i) Với mỗi i I, R 0 i là một iđêan phải của M 0 ; hai phần tử
R - tương đương của M 0 \0 phải thuộc cùng một R i với i nào đó thuộc I
(ii) Nếu P là chính quy (mỗi dòng và mỗi cột của P chứa một phần tử khác không) thì với mỗi i I, R 0 i là iđêan phải 0 - tối tiểu của M 0 , và R i là một
(iii) Nếu với i nào đó thuộc I, p i 0 với mỗi thì R i 0 là iđêan hai phía của M 0 , sao cho M 0 o R 0 i = 0; đặc biệt ( R i 0 ) 2 = 0
Tập H i (i I; ) chứa một phần tử lũy đẳng nếu và chỉ khi p i 0 Khi p i 0, H i trở thành một H - lớp của M 0 và là nhóm con của M 0 với phần tử đơn vị e i (p i 1) i Phép ánh xạ a (ap i 1) i là một phép đẳng cấu từ G lên H i .
Ta nhắc lại rằng, nửa nhóm ma trận Rixơ (G; I, ; P) đƣợc gọi là chính quy khi và chỉ khi ma trận đệm P là ma trận chính quy
1.2.4 Định lý Nửa nhóm ma trận Rixơ 0 - đơn khi và chỉ khi nó là chính quy, và khi đó nó là 0 - đơn hoàn toàn
Giả sử M 0 = M 0 (G; I, ; P) là nửa nhóm ma trận Rixơ Nếu M 0 không chính quy, theo Mệnh đề 1.2.2, tồn tại một dòng hoặc cột của P gồm toàn phần tử không, ví dụ cột thứ i với p i = 0 cho mọi ∈ Theo Mệnh đề 1.2.3(iii), R 0 i là iđêan lũy linh khác không của M 0, từ đó suy ra M 0 không thể là 0 - đơn Ngược lại, nếu M 0 là chính quy, với hai phần tử tùy ý a i và b j thuộc M 0 (với a ≠ 0), theo Mệnh đề 1.2.2, tồn tại ∈ và k ∈ I sao cho p i ≠ 0 và p k ≠ 0 Giả sử c = b( p ap i k ) − 1 và e là phần tử đơn vị của G.
( ) c j o a ( ) i o e ( ) k ( ) b j và do đó M 0 là 0 - đơn
Do Mệnh đề 1.2.3(iv), các lũy đẳng khác không của M 0 là các phần tử
Mỗi cặp i, λ (với i thuộc I và λ thuộc Λ) tồn tại một phần tử e_i^λ sao cho p_λ^i khác 0 Nếu e_i^λ o e_j^μ = e_j^μ o e_i^λ, thì i phải bằng j và λ μ phải bằng nhau, do đó e_i^λ = e_j^μ Điều này cho thấy mỗi lũy thừa khác không của M_0 là nguyên thủy, dẫn đến kết luận rằng M_0 là 0 - đơn hoàn toàn.
Nếu M 0 bằng 0, điều này cho thấy M là đơn hoàn toàn và P là chính quy Theo mệnh đề 1.2.3 (ii) và mệnh đề đối ngẫu, mỗi Ri được xác định là một R - lớp, trong khi mỗi L được xác định là một L - lớp.
NỬA NHÓM 0 – ĐƠN HOÀN TOÀN VỚI BIỂU DIỄN HỮU HẠN
Nửa nhóm tự do Vị nhóm tự do
2.1.1 Định nghĩa Giả sử A là một tập các ký hiệu Chúng ta sẽ gọi A là một bảng chữ cái và các phần tử của nó là các chữ cái Một dãy hữu hạn các chữ cái gọi là một từ Tập hợp tất cả các từ trên A đƣợc ký hiệu là A + Chúng ta sẽ viết u v nếu các từ u và v là nhƣ nhau
Tập hợp A + được định nghĩa là nửa nhóm của các từ trong A, trong đó tích của các từ được xác định bằng cách ghép nối các từ liên tiếp Cụ thể, nếu w1 = a1a2 an và w2 = b1b2 bm (với ai, bj thuộc A), thì tích w sẽ được biểu diễn là w = a1a2 an b1b2 bm.
Khi bổ sung vào A + từ rỗng 1 (từ không có chữ cái nào), chúng ta nhận đƣợc vị nhóm các từ A * Rõ ràng A * = A + {1} với 1 A + và 1.w = w.1 = w, với mọi w A +
2.1.2 Định nghĩa Giả sử S là một nửa nhóm Một tập con X của S đƣợc gọi là sinh ra S một cách tự do nếu X là một tập sinh của S (ký hiệu là S = [X]S) và mỗi ánh xạ 0 : X P (trong đó P là nửa nhóm bất kỳ) có thể mở rộng thành một đồng cấu : SP sao cho | X = 0 Khi đó chúng ta sẽ nói rằng
là một mở rộng đồng cấu của ánh xạ 0
Nếu S đƣợc sinh tự do bởi một tập nào đó thì S đƣợc gọi là nửa nhóm tự do
2.1.3 Ví dụ 1 ( * , +) nửa nhóm tự do với X = {1} là tập sinh tự do của nó
Nếu 0 : X P là một ánh xạ thì ta định nghĩa : * P bởi (n) = 0 (1) n
Khi đó |X = 0 và là đồng cấu vì
2 ( * , ) không phải là nửa nhóm tự do Giả sử X * , chọn
P = ( * , +) và giả sử 0(n) = n, nX Nếu : ( * , ) P là một đồng cấu thì (n) = (1.n) = (1) + (n) và do đó (1) = 0 P Nhƣ vậy
không phải là mở rộng của 0
2.1.4 Định lý Đối với bảng chữ cái A tùy ý, A + là một nửa nhóm tự do được sinh bởi A
Chứng minh rằng A sinh ra A+ vì mọi từ đều là một chuỗi các ký tự thuộc A Giả sử S là một nửa nhóm tùy ý và ánh xạ 0: A S là bất kỳ Chúng ta định nghĩa ánh xạ : A+ S với công thức (a1 a2 an) = 0(a1)0(a2)
0(an), (n1, ai A) Khi đó, (a) = 0 (a) (chọn n = 1) nên |A = 0 Mặt khác là đòng cấu theo cách xác định và định nghĩa nửa nhóm A +
2.1.5 Định lý Nếu S được sinh tự do bởi X và 0 : X P là một ánh xạ, thì
0 có một mở rộng đồng cấu duy nhất : S P
Chứng minh Theo định nghĩa, mỗi 0 có một mở rộng Giả sử : S P và
: S P là các mở rộng đồng cấu của 0 Khi đó với mọi x S, x = x1 x2 xn với các phần tử xi X nào đó, vì X sinh ra S Thế thì
(x) = (x1) (x2) (xn) = 0 (x1) 0 (x2) 0 (xn) = (x 1 ) (x 2 ) (x n ) = (x 1 x 2 x n ) = (x) và do đó =
Kết quả cho thấy rằng mỗi nửa nhóm S là một ảnh đồng cấu của nửa nhóm các từ, từ đó các nửa nhóm này trở thành cơ sở cho các nửa nhóm khác Điều này cho phép xây dựng mọi nửa nhóm tùy ý dựa trên nửa nhóm các từ.
2.1.6 Định lý Đối với nửa nhóm S, tồn tại một bảng chữ cái A và một toàn cấu : A + S
Giả sử X là một tập sinh tùy ý của S và A là một bảng chữ cái với |A| = |X|, thì tồn tại một song ánh 0: A X Theo định nghĩa về tính tự do, 0 có thể được mở rộng thành một đồng cấu : A + S Mở rộng này là toàn ánh, vì A + = A A dẫn đến (A + ) = ( A A ) = [ (A)] S = [X]S = S, do S sinh ra X.
2.1.7 Hệ quả Mỗi nửa nhóm là một thương của nửa nhóm tự do
Chứng minh Thật vậy, S A / er( ) k đối với toàn cấu đã nêu trong Định lý
2.1.8 Định lý Một nửa nhóm tự do nếu và chỉ nếu nó đẳng cấu với nửa nhóm các từ A + với một bảng chữ cái A nào đó
Giả sử S được sinh tự do bởi tập con X ⊆ S và A là một bảng chữ cái với |A| = |X| Từ đó, ta có thể xác định một song ánh ψ₀: A → X Do A sinh ra A+ một cách tự do, theo Định lý 1.2.6, tồn tại một mở rộng toàn cấu ψ: A+ → S.
0 : X A cũng là song ánh và S đƣợc sinh ra tự do bởi X nên 0 1 có một mở rộng toàn cấu : S A + Cái hợp thành : A + A + là một toàn cấu thỏa mãn điều kiện:
Vì i A : A A đƣợc mở rộng một cách duy nhất tới đồng cấu đồng nhất
A : i A A nên = i A Vì = i A là song ánh nên đơn ánh và do đó
là song ánh Từ đó là một đẳng cấu
Mặt khác, giả sử rằng tồn tại một đẳng cấu : A + S Khi đó
S = [ (A)]S và có một ánh xạ ngƣợc 1 : S A + cũng là đẳng cấu Xác định ánh xạ 0 = |A và X = (A) Giả sử P là một nửa nhóm tùy ý và
Ánh xạ bất kỳ 0: X P cho phép mở rộng duy nhất thành đồng cấu : A + P thông qua ánh xạ 0 0 : A P Xét ánh xạ = 1 : S P, đây cũng là một đồng cấu do 1 và đều là đồng cấu Hơn nữa, với mỗi x thuộc X, điều này được xác nhận.
(x) = ( 1 (x)) = 0 0 0 1 (x) = 0 (x), và do đó |X = 0 , nghĩa là là một mở rộng đồng cấu của 0 Theo định nghĩa S đƣợc sinh tự do bởi X
2.1.9 Định nghĩa Vị nhóm M gọi là một vị nhóm tự do đƣợc sinh tự do bởi một tập con X với 1 X nếu X {1} là một tập sinh của M và mỗi ánh xạ
0: X P (trong đó P là một vị nhóm) mở rộng đƣợc thành một đồng cấu vị nhóm duy nhất : M P, nghĩa là |X = 0 và (1M) = 1P
2.1.10 Định lý Nếu S là một nửa nhóm tự do thì S 1 là vị nhóm tự do
2.1.11 Hệ quả Vị nhóm các từ A + là một vị nhóm tự do với mọi bảng chữ cái A.
Biểu diễn mô tả của các nửa nhóm
2.2.1 Định nghĩa và ký hiệu (i) Giả sử A là một bảng chữ cái Một biểu diễn nửa nhóm là cặp trong đó R A + x A + với A + là nửa nhóm các từ trên A Các phần tử của A đƣợc gọi là các ký hiệu sinh hay là các phần tử sinh, và các phần tử của R đƣợc gọi là các hệ thức xác định Một cặp
Trong không gian R, hai phần tử u và v luôn được biểu diễn bởi u = v Nửa nhóm được xác định bởi biểu diễn là nửa nhóm thương S = A + /ρ, trong đó ρ là tương đẳng nhỏ nhất trên A + chứa R Đối với hai từ w1 và w2 thuộc A +, ta ký hiệu w1 w2 nếu chúng là các từ đồng nhất trong A +, và w1 = w2 nếu chúng biểu diễn cùng một phần tử của S, tức là (w1, w2) thuộc ρ Khi đó, ta nói rằng S thỏa mãn hệ thức w1 = w2.
(ii) Giả sử T là một nửa nhóm đƣợc sinh bởi một tập B và : A B là một toàn ánh Ta có thể mở rộng theo cách duy nhất thành toàn cấu
T nói rằng T thỏa mãn các hệ thức R nếu với mỗi hệ thức u = v trong R, ta có u’ = v’ Chú ý rằng từ đây, chúng ta sẽ sử dụng ký hiệu u thay cho (u) Do đó, hệ thức được viết lại thành u’ = v’ Hạt nhân của ’, ký hiệu là ker(’), được định nghĩa là tập hợp các cặp (u, v) thuộc A + x A + sao cho u’ = v’.
2.2.2 Mệnh đề Giả sử là một biểu diễn, S là nửa nhóm được xác định bởi nó và T là một nửa nhóm thỏa mãn R Thế thì T là ảnh đồng cấu của S.
Theo Định nghĩa 2.1.1, S = A + /ρ, trong đó ρ là tương đẳng nhỏ nhất trên S chứa R Vì T thỏa mãn R, tồn tại toàn cấu φ: A + → T sao cho với (u = v) ∈ R, có uφ = vφ Từ đó, R ⊆ Ker(φ), mà Ker(φ) là một tương đẳng trên A + nên ρ ⊆ Ker(φ) Do đó, A + /Ker(φ) là ảnh đồng cấu của A + /ρ Theo Định lý đồng cấu nửa nhóm, A + /Ker(φ) ≅ T và theo giả thiết, A + /ρ ≅ S Như vậy, T là một ảnh đồng cấu của S.
2.2.3 Chú ý Giả sử w1, w2 A + , ta nói rằng w2 nhận được từ w1 bằng cách áp dụng một hệ thức từ R nếu tồn tại , A và một hệ thức u = v trong R sao cho w 1 u ; w 2 v Ký hiệu w1 w2
Ta nói rằng w2 đƣợc dẫn xuất từ w1 nếu tồn tại một dãy hữu hạn
1 1 2 1 2 w , , , k , k w sao cho i i 1 , i 1, k 1 Ta cũng nói rằng w1 = w2 là một hệ quả của R
Kết quả sau đây đƣợc nêu trong [4] (trang 23 – 24)
2.2.4 Mệnh đề Giả sử S là một vị nhóm được sinh bởi tập A và R là một tập con của A + x A + Thế thì là một biểu diễn đối với S nếu và chỉ nếu:
(i) S thỏa mãn tất cả các hệ thức từ R
(ii) Nếu u,v là hai từ thuộc A + sao cho S thỏa mãn u = v Thế thì u = v là một hệ quả của R
2.2.5 Ví dụ 1 Biểu diễn xác định nửa nhóm tự do A + , vì tương đẳng nhỏ nhất trên A + chứa tập rỗng là quan hệ đường chéo
2 Xét tập con R = {(a,a 2 )} của {a} + x {a} + và là tương đẳng nhỏ nhất trên {a} + chứa R , thế thì: aa 2 a 2 a 3 aa 2 a 2 a 3 aa 3 aa 3 a 2 a 4 aa 2 a 2 a 4 aa 4
Do đó a = {a} + , từ đó {a} + / là nửa nhóm tầm thường Vậy ta có thể kết luận được rằng biểu diễn xác định nửa nhóm tầm thường
3 Biểu diễn xác định nửa nhóm đơn diễn (xyclic) cấp n + r – 1 và chu kỳ n
Giả sử M = {a, a², …, aⁿ, …, aⁿ⁺ʳ⁻¹} là nửa nhóm đơn diễn cấp n + r - 1 và chu kỳ n, với r là số nguyên dương nhỏ nhất sao cho aᵏ được lặp lại Khi đó, n+r là lũy thừa lặp lại đầu tiên của r, dẫn đến aʳ = aⁿ⁺ʳ Nếu M thỏa mãn hệ thức aₚ₁ = aₚ₂, ta có thể giả thiết aₚ₂ là sự lặp lại đầu tiên của aₚ₁ Chúng ta chứng minh rằng aₚ₁ ≡ aₚ₂ nếu p₁ = p₂ Nếu p₁ > p₂ mà không mất tính tổng quát, và p₁, p₂ ≥ r với p₁ ≡ p₂ (mod n), thì aₚ₁ ≡ aₚ₂ được dẫn xuất từ aⁿ⁺ʳ = aʳ Trong trường hợp này, có thể viết p₂ - p₁ = kn với k ∈ ℕ, dẫn đến aₚ₁ ≡ aᵏⁿ₊₂ ≡ aᵏⁿʳ + aₚ₂ - r.
( k 2) n n r p 2 r a a a a ( k 2) n a a r p 2 r … a a r p 2 r a p 2 , do đó có thể kết luận đƣợc rằng a p 1 a p 2 có thể đƣợc dẫn xuất từ a n+r = a r
Vì r là lũy thừa nhỏ nhất của a được lặp lại trong M, nên p1 ≥ r và p2 ≥ r Giả sử n không phải là ước của p2 - p1, ta có p2 - p1 = kn + q với k ∈ N và 0 < q < n Từ đó, ta có p1a = ap1 - ra^r = ap1 - ra^n + = ap1 - ra^(kn) = ap1 + kn = ap2 - q Điều này dẫn đến p1a = ap2 - q và p2 - q < p2, tạo ra mâu thuẫn với việc ap2 là sự lặp lại đầu tiên của ap1.
Vậy phải có p2 p1 (mod n) và chúng ta kết luận đƣợc rằng a p 1 = a p 2 là một hệ quả của a n+r = a r Theo Mệnh đề 2.2.4 biểu diễn xác định M
Kết quả sau đây chứng tỏ rằng chúng ta luôn luôn có thể nhận đƣợc một biểu diễn đối với một nửa nhóm bởi bảng nhân của nó
2.2.6 Mệnh đề Một nửa nhóm tùy ý có thể được xác định bởi một biểu diễn
Chứng minh Giả sử S là một nửa nhóm tùy ý và xác định một bảng chữ cái
A = {as | s S} Khi đó A tương ứng một một với S Tập hợp R = {a xay = axy| x, y S} đƣợc chứa trong A + x A + nên có thể xét biểu diễn Giả sử
T là nửa nhóm được xác định bởi biểu diễn này, trong khi S thỏa mãn tất cả các hệ thức của R, theo định nghĩa của nửa nhóm Do đó, theo Mệnh đề 2.2.2, S là một ảnh đồng cấu của T, nghĩa là tồn tại một toàn cấu : T S, với a s s.
Giả sử u, v thuộc A+ và u φ = v φ, thì tồn tại x, y thuộc S sao cho u = ax và v = ay trong T Từ đó, ta có a x φ = a y φ tương đương với x = y, dẫn đến ax = ay, do đó u = v trong T Như vậy, φ là một ánh xạ một-một và từ đó S đẳng cấu với
T, nên S đƣợc biểu diễn bởi
2.2.7 Chú ý Giả sử A là một bảng chữ cái Chúng ta định nghĩa một biểu diễn vị nhóm hoàn toàn giống nhƣ một biểu diễn nửa nhóm bằng cách thay thế A + bởi A*
Một biểu diễn nhóm cũng đƣợc định nghĩa nhƣ biểu diễn nửa nhóm nhƣng thay thế A bởi GF(A), trong đó GF(A) là nhóm tự do sinh bởi A
(1) Giả sử S là một vị nhóm đƣợc xác định bởi biểu diễn , thế thì S đƣợc xác định bởi biểu diễn nửa nhóm
Giả sử S là một vị nhóm đƣợc xác định bởi biểu diễn nửa nhóm
Tồn tại một phần tử w trong A + biểu diễn đơn vị của S và khi đó S đƣợc xác định bởi biểu diễn vị nhóm
(2) Giả sử nhóm G đƣợc xác định bởi biểu diễn nhóm Khi đó G đƣợc xác định bởi biểu diễn vị nhóm
2.2.9 Phương pháp tìm biểu diễn của một nửa nhóm cho trước
Cho một nửa nhóm S, một phương pháp để nhận được biểu diễn của S bao gồm các bước sau:
*) Tìm một tập hợp các phần tử sinh A của S;
*) Tìm một tập hợp R các hệ thức mà chúng đƣợc thỏa mãn bởi các phần tử sinh A, và đủ để xác định S;
*) Tìm một tập hợp W A + sao cho mỗi từ thuộc A + có thể đƣợc biến đổi thành một từ thuộc W bằng cách áp dụng các hệ thức thuộc R ;
*) Chứng minh rằng các từ phân biệt thuộc W biểu diễn các phần tử phân biệt thuộc S
Tập W đƣợc mô tả nhƣ trên đƣợc gọi là một tập hợp các dạng chính tắc hay các dạng chuẩn tắc đối với S
Phương pháp tìm biểu diễn như trên được N Ruskue (1995) đề xuất, và kết quả dưới đây chứng minh rằng biểu diễn mà chúng ta thu được thực sự là biểu diễn đối với S.
2.2.10 Mệnh đề Giả sử S là một nửa nhóm, A là một tập sinh của S,
(i) Các phần tử sinh A của S thỏa mãn tất cả các hệ thức từ R ;
(ii) Đối với mỗi từ w A + tồn tại một từ w’ W sao cho w = w’ là một hệ quả của R;
(iii) Nếu u,v W sao cho u v thế thì u v trong S; khi đó xác định S theo các phần tử sinh A
Chứng minh rằng tập hợp A sinh ra nửa nhóm S và R thỏa mãn trong S Để làm điều này, chỉ cần chỉ ra rằng một hệ thức bất kỳ trong S là hệ quả của R Giả sử w1 và w2 là các phần tử tùy ý thuộc S, với điều kiện w1 = w2 đúng trong S Do đó, tồn tại w1, w2 thuộc W sao cho các hệ thức w1 = w'1 và w2 = w'2 là hệ quả của R.
Từ w1 = w2 ta có (theo (iii)) w1 w2 Do đó w1 = w’1 = w’2 = w2 là một hệ quả của R Nhƣ vậy S đƣợc xác định bởi biểu diễn
2.2.11 Các phép biến đổi Tietze
Một phương pháp để liên hệ hai biểu diễn khác nhau của cùng một nửa nhóm là các phép biến đổi Tietze Các phép biến đổi này bao gồm bốn toán tử, cho phép chuyển đổi từ một biểu diễn này sang một biểu diễn khác mà vẫn giữ nguyên cấu trúc.
Cho trước một biểu diễn , chúng ta có thể:
Bổ sung một hệ thức cho trước u, v thuộc A+ với điều kiện u = v không phụ thuộc vào R, nhưng lại là hệ quả của các hệ thức trong R Do đó, biểu diễn sẽ xác định cùng một cấu trúc như .
T2) Khử một hệ thức: Nếu u = v là một hệ thức sao cho nó là một hệ quả của các hệ thức trong R \{(u,v)}; thế thì cấu trúc đƣợc xác định bởi
có thể đƣợc xác định bởi biểu diễn
Nửa nhóm 0 – đơn hoàn toàn với biểu diễn hữu hạn
Để tiện theo dõi, ta nhắc lại một số khái niệm và kết quả liên quan đã trình bày ở chương trước hoặc đã biết
Một nửa nhóm không có phần tử zero được gọi là đơn nếu không có iđêan thực sự Nếu nửa nhóm S có phần tử zero 0 và chỉ có hai iđêan {0} và S, với S khác 2, thì S được gọi là 0-đơn Nửa nhóm 0-đơn cũng được xem là đơn.
0 - đơn hoàn toàn (tương ứng đơn hoàn toàn) nếu nó chứa một lũy đẳng nguyên thủy (là lũy đẳng tối tiểu trong tập các lũy đẳng khác không)
Từ Định lý Rixơ, ta có kết quả sau đây
2.3.1.Mệnh đề Giả sử G o (G) là một 0 - nhóm (nhóm) Giả sử I, là các tập hợp khác rỗng và giả sử P =(pu) là một I x ma trận với các thành phần trong G o (tương ứng trong G) Giả thiết rằng không có dòng nào hoặc cột nào của P chỉ bao gồm các thành phần đều là zero Giả sử
S = (G x I x) {0} (tương ứng S = G x I x) và định nghĩa trên S một phép toán nhân như sau:
Thế thì S là một nửa nhóm 0 - đơn hoàn toàn (tương ứng đơn hoàn toàn)
Nửa nhóm S được ký hiệu là M 0 (G; I, ; P), tương ứng với M (G; I, ; P) Mỗi nửa nhóm 0 - đơn hoàn toàn đẳng cấu với một nửa nhóm ma trận, được xây dựng theo cách tương tự Những nửa nhóm ma trận này được gọi là nửa nhóm ma trận Rixơ.
Trong công trình [5], J.M.Howie và N.Ruskue đã chứng minh đƣợc kết quả sau đây
2.3.2 Mệnh đề Giả sử M (G; I, ; P) là một nửa nhóm ma trận Rixơ, trong đó G là một nhóm và P(P i ) là I ma trận chuẩn tắc với các thành phần trên G Giả sử là một biểu diễn nửa nhóm đối với G, và giả sử e A + là một từ khác từ rỗng biểu diễn phần tử đơn vị của G, và
B = A {y i | i I\{ }} { z | \{1} } Thế thì S có biểu diễn nửa nhóm:
Trong [7], N Ruskue đã chứng minh đƣợc mệnh đề sau
2.3.3 Mệnh đề Một nhóm con với chỉ số hữu hạn trong một nửa nhóm ngược hữu hạn sinh (tương ứng biểu diễn hữu hạn được) là hữu hạn sinh
(tương ứng biểu diễn hữu hạn được)
Chỉ số của một tập con trong nửa nhóm ngược được định nghĩa như sau: cho nửa nhóm ngược S và một tập rỗng X thuộc S, các lớp (cosets) của X trong S được biểu diễn dưới dạng Xs với s thuộc S, sao cho tồn tại t thuộc S thỏa mãn Xst = S Tập hợp tất cả các lớp của X trong S được ký hiệu là C = {Ci: I thuộc I} Số lượng phần tử của C được gọi là chỉ số của X, ký hiệu là [S:X].
Bây giờ ta có thể chứng minh kết quả chính của tiết này
2.3.4 Định lý Một nửa nhóm 0 - đơn hoàn toàn S = M (G; I, ; P) biểu diễn hữu hạn được nếu và chỉ nếu I và đều hữu hạn.
Chứng minh S là nửa nhóm (G x I x ){0} với phép nhân:
Đối với một tập S hữu hạn sinh, điều kiện cần là 0(g, i, ) = (g, i, )0 = 00 = 0 Giả sử S được biểu diễn bởi tập hợp hữu hạn {(g1, i1, 1),( g2, i2, 2),…,( gk, ik, k)} ∪ {0}, ta có thể xem I và như là các tập hợp dựa trên định nghĩa phép nhân trên S.
Do đó, các tập này là hữu hạn Giả sử chúng ta cố định một phần tử khác không thuộc P, ký hiệu là P o o i, và lưu ý rằng P o o i thuộc G Trước tiên, chúng ta sẽ chứng minh khẳng định này.
Khẳng định 1 (G, i o , 0 ) là một nhóm con tối đại của S
Chứng minh Ánh xạ :(G, io, 0 )G xác định bởi (g, i o , 0 ) 0 0 0 0
1 2 i i p gp xác định vì p 0 0 i 0 và p 0 0 i , g G
Giả sử (g, io, 0 ), (h, io, 0 ) (G, io, 0 ) Khi đó:
1 2 i i i p gp hp và: (g, io, 0 ) (h, io, 0 ) = p 1 0 0 i gp 2 0 0 i p 1 0 0 i hp 2 0 0 i p 1 0 0 i gp 0 0 i hp 2 0 0 i nên là đẳng cấu Giả thiết rằng (g, io, 0 ) = (h, io, 0 ) thế thì
Trong bài viết này, chúng ta xem xét một nhóm G với các yếu tố g và h, từ đó chứng minh rằng g = h, dẫn đến việc ánh xạ φ là đơn ánh Đối với bất kỳ g thuộc G, chúng ta có thể biểu diễn g qua các yếu tố p và λ, cho thấy φ là toàn ánh Kết quả là, φ trở thành song ánh và do đó là đẳng cấu Cuối cùng, chúng ta kết luận rằng (G, io, λ0) đẳng cấu với G, và do G là nhóm, (G, io, λ0) cũng là một nhóm con của S.
T là một nhóm con của S sao cho (G, io, 0) T thế thì T có dạng (G, I’, ’) với i o I’ và 0 ’ Giả sử (e, i, ) là đơn vị của T
(e, i, ).(g, io, 0 ) = (g, io, 0 ) suy ra i = io, do đó (
1 p i , io, 0 ) là đơn vị của
T Đối với (g, i, ) T tùy ý, có (g, i, )( p 1 0 0 i , io, 0 ) = (g, i, )
( gp 0 0 i p 1 0 0 i , i, 0 ) = (g, i, ) suy ra = 0 , và tương tự nhận được i = io Do đó T = (G, i o , 0 ) và từ đó suy ra (G, io, 0 ) là một nhóm con tối đại của S
Bây giờ ta chứng minh một khẳng định thứ hai
Khẳng định 2 (G, io, 0) có một số hữu hạn lớp
Chứng minh Giả sử (g, i, ) S sao cho 0 o i p Bằng cách xét một phần tử (h, j, 0 ) trong S, ta có:
Đối với bất kỳ (g, i, ) thuộc S sao cho 0 o i p , tập hợp (G, i o , 0 ) (g, i, ) là một lớp của (G, io, 0 ) trong S Theo quy tắc nhân trong S, nếu 0 o i p , thì (G, io, 0)(g, i, ) không thể là một lớp Do đó, các lớp của (G, i o , 0 ) là các tập hợp (i o , G, ) với thuộc .
Vì hữu hạn nên ta kết luận đƣợc rằng (G, io, 0) chỉ có hữu hạn lớp trong S
Trở lại chứng minh điều kiện cần của Định lý, theo khẳng định 2, (G, io, 0) là một nhóm con với chỉ số hữu hạn của S, và do S biểu diễn hữu hạn được, nên (G, io, 0) cũng biểu diễn hữu hạn được theo Mệnh đề 2.3.4 Vì G tương đương với (G, io, 0), nên G biểu diễn hữu hạn được Đối với điều kiện đủ, giả thiết I và là các tập hữu hạn và G biểu diễn hữu hạn được Theo Mệnh đề 2.2.13 và 2.2.14, G biểu diễn hữu hạn được như một nhóm nếu và chỉ nếu nó biểu diễn hữu hạn được như một nửa nhóm Do đó, có thể giả sử là biểu diễn hữu hạn xác định G như một nửa nhóm, và chúng ta có thể sắp xếp lại các phần tử của P sao cho p11 là đơn vị.
G Giả sử e A + là một từ biểu diễn đơn vị của G và ta định nghĩa một tập hợp:
Theo Mệnh đề 2.3.3, biểu diễn đối với S là:
và do A, R , I và hữu hạn nên S biểu diễn hữu hạn đƣợc.
Giả sử A là một tập hợp và A* là nhóm tự do trên A Một hệ thống chép lại R trên A được định nghĩa là một tập con của A* x A* Đối với hai từ w1 và w2 thuộc A*, chúng ta ký hiệu w1 w2 nếu chúng là những từ đồng nhất Khi w1 được chép lại thành w2, điều này có nghĩa là tồn tại các phần tử b, c thuộc A* và một cặp (u, v) thuộc R sao cho w1 buc và w2 bvc, ký hiệu là w1 w2.
Trong lý thuyết ngôn ngữ hình thức, một từ w được coi là khả quy nếu tồn tại một từ z sao cho w khả quy sang z; ngược lại, nếu không có từ nào như vậy, w được gọi là bất khả quy Nếu w có thể chuyển đổi thành y qua một chuỗi các phép biến đổi và y là bất khả quy, thì y được xem là một dạng bất khả quy của w Hệ thống chép lại R được xem là kết thúc khi không tồn tại chuỗi vô hạn (wn) sao cho wn luôn có thể chuyển đổi thành wn+1 cho mọi n ≥ 1 Độ dài của từ w được ký hiệu là |w| và sự rút gọn độ dài được xác định khi u lớn hơn v đối với tất cả các trường hợp.
(u, v) R Rõ ràng nếu R là hệ chép lại rút gọn độ dài, thế thì R là hệ chép lại kết thúc
Hệ R được coi là suy biến nếu với x, y, z thuộc A*, khi x chuyển đổi thành y và z, tồn tại w thuộc A* sao cho y và z đều chuyển đổi thành w Một hệ chép lại R được xem là đầy đủ khi nó vừa suy biến vừa kết thúc Định nghĩa R1 bao gồm tất cả r thuộc A* mà tồn tại (r, s) thuộc R với s thuộc A* Hệ R được gọi là đã được rút gọn nếu với (r, s) thuộc R, có R1 giao A*rA* = {r} và s là R-bất khả quy Hệ thống chép lại đầy đủ đã được rút gọn R ⊆ A* x A* được gọi là hệ thống chép lại có kết thúc duy nhất.
Kết quả sau đây đƣợc chứng minh trong [3] (trang 132)
2.3.5 Mệnh đề Giả sử R là một hệ thống chép lại có kết thúc Thế thì các điều kiện sau đây tương đương:
(i) R suy biến (từ đó R đầy đủ)
(ii) Đối với (r 1 r 2 , s 12 ), (r 2 r 3 , s 23 ) R tùy ý, trong đó r 2 khác từ rỗng, tồn tại một từ w A* sao cho: s 12 r 3 * w, r 1 s 23 * w; đối với (r 1 r 2 r 3 , s 12 ), (r 2 , s 23 ) R tùy ý, tồn tại một từ w A* sao cho: s 12 * w, r 1 s 23 r 3 * w
(iii) Từ w A* có đúng một dạng bất khả quy Hơn nữa, w ~ w’ nếu và chỉ nếu w,w’ có cùng một dạng bất khả quy
2.3.6 Định nghĩa Chúng ta định nghĩa các phủ là các cặp đƣợc sắp thứ tự dạng [(r1r2, s12), (r2r3, s23)] và [(r4r5r6, s45), (r5, s56)], trong đó (r1r2, s12), (r2r3, s23), (r4r5r6, s45), (r5, s56) R và r 2, r5 không phải là từ rỗng
2.3.7 Chú ý Trong biểu diễn ở Mệnh đề 2.3.3 có một số phủ, chẳng hạn
Tập hợp các hệ thức không tạo thành một hệ thống chép lại duy nhất và có kết thúc Do đó, chúng ta cần xây dựng một biểu diễn mới với hệ chép lại có kết thúc duy nhất cho các hệ thức này.
Chúng ta lấy biểu diễn là một bảng Caylay, nghĩa là A = G và
R là một hệ thống chép lại có kết thúc duy nhất trên A, với x0 ∈ A là đơn vị của G Bằng cách lấy e ≡ x0 và bổ sung các hệ thức mới như xyi = x, z λ x = x, yiyi’ = yi và z λ z λ’ = z λ’ (với x ∈ A\{x0}; i, i’ ∈ I\{1}, λ, λ’ ∈ ∧\{1}), các hệ thức này thỏa mãn trong S và nhận được biểu diễn phù hợp.
xác định nửa nhóm