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

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

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

参照用 記事

引き算と無限個の足し算は両立しない

次の論文のなかにあった小ネタを紹介します。

簡単な話ですが、「ヘーッ」と目から鱗でした。

[追記]以下、半環と環の話になってますが、掛け算を使ってないので可換モノイドと可換群としても通用します。[/追記]

半環については昨日の記事でも紹介しました。足し算と掛け算が自由にできるが、引き算は要求しないような代数系です。別な言い方をすると、aに対して-a(マイナス)が必ずしも存在しなくていいのが半環です。-aの存在を要求すればとなります。

自然数(非負整数)の全体Nは半環、整数の全体Zは環です。

過去の記事「可算な総和可能性」において、モノイドのω-総和可能性という概念*1を紹介しました。半環においては、足し算がω-総和可能ならω-総和可能な半環とします。要するに、無限個の要素の足し算が定義されていることです*2。ω-総和可能な半環では、無限個の足し算も有限個の足し算と同様に扱えます。

ブール代数の半環 B = {0, 1}、自然数に無限大を付け足した半環 N∪{∞}、集合S のベキ集合の半環 Pow(S) などはω-総和可能です。

さて、半環Hがゼロ和自由(zerosumfree)であることを次のように定義します。

  • s, t∈H、s + t = 0 ならば、s = t = 0 。

今まで例に出した半環 NBN∪{∞}、Pow(S) はすべてゼロ和自由です。一方で、Zはゼロ和自由ではありません。1 + (-1) = 0 ですが、1は0ではありません。一般に次が言えます。

  • 環はゼロ和自由ではない。ゼロでないsに対して、s + (-s) = 0 だから。

アイレンベルク/スウィンドル(Eilenberg and Swindle)は次を示しました*3

  • 半環Hがω-総和可能ならば、Hはゼロ和自由である。

これは簡単に分かります。s + t = 0 というs, tを取って、次の計算をします。

0 = 0 + 0 + ... /* ゼロを無限個足してもゼロ */
  = (s + t) + (s + t) + ... /* 0 = s + t */
  = s + (t + s) + (t + s) + ... /* 括弧の付け替え */
  = s + (s + t) + (s + t) + ... /* 足し算の順序交換 */
  = s + 0 + 0 + ... /* s + t = 0 だったから */
  = s + 0 /* ゼロを無限個足してもゼロ */
  = s

これでsは0、tが0なのも同様です。

以上で次の事実が分かりました。

  1. 環はゼロ和自由ではない。
  2. 半環Hがω-総和可能ならば、Hはゼロ和自由である。

これらから、「ω-総和可能な環は存在しない」ことが分かります。これは意外なことに思えます(僕は意表を突かれた感じです)。「引き算が自由にできる」ことと、「無限個の和が計算できる」ことは絶対に両立しないのです。

*1:昨日の記事の記法では、≦ω-総和可能性です。

*2:分配法則も、無限和に対してまで拡張します。

*3:もとの論文では、任意の基数に対して総和可能な半環を完備半環(complete semiring)と呼び、完備半環に関して述べています。