Nửa vành

Trong đại số trừu tượng, 'nửa vành là một cấu trúc đại số tương tự với vành nhưng không yêu cầu mỗi phần tử phải có nghịch đảo phép cộng.

Nửa vành nhiệt đới hiện đang được nghiên cứu mạnh bởi nó là cầu nối giữa các đa tạp đại số với các cấu trúc tuyến tính từng phần.

Định nghĩa

Nửa vành là tập $R$ đi kèm với hai phép toán hai ngôi $\,+\,$ và $\,\cdot ,\,$ được gọi là phép cộng và phép nhân sao cho:

• $(R,+)$ là monoid giao hoán với phần tử đơn vị $0$:
  • $(a+b)+c=a+(b+c)$
  • $0+a=a=a+0$
  • $a+b=b+a$
• $(R,\,\cdot \,)$ là monoid với phần tử đơn vị $1$:
  • $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
  • $1\cdot a=a=a\cdot 1$
• Phép nhân có tính phân phối trái và phải trên phép cộng:
  • $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$
  • $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$
• Nhân bởi số $0$ $R$:
  • $0\cdot a=0=a\cdot 0$

Ký hiệu $\,\cdot \,$ thường bị ẩn bị; nghĩa là, $a\cdot b$ viết gọi lại thành $ab.$ Ngoài ra thứ tự các phép toán vẫn giữ nguyên, nghĩa là phép $\,\cdot \,$ thực hiện trước phép $\,+\,$; ví dụ như $a+bc$ là $a+(bc).$

So với vành, nửa vành chỉ bỏ đi yêu cầu giá trị nghịch đảo của phép cộng; nghĩa là nó chỉ cần monoid giao hoán chứ không cần nhóm giao hoán. Nếu phép nhân của nửa vành có tính giao hoán thì nó được gọi là nửa vành giao hoán.

Lý thuyết

Ta có thể trực tiếp tổng quát hóa các lý thuyết đại số) kết hợp trên vành giao hoán sang lý thuyết đại số trên nửa vành.

Một nửa vành mà mỗi phần tử lũy đẳng với phép cộng (nghĩa là $a+a=a$ với mọi $a$) được gọi là nửa vành lũy đẳng., Nửa vành lũy đẳng mà cũng là vành thì là vành tầm thường (vành chỉ có 1 phần tử) Ngoài ra ta có thể định nghĩa thứ tự một phần $\,\leq \,$ trên nửa vành lũy đẳng bằng cách đặt $a\leq b$ khi $a+b=b$ (hay tồn tại $x$ sao cho $a+x=b$). giá trị tối thiểu thỏa mãn quan hệ này là $0,$ nghĩa là $0\leq a$ với mọi $a.$ Phép cộng và phép nhân bảo toàn thứ tự như sau $a\leq b$ thì $ac\leq bc$; $ca\leq cb$ và $(a+c)\leq (b+c).$

Các ứng dụng

Nửa vành nhiệt đới $(\max ,+)$ và $(\min ,+)$ trên các số thực được dùng để đánh giá hiệu suất trên các hệ thống sự kiện rời rạc. Các số thực trở thành "chi phí" hoặc "thời gian đến"; Phép toán "max" tương ứng với thời gian đợi tất cả điều kiện tiên quyết của sự kiện được thỏa mãn (do đó thời gian tốn là cực đại) trong khi phép "min" tương ứng với cách chọn tối ưu ít chi phí nhất; phép + tương ứng với các tích lũy trên cùng 1 đường.

Thuật toán Floyd–Warshall tìm đường đi ngắn nhất có thể đổi thành bài tính trên đại số $(\min ,+)$. Tương tự như vậy, thuật toán Viterbi tìm dãy trạng thái khả thi nhất đối với dãy quan sát trong mô hình Markov ẩn có thể đổi thành bài tính trên đại số $(\max ,\times )$ của xác suất. Các thuật toán quy hoạch động này dựa trên tính phân phối của nửa vành tương ứng để tính một số lượng lớn (có thể lũy thừa) số các phần tử thay vì phải chạy qua từng cái một.

Các ví dụ

Theo định nghĩa thì mọi vành đều là nửa vành. Các ví dụ nửa vành nhưng không phải vành là tập các số tự nhiên $\mathbb {N}$ số (bao gồm 0) dưới phép cộng và phép nhân như thường.Số hữu tỉ không âm và số thực không âm cũng tạo thành nửa vành. Các nửa vành này đều giao hoán.

Các ví dụ chung

• Tập các ideal của 1 vành lập thành nửa vành lũy đẳng với phép nhân và cộng ideal
• Đại số Boolean là nửa vành, vành Boolean cũng là nửa vành (bởi vì nó là vành) nhưng nó không lũy đẳng dưới phép cộng. nửa vành Boolean được định nghĩa là một nửa vành đẳng cấu với nửa vành con của đại số Boolean .
• Mọi c-nửa vành cũng là nửa vành, trong đó phép cộng lũy đẳng và trên mọi tập hợp

Tham khảo

• Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paris)
• François Baccelli, Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, Synchronization and Linearity (online version), Wiley, 1992, ISBN 0-471-93609-X
• Golan, Jonathan S., Semirings and their applications. Updated and expanded version of The theory of semirings, with applications to mathematics and theoretical computer science (Longman Sci. Tech., Harlow, 1992, MR1163371. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. ISBN 0-7923-5786-8 MR1746739
• Berstel, Jean; Perrin, Dominique (1985). Theory of codes. Pure and applied mathematics. 117. Academic Press. ISBN 978-0-12-093420-1. Zbl 0587.68066.
• Bản mẫu:Durrett Probability Theory and Examples 5th Edition
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067.
• Głazek, Kazimierz (2002). A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography. Dordrecht: Kluwer Academic. ISBN 1-4020-0717-5. Zbl 1072.16040.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
• Berstel, Jean; Reutenauer, Christophe (2011). Noncommutative rational series with applications. Encyclopedia of Mathematics and Its Applications. 137. Cambridge: Cambridge University Press. ISBN 978-0-521-19022-0. Zbl 1250.68007.

Đọc thêm

• Golan, Jonathan S. (2003). Semirings and Affine Equations over Them. Springer Science & Business Media. ISBN 978-1-4020-1358-4. Zbl 1042.16038.
• Gondran, Michel; Minoux, Michel (2008). Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces Series. 41. Dordrecht: Springer Science & Business Media. ISBN 978-0-387-75450-5. Zbl 1201.16038.
• Grillet, Mireille P. (1970). “Green's relations in a semiring”. Port. Math. 29: 181–195. Zbl 0227.16029.
• Gunawardena, Jeremy (1998). “An introduction to idempotency”. Trong Gunawardena, Jeremy (biên tập). Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994 (PDF). Cambridge: Cambridge University Press. tr. 1–49. Zbl 0898.16032.
• Jipsen, P. (2004). “From semirings to residuated Kleene lattices”. Studia Logica. 76 (2): 291–303. doi:10.1023/B:STUD.0000032089.54776.63. S2CID 9946523. Zbl 1045.03049.
• Steven Dolan (2013) Fun with Semirings, doi:10.1145/2500365.2500613