半環

抽象代数学において、半環（はんかん、）とは環に類似した代数的構造で、環の公理から加法的逆元の存在を除いたものである。負元 (negative) の無い環 (ring) ということから rig という用語もしばしば用いられる。
定義.
半環は、以下の性質を満たす二つの二項演算、即ち加法（和）"+" と乗法（積）"·" とを備えた集合 "R" を言う：
上記の最後の公理は環の場合には他の公理から導かれるので不要だが、一般の半環では成り立つとは限らないので明示的に要求する必要がある。半環が環と異なる点は、加法が単に可換モノイドを成せばよく、可換群を成すとは限らないことである。
通例、乗法の記号はしばしば省略して "a" · "b" を単に "ab" と記し、また演算の優先順位として乗法は加法 "+" に優先するものと約束する（例えば は の意である）。
乗法が可換な半環を可換半環 ("commutative semiring") と言う。加法が冪等演算となる（つまり任意の "a" が "a" + "a" = "a" を満たす）半環を冪等半環 ("idempotent semiring", dioid) と言う。言い換えれば、冪等半環の加法モノイド ("R", +, 0) は零付き結び半束を成す。
文献によっては半環が 0 や 1 を持つことを仮定しないものもある。このような扱いをすると、「環と半環との関係」が「群と半群との関係」の類似対応物としてより捉えやすくなるという利点がある。この場合、本項で言うところの「半環」の概念を特に "rig" と呼んで呼び分けるのが普通である。
半環論.
環論における議論の大半は、勝手な半環に対して用いても引き続き意味を成す。特に、可換環上の多元環論は直截に可換半環上の多元環論に一般化することができる。この意味で環は、単に整数全体の成す可換半環 Z 上の多元環である。数学者によっては、本当は環よりも半環の方が代数学のより基礎を成す概念であり、環という構造は例えば「複素数体上の多元環」を捉えるのと同様の視点から捉えるべきとする。
加法の冪等性が自明であるような任意の環として、冪等半環は半環論において特別である。冪等半環上の半順序 ≤ が "a" ≤ "b" ⇔ "a" + "b" = "b"（あるいは同じことだが、"a" ≤ "b" ⇔ ["a" + "x" = "b" なる "x" が存在する]）として定められる。零元 0 がこの順序に関する最小元、即ち任意の "a" に対して 0 ≤ "a" となることを見るのは容易い。乗法および加法は "a" ≤ "b" ならば "ac" ≤ "bc" かつ "ca" ≤ "cb" および ("a"+"c") ≤ ("b"+"c") を満たすという意味でこの順序と両立する。
更なる一般化.
半環の定義において加法の可換性も右分配律もともに仮定から落とすならば近環 ("near-ring") の概念が得られる。先に挙げた意味での基数全体が半環を成すのとまったく同様の意味で、順序数の全体は近環を成す。
圏論において（半環的 2-圏、2-rig）は、半環演算と類似対応する函手演算を備えた圏である。「基数全体が半環を成す」ことを圏化して「集合の圏（あるいはより一般に任意のトポス）が半環圏を成す」ことが述べられる。
応用.
冪等半環、特に実数体上のマックスプラス代数 とミニマムプラス代数 は離散事象系のによく用いられる。このとき実数は「コスト」や「到達時間」を表すものであり、演算 "max" は事象の全ての要件が揃うまで待つこと（従って最大の時間を取ること）、および演算 "min" はより選択コストの必要ない最適解を選べることに対応し、また演算 "+" は同じ経路に沿って積算することに対応する。
最短経路問題に対するフロイド-ワーシャルアルゴリズムは、ミニマムプラス代数 (min, +) 上の計算として再定式化することができる。同様に、隠れマルコフモデルにおいて観測される事象列に対応する尤もらしい状態列を求めるビタビアルゴリズムは、確率上のマックスタイムズ代数 上の計算に帰着される。これら動的計画法アルゴリズムは、付随する半環の分配性に依拠して、非常に膨大な数（指数函数的挙動に従うほど多くともよい）の項を持つ量に対する計算を、それらの項を個々に扱うよりも効率的に計算する。
集合半環.
集合半環あるいは単に半環は、空でない集合族 "S" で、以下の三条件
を満たすものを言う。集合半環は測度論で用いられ、その例の一つは実数からなる全ての半開半閉区間 からなる集合族として与えられる。