Xem mã nguồn của Nửa vành

{{Short description|Vành đại số không cần có phần tử âm cho phép cộng}}
<!--{{Ring theory sidebar}}-->
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 [[đa tạp tuyến tính từng phần|tuyến tính từng phần]].<ref name=":0">{{chú thích tạp chí|last1=Speyer|first1=David|last2=Sturmfels|first2=Bernd|date=2009|title=Tropical Mathematics|url=https://www.tandfonline.com/doi/full/10.1080/0025570X.2009.11953615|journal=Mathematics Magazine|language=en|volume=82|issue=3|pages=163–173|doi=10.1080/0025570X.2009.11953615|s2cid=15278805|issn=0025-570X}}</ref>
{{Cấu trúc đại số |Vành}}
<!--{{Algebraic structures |Ring}}-->

== Định nghĩa ==

'''Nửa vành''' là [[Tập hợp|tập]] <math>R</math> đi kèm với hai [[phép toán hai ngôi]] <math>\,+\,</math> và <math>\,\cdot,\,</math> được gọi là phép cộng và phép nhân sao cho:<ref>Berstel & Perrin (1985), [{{Google books|plainurl=y|id=GHJHqezwwpcC|page=26|text=a semiring K is a set equipped with two operations}} p. 26]</ref><ref name=LotIII211>Lothaire (2005) p.211</ref><ref name=Sak2728>Sakarovitch (2009) pp.27–28</ref>

* <math>(R, +)</math> là [[monoid#monoid giao hoán|monoid giao hoán]] với [[phần tử đơn vị]] <math>0</math>:
** <math>(a + b) + c = a + (b + c)</math>
** <math>0 + a = a = a + 0</math>
** <math>a + b = b + a</math>
* <math>(R, \,\cdot\,)</math> là [[monoid]] với phần tử đơn vị <math>1</math>:
** <math>(a \cdot b) \cdot c = a \cdot (b \cdot c)</math>
** <math>1 \cdot a = a = a \cdot 1</math>
* Phép nhân có tính [[Luật phân phối|phân phối]] trái và phải trên phép cộng:
** <math>a \cdot (b + c) = (a \cdot b) + (a \cdot c)</math>
** <math>(a + b) \cdot c = (a \cdot c) + (b \cdot c)</math>
* Nhân bởi số <math>0</math> <math>R</math>:
** <math>0 \cdot a = 0 = a \cdot 0</math>

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

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#monoid giao hoá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'''.<ref name=LotIII212>Lothaire (2005) p.212</ref>

== Lý thuyết ==

Ta có thể trực tiếp tổng quát hóa các lý thuyết [[Đại số (lý thuyết vành|đạ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.{{citation needed|date=November 2020}}

Một nửa vành mà mỗi phần tử [[lũy đẳng]] với phép cộng (nghĩa là <math>a + a = a</math> với mọi <math>a</math>) được gọi là '''{{visible anchor|nửa vành lũy đẳng}}'''.,<ref name=Esik08>{{chú thích sách|last=Ésik|first=Zoltán|chapter=Iteration semirings|zbl=1161.68598|editor1-last=Ito|editor1-first=Masami|title=Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings|location=Berlin|publisher=[[Springer-Verlag]]|isbn=978-3-540-85779-2|series=Lecture Notes in Computer Science|volume=5257|pages=1–20|year=2008|doi=10.1007/978-3-540-85780-8_1}}</ref> 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ử)<ref group=note>, bởi vì vành phải có nghịch đảo phép cộng, không như nửa vành.</ref> Ngoài ra ta có thể định nghĩa [[tập hợp sắp thứ tự một phần|thứ tự một phần]] <math>\,\leq\,</math> trên nửa vành lũy đẳng bằng cách đặt <math>a \leq b</math> khi <math>a + b = b</math> (hay tồn tại <math>x</math> sao cho <math>a + x = b</math>). [[Giá trị tối tiểu]] thỏa mãn quan hệ này là <math>0,</math> nghĩa là <math>0 \leq a</math> với mọi <math>a.</math> Phép cộng và phép nhân bảo toàn thứ tự như sau <math>a \leq b</math> thì <math>a c \leq b c</math>; <math>c a \leq c b</math> và <math>(a + c) \leq (b + c).</math>

=== Các ứng dụng ===

[[Nửa vành nhiệt đới]] <math>(\max, +)</math> và <math>(\min, +)</math> trên các số thực được dùng để đánh giá [[đánh giá hiệu suất|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ố <math>(\min, +)</math>.  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ố <math>(\max, \times)</math> của xác suất.  Các [[quy hoạc h động|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.<ref name="Pair1966">
{{citation|last=Pair|first=Claude|chapter=Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (On algorithms for path problems in finite graphs)|title=Théorie des graphes (journées internationales d'études) -- Theory of Graphs (international symposium)|publisher=Dunod (Paris) et Gordon and Breach (New York)|date=1967|location=Rome (Italy), July 1966|page=271|editor=Rosentiehl}}</ref><ref>{{citation|last1=Derniame|first1=Jean Claude|last2=Pair|first2=Claude|title=Problèmes de cheminement dans les graphes (Path Problems in Graphs)|publisher=Dunod (Paris)|year=1971}}</ref>

== 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]] <math>\N</math> số (bao gồm [[0 (số)|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.<ref name=Gut08/><ref name=Sak28>Sakarovitch (2009) p.28</ref>

=== Các ví dụ chung ===
* Tập các [[ideal (lý thuyết vành)|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 <ref name=Gut08>{{chú thích sách|title=Surveys in Contemporary Mathematics|volume=347|series=London Mathematical Society Lecture Note Series|issn=0076-0552|editor1-first=Nicholas|editor1-last=Young|editor2-first=Yemon|editor2-last=Choi|publisher=[[Cambridge University Press]]|year=2008|isbn=978-0-521-70564-6|chapter=Rank and determinant functions for matrices over semirings|first=Alexander E.|last=Guterman|pages=1–33|zbl=1181.16042}}</ref>.
* 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

==== Nửa vành của tập hợp ====

{{See also|Vành của tập hợp}}

Một '''{{em|nửa vành}}''' ('''của tập hợp''')<ref>Noel Vaillant, [http://www.probability.net/WEBcaratheodory.pdf Caratheodory's Extension], on probability.net.</ref> là tập không rỗng  <math>\mathcal{S}</math> các tập con của <math>X</math> sao cho
<ol>
<li><math>\varnothing \in \mathcal{S}.</math>
* Nếu (3) được thỏa mãn, thì <math>\varnothing \in \mathcal{S}</math> khi và chỉ khi <math>\mathcal{S} \neq \varnothing.</math></li>
<li>Nếu <math>E, F \in \mathcal{S}</math> thì <math>E \cap F \in \mathcal{S}.</math></li>
<li>Nếu <math>E, F \in \mathcal{S}</math> thì tồn tại hữu hạn số [[tập không giao nhau]] <math>C_1, \ldots, C_n \in \mathcal{S}</math> sao cho <math>E \setminus F = \bigcup_{i=1}^n C_i.</math></li>
</ol>

Từ điều kiện (2) và (3) cùng với <math>S \neq \varnothing</math> suy ra được <math>\varnothing \in S.</math> Các nửa vành này được dùng trong [[lý thuyết độ đo]]. Ví dụ như tập các [[Khoảng (toán học)|khoảng]] thực nửa đóng nửa mở <math>[a, b) \subset \R.</math>

Một '''{{em|{{visible anchor|nửa đại số}}}}''' trên <math>X</math> là nửa vành có các tập con của <math>X</math> làm phần tử.{{sfn|Durrett|2019|pp=3-4}}

=== Các ví dụ cụ thể ===

{{unordered list
| [[Tập số tự nhiên mở rộng]] <math>\N \cup \{ \infty \}</math> với phép cộng và phép nhân được mở rộng (và <math>0 \cdot \infty = 0</math>).<ref name=Sak28/>
| Cho nửa vành <math>S,</math> [[nửa vành ma trận]] <math>M_n(S)</math> của [[ma trận (Toán học)|ma trận]] hình vuông <math>n \times n</math>  tạo thành nửa vành dưới phép cộng ma trận và [[phép nhân ma trận]], loại nửa vành này thường thì không giao hoán trừ khi <math>S</math> giao hoán. Ví dụ tập các ma trận với phần tử không âm tạo thành 1 nửa vành <math>M_n(\N),</math>.<ref name=Gut08/>
| Nếu <math>A</math> là monoid giao hoán, tập <math>\operatorname{End}(A)</math> chứa các [[tự đồng cấu]] <math>f : A \to A</math> suýt tạo thành nửa vành, trong đó phép cộng là cộng từng điểm và phép nhân là phép [[hợp hàm]]. [[Cấu xạ không]] và phần tử đơn vị là hai phần tử trung hòa. Đây không phải nửa vành bởi vì phép hợp không thỏa mãn phân phối trái với phép cộng từng điểm: <math>a \cdot (b + c) \neq (a \cdot b) + (a \cdot c).</math><br />Nếu <math>A</math> là monoid cộng tính của số tự nhiên thì ta thu được nửa vành của số tự nhiên như <math>\operatorname{End}(A),</math> nếu <math>A = S^n</math> với <math>S</math> là nửa vành thì ta thu được (sau khi kết hợp mỗi cấu xạ với một ma trận) nửa vành các ma trận <math>n \text{ x } n</math> với các hệ số thuộc <math>S,</math> và nếu <math>A</math> là [[nhóm Abel]] thì <math>\operatorname{End}(A)</math> trở thành [[vành tự đồng cấu]] (không nhất thiết phải giao hoán).

| '''{{visible anchor|Nửa vành Boolean}}''' là nửa vành giao hoán <math>\mathbf{B}</math> được tạo từ [[đại số Boolean hai phần tử]] và định nghĩa bởi <math>1 + 1 = 1.</math><ref name=LotIII211/><ref name=Sak28/><ref name=BR4>Berstel & Reutenauer (2011) p.&nbsp;4</ref> Nửa vành này lũy đẳng <ref name=Esik08/> và là một trong những ví dụ đơn giản nhất của nửa vành không phải vành. Cho hai tập <math>X</math> và <math>Y,</math> các [[quan hệ hai ngôi]] giữa <math>X</math> và <math>Y</math> tương ứng với các ma trận đánh chỉ số bởi <math>X</math> và <math>Y</math> với các phần tử thuộc nửa vành Boolean, [[phép cộng ma trận]] tương đương với hợp (trong tập hợp) của quan hệ còn [[phép nhân ma trận]] tương đương với [[phép hợp thành quan hệ]].<ref>{{chú thích báogroup|title=quantum mechanics over a commutative rig|author=John C. Baez|author-link=John C. Baez|date=6 Nov 2001|newsgroup=sci.physics.research|message-id=9s87n0$iv5@gap.cco.caltech.edu|url=https://groups.google.com/d/msg/sci.physics.research/VJNPMCfreao/TMKt9tFYNwEJ|access-date=November 25, 2018}}</ref>
}}
== Chú thích ==

{{tham khảo|group=note}}

== Tham khảo ==

{{tham khảo}}

* {{citation|first1=Jean Claude|last1=Derniame|first2=Claude|last2=Pair|title=Problèmes de cheminement dans les graphes (Path Problems in Graphs)|publisher=Dunod (Paris)|year=1971}}
* [[François Baccelli]], Guy Cohen, Geert Jan Olsder, Jean-Pierre Quadrat, ''[http://cermics.enpc.fr/~cohen-g//SED/book-online.html Synchronization and Linearity (online version)] {{Webarchive|url=https://web.archive.org/web/20161104002419/http://cermics.enpc.fr/~cohen-g//SED/book-online.html |date=2016-11-04 }}'', 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, {{MathSciNet|id=1163371}}. Kluwer Academic Publishers, Dordrecht, 1999. xii+381 pp. {{isbn|0-7923-5786-8}} {{MathSciNet|id=1746739}}
* {{chú thích sách|last1=Berstel|first1=Jean|last2=Perrin|first2=Dominique|title=Theory of codes|series=Pure and applied mathematics|volume=117|year=1985|publisher=Academic Press|isbn=978-0-12-093420-1|zbl=0587.68066}}
* {{Durrett Probability Theory and Examples 5th Edition}} <!-- {{sfn|Durrett|2019|p=}} -->
*{{chú thích sách|last=Lothaire|first=M.|author-link=M. Lothaire|title=Applied combinatorics on words|others=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é]]|series=Encyclopedia of Mathematics and Its Applications|volume=105|location=Cambridge|publisher=[[Cambridge University Press]]|year=2005|isbn=0-521-84802-4|zbl=1133.68067|url-access=registration|url=https://archive.org/details/appliedcombinato0000loth}}
*{{chú thích sách|last=Głazek|first=Kazimierz|title=A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography|location=Dordrecht|publisher=Kluwer Academic|year=2002|isbn=1-4020-0717-5|zbl=1072.16040}}
* {{chú thích sách|last=Sakarovitch|first=Jacques|title=Elements of automata theory|others=Translated from the French by Reuben Thomas|location=Cambridge|publisher=[[Cambridge University Press]]|year=2009|isbn=978-0-521-84425-3|zbl=1188.68177}}
* {{chú thích sách|last1=Berstel|first1=Jean|last2=Reutenauer|first2=Christophe|title=Noncommutative rational series with applications|series=Encyclopedia of Mathematics and Its Applications|volume=137|location=Cambridge|publisher=[[Cambridge University Press]]|year=2011|isbn=978-0-521-19022-0|zbl=1250.68007}}

== Đọc thêm ==

* {{chú thích sách|first=Jonathan S.|last=Golan|title=Semirings and Affine Equations over Them|url=https://archive.org/details/semiringsaffinee0000gola|year=2003|publisher=Springer Science & Business Media|isbn=978-1-4020-1358-4|zbl=1042.16038}}
* {{chú thích sách|first1=Michel|last1=Gondran|first2=Michel|last2=Minoux|title=Graphs, Dioids and Semirings: New Models and Algorithms|year=2008|location=Dordrecht|publisher=Springer Science & Business Media|isbn=978-0-387-75450-5|zbl=1201.16038|series=Operations Research/Computer Science Interfaces Series|volume=41}}
* {{chú thích tạp chí|last=Grillet|first=Mireille P.|title=Green's relations in a semiring|zbl=0227.16029|journal=Port. Math.|volume=29|pages=181–195|year=1970|url=https://eudml.org/doc/115127 }}
* {{chú thích sách|last=Gunawardena|first=Jeremy|chapter=An introduction to idempotency|zbl=0898.16032|editor1-last=Gunawardena|editor1-first=Jeremy|title=Idempotency. Based on a workshop, Bristol, UK, October 3–7, 1994|location=Cambridge|publisher=[[Cambridge University Press]]|pages=1–49|year=1998|url=http://www.hpl.hp.com/techreports/96/HPL-BRIMS-96-24.pdf }}
* {{chú thích tạp chí|first=P.|last=Jipsen|title=From semirings to residuated Kleene lattices|journal=Studia Logica|volume=76|number=2|year=2004|pages=291–303|zbl=1045.03049|doi=10.1023/B:STUD.0000032089.54776.63|s2cid=9946523 }}
* Steven Dolan (2013) [http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf Fun with Semirings] {{Webarchive|url=https://web.archive.org/web/20180713052220/http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf |date=2018-07-13 }}, {{doi|10.1145/2500365.2500613}}

{{Authority control}}

[[Thể loại:Cấu trúc đại số]]
[[Thể loại:Lý thuyết vành]]