とあるタイプの可換半環に関するとある公式の証明 - (保存用) 檜山正幸のキマイラ飼育記メモ編

乗法もベキ等な可換ISR（(ordered) idempotent semiring）での話。

加法はベキ等
ベキ等な加法に基づく順序が入っている。
乗法は順序を保存する。

ここまではISRの定義。さらに：

乗法もベキ等
すべての元は単位元より大きくならない ∀x. x≦1

次の等式は仮定する（数学的帰納法の仮定）：

$\prod_{1\leq i < j \leq n}\,(a_i + a_j) \: =\: \sum_{1\leq k \leq n}$ \prod_{1\leq i \leq n\\ i \neq k} \, a_i$$

両辺に、 $\prod_{1\leq l \leq n}(a_l + a_{n + 1})$ を掛けても等号は成立するから：

$\prod_{1\leq i < j \leq n}\,(a_i + a_j) \prod_{1\leq l \leq n}(a_l + a_{n + 1}) \: =\: $\sum_{1\leq k \leq n}\( \prod_{1\leq i \leq n\\ i \neq k} \, a_i$\) \prod_{1\leq l \leq n}(a_l + a_{n + 1})$

左辺は、 $\prod_{1\leq i < j \leq n+1}\,(a_i + a_j)$ となるので、右辺に注目する。

$$\sum_{1\leq k \leq n}\( \prod_{1\leq i \leq n\\ i \neq k} \, a_i$\) \prod_{1\leq l \leq n}(a_l + a_{n + 1})$
$=\: \sum_{1\leq k \leq n}$\( \prod_{1\leq i \leq n\\ i \neq k} \, a_i$$\prod_{1\leq l \leq n}(a_l + a_{n + 1})$\)$

summandのなかの $\prod_{1\leq l \leq n}(a_l + a_{n + 1})$ を取り出して計算すると：

$\prod_{1\leq l \leq n}(a_l + a_{n + 1}) \:=\: $\prod_{1\leq l \leq n} a_l$ + a_{n+1}$

ここで、ab + b = b を使っている。

次に、上記の計算結果を使ってsummandを計算する。

$\prod_{1\leq i \leq n\\ i \neq k} \, a_i\)$\prod_{1\leq l \leq n}(a_l + a_{n + 1})$
$=\: \( \prod_{1\leq i \leq n\\ i \neq k} \, a_i$ $\(\prod_{1\leq l \leq n} a_l$ + a_{n+1}\)$
$=\: $ \prod_{1\leq i \leq n\\ i \neq k} \, a_i$$\prod_{1\leq l \leq n} a_l$ + $ \prod_{1\leq i \leq n\\ i \neq k} \, a_i$ a_{n+1}$
$=\: $ \prod_{1\leq i \leq n} \, a_i$ + $ \prod_{1\leq i \leq n+1\\ i \neq k} \, a_i$$

これを総和記号のなかに入れる。

$\sum_{1\leq k \leq n}$ \( \prod_{1\leq i \leq n} \, a_i$ + $ \prod_{1\leq i \leq n+1\\ i \neq k} \, a_i$ \)$
$\:=\: \sum_{1\leq k \leq n} $ \prod_{1\leq i \leq n} \, a_i$ + \sum_{1\leq k \leq n}$ \prod_{1\leq i \leq n+1\\ i \neq k} \, a_i$$
$\:=\: $ \prod_{1\leq i \leq n} \, a_i$ + \sum_{1\leq k \leq n}$ \prod_{1\leq i \leq n+1\\ i \neq k} \, a_i$$
$\:=\: \sum_{1\leq k \leq n + 1}$ \prod_{1\leq i \leq n+1\\ i \neq k} \, a_i$$

以上より、次が成立する。

$\prod_{1\leq i < j \leq n+1}\,(a_i + a_j) \:\:=\: \sum_{1\leq k \leq n + 1}$ \prod_{1\leq i \leq n+1\\ i \neq k} \, a_i$$

数学的帰納法により、2以上のすべてのnに対して等式は成立する。