半環

環なら $u=-1$ がとれる。逆に $1+u=0$ とする。$a\in S$ について、分配法則と吸収律から
$$ a+au=a(1+u)=a\cdot 0=0 $$
であり、加法は可換なので $au$ が $a$ の加法の逆元である。よって $(S,+)$ は群で、$S$ は環である。$\square$

準同型 $f$ は $f(0)=0$、$f(1)=1$ と加法性から $f(n)=f(1+\dots+1)=n\cdot1$ を満たすので、一意である。$\varphi(n):=n\cdot 1$ が準同型であることを示す。$\varphi(0)=0$、$\varphi(1)=1$ であり、$\varphi(m+n)=\varphi(m)+\varphi(n)$ は加法の結合律から従う。乗法性は $n$ についての帰納法で示す。$\varphi(m\cdot0)=0=\varphi(m)\cdot0$ は吸収律による。$\varphi(mn)=\varphi(m)\varphi(n)$ を仮定すると、分配法則により
$$ \varphi(m(n+1))=\varphi(mn)+\varphi(m)=\varphi(m)\varphi(n)+\varphi(m)\cdot1=\varphi(m)\bigl(\varphi(n)+1\bigr)=\varphi(m)\varphi(n+1) $$
である。$\square$

1．$a+a=a(1+1)=a\cdot1=a$ である。
2．反射律は 1 による。$a+b=b$ かつ $b+a=a$ なら、加法の可換性から $a=b$ である（反対称律）。$a+b=b$、$b+c=c$ なら $a+c=a+(b+c)=(a+b)+c=b+c=c$ である（推移律）。$0+a=a$ なので $0\le a$ である。$a+(a+b)=(a+a)+b=a+b$ から $a\le a+b$、同様に $b\le a+b$ である。$a\le c$、$b\le c$ なら $(a+b)+c=a+(b+c)=a+c=c$ なので $a+b\le c$ である。よって $a+b$ は上限である。
3．$a+b=b$ とする。$(a+c)+(b+c)=(a+b)+(c+c)=b+c$、$ac+bc=(a+b)c=bc$、$ca+cb=c(a+b)=cb$ である。$\square$

積の構成。 $s\in S$ を固定すると、左からの掛け算 $\lambda_s\colon S\to S$、$a\mapsto sa$ は分配法則と吸収律から可換モノイドの準同型である。Grothendieck群 の定理「Grothendieck群の普遍性」を $\gamma\circ\lambda_s\colon S\to K(S)$ に当てると、群準同型 $\Lambda_s\colon K(S)\to K(S)$ で $\Lambda_s(\gamma(a))=\gamma(sa)$ を満たすものがただ一つある。$\Lambda_{s+s'}$ と $\Lambda_s+\Lambda_{s'}$ はどちらも $\gamma(a)$ を $\gamma(sa+s'a)$ に送る群準同型なので、同じ一意性から等しく、$\Lambda_0=0$ である。よって $s\mapsto\Lambda_s$ は可換モノイド $S$ から加法群 $\operatorname{End}(K(S))$ への準同型であり、もう一度普遍性を使うと群準同型 $x\mapsto\Lambda_x$（$K(S)\to\operatorname{End}(K(S))$）で $\Lambda_{\gamma(s)}=\Lambda_s$ となるものが得られる。$xy:=\Lambda_x(y)$ と定めると、この積は両方の変数について加法的で、$\gamma(s)\gamma(a)=\gamma(sa)$ を満たす。
環の公理。 $K(S)$ は加法群として $\gamma(S)$ で生成される。結合律の両辺 $(xy)z$、$x(yz)$ は三つの変数それぞれについて加法的なので、$x=\gamma(a)$、$y=\gamma(b)$、$z=\gamma(c)$ の場合に確かめれば足り、その場合はどちらも $\gamma(abc)$ である。同様に $\gamma(1)$ が単位元であること、分配法則（積の加法性そのもの）、$S$ が可換なときの可換性が従う。$\gamma$ は加法と乗法を保ち、$\gamma(0)=0$、$\gamma(1)$ は単位元なので半環の準同型である。積の式は
$$ (\gamma(a)-\gamma(b))(\gamma(c)-\gamma(d))=\gamma(ac+bd)-\gamma(ad+bc) $$
による。$\gamma$ を準同型にする加法的な積は生成元の上で $\gamma(a)\gamma(b)=\gamma(ab)$ と決まるので、環の構造は一意である。
普遍性。 $f$ は可換モノイドの準同型なので、Grothendieck群 の定理「Grothendieck群の普遍性」により群準同型 $\bar f$ で $\bar f\circ\gamma=f$ となるものがただ一つある。$\bar f(xy)$ と $\bar f(x)\bar f(y)$ はどちらも $x,y$ について加法的で、$x=\gamma(a)$、$y=\gamma(b)$ では $f(ab)=f(a)f(b)$ により一致するので、$\bar f$ は乗法を保つ。$\bar f(\gamma(1))=f(1)=1$ である。一意性は群準同型としての一意性から従う。
3。 $\gamma(a)=\gamma(b)$ は $(a,0)\sim(b,0)$、すなわち $a+0+c=0+b+c$ となる $c$ があることを意味する。$\square$

1 は thm-semiring-ring-completion の 3 の言い換えである。2：$1+1=1$ なので $\gamma(1)+\gamma(1)=\gamma(1)$、群 $K(S)$ で $\gamma(1)$ を引いて $\gamma(1)=0$ を得る。環の単位元が $0$ なので $K(S)$ は零環である。準同型 $f\colon S\to R$ があれば、同じ計算で $R$ の中で $1=f(1)=0$ となる。$\square$

1．$k$ についての帰納法。$k=0$ は $E$ の定義そのものである。長さ $k+1$ の歩道 $i\to\dots\to j$ は、最後の一つ手前の頂点 $l$ で、長さ $k$ の歩道 $i\to\dots\to l$ と辺 $l\to j$ に一意に分かれ、重みはその和である。$\mathbb{T}$ の積の定義により
$$ (A^{\odot(k+1)})_{ij}=\min_{1\le l\le n}\bigl((A^{\odot k})_{il}+w_{lj}\bigr) $$
であり、帰納法の仮定から右辺の各項は「$l$ を経由する長さ $k+1$ の歩道の最小の重み」である（辺がないときや歩道がないときは $+\infty$ が足されて $+\infty$ になる）。それらの最小値が長さ $k+1$ の歩道全体の最小値である。歩道は有限個なので最小値は存在する。
2．$\mathbb{T}$ の加法は冪等なので、$B^{\odot m}=(E\oplus A)^{\odot m}$ を分配法則で展開すると、$E$ と $A$ の積の語は $A$ の個数が $k$ なら $A^{\odot k}$ に等しく、同じ項が何度現れても冪等性で一つにまとまるから
$$ B^{\odot m}=\bigoplus_{k=0}^{m}A^{\odot k} $$
である。1 により $(B^{\odot(n-1)})_{ij}$ は長さ $n-1$ 以下の歩道の重みの最小値である。長さ $n$ 以上の歩道は $n+1$ 個以上の頂点を通るので、ある頂点を 2 回通る。その 2 回の間の部分は閉歩道で、仮定によりその重みは $0$ 以上だから、取り除いて得られる短い歩道の重みは元の重み以下である。これを繰り返すと、任意の歩道について、重みが元の重み以下で長さ $n-1$ 以下の歩道が得られる。よって歩道全体の重みの下限は、長さ $n-1$ 以下の有限個の歩道の最小値に等しい。$\square$