✨Nửa nhóm

thumb|Các cấu trúc đại số nằm giữa [[Magma (đại số)|magma và nhóm: nửa nhóm là magma đi kèm theo tính kết hợp. monoid là nửa nhóm kèm thêm phần tử đơn vị.]] 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 . Tính kết hợp thường được viết như sau: 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. 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. 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 "$\backslash cdot$" (hay là hàm $\backslash cdot:S\backslash times\; S\backslash rightarrow\; S$) thỏa mãn tính kết hợp:

:Với mọi $a,b,c\backslash in\; S$, phương trình $(a\backslash cdot\; b)\backslash cdot\; c\; =\; a\backslash cdot(b\backslash 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 .
• 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\; \backslash notin\; S$ với $S$ và định nghĩa $e\; \backslash cdot\; s\; =\; s\; \backslash cdot\; e\; =\; s$ for all $s\; \backslash in\; S\; \backslash cup\; \{e\}$. 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). Tâm của nửa nhóm là nửa nhóm con.

Đồ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 giữa hai nửa nhóm là đồng cấu nếu phương trình :. 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\backslash 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 . Nửa nhóm đẳng cấu với nhau có cấu trúc như nhau.

Tương đẳng nửa nhóm $\backslash 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 $\backslash sim\backslash ;\backslash subseteq\; S\backslash times\; S$ là quan hệ tương đương và $x\backslash sim\; y\backslash ,$ và $u\backslash sim\; v\backslash ,$ suy ra $xu\backslash sim\; yv\backslash ,$ 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 $\backslash sim$ cảm sinh các lớp tương đẳng

:$[a]\_\backslash sim\; =\; \{x\; \backslash in\; S\; \backslash mid\; x\; \backslash sim\; a\}$

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

:$[u]$\sim\circ [v]\sim = [uv]_\sim

Bởi $\backslash sim$ là tương đẳng, tập các lớp tương đương dưới phép $\backslash sim$ tạo thành nửa nhóm với phép toán $\backslash 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/!!\backslash sim$. Ánh xạ $x\; \backslash mapsto\; [x]\_\backslash 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]\_\backslash 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.