半環

抽象代数学において、半環（はんかん、英: semi-ring）とは環に類似した代数的構造で、環の公理から加法的逆元の存在を除いたものである。負元 (negative) の無い環 (ring) ということから rig という用語もしばしば用いられる。

半環は、以下の性質を満たす二つの二項演算、即ち加法（和）"+" と乗法（積）"·" とを備えた集合 R を言う^[1]：

1. (R, +) は単位元 0 を持つ可換モノイドを成す:
   1. (a + b) + c = a + (b + c),
   2. 0 + a = a + 0 = a,
   3. a + b = b + a.
2. (R, ·) は単位元 1 を持つモノイドを成す:
   1. (a · b)· c = a ·(b · c),
   2. 1 · a = a · 1 = a.
3. 乗法は加法の上に分配的である:
   1. a ·(b + c) = (a · b) + (a · c),
   2. (a + b)· c = (a · c) + (b · c).
4. 0-倍は R を零化する:
   1. 0 · a = a · 0 = 0.

上記の最後の公理は環の場合には他の公理から導かれるので不要だが、一般の半環では成り立つとは限らないので明示的に要求する必要がある。半環が環と異なる点は、加法が単に可換モノイドを成せばよく、可換群を成すとは限らないことである。

通例、乗法の記号はしばしば省略して a · b を単に ab と記し、また演算の優先順位として乗法は加法 "+" に優先するものと約束する（例えば a + bc は a + (bc) の意である）。

乗法が可換な半環を可換半環 (commutative semiring) と言う。加法が冪等演算となる（つまり任意の a が a + a = a を満たす）半環を冪等半環 (idempotent semiring, dioid) と言う。言い換えれば、冪等半環の加法モノイド (R, +, 0) は零付き結び半束を成す。

文献によっては半環が 0 や 1 を持つことを仮定しないものもある。このような扱いをすると、「環と半環との関係」が「群と半群との関係」の類似対応物としてより捉えやすくなるという利点がある。この場合、本項で言うところの「半環」の概念を特に rig と呼んで呼び分けるのが普通である。

• 任意の環は半環である。
• 一つの環のイデアルの全体は、イデアルの和と積に関して半環を成す。
• 単位的完備冪等半環（英語版）は、結びと乗法に関して冪等半環 (dioid) である。
• 任意の有界分配束は結びと交わりに関して可換冪等半環を成す。特にブール代数はそのような半環である。ブール環も半環を成し、実際には環を成すが、これは加法が冪等でない。
• 環 R における正規歪束（英語版） は乗法と
  ${\displaystyle a\mathop {}\nabla {} b:=a+b+ba-aba-bab}$
  で定義される束演算（ナブラ）に関して冪等半環となる。
• クリーネ代数（英語版） はクリーネスターと呼ばれる単項演算 ∗: R → R を備えた冪等半環 R である。クリーネ代数は形式文法や正規表現の理論において重要である。

• 半環の原型的な例は、自然数全体の成す集合 N（ここでは 0 を含む）に通常の加法と乗法を考えたもの（自然数半環）である。非負有理数の全体や非負実数の全体も同じくして半環を成す。以上の例は全て可換半環である。
• 各成分が非負な n-次正方行列の全体は、通常の行列の加法と乗法に関して非可換半環を成す。同様の仕方でより一般に、任意に与えられた半環 S に成分を持つ正方行列の全体は半環を成し、S 自身はたとえ可換であったとしても、この行列半環は一般に非可換となる。
• 可換モノイド A に対し、自己準同型 f: A → A の全体 End(A) は、点ごとの和を加法とし、写像の合成を乗法として、半環となる。加法および乗法の単位元はそれぞれ、零準同型（零値写像）と恒等写像で与えられる。A が自然数全体の成す加法モノイド（自然数モノイド）であるとき、自然数半環は End(A) として得られる。あるいは半環 S に対して A = Sⁿ であるとき、（自己準同型を行列と同一視すれば）End(A) は S-係数の n-次行列半環になる。
• 環を成さない半環の最も簡単な例は、二元ブール代数（英語版） B で、これは可換半環を成す。
• 自然数係数多項式の全体 N[x] は可換半環を成す。実はこれが単項生成な自由可換半環を与える。
• 個別の環、例えば整数全体 Z や実数全体 R の成す環は、それ自身が半環の個別の例を与える。
• 熱帯半環 R ∪ {−∞} は、max(a, b) を半環の加法（単位元は −∞）、通常の加法を半環の乗法（単位元は 0）として、可換冪等半環を成す。加法演算として max の代わりに min を考えて R ∪ {∞} を熱帯半環として定式化することもできる。
• 任意に与えられた無限基数に対して、その基数よりも小さな基数（濃度）全体の成す集合は、基数の加法と乗法に関して半環を成す。あるいは、内部モデル（英語版）での基数全体の成す集合は（内部モデルでの）基数の加法と乗法に関して半環を成す。

環論における議論の大半は、勝手な半環に対して用いても引き続き意味を成す。特に、可換環上の多元環論は直截に可換半環上の多元環論に一般化することができる。この意味で環は、単に整数全体の成す可換半環 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, +) は離散事象系の性能評価（英語版）によく用いられる。このとき実数は「コスト」や「到達時間」を表すものであり、演算 "max" は事象の全ての要件が揃うまで待つこと（従って最大の時間を取ること）、および演算 "min" はより選択コストの必要ない最適解を選べることに対応し、また演算 "+" は同じ経路に沿って積算することに対応する。

最短経路問題に対するフロイド-ワーシャルアルゴリズムは、ミニマムプラス代数 (min, +) 上の計算として再定式化することができる。同様に、隠れマルコフモデルにおいて観測される事象列に対応する尤もらしい状態列を求めるビタビアルゴリズムは、確率上のマックスタイムズ代数 (max, ×) 上の計算に帰着される。これら動的計画法アルゴリズムは、付随する半環の分配性に依拠して、非常に膨大な数（指数函数的挙動に従うほど多くともよい）の項を持つ量に対する計算を、それらの項を個々に扱うよりも効率的に計算する。

集合半環あるいは単に半環は、空でない集合族 S で、以下の三条件

1. ∅ ∈ S,
2. E ∈ S かつ F ∈ S ならば E ∩ F ∈ S,
3. E ∈ S かつ F ∈ S ならば互いに素な集合の有限列 C_i ∈ S (i = 1, …, n) で
   ${\displaystyle E\smallsetminus F=\bigcup _{i=1}^{n}C_{i}$
   なるものを取れる,

を満たすものを言う^[2]。集合半環は測度論で用いられ、その例の一つは実数からなる全ての半開半閉区間 [a, b) ⊂ R からなる集合族として与えられる。

1. ^ Berstel & Perrin (1985), p. 26
2. ^ Noel Vaillant, Caratheodory's Extension, on probability.net.

• 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 

• 環 (数学)
• 集合半環