Nửa nhóm

Trong toán học, nửa nhóm là cấu trúc đại số bao gồm một tập hợp đi cùng với một phép toán hai ngôi có tính kết hợp.

Phép toán hai ngôi của nửa nhóm thường được ký hiệu theo phép nhân: x·y, hoặc đơn giản là xy, ký hiệu cho kết quả của phép toán cho cặp được sắp (x, y). Tính kết hợp thường được viết như sau: (x·y)·z = x·(y·z) với mọi x, y và z thuộc nửa nhóm.

Nửa nhóm được coi là một trường hợp đặc biệt của các magma, trong đó phép toán có tính kết hợp, hoặc là dạng tổng quát của các nhóm bởi không cần đến phần tử đơn vị hay phần tử nghịch đảo.^{[note 1]} Giống như nhóm hoặc magma, phép toán trong nửa nhóm không cần phải có tính giao hoán, nên x·y không nhất thiết phải bằng với y·x; Một ví dụ nổi bật về phép toán có tính kết hợp nhưng không có tính giao hoán là phép nhân ma trận. Nếu phép toán có tính giao hoán, thì nửa nhóm đó được gọi là nửa nhóm giao hoán hoặc (tương tự cách gọi nhóm Abel nhưng ít khi gọi hơn) là nửa nhóm abel.

Monoid là cấu trúc đại số trung gian nằm giữa nửa nhóm và nhóm, là nửa nhóm đi kèm theo phần tử đơn vị, do đó thỏa mãn tất cả các tiên đề của nhóm ngoại trừ tiên đề phần tử nghịch đảo. Một ví dụ chẳng hạn như tập các xâu cùng với phép nối xâu làm phép toán hai ngôi và phần tử đơn vị là xâu rỗng. Nếu bỏ đi xâu rỗng thì tập các xâu này tạo thành một nửa nhóm không phải monoid. Tập các số nguyên dương cùng phép cộng tạo thành nửa nhóm giao hoán nhưng không phải monoid, trong khi tập các số nguyên không âm có tạo thành một monoid. Nửa nhóm có thể dễ dàng biến thành monoid bằng cách thêm phần tử đơn vị. Bởi vậy, các monoid thường được nghiên cứu trong lý thuyết nửa nhóm thay vì trong lý thuyết nhóm. Ta không nên nhầm lẫn giữa nửa nhóm với tựa nhóm, tựa nhóm là dạng tổng quát của nhóm theo hướng khác; phép toán trong tựa nhóm không cần tính giao hoán nhưng cần bảo toàn phép chia. Phép chia trong nửa nhóm (hoặc trong monoid) thường không khả thi.

Nghiên cứu các nửa nhóm chính thức bắt đầu từ ban đầu thế kỷ 20. Các kết quả ban đầu bao gồm định lý Cayley cho các nửa nhóm, trong đó các hàm tùy ý thay thế vị trí của các song ánh trong lý thuyết nhóm. Một kết quả sâu hơn nằm trong phân loại các nửa nhóm hữu hạn là lý thuyết Krohn–Rhodes, tương tự với phân tích Jordan–Hölder cho nhóm hữu hạn. Một số kỹ thuật để nghiên cứu nửa nhóm như các quan hệ của Green, không có trong lý thuyết nhóm.

Lý thuyết của các nửa nhóm hữu hạn có ứng dụng quan trọng trong khoa học máy tính lý thuyết kể từ những năm 1950 bởi liên hệ tự nhiên giữa các nửa nhóm hữu hạn và automata hữu hạn qua monoid cú pháp. Trong lý thuyết xác suất, nửa nhóm thường được xét trong các tiến trình Markov.^[1] Trong các nhánh khác của toán học ứng dụng, nửa nhóm là mô hình cơ bản cho các hệ thống tuyến tính bất biến thời gian. Trong các phương trình vi phân riêng phần, Nửa nhóm thường được xét với các phương trình có tiến hóa không phụ thuộc vào thời gian.

Có nhiều lớp đặc biệt của nửa nhóm, là các nửa nhóm đi kèm thêm một số tính chất đặc biệt. Một số lớp còn biểu hiện gần hết các tính chất của nhóm. Trong đó bao gồm: nửa nhóm chính quy, nửa nhóm cùng phép chập, nửa nhóm khả nghịch và nửa nhóm khử được.

Định nghĩa

Nửa nhóm là tập hợp $S$ đi cùng phép toán hai ngôi " $\cdot$ " (hay là hàm $\cdot :S\times S\rightarrow S$ ) thỏa mãn tính kết hợp:

Với mọi

a,b,c\in S

, phương trình

(a\cdot b)\cdot c=a\cdot (b\cdot c)

được thỏa mãn.

Ngắn gọn hơn, nửa nhóm là magma có tính kết hợp.

Các ví dụ của nửa nhóm

Nửa nhóm rỗng: tập rỗng tạo thành một nửa nhóm với hàm rỗng làm phép toán hai ngôi.
Nửa nhóm có một phần tử: chỉ có một (và chỉ đúng một xê xích đẳng cấu), chứa duy nhất một phần tử {a} cùng phép toán a · a = a.
Nửa nhóm có hai phần tử: có 5 nửa nhóm khác nhau.
Monoid "flip-flop": nửa nhóm có ba phần tử biểu diễn ba phép toán trên một công tắc - set, reset, và không làm gì.
Tập các số nguyên dương cùng với phép cộng. (Nếu thêm số 0 thì thành monoid.)
Tập các số nguyên cùng với phép lấy lớn nhất hoặc nhỏ nhất. (Nếu thêm cực dương/cực âm tương ứng, thì nó thành monoid)
Các ma trận vuông không âm có kích cỡ nhất định cùng với phép toán hai ngôi.
Bất cứ ideal của vành cùng với phép nhân của vành.
Tập các xâu trên bảng chữ cái cố định Σ cùng phép nối xâu làm phép toán hai ngôi — hay còn hay gọi là "nửa nhóm tự do trên Σ". Nếu thêm xâu rỗng thì nó trở thành monoid tự do trên Σ.

Các khái niệm cơ bản

Phần tử đơn vị và phần tử không

Phần tử đơn vị trái của nửa nhóm $S$ (hoặc tổng quát hơn là của magma) là phần tử $e$ sao cho với mọi $x$ thuộc $S$ , $ex=x$ . Tương tự như vậy, phần tử đơn vị phải là phần tử $f$ sao cho với mọi phần tử $x$ thuộc $S$ , $xf=x$ . Phần tử đơn vị trái và phải đều được gọi là phần tử đơn vị một phía. Một nửa nhóm có thể có một hoặc nhiều hơn số phần tử đơn vị trái nhưng không có phần tử đơn vị phải nào và ngược lại.

Phần tử đơn vị hai phía (hay gọi ngắn đi là phần tử đơn vị) là phần tử đồng thời vừa là đơn vị trái, vừa là đơn vị phải. Nửa nhóm có phần tử đơn vị hai phía được gọi là monoid. Một nửa nhóm chỉ có tối đa một phần tử đơn vị hai phía. Nếu nửa nhóm có một phần tử đơn vị hai phía, thì phần tử đơn vị hai phía đó là phần tử đơn vị một phía duy nhất trong nửa nhóm. Nếu một nửa nhóm có cả hai đơn vị trái và đơn vị phải, thì nó có một phần tử đơn vị hai phía (là phần tử đơn vị duy nhất).

Nửa nhóm $S$ không có phần tử đơn vị có thể được nhúng trong monoid được tạo bằng cách hợp phần tử $e\notin S$ với $S$ và định nghĩa $e\cdot s=s\cdot e=s$ for all $s\in S\cup \{e\}$ .^[2]^[3] Ký hiệu $S^{1}$ ký hiệu cho monoid được tạo từ $S$ bằng cách thêm phần tử đơn vị nếu cần thiết ( $S^{1}=S$ cho monoid).^[3]

Tương tự như vậy, mỗi magma có tối đa một phần tử hút, mà trong lý thuyết nửa nhóm ta gọi nó là phần tử không. Tương tự với cách xây trên, với mọi nửa nhóm $S$ , ta có thể định nghĩa $S^{0}$ là nửa nhóm cùng với 0 nhúng lên $S$ .

Nửa nhóm con và ideal

Từ nửa nhóm quy nạp ra được phép toán trên họ các tập con của nửa nhóm: Cho các tập con A và B của nửa nhóm S, tích của chúng A · B, thường viết là AB, là tập hợp { ab | a thuộc A và b thuộc B }. (Thuật ngữ này tương đương với nhóm.) Dùng phép toán này, tập con A được gọi là

nửa nhóm con nếu AA là tập con của A,
ideal phải nếu AS là tập con của A, và
ideal trái nếu SA là tập con của A.

Nếu A vừa là ideal trái vừa là ideal phải thì nó được gọi là ideal (hoặc ideal hai phía).

Nếu S là nửa nhóm, thì giao của bất cứ họ các nửa nhóm con của S cũng là nửa nhóm con của S. Do đó tập các nửa nhóm con của S tạo thành một dàn đầy đủ.

Một ví dụ của nửa nhóm không có ideal tối tiểu là tập các số nguyên dương dưới phép cộng. Ideal tối tiểu của nửa nhóm giao hoán, nếu nó tồn tại thì nó là nhóm.

Quan hệ Green là tập năm quan hệ tương đương mô tả các phần tử bằng các ideal chính chúng sinh ra, là kỹ thuật quan trọng để phân tích các ideal của nửa nhóm và cấu trúc có quan hệ.

Tập con có tính chất mọi phần tử thuộc tập đó giao hoán với các phần tử còn lại trong nửa nhóm được gọi là tâm của nửa nhóm.^[4] Tâm của nửa nhóm là nửa nhóm con.^[5]

Đồng cấu và tương đẳng

Đồng cấu nửa nhóm là hàm bảo toàn cấu trúc của nửa nhóm. Hàm f: S → T giữa hai nửa nhóm là đồng cấu nếu phương trình

f(ab) = f(a)f(b).

thỏa mãn với mọi a, b thuộc S, tức kết quả là như nhau khi áp dụng phép toán trước hay sau khi tính hàm f.

Đồng cấu nửa nhóm giữa các monoid bảo toàn phần tử đơn vị nếu nó là đồng cấu monoid. Bởi có các đồng cấu nửa nhóm nhưng không phải đồng cấu monoid. Ví dụ chẳng hạn như phép nhúng chính tắc của nửa nhóm $S$ không phần tử đơn vị vào $S^{1}$ . Gọi $f:S_{0}\to S_{1}$ là đồng cấu nửa nhóm. Ảnh của $f$ cũng là nửa nhóm. Nếu $S_{0}$ là monoid cùng phần tử đơn vị $e_{0}$ , thì $f(e_{0})$ là phần tử đơn vị trong ảnh của $f$ . Nếu $S_{1}$ là monoid cùng phần tử đơn vị $e_{1}$ và $e_{1}$ thuộc ảnh của $f$ , thì $f(e_{0})=e_{1}$ , tức là $f$ là đồng cấu monoid. Cụ thể hơn, nếu $f$ là toàn ánh, thì nó là đồng cấu monoid.

Hai nửa nhóm S và T được gọi là đẳng cấu với nhau nếu tồn tại đồng cấu nửa nhóm có tính song ánh f : S → T. Nửa nhóm đẳng cấu với nhau có cấu trúc như nhau.

Tương đẳng nửa nhóm $\sim$ là quan hệ tương đương tương thích với phép toán hai ngôi của nửa nhóm. Nghĩa là, một tập con của $\sim \;\subseteq S\times S$ là quan hệ tương đương và $x\sim y\,$ và $u\sim v\,$ suy ra $xu\sim yv\,$ với mọi $x,y,u,v$ thuộc S. Giống bất kỳ quan hệ tương đương, tương đẳng nửa nhóm $\sim$ cảm sinh các lớp tương đẳng

[a]_{\sim }=\{x\in S\mid x\sim a\}

và phép toán của nửa nhóm cảm sinh phép toán hai ngôi $\circ$ trên tập các lớp tương đẳng:

[u]_{\sim }\circ [v]_{\sim }=[uv]_{\sim }

Bởi $\sim$ là tương đẳng, tập các lớp tương đương dưới phép $\sim$ tạo thành nửa nhóm với phép toán $\circ$ , được gọi là nửa nhóm thương hau nửa nhóm nhân tử, và được ký hiệu là $S/\!\!\sim$ . Ánh xạ $x\mapsto [x]_{\sim }$ là đồng cấu nửa nhóm, hay được gọi là ánh xạ thương, toàn xạ chính tắc hoặc phép chiếu chính tắc; nếu S là monoid thì nửa nhóm thương là monoid cùng với phần tử đơn vị $[1]_{\sim }$ . Ngược lại, nhân của bất cứ đồng cấu nửa nhóm là tương đẳng nửa nhóm. Lớp tương đẳng và monoid nhân tử là các đối tượng được nghiên cứu trong các hệ thống viết lại xâu.

Xem thêm

Chú thích

^ Tiên đề đóng suy ra bằng định nghĩa của phép toán hai ngôi trên tập hợp. Do đó các tác giả thường không nhắc đến nó, mà chỉ lấy 3 tiên đề cho nhóm và một tiên đề (tính kết hợp) cho nửa nhóm.

Tham khảo

^ Feller (1971)
^ Jacobson (2009, tr. 30, ex. 5)
^ ^a ^b Lawson (1998, p. 20)
^ Kilp, Mati; Knauer, U.; Mikhalev, Aleksandr V. (2000). Monoids, Acts, and Categories: With Applications to Wreath Products and Graphs : a Handbook for Students and Researchers. Walter de Gruyter. tr. 25. ISBN 978-3-11-015248-7. Zbl 0945.20036.
^ Li͡apin, E. S. (1968). Semigroups. American Mathematical Soc. tr. 96. ISBN 978-0-8218-8641-0.

Tham khảo khác

Tham khảo chung

Howie, John M. (1995). Fundamentals of Semigroup Theory. Clarendon Press. ISBN 978-0-19-851194-6. Zbl 0835.20077.
Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (1961). The Algebraic Theory of Semigroups. 1. American Mathematical Society. ISBN 978-0-8218-0271-7. Zbl 0111.03403.
Clifford, Alfred Hoblitzelle; Preston, Gordon Bamford (2010) [1967]. The algebraic theory of semigroups. 2. American Mathematical Society. ISBN 978-0-8218-0272-4.
Grillet, Pierre Antoine (1995). Semigroups: An Introduction to the Structure Theory. Marcel Dekker. ISBN 978-0-8247-9662-4. Zbl 0830.20079.
Grillet, Pierre Antoine (2001). Commutative Semigroups. Springer Verlag. ISBN 978-0-7923-7067-3. Zbl 1040.20048.
Hollings, Christopher (2009). “The Early Development of the Algebraic Theory of Semigroups”. Archive for History of Exact Sciences. 63: 497–536. doi:10.1007/s00407-009-0044-3.
Hollings, Christopher (2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. ISBN 978-1-4704-1493-1. Zbl 1317.20001.
Petrich, Mario (1973). Introduction to Semigroups. Charles E. Merrill. ISBN 978-0-675-09062-9. Zbl 0321.20037.

Tham khảo riêng

Feller, William (1971). An introduction to probability theory and its applications. II (ấn bản thứ 2). Wiley. MR 0270403.
Hille, Einar; Phillips, Ralph S. (1974). Functional analysis and semi-groups. American Mathematical Society. ISBN 978-0821874646. MR 0423094.
Suschkewitsch, Anton (1928). Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit. Mathematische Annalen. 99. tr. 30–50. doi:10.1007/BF01459084. hdl:10338.dmlcz/100078. ISSN 0025-5831. MR 1512437.
Kantorovitz, Shmuel (2009). Topics in Operator Semigroups. Springer. ISBN 978-0-8176-4932-6. Zbl 1187.47003.
Jacobson, Nathan (2009). Basic algebra. 1 (ấn bản thứ 2). Dover. ISBN 978-0-486-47189-1.
Lawson, Mark V. (1998). Inverse semigroups: the theory of partial symmetries. World Scientific. ISBN 978-981-02-3316-7. Zbl 1079.20505.
Lothaire, M. (2011) [2002]. Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. 90. Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.

[1] Tiên đề đóng suy ra bằng định nghĩa của phép toán hai ngôi trên tập hợp. Do đó các tác giả thường không nhắc đến nó, mà chỉ lấy 3 tiên đề cho nhóm và một tiên đề (tính kết hợp) cho nửa nhóm.

[2] Feller (1971)

[3] Jacobson (2009, tr. 30, ex. 5)

[lawson98-4] Lawson (1998, p. 20)

[KilpKilʹp2000-5] Kilp, Mati; Knauer, U.; Mikhalev, Aleksandr V. (2000). Monoids, Acts, and Categories: With Applications to Wreath Products and Graphs : a Handbook for Students and Researchers. Walter de Gruyter. tr. 25. ISBN 978-3-11-015248-7. Zbl 0945.20036.

[Li͡apin1968-6] Li͡apin, E. S. (1968). Semigroups. American Mathematical Soc. tr. 96. ISBN 978-0-8218-8641-0.

[note 1]

[1]

[2]

[3]

[4]

[5]