このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

零の概念とmax-plus半環の紹介

1 = 0 のとき、いったい何が起きるのか?」に補足をします。普通に考えると、1 = 0 という等式が変だと感じるのはなぜか? をもう少し詮索します。また、「1 = 0 のとき、いったい何が起きるのか?」の最後で触れた以下のような「もっと奇妙な例」も紹介します。

もっと奇妙な例として:

  • 非負実数全体を台集合とする。
  • 足し算は max{x, y} で定義する。
  • 掛け算は普通の足し算とする。

内容:

モノイドの中立元と吸収元

モノイドとは単一の二項演算を持つ代数系です。二項演算の記号として、日常的には用いられない記号□を使うことにします。また、モノイドの特別な要素はギリシャ文字で表します。なぜそのようにするかというと、「+, ・, 0, 1」などの普通の記号を使うと、それが持っている本来の意味に引きずられて誤解を生む可能性があるからです。

Mを集合、□が M×M→M という写像、νはMの特定の要素だとします。(M, □, ν) がモノイドだとは、次の計算法則が成立することです。

  1. x, y, z∈M に対して、(x□y)□z = x□(y□z)
  2. x∈M に対して、x□ν = ν□x = x

νをモノイドの中立元(neutral element)と呼びます。単位元と呼ぶことが多いですが、「単位」は乗法の単位の意味が強いので中立元とします。

Mの要素αが次の性質を持つとき吸収元(absorbing element)と呼びます。

  • x∈M に対して、x□α = α□x = α

吸収元αを一緒に考えたモノイド (M, □, ν, α) が吸収元付きモノイド(monoid with absorbing element)で、一元体F1との関係で最近はよく話題にのぼりますね。

モノイドの実例をいくつか挙げます。

  1. (R, +, 0) -- 実数の足し算、中立元は0
  2. (R, ・, 1) -- 実数の掛け算、中立元は1
  3. ({true, false}, ∧, true) -- 二値論理のAND、中立元はtrue
  4. (MatR(2, 2), ・, I) -- 実数成分の2×2行列の掛け算、中立元は単位行列
  5. ({1, 2, ...}, △, 1) -- 正整数に、n△m := n + m - 1 で定義される演算、中立元は1
  6. (P, \oplush, 0) -- 非負実数のh-マスロフ和、中立元は0

最後の例は「なぜ、どのように足し算が消失したのか:プランク定数の大惨事と生存者達」で説明しています。

半環と零

半環(semiring)は、足し算と掛け算を持ち、分配法則が成立する代数系です。モノイドの説明に変わった記号□を使ったのと同じ理由で、以下では足し算を\oplus、掛け算を\odotで表すことにします。

半環を (A, \oplus, θ, \odot, ι) で表します。θ(ギリシャ文字シータ)は\oplusの中立元、ι(イオタ)は\odotの中立元です。(A, \oplus, θ)、(A, \odot, ι) はそれぞれモノイドになっています。

零の意味を半環の文脈で考えてみると、我々は二通りの解釈を持っています。

  • 足し算の中立元が零である。
  • 掛け算の吸収元が零である。

この二通りの解釈は、通常同じ特定要素を指すので、それが異なることは想定しません。つまり、零とは「足し算の中立元であり、掛け算の吸収元でもある数」と認識されているわけです。

しかし、「1 = 0 のとき、いったい何が起きるのか?」で述べたように、足し算の中立元と掛け算の吸収元が一致する保証はありません。この事情を考慮して、加法的零(additive zero)と乗法的零(multicative zero)という言葉を使う人もいます。

  • 加法的零 -- 足し算の中立元
  • 乗法的零 -- 掛け算の吸収元

max-plus半環

1 = 0 のとき、いったい何が起きるのか?」で、加法的零と乗法的零が一致しない代数系の例を挙げましたが、もう一つの例を紹介しておきます。

Pは非負実数の全体として、P = P∪{∞} = {x∈R | 0 ≦ x}∪{∞} とします*1Pを台集合とする半環 (P, \oplus, θ, \odot, ι) を次のように定義します。

  • x \oplus y := max{x, y}
  • θ := 0
  • x\odoty := x + y
  • ι := 0

x\odoty := x + y は、「半環の掛け算を、通常の足し算として定義する」ことです。ここは「それが定義なんだ」と割りきって、次の法則を確認してみてください。

  1. (x \oplus y) \oplus z = x \oplus (y \oplus z)
  2. x \oplus θ = θ \oplus x = x
  3. x \oplus y = y \oplus x
  4. (x\odoty)\odotz = x\odot(y\odotz)
  5. x\odotι = ι\odotx = x
  6. x\odoty = y\odot x
  7. x\odot(y \oplus z) = x\odoty \oplus x\odotz
  8. (x \oplus y)\odotz = x\odotz \oplus y\odotz

見慣れない記号で面食らうかもしれませんが、内容的には次のことです。

  1. max{max{x y}, z} = max{x, max{y, z}}
  2. max{x, 0} = max{0, x} = x
  3. max{x, y} = max{y, x}
  4. x + (y + z) = (x + y) + z
  5. x + 0 = 0 + x = x
  6. x + y = y + x
  7. x + max{y, z} = max{x + y, x + z}
  8. max{x, y} + z = max{x + z, y + z}

この半環には、足し算の吸収元と掛け算の吸収元が存在します。そしてそれらは一致します。

  • \oplus x = x \oplus ∞ = ∞
  • \odotx = x\odot∞ = ∞

今紹介した半環 (P, \oplus, θ, \odot, ι) は、max-plus半環と呼ばれています(他にいくつかの定義のバリエーションがあります)。max-plus半環では、次のような状況になっています。

  • 加法的零(0)と乗法的零(∞)は一致しない。
  • 加法的零と乗法の単位(中立元)は一致する。
  • 加法の吸収元と乗法的零は一致する。

min-plus半環と三元の半環

max-plus半環のmaxをmin(小さい方)に置き換えるとmin-plus半環ができます。max-plus半環とmin-plus半環はほとんど同じですが、足し算の中立元と吸収元が異なります。

max-plus半環 min-plus半環
足し算の中立元 0
足し算の吸収元 0
掛け算の中立元 0 0
掛け算の吸収元

min-plus代数では、加法的零と乗法的零が一致するので、幾分は「常識的」になっています。しかし、零の正体は∞です。

min-plus半環のミニチュア版として、{0, 1, ∞} の三元集合の上に足し算と掛け算を定義した代数系を定義することができます。三元min-plus半環に関する演算表は次のようです。

足し算(min)の表

\oplus 0 1
0 0 0 0
1 0 1 1
0 1

掛け算(plus)の表

\odot 0 1
0 0 1
1 1 1

三元のmax-plus半環を考えると、足し算と掛け算が一致してしまい、半環が単なるモノイドに退化してしまいます。

足し算(max)の表:掛け算(plus)と同じ

\oplus 0 1
0 0 1
1 1 1

2つの演算が一致してしまう現象はモノイダルモノイドでも起こります。こういうことに何か意味があるのかな?

トロピカル代数

max-plus半環やmin-plus半環の計算技術は、トロピカル代数(tropical algebra、より一般にはエキゾチック代数)と呼ばれたりします。トロピカル代数はマスロフ脱量子化(Maslov Dequantization)との関係でも面白いし、それ自身でも応用があります。例えば、プログラム意味論に計量的な要素を入れるとき、トロピカル代数が使えそうです。

*1:[追記]Pという記号は、「なぜ、どのように足し算が消失したのか:プランク定数の大惨事と生存者達」で導入したP+∞と紛らわしいですね。Pと上付きにする方法もあるけど、これはPの無限個の直積のように見えるし。上に横棒を置いた\bar{\bf{P}}がヨサゲだが、書くのが面倒。[/追記]