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

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

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

［参照用 記事］

可変項数演算と代数系としての宇宙

雑記／備忘

二項演算や単項演算はお馴染みの概念だと思います。無項演算や可変項数演算も考えることができます。台集合の上に、幾つかの演算が載った構造が代数系です。大きい台集合も許すならば、グロタンディーク宇宙も一種の代数系とみなせます。$`\newcommand{\mrm}[1]{\mathrm{#1} }
\newcommand{\cat}[1]{\mathcal{#1} }
\newcommand{\mbf}[1]{\mathbf{#1} }
%\newcommand{\mbb}[1]{\mathbb{#1} }
%\newcommand{\u}[1]{\underline{#1} }
\newcommand{\Imp}{\mathrel{\Rightarrow} }
\newcommand{\In}{\text{ in } }
%\newcommand{\op}{\mathrm{op} }
%\newcommand{\hyp}{\text{－} }
%\newcommand{\Iff}{\mathrel{\Leftrightarrow} }
`$

内容：

n項演算

演算とは関数のことですが、特定の集合 $`X`$ に対して次の形の関数を「演算」と呼ぶことが多いようです。

  • $`X^0 \to X \In \mbf{Set}`$
  • $`X^1 \to X \In \mbf{Set}`$
  • $`X^2 \to X \In \mbf{Set}`$
  • $`X^3 \to X \In \mbf{Set}`$

上から順に、

  • 無項演算〈nullary operation〉
  • 単項演算〈unary operation〉
  • 二項演算〈binary operation〉
  • 三項演算〈ternary operation〉

$`X`$ の右肩に載っている自然数は項数〈arity〉です。一般的には、n項演算〈n-ary operation〉という言葉を使います。

項数が 0 のとき、$`X^0`$ は特定された単元集合〈distinguished singleton set〉 $`\mbf{1}`$ のことなので、0項演算〈無項演算〉は次の形の関数です。

$`\quad \mbf{1} \to X \In \mbf{Set}`$

次の（集合のあいだの）同型があるので、0項演算〈無項演算〉と $`X`$ の要素は一対一対応します。

$`\quad \mrm{Map}(\mbf{1}, X) \cong X \In \mbf{Set}`$

しばしば、0項演算と要素は同一視されます。

指数記法〈累乗記法〉を関数集合〈写像集合 | 関数空間 | 写像空間〉の記法だと解釈すると、次のような同型が成立します。以下、 $`\bar{n} := \{1, \cdots, n\}`$ と約束します。

$`\quad X^0 = \mbf{1} \cong \mrm{Map}(\emptyset, X) = X^\bar{0}\\
\quad X^1 = X \cong \mrm{Map}(\mbf{1}, X) = X^\bar{1}\\
\quad X^2 = X\times X \cong \mrm{Map}(\bar{2}, X) = X^\bar{2}\\
\quad X^3 = X\times X \times X \cong \mrm{Map}(\bar{3}, X) = X^\bar{3}
`$

$`X^n`$ と $`X^\bar{n} = \mrm{Map}(\bar{n}, X)`$ は同一視してもかまわないでしょう。

項数〈arity〉概念を一般化して、自然数ではなくて集合 $`\alpha`$ を項数（一般化）だとすると、$`\alpha`$項演算は次の形の関数です。

$`\quad X^\alpha \to X \In \mbf{Set}`$

ここでの指数記法〈累乗記法〉は、関数集合 $`\mrm{Map}(\alpha, X)`$ の意味です。

例えば $`\alpha = \mbf{N}`$ と置くと、$`\mbf{N}`$項演算になります。$`\mbf{N}`$項演算とは、可算無限項数の演算です。

$`\quad X^\mbf{N} \to X \In \mbf{Set}`$

可変項数演算

むかーし昔、「varargs〈ばーあーぐす〉」なんて言葉がありました*1。これは、variable-length arguments -- 可変長引数のことです。ひとつの関数の引数の個数が変化してもいいことです。「演算」という言葉に“varargs的形容詞”を付けるならば可変項数演算〈variable-arity operation〉ですね。ひとつの名前・記号で指される演算が、複数の項数を持つ、ということです。

例えば、マイナス記号で指される実数演算は次の2つのプロファイル（入力と出力の仕様）を持ちます。

  • $`(-) : \mbf{R}^\bar{1} \to \mbf{R}`$ 単項演算、符号を反転する。ゼロはゼロのまま。
  • $`(-) : \mbf{R}^\bar{2} \to \mbf{R}`$ ニ項演算、引き算。

マイナス記号が指す演算を、ひとつのプロファイルで書くなら次のようです。

$`\quad (-) : (\mbf{R}^\bar{1} + \mbf{R}^\bar{2}) \to \mbf{R} \In \mbf{Set}`$

ここで、足し算記号は集合の直和を表します。

実数を成分とするリストを総和する演算を $`\mrm{sum}`$ という名前にすると、演算 $`\mrm{sum}`$ は可変項数の演算になります。この可変項数演算をひとつのプロファイルで書くなら：

$`\quad \mrm{sum} : (\mbf{R}^\bar{0} + \mbf{R}^\bar{1} + \cdots) \to \mbf{R} \In \mbf{Set}`$

無限個の集合達の直和が演算の域〈ドメイン〉になります。無限個の直和をシグマ記号で書くなら次のようです。

$`\quad \mrm{sum} : (\sum_{n \in \mbf{N}} \mbf{R}^\bar{n}) \to \mbf{R} \In \mbf{Set}`$

無限個の直和で定義される集合〈データ型〉がリストですから、次のように簡潔に書けます。

$`\quad \mrm{sum} : \mrm{List}(\mbf{R}) \to \mbf{R} \In \mbf{Set}`$

可変項数演算は、多相関数や関数名オーバーロードの簡単な事例になっています。

グロタンディーク宇宙

グロタンディーク宇宙の話はこのブログ内で何度もしています。

比較的新しい記事をひとつだけ挙げるならば：

グロタンディーク宇宙 $`U`$ は、ZF集合論〈ツェルメロ／フレンケル集合論〉のなかでは、通常の集合です。しかし、普通の感覚で言えば非常に巨大な集合で、必要な集合は何でも入っている（要素として含んでいる）集合です。

グロタンディーク宇宙 $`U`$ を特徴づける性質は次の2つです。

  1. $`U`$ は、所属関係 $`\in`$ に関して推移的な集合である。
  2. $`U`$ は幾つかの演算に関して閉じた集合である。

所属関係に関して推移的〈transitive〉とは次のことです。

$`\quad \forall x, y.(\, x\in U \land y\in x \Imp y \in U\,)`$

言い方を変えれば：

$`\quad \forall x.(\, x\in U \Imp x \subseteq U \,)`$

つまり、ある集合 $`x`$ が $`U`$ の要素なら、$`x`$ は $`U`$ の部分集合になっているということです。

二番目の条件に出てくる「幾つかの演算」とは、具体的には次の演算です。

  1. $`U`$ の2つの要素（要素は集合）から、順序なしペアを作る演算
  2. $`U`$ の要素から、そのベキ集合を作る演算
  3. $`U`$ の要素の族〈ファミリー〉から、族の合併を作る演算

それぞれの演算を $`\mrm{UnordPair}, \mrm{Pow}, \mrm{Union}`$ という名前で呼ぶことにすると、$`\mrm{UnordPair}`$ は二項演算、$`\mrm{Pow}`$ は単項演算です。

$`\quad \mrm{UnordPair} : U^\bar{2} \to U \In \mbf{SET}\\
\quad \mrm{Pow} : U^\bar{1} \to U \In \mbf{SET}
`$

ここで、$`\mbf{SET}`$ は、$`U`$ をひとつの対象として持つ十分に大きな集合圏です。

ひとつの台集合と、その上の幾つかのn項演算からなる構造は、代数系〈代数構造〉です。例えば、ひとつの台集合の上に、足し算、ゼロ元（足し算の単位元）、反元（足し算の逆元）を対応させる写像、掛け算、単位元を持つような代数系に環〈ring〉があります。

グロタンディーク宇宙も、推移性を持つような台集合の上に、順序なしペア、ベキ集合、合併の演算が載った代数系と考えることができます。ただし、合併は項数が決まってなくて、可変項数の演算になっています。

族の合併演算

先に述べたように、項数とは集合だと考えます*2。$`A`$ を項数（実体は集合）の集合だとします。台集合が $`X`$ である可変項数の演算のプロファイルは次のように書けます。

$`\quad (\sum_{\alpha \in A} X^\alpha) \to X \In \mbf{Set}`$

指数記法は関数集合を表すので、次のように書いても同じです。

$`\quad (\sum_{\alpha \in A} \mrm{Map}(\alpha, X) ) \to X \In \mbf{Set}`$

グロタンディーク宇宙の場合、「$`U`$ の要素の族〈ファミリー〉」とは、次の形の関数のことです。

$`\quad f: \alpha \to U \In \mbf{SET}\\
\text{i.e. } f\in \mrm{Map}(\alpha, U)
`$

$`U`$ は“巨大な集合”なので、それを収めるために十分に大きな集合圏 $`\mbf{SET}`$ を考えています*3。

$`\alpha`$ は族〈ファミリー）のインデキシング集合です。インデキシング集合を色々動かして寄せ集めると、可変項数の演算の域〈ドメイン）になるので、族の合併演算は次のプロファイルを持ちます。

$`\quad \mrm{Union} : (\sum_{\alpha \in A}\mrm{Map}(\alpha, U) ) \to U \In \mbf{SET}`$

項数（である集合）の集合 $`A`$ は、許されるインデキシング集合の集合です。グロタンディーク宇宙の場合、$`U`$ の要素（である集合）はすべてインデキシング集合として許すので、$`\mrm{Union}`$ のプロファイルは次のようになります。

$`\quad \mrm{Union} : (\sum_{\alpha \in U}\mrm{Map}(\alpha, U) ) \to U \In \mbf{SET}`$

$`U`$ の要素である特定の集合 $`x\in U`$ に関しては、合併は“$`x`$項演算”になります。

$`\quad \mrm{Union}_x : \mrm{Map}(x, U) \to U \In \mbf{SET}`$

例えば、$`x = \bar{2}`$ ならば、2つの集合を合併するニ項演算になります。

$`\quad \mrm{Union}_{\bar{2}} : \mrm{Map}(\bar{2}, U) \to U \In \mbf{SET}`$

代数系としてのグロタンディーク宇宙

ZF集合論のなかで考えたグロタンディーク宇宙は、巨大な集合ではありますが、構造としては代数系です。所属関係に関して推移的な台集合 $`U`$ と、その上の3つの演算により代数構造が定義されます。

  1. 二項演算 $`\mrm{UnordPair} : U^\bar{2} \to U \In \mbf{SET}`$
  2. 単項演算 $`\mrm{Pow} : U^\bar{1} \to U \In \mbf{SET}`$
  3. 可変項演算 $`\mrm{Union} : (\sum_{\alpha \in U} U^\alpha) \to U \In \mbf{SET}`$

これらの演算達が満たすべき法則は、$`U`$ がZF集合論のモデルになっていることです。このことについては、次の過去記事で書いています。

*1:今でも使う言葉なのだろうか？ 僕は、C言語のトリッキーなマクロを連想するけど。「さよなら varargs.h」参照。

*2:自然数も、ノイマン流に定義すれば集合です。だから、項数とは最初から集合であり、「集合ではない項数」なんてあり得ない、というのが実情です。

*3:$`\mbf{SET}`$ 内で考えた関数集合は、全部大文字で $`\mrm{MAP}`$ とか書いたほうが正確ですが、横着しています。