半はん環たまき

抽象ちゅうしょう代だい数学すうがくにおいて、半はん環たまき（はんかん、英えい: semi-ring）とは環たまきに類似るいじした代数だいすう的てき構造こうぞうで、環たまきの公理こうりから加法かほう的てき逆ぎゃく元もとの存在そんざいを除のぞいたものである。負まけ元もと (negative) の無ない環たまき (ring) ということから rig という用語ようごもしばしば用もちいられる。

定義ていぎ

半はん環たまきは、以下いかの性質せいしつを満みたす二ふたつの二に項こう演算えんざん、即すなわち加法かほう（和わ）"+" と乗法じょうほう（積せき）"·" とを備そなえた集合しゅうごう R を言いう^[1]：

(R, +) は単位たんい元もと 0 を持もつ可か換かわモノイドを成なす:
1. (a + b) + c = a + (b + c),
2. 0 + a = a + 0 = a,
3. a + b = b + a.
(R, ·) は単位たんい元もと 1 を持もつモノイドを成なす:
1. (a · b)· c = a ·(b · c),
2. 1 · a = a · 1 = a.
乗法じょうほうは加法かほうの上うえに分配ぶんぱい的てきである:
1. a ·(b + c) = (a · b) + (a · c),
2. (a + b)· c = (a · c) + (b · c).
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 における正規せいき歪いびつ束たば（英語えいご版ばん）は乗法じょうほうと
$a\mathop {{}\nabla {}} b:=a+b+ba-aba-bab$
で定義ていぎされる束たば演算えんざん（ナブラ）に関かんして冪べき等とう半はん環たまきとなる。
クリーネ代数だいすう（英語えいご版ばん）はクリーネスターと呼よばれる単項たんこう演算えんざん ∗: R → R を備そなえた冪べき等とう半はん環たまき R である。クリーネ代数だいすうは形式けいしき文法ぶんぽうや正規せいき表現ひょうげんの理論りろんにおいて重要じゅうようである。

個別こべつの例れい

半はん環たまきの原型げんけい的てきな例れいは、自然しぜん数すう全体ぜんたいの成なす集合しゅうごう N（ここでは 0 を含ふくむ）に通常つうじょうの加法かほうと乗法じょうほうを考かんがえたもの（自然しぜん数すう半はん環たまき）である。非負ひふ有理数ゆうりすうの全体ぜんたいや非負ひふ実数じっすうの全体ぜんたいも同おなじくして半はん環たまきを成なす。以上いじょうの例れいは全すべて可か換かわ半はん環たまきである。
各かく成分せいぶんが非負ひふな n-次つぎ正方まさかた行列ぎょうれつの全体ぜんたいは、通常つうじょうの行列ぎょうれつの加法かほうと乗法じょうほうに関かんして非ひ可か換かわ半はん環たまきを成なす。同様どうようの仕方しかたでより一般いっぱんに、任意にんいに与あたえられた半はん環たまき S に成分せいぶんを持もつ正方せいほう行列ぎょうれつの全体ぜんたいは半はん環たまきを成なし、S 自身じしんはたとえ可か換かわであったとしても、この行列ぎょうれつ半はん環たまきは一般いっぱんに非ひ可か換かわとなる。
可か換かわモノイド A に対たいし、自己じこ準じゅん同型どうけい $f : A \to 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, \times)$ 上うえの計算けいさんに帰着きちゃくされる。これら動的どうてき計画けいかく法ほうアルゴリズムは、付随ふずいする半はん環たまきの分配ぶんぱい性せいに依拠いきょして、非常ひじょうに膨大ぼうだいな数かず（指数しすう函数かんすう的てき挙動きょどうに従したがうほど多おおくともよい）の項こうを持もつ量りょうに対たいする計算けいさんを、それらの項こうを個々ここに扱あつかうよりも効率こうりつ的てきに計算けいさんする。

集合しゅうごう半はん環たまき

→詳細しょうさいは「集合しゅうごう半はん環たまき」を参照さんしょう

集合しゅうごう半はん環たまきあるいは単たんに半はん環たまきは、空そらでない集合しゅうごう族ぞく S で、以下いかの三さん条件じょうけん

∅ ∈ S,
E ∈ S かつ F ∈ S ならば E ∩ F ∈ S,
E ∈ S かつ F ∈ S ならば互たがいに素そな集合しゅうごうの有限ゆうげん列れつ C_i ∈ S (i = 1, …, n) で
$E\smallsetminus F=\bigcup _{i=1}^{n}C_{i}$
なるものを取とれる,

を満みたすものを言いう^[2]。集合しゅうごう半はん環たまきは測度そくど論ろんで用もちいられ、その例れいの一ひとつは実数じっすうからなる全すべての半開はんかい半はん閉区間くかん $[a, b) \subset R$ からなる集合しゅうごう族ぞくとして与あたえられる。

参考さんこう文献ぶんけん

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

典拠てんきょ管理かんりデータベース
全般ぜんぱん	FAST
国立こくりつ図書館としょかん	フランス BnF data ドイツイスラエルアメリカ