檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード Twitter

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2010-06-30 (水)

「掛け算ありき」から見えるエキゾチックな世界と真実の世界

| 11:44 | 「掛け算ありき」から見えるエキゾチックな世界と真実の世界を含むブックマーク

昨日のパズルに既に回答が寄せられていますが、ネタ元論文はまだ伏せておきます(そのうちバラしますけどね*1)。([追記]ネタばらしはコチラ[/追記]

で、その某論文なんですが、題名や著者からして、僕には1ページたりとも読めそうにないシロモノだろうと思いながらペラペラと眺めていると、計算がやたら丁寧に載っているんですよね。掛け算から足し算を作る話も、そのアイディアを思いつくのは困難ですが、計算は高校生でも追えます。その高校生レベルの計算が省略なしで書いてありました。

初等的計算の先にある話になるとヤッパリ僕には歯が立たないですが、語り口が優しいので、示唆されている発想や構想は理解できなくもない気分がします(二重否定で曖昧な表現)。分かった範囲で(って分かってないかもしれんが)紹介します。

内容:

  1. サクセッサ付きの可換群は面白くない?
  2. 体の概念を拡張する
  3. 標数概念を再解釈する
  4. 標数1の半体ってなーに?
  5. べき等半環の世界
  6. 真実の標数1

サクセッサ付きの可換群は面白くない?

昨日の話を復習すると; Gを可換群として、G + {0} の上にサクセッサがあれば、掛け算(Gの演算)とサクセッサを使って足し算を定義できて、G + {0} を体にできるってことです。

サクセッサ付きの可換群の圏をAGS(Abelian group with successor)、体の圏をFieldとします。AGSの対象を引数として、足し算を定義して体を作る関手を F:AGSField として、Fieldの対象から0を取り除いた乗法群を作り、λx.(x + 1) を添える関手は U:FieldAGS とします(射に対する対応も都合よく決めるとする)。FとUにより、AGSFieldは圏同値になります。

これは何を意味するでしょう? 圏AGSと圏Fieldは事実上同じものです。一方の圏Fieldは、非常によく調べられています。同値な圏AGSを今さら調べても、それは既にFieldで知られている事実を言い換えるに過ぎません。

この考え方によれば、圏AGSは圏Fieldの言い換えを与えるだけで面白くありません。

体の概念を拡張する

体の定義を「可換群+サクセッサ」として、この定義法(通常の定義とは異なります)を足がかりに、体の概念を拡張できないでしょうか。つまり、AGS ⊆ X という未知の圏Xを探ることにより、Field ⊆ X' という圏X'が作れないか、ということです。

誰でも思いつくのは次のようなアイディアでしょう。M = G + {0} とすると、Mは吸収元(absorbing element)付きのモノイドになります。吸収元とはゼロのことですが、単位元とは別物です。演算を・、単位元をe、吸収元をzとして吸収元付きモノイドの計算法則(公理)を書くと:

  1. (a・b)・c = a・(b・c)
  2. e・a = a・e = a
  3. z・a = a・z = z

Mを、可換群に吸収元だけを付け足した形から一般の吸収元付きモノイドに拡張して、それにサクセッサ s:M→M を添えてはどうでしょうか。これは意味のあるアプローチでしょうが、これだけだと「ありがちだなー」という印象は拭えませんね。

標数概念を再解釈する

某論文が追求している方向は、体の標数の概念を再解釈することです。F3 = Z/3Z(mod 3 で計算する整数)は、3個の要素を持つ有限体で、1 + 1 + 1 = 0 が成立します。1をn個足した結果を n・1 と書くとして、n・1 = 0 が成立する最小の正整数nが体の標数です。1をいくら足しても0にならないなら、標数は0です。

標数1の体を考えると、1・1 = 0 なので、1 = 0 となり、単元集合に潰れてしまいます。つまり、通常の解釈では、標数1の体はまったくもってツマラナイものです。単元集合の上に興味ある構造や現象があるとは思えません。

さて、体の標数をサクセッサsを使って定式化してみます。例えば、標数3なら、

  • s(s(s(x))) = x

と書けます。写像の結合(合成)を図式順で「;」で書けば次のようです。([追記]sしか出てこないなら、図示順でも反図式順でも同じじゃん ^^; [/追記]

  • s;s;s = id

両側にもう1回サクセッサを適用すると:

  • s;s;s;s = s

標数2ならば、

  • s;s;s; = s

ですね。

標数3, 2と降りてきたので、標数1は当然のごとく:

  • s;s = s

これが新しい標数1の定義です。

標数1の半体ってなーに?

s;s = s を満たすような写像はベキ等な写像といいます。ベキ等写像はレトラクト(レトラクション)と深い関係にあり、ベキ等写像とレトラクトはほとんど同じ概念です(「レトラクションとベキ等自己射」を参照)。そのレトラクトは、図形的には潰すとか引きこむことで、ソフトウェア処理では正規化を意味します。

標数1の体では、サクセッサ(1を足す関数)がベキ等(あるいはレトラクト)になります。こうなると、「サクセッサは全単射だ」という条件を守ることが難しくなります。そこで、サクセッサの全単射性は落としてしまいましょう。サクセッサへの要求は次のとおりです。

  1. s(0) = 1
  2. s(a×s(b×a-1)) = a×s(s(b)×a-1) *2

全単射の条件を落とすと、引き算がうまく定義できなくなるので、それはあきらめます。引き算は要求しないで、他は体と同じ計算ができるような代数系は半体(semi-field)と呼びます。サクセッサがベキ等であることは、(0 + 1) + 1 = 0 + 1 を導くので、1 + 1 = 1 となり、分配法則を使えば a + a = a、結局、足し算がベキ等な半体に到達します。

B = {0, 1}に、普通の掛け算と 1 + 1 = 1 という足し算を入れると、ベキ等な半体になります。これは、真偽値の代数と事実上同じです。Bと標数2の体F2は台集合(underlying set)を共有し、BF2の代数構造を関係付けることもできます(「古典論理は可換環論なんだよ」参照)。

さて、Bはつまらないモノでしょうか? そんなことはありません! 古典論理はすべてB上で展開されます。今までは、古典論理を 1 + 1 = 0 という標数2の体を使って代数と関係付けました。しかし、1 + 1 = 1 という標数1の半体を使って代数と論理を架け橋する途もあります。むしろ、1 + 1 = 1 のほうが自然かもしれません。

べき等半環の世界

通常の体の上に環(や多元環)を考えたように、半体B上の半環を考えることができます。Bの足し算がベキ等なので、係数にBを許す半環もまた足し算がべき等となります。足し算がベキ等である半環はベキ等半環(ISR; idempotent semiring)と呼びます。ベキ等半環とその準同型の圏をISRとすると、BISRの始対象となっています。

ISRは、標数2の体F2上の環/加群/多元環の圏などとはだいぶ様相が違います。BF2どうしを直接に比較するとけっこう似てるのですが、その上に広がる世界は全然別のようです。

F5F3F2 のような系列で考えると、F2整数論のどん詰まりで、クセのある特殊な有限体です。また、F2上のイデアル論や幾何は、キッチリとしたかたーい論理に対応します。

かたや、B上に広がるISR(さらには半加群など)は、工学、物理、計算科学に関係します。例えば、次の記事で紹介したエキゾチック代数は、最適化問題とかマスロフ脱量子化が背景です。

比較的最近の記事で取り上げた、ホーア式のモデルや正規言語の話のなかでもベキ等半環が出てきます。

そういえば、HTTPメソッドにさえベキ等概念は登場しますよね。

ベキ等性はまた、正規化や観測の概念につながります。(ただし、足し算というより掛け算です。)

計算(computation)とソフトウェアの話題が多い僕のブログ内で、どれほど「ベキ等」「レトラクト/レトラクション」という語が使われているかを知りたいなら:

真実の標数1

今まで述べた「標数3なら s;s;s;s = s」、「標数2なら s;s;s = s」、「標数1なら s;s = s」という発想は、確かに標数1の新解釈を与えます。そして、標数1の世界はベキ等半体やベキ等半環の世界のようにも思えます。

しかし、これが標数1の唯一の解釈ではありません。そしてどうやら、BISRとは別に、もっと過激に標数1の世界があるらしいのです。なにをもって「真実の標数1」と呼ぶかは難しすぎてよく分かりませんが、「掛け算から足し算を作る発想」が(仮称)“真実の標数1”への方向を指し示しているようです。

*1:以下に出てくるキーワードから、知っている人なら、誰が書いた論文かは予想がつくと思います。

*2:実際には、この形より少し一般的な定式化を使います。