Ark's Blog

数学とか競プロとか参加記とか備忘録とか

ようこそ

max(∅)=-∞ は半群のモノイド化

全順序集合に思いを馳せながら寝たら思いついたネタを投げます。

導入

数学書かなにかで次のような記述を見たことがあるかもしれません。

 \mathbb{N}を正の整数全体の集合とする。

このとき、 A\subset \mathbb{N}に対して \max(A) := \text{「}A\text{のうち最も大きな値」}と定義する。

ただし、\max(\emptyset) = -\inftyとする


「ただし、\max(\emptyset) = -\inftyとする」

これ、特殊扱いしてるみたいで気持ち悪くないですか?

しかも、今回の場合は「\max(\emptyset) = 0」でも「\max(\emptyset) = -1」でも「\max(\emptyset) = -5000\text{兆}」でも問題ないです。要は ^\forall n \in \mathbb{N}, x \lt nを満たすxなら何でもいいです。

ただ、これを半群のモノイド化(1-添加と言うらしい?)と解釈したらスッキリしました。これについて以下にまとめます。

思考

  •  Xを任意の全順序集合とする。
  • このとき、 Xは二項演算 \max_2に関して半群である。
    • ここで、二項演算であることを強調して \max_2の記法を使用。以降も同様。
    • 注) Xは一般にモノイドではない。
      • 例えば X = \{ x\in \mathbb{R} | x \gt 0 \}は全順序集合だが、 \max_2に関して単位元を持たない。
  • ここで、 ^\forall x\in X, \alpha \lt xなる元 \alphaを導入して T := X\cup \{ \alpha \}と定義すると
    •  \langle T, \alpha, \max_2\rangle はモノイドになる。(モノイドの定義より明らか)
  •  S := \{ A \subset X \mid A\text{は有限集合} \}とおく。
    • 特に Xが有限集合のときは、 S = 2^Xである。
    • 言わずもがな  \langle S, \emptyset, \cup\rangle はモノイドである。
  • このとき、写像 \max: S \to Tを次のように定義する。
    •  A\in Sに対して
      •  A\neq \emptysetならば、 \max(A) := \text{「}A\text{のうち最も大きな値」}
      •  A = \emptysetならば、 \max(A) := \alpha
  • すると、 \max \langle S, \emptyset, \cup\rangleから \langle T, \alpha, \max_2\rangleへのモノイド準同型である。なぜなら
    •  ^\forall A, B \in Sについて
      •  A\neq \emptyset \land B\neq \emptyset ならば \begin{aligned}\max(A\cup B) &= \text{「}A\cup B\text{のうち最も大きな値」} \\ &= \max\nolimits_2(\text{「}A\text{のうち最も大きな値」}, \text{「}B\text{のうち最も大きな値」}) \\ &= \max\nolimits_2(\max(A), \max(B)) \end{aligned}
      •  A = \emptysetならば \begin{aligned}\max(A\cup B) &=\max(B) \\ &= \max\nolimits_2(\alpha, \max(B))\\ &= \max\nolimits_2(\max(A), \max(B)) \end{aligned}
      •  B = \emptysetならば \begin{aligned}\max(A\cup B) &=\max(A) \\ &= \max\nolimits_2(\max(A), \alpha)\\ &= \max\nolimits_2(\max(A), \max(B)) \end{aligned}

結論

「ただし、\max(\emptyset) = -\inftyとする」は

  • 全順序集合 Xをモノイド \langle X \cup \{\alpha\}, \alpha, \max_2\rangleに拡張し、
  •  \maxを、 \langle \{ A \subset X \mid A\text{は有限集合} \}, \emptyset, \cup\rangleから \langle X \cup \{\alpha\}, \alpha, \max_2\rangleへのモノイド準同型にする

ための操作だと解釈できる。つまり、\max(\emptyset)の値は半群 \langle X, \max_2\rangleの結合律を壊さない範囲で適切な単位元を導入すれば良いので、冒頭のような自由度のある値設定が生まれてくる。

補足

↑は \maxについてしか書かなかったけど、当然 \minについでも同様な議論ができる。

感想

スッキリした。おやすみ

ノリで書いたので何かミスがあるかも