半環状

抽象代数学において、半環は代数構造の一種である。半環は環の一般化であり、各要素が加法逆元を持つという要件を取り除いたものである。同時に、半環は有界分配束の一般化でもある。

環ではない最小の半環は、例えば論理和を用いた2要素ブール代数である。${\displaystyle \lor }$追加として。環でも格子でもない動機付けとなる例として、自然数の集合が挙げられる。${\displaystyle \mathbb {N} }$（ゼロを含む）通常の加算と乗算の下で。半環は、任意の可換モノイド上の自己準同型の関数合成として適切な乗算演算が生じるため、豊富に存在します。

一部の著者は、半環を、${\displaystyle 0}$または${\displaystyle 1}$これにより、一方では環と半環、他方では群と半群の間の類推がよりスムーズに機能するようになります。これらの著者は、ここで定義された概念に対してrig をよく使用します。 ^{[ 1 ] [ a ]}これは、rig は負の要素のない環であるという冗談から始まりました。（乗法的な単位元のない ar i ng を意味する rng の使用に似ています。）

二元モノイド（「二重モノイド」の略）という用語は、半環やその他の構造を意味するために使用されてきました。1972年にクンツマンによって半環を表すために使用されました。^{[ 2 ]}（自然順序半環にも使用されることがありますが^{[ 3 ]} 、 1992年にバチェリらによって冪等部分群にも使用されました。 ^{[ 4 ]}）

半環は集合である${\displaystyle R}$2つのバイナリ演算機能を備えています${\displaystyle +}$そして${\displaystyle \cdot ,}$加算と乗算と呼ばれ、次のようになります。^{[ 5 ] [ 6 ] [ 7 ]}

• ${\displaystyle (R,+)}$は、単位元を持つ可換モノイドである。${\displaystyle 0}$:
  • ${\displaystyle (a+b)+c=a+(b+c)}$
  • ${\displaystyle 0+a=a}$
  • ${\displaystyle a+0=a}$
  • ${\displaystyle a+b=b+a}$
• ${\displaystyle (R,\,\cdot \,)}$は、単位元を持つモノイドである。${\displaystyle 1}$:
  • ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$
  • ${\displaystyle 1\cdot a=a}$
  • ${\displaystyle a\cdot 1=a}$

さらに、以下の公理は両方の操作に関連しています。

• 乗法によって、任意の要素は加法単位元によって 左辺と右辺で消去される。
  • ${\displaystyle 0\cdot a=0}$
  • ${\displaystyle a\cdot 0=0}$
• 乗算の左分配法則と右分配法則は加算に適用される。
  • ${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$
  • ${\displaystyle (b+c)\cdot a=(b\cdot a)+(c\cdot a)}$

基礎となるセットを持つゼロリング${\displaystyle \{0\}}$は自明な半環と呼ばれる半環である。この自明性は、${\displaystyle 0=1}$したがって、非自明な半環について話すときは、${\displaystyle 0\neq 1}$これはしばしば、追加の公理であるかのように暗黙のうちに前提とされている。さて、任意の半環が与えられた場合、新しい半環を定義する方法はいくつかある。

前述のとおり、自然数は${\displaystyle {\mathbb {N} }}$その算術構造は半環を形成する。半環におけるゼロと後続演算の像を取る${\displaystyle R}$つまり、集合${\displaystyle \{x\in R\mid x=0_{R}\lor \exists p\in R.x=p+1_{R}\}}$継承された操作と合わせて、常にサブセミリンジである${\displaystyle R}$。

もし${\displaystyle (M,+)}$は可換モノイドであり、関数合成によって乗算が行われ、半環が形成される。${\displaystyle \operatorname {End} (M)}$内準同型の${\displaystyle M\to M}$は、点ごとの加算から定義される半環を形成する。${\displaystyle M}$ゼロ射と恒等射はそれぞれ中立元である。${\displaystyle M=R^{n}}$と${\displaystyle R}$半環、正方形に関連付けられる半環が得られます${\displaystyle n\times n}$行列${\displaystyle {\mathcal {M}}_{n}(R)}$係数は${\displaystyle R}$行列の通常の加算と乗算規則を用いた行列半環。${\displaystyle n\in {\mathbb {N} }}$そして${\displaystyle R}$半環、${\displaystyle {\mathcal {M}}_{n}(R)}$は常に半環でもある。一般に非可換である。${\displaystyle R}$可換であった。

Dorroh拡張機能：もし${\displaystyle R}$半環である場合、${\displaystyle R\times {\mathbb {N} }}$ポイントごとの加算と乗算は次のように与えられる。${\displaystyle \langle x,n\rangle \bullet \langle y,m\rangle$ :=\langle x\cdot y+(x\,m+y\,n),n\cdot m\rangle } は 乗法単位を持つ別の半環を定義します${\displaystyle 1_{R\times {\mathbb {N} }}:=\langle 0_{R},1_{\mathbb {N} }\rangle }$非常によく似た場合、${\displaystyle N}$は、${\displaystyle R}$また、半環を定義することもできる。${\displaystyle R\times N}$式中の繰り返し加算を乗算に置き換えるだけで、実際には、これらの構成はより緩い条件下でも機能し、構造は${\displaystyle R}$乗法単位を持つことは必ずしも必要ではない。

ゼロサムフリー半環は、ある意味で環から最も遠い存在である。半環が与えられた場合、新しいゼロを隣接させることができる。${\displaystyle 0'}$基礎となる集合に、零因子を持たない零和のない半環を得る。特に、${\displaystyle 0\cdot 0'=0'}$そして、古い半環は実際には部分半環ではありません。次に、常にゼロを尊重しながら、新しい要素を一度に1つずつ「上に」追加することができます。これらの2つの戦略は、より緩い条件下でも機能します。表記法によっては${\displaystyle -\infty }$応答${\displaystyle +\infty }$これらの構造物を作成する際に使用されます。

このように、自明な半環に新たな零点を付加すると、論理結合子である選言と連言を用いて表現できる別の半環が得られる。${\displaystyle \langle \{0,1\},+,\cdot ,\langle 0,1\rangle \rangle =\langle \{\bot ,\top \},\lor ,\land ,\langle \bot ,\top \rangle \rangle }$したがって、これは環ではない最小の半環である。具体的には、これは環の公理に違反する。${\displaystyle \top \lor P=\top }$すべての人々のために${\displaystyle P}$つまり${\displaystyle 1}$加法逆元を持たない。自己双対定義では、欠陥は${\displaystyle \bot \land P=\bot }$（これは指輪と混同してはならない）${\displaystyle \mathbb {Z} _{2}}$その加算は排他的論理和として機能します。${\displaystyle \veebar }$）フォン・ノイマンの自然数モデルでは、${\displaystyle 0_{\omega }:=\{\}}$、${\displaystyle 1_{\omega }:=\{0_{\omega }\}}$そして${\displaystyle 2_{\omega }:=\{0_{\omega },1_{\omega }\}={\mathcal {P}}1_{\omega }}$2要素半環は、集合論的な和集合と積集合を用いて次のように表すことができる。${\displaystyle \langle {\mathcal {P}}1_{\omega },\cup ,\cap ,\langle \{\},1_{\omega }\rangle \rangle }$。実際、この構造は依然として半環を構成しており、${\displaystyle 1_{\omega }}$居住可能なあらゆる集合体に置き換えられる。

半環上の理想${\displaystyle R}$部分集合に対する標準演算により、格子順序付けされた単純かつゼロサムフリーの半環を形成する。${\displaystyle {\mathcal {M}}_{n}(R)}$理想と一致する${\displaystyle R}$左派のイデオロギーの集合体${\displaystyle R}$（そして同様に右イデアルも）その代数的構造の多くを持っているが、${\displaystyle R}$両側乗法単位元としては機能しない。

もし${\displaystyle R}$は半環であり、${\displaystyle A}$居住地である集合、${\displaystyle A^{*}}$自由モノイドと形式多項式を表す${\displaystyle R[A^{*}]}$その単語の上に別の半環が形成される。小さな集合の場合、生成要素は慣習的に多項式半環を表すために使用される。たとえば、シングルトンの場合${\displaystyle A=\{X\}}$そのため${\displaystyle A^{*}=\{\varepsilon ,X,X^{2},X^{3},\dots \}}$とある人は書いている${\displaystyle R[X]}$ゼロサムフリー部分半環${\displaystyle R}$サブセミリングを決定するために使用できます${\displaystyle R[A^{*}]}$。

集合が与えられた${\displaystyle A}$必ずしも単一要素である必要はなく、半環の基となる集合にデフォルト要素を隣接させる。${\displaystyle R}$部分関数の半環は次のように定義できる。${\displaystyle A}$に${\displaystyle R}$。

導出が与えられた場合${\displaystyle {\mathrm {d} }}$半環状${\displaystyle R}$もう一つの作戦「${\displaystyle \bullet }$「充実感」${\displaystyle X\bullet y=y\bullet X+{\mathrm {d} }(y)}$は、新しい乗算の一部として定義できます。${\displaystyle R[X]}$その結果、別の半環が生成される。

上記は、体系的な構成の網羅的なリストでは決してありません。

半環の基本的な性質は、${\displaystyle 1}$は左または右の零因子ではなく、${\displaystyle 1}$だけでなく、${\displaystyle 0}$自身に正方形、つまりこれらは${\displaystyle u^{2}=u}$。

モノイド構造から受け継がれる注目すべき性質がいくつかあります。モノイド公理は単位元の存在を要求するため、半環の基となる集合は空集合であってはなりません。また、2項述語${\displaystyle x\leq _{\text{pre}}y}$定義される${\displaystyle \exists d.x+d=y}$ここで加算演算に対して定義されている は、常に右正準前順序関係を構成する。反射性${\displaystyle y\leq _{\text{pre}}y}$その身元によって証明される。さらに、${\displaystyle 0\leq _{\text{pre}}y}$は常に有効であり、したがってゼロはこの順序に関して最小の要素です。特に可換加算について考えると、「右」の区別は無視できます。非負整数では${\displaystyle \mathbb {N} }$例えば、この関係は反対称かつ強連結であり、したがって実際には（非厳密な）全順序である。

以下では、さらに条件付き特性について説明します。

• 定義上、任意の環と任意の半体は、いずれも半環である。
• 可換で離散的に順序付けられた環の非負の要素は、可換で離散的に（上記で定義された意味で）順序付けられた半環を形成する。これには非負の整数が含まれる。${\displaystyle \mathbb {N} }$。
• また、非負の有理数と非負の実数は、可換な順序付き半環を形成する。^{[ 20 ] [ 21 ] [ 22 ]}後者は、確率半環。 ^{[ 6 ]}環でも分配束でもない。これらの例には乗法逆元も存在する。
• 既存の半環から条件付きで新しい半環を構築することができる。拡張された自然数${\displaystyle \mathbb {N} \cup \{\infty \}}$加算と乗算を拡張して${\displaystyle 0\cdot \infty =0}$[ ^{21 ]​}
• 自然数係数を持つ多項式の集合は、${\displaystyle \mathbb {N} [x],}$可換半環を形成する。実際、これは単一の生成元を持つ自由可換半環である。${\displaystyle \{x\}.}$また、前述のように、他の半環を係数とする多項式も定義できる。
• 非負の有限分数${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}:=\left\{mb^{-n}\mid m,n\in \mathbb {N} \right\}}$位置記数法において、与えられた基数に対して${\displaystyle b\in \mathbb {N} }$は、有理数の部分半環を形成する。${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\subseteq {\tfrac {\mathbb {N} }{c^{\mathbb {N} }}}}$もし${\displaystyle b}$分ける${\displaystyle c}$。 のために${\displaystyle |b|>1}$セット${\displaystyle {\tfrac {\mathbb {Z} _{0}}{b^{\mathbb {Z} _{0}}}}:={\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\cup \left(-{\tfrac {\mathbb {N} _{0}}{b^{\mathbb {N} }}}\right)}$は、底に収束するすべての有限分数の環である。${\displaystyle b,}$そして密度が高い${\displaystyle \mathbb {Q} }$。
• 丸太の半年輪は${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$追加により${\displaystyle x\oplus y=-\log \left(e^{-x}+e^{-y}\right)}$乗算${\displaystyle +,}$ゼロ要素${\displaystyle +\infty ,}$および単位要素${\displaystyle 0.}$^{[ 6 ]}
• 同様に、最大プラス熱帯半環は以下のように定義される。${\displaystyle \mathbb {R} \cup \{-\infty \}}$と${\displaystyle \max(a,b)}$半環付加（同一性）として機能する${\displaystyle -\infty }$）と通常の加算（恒等式 0）が半環乗算として機能する。同様に、min-plusトロピカル半環は${\displaystyle \mathbb {R} \cup \{\infty \},}$また、加算演算としてmaxの代わりにminが使用される。^{[ 23 ]} 関連するバージョンでは${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$基礎となる集合として。^{[ 6 ] [ 10 ]}これらは、代数多様体と区分的線形構造を結びつける活発な研究分野である。^{[ 24 ]}
• ルカシェヴィチ半環：閉区間${\displaystyle [0,1]}$追加${\displaystyle a}$そして${\displaystyle b}$引数の最大値を取ることによって与えられる（${\displaystyle \max(a,b)}$）と乗算${\displaystyle a}$そして${\displaystyle b}$によって与えられた${\displaystyle \max(0,a+b-1)}$多値論理に現れる。^{[ 11 ]}
• ビテルビ半環は基底集合上でも定義される。${\displaystyle [0,1]}$加算では最大値をとりますが、乗算では通常の実数の乗算を行います。確率的構文解析に現れます。^{[ 11 ]}

• 与えられた半環のすべてのイデアルの集合は、イデアルの加法と乗法に関して半環を形成する。
• 有界な分配束は、結合と交わりに関して可換な半環である。ブール代数は、これらの特殊な場合である。ブール環も半環（実際には環）であるが、加法に関して冪等ではない。ブール半環は、ブール代数の部分半環と同型な半環である。^{[ 20 ]}
• 2要素ブール代数によって形成され、定義される可換半環${\displaystyle 1+1=1}$。また、ブール半環。 ^{[ 6 ] [ 21 ] [ 22 ] [ 9 ]} 2つの集合が与えられた場合${\displaystyle X}$そして${\displaystyle Y,}$二項関係${\displaystyle X}$そして${\displaystyle Y}$インデックスによって示される行列に対応する${\displaystyle X}$そして${\displaystyle Y}$ブール半環のエントリでは、行列の加算は関係の和集合に対応し、行列の乗算は関係の合成に対応する。^{[ 25 ]}
• 任意の単位的量子は、結合と乗算に関して半環である。
• リング内の通常の斜め格子${\displaystyle R}$は乗算とナブラ演算の半環であり、後者の演算は次のように定義される。${\displaystyle a\mathbin {\nabla } b=a+b+ba-aba-bab}$

モノイドをさらに使用して、

• 半環の構築${\displaystyle \operatorname {End} (M)}$可換モノイドから${\displaystyle M}$すでに述べたように、半環を与える。${\displaystyle R}$、${\displaystyle n\times n}$行列は別の半環を形成する。例えば、非負の要素を持つ行列は、${\displaystyle {\mathcal {M}}_{n}(\mathbb {N} ),}$マトリックス半環を形成する。^{[ 20 ]}
• アルファベット（有限集合）Σが与えられたとき、その上の形式言語の集合は${\displaystyle \Sigma }$（サブセット）${\displaystyle \Sigma ^{*}}$）は文字列連結によって誘導される積を持つ半環である。${\displaystyle L_{1}\cdot L_{2}=\left\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\right\}}$そして、言語の和集合としての加算（つまり、通常の和集合としての和集合）。この半環の零点は空集合（空言語）であり、半環の単位は空文字列のみを含む言語である。^{[ 11 ]}
• 前の例を一般化する（${\displaystyle \Sigma ^{*}}$自由モノイドとして${\displaystyle \Sigma }$）、 取る${\displaystyle M}$任意のモノイドであること。冪集合${\displaystyle \wp (M)}$すべてのサブセットの${\displaystyle M}$集合論的な和集合を加算、集合ごとの乗算として扱うと、半環を形成する。${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}.}$^{[ 22 ]}
• 同様に、${\displaystyle (M,e,\cdot )}$がモノイドである場合、 の有限多重集合の集合は${\displaystyle M}$半環を形成する。つまり、要素は関数である。${\displaystyle f\mid M\to \mathbb {N} }$; 要素が与えられた場合${\displaystyle M,}$この関数は、それが表すマルチセット内でその要素が何回出現するかを示します。加算単位は定数ゼロ関数です。乗算単位は関数マッピングです。${\displaystyle e}$に${\displaystyle 1,}$そしてその他すべての要素${\displaystyle M}$に${\displaystyle 0.}$合計は次のように与えられる。${\displaystyle (f+g)(x)=f(x)+g(x)}$そしてその積は次のように与えられる。${\displaystyle (fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}.}$

集合や同様の抽象化に関して、

• 集合が与えられた${\displaystyle U,}$上の二項関係の集合${\displaystyle U}$は、加算が（集合としての関係の）和集合、乗算が関係の合成である半環である。半環の零点は空関係であり、単位元は恒等関係である。^{[ 11 ]}これらの関係は、によって添え字付けられた正方行列の行列半環（実際には行列半代数）に対応する。${\displaystyle U}$ブール半環のエントリを持ち、加算と乗算は通常の行列演算であり、ゼロと単位は通常のゼロ行列と単位行列です。
• 任意の無限基数よりも小さい基数の集合は、基数の加算と乗算に関して半環を形成する。内部モデルのすべての基数のクラスは、（内部モデルの）基数の加算と乗算に関して（クラス）半環を形成する。
• 空集合をゼロ対象とし、空集合のみからなる集合を単位とし、集合の非交和を加算とし、集合の直積を乗算とする組み合わせクラス（非負整数サイズを持つ可算個のオブジェクトの集合で、各サイズにつき有限個のオブジェクトが存在する）の同型同値類の族。^{[ 26 ]}
• 任意の分配圏における対象の同型類は、余積および積演算の下で、バーンサイド・リグとして知られる半環を形成する。^{[ 27 ]}バーンサイド・リグは、圏が自明である場合に限り環となる。

の${\displaystyle (\max ,+)}$そして${\displaystyle (\min ,+)}$実数上のトロピカル半環は、離散イベントシステムの性能評価によく用いられます。実数は「コスト」または「到着時間」を表し、「max」演算はイベントのすべての前提条件が満たされるまで待つ必要があること（つまり、最大時間を要すること）に対応し、「min」演算は最もコストの低い選択肢を選ぶことができることに対応します。また、「+」は同じ経路に沿った累積に対応します。

最短経路のためのフロイド・ウォーシャルアルゴリズムは、次のように再定式化できる。${\displaystyle (\min ,+)}$同様に、隠れマルコフモデルにおける観測シーケンスに対応する最も可能性の高い状態シーケンスを見つけるためのビタビアルゴリズムも、代数上の計算として定式化できます。${\displaystyle (\max ,\times )}$確率に関する代数。これらの動的計画法アルゴリズムは、関連する半環の分配法則を利用して、多数の項（指数関数的に増加する可能性もある）にわたる量を、各項を列挙するよりも効率的に計算します。^{[ 28 ] [ 29 ]}

半環の一般化では乗法単位元の存在は必要なく、乗法はモノイドではなく半群になります。このような構造はヘミリング^{[ 30 ]}またはプレ半環^{[ 31 ]}と呼ばれます。さらに一般化されたものとして、左プレ半環^{[ 32 ]}があり、これは右分配性も必要としません（または、左分配性を必要としない右プレ半環）。

さらに一般化されたものとして、準半環があります。これは、積に中立元を必要としないこと、つまり右分配法則（または左分配法則）を必要としないことに加えて、加算が可換である必要もありません。基数が（クラス）半環を形成するのと同様に、順序数も、標準的な順序数の加算と乗算を考慮に入れると、準半環を形成します。ただし、順序数のクラスは、いわゆる自然演算（またはヘッセンベルク演算）を考慮することで、半環に変換できます。

圏論において、2-リグとは、リグと同様の関数演算を持つ圏のことである。基数がリグを形成するという事実は、集合の圏（あるいはより一般的には、任意のトポス）が2-リグである、と分類することができる。

• 集合の環– 結合と相対補集合に関して閉じた族 
• 評価代数– 情報処理を記述する代数リダイレクト先の簡単な説明を表示するページ