零項演算とは何か？ - 檜山正幸のキマイラ飼育記 (はてなBlog)

セミナーで受けた質問シリーズ(なのか？)、その3：過去に何度も聞かれたことがある一般的な質問；数の足し算・掛け算、集合の合併・共通部分などの演算に対して、オペランド（演算すべき対象物）が一つもないときどうなるのか？

内容：

オペランドが一つもないとき
リストの連接から考える
集合演算の定義から直接導く
順序集合の上限と下限

オペランドが一つもないとき

幾つかの数 a₁, a₂, ..., a_n を全部足し算すること（あるいはその結果である総和）を次のように書きます。

$\sum_{i = 1}^{n} a_i$

a₁, a₂, ..., a_n を全部掛け算するなら：

$\prod_{i = 1}^{n} a_i$

幾つかの集合 A₁, A₂, ..., A_n を全部合併することは次のように書きます。

$\bigcup_{i = 1}^{n} A_i$

A₁, A₂, ..., A_n 達すべての共通部分なら：

$\bigcap_{i = 1}^{n} A_i$

これらは、数や集合のリストに対する演算と思えるので、次のように書いてもいいでしょう。

$\sum (a_1, a_2, \cdots, a_n)$
$\prod (a_1, a_2, \cdots, a_n)$
$\bigcup (A_1, A_2, \cdots, a_n)$
$\bigcap (A_1, A_2, \cdots, a_n)$

n = 2 の場合は：

$\sum (a_1, a_2) = a_1 + a_2$
$\prod (a_1, a_2) = a_1 \times a_2$
$\bigcup (A_1, A_2) = A_1 \cup A_2$
$\bigcap (A_1, A_2) = A_1 \cap A_2$

n = 1 の場合は次でいいでしょう。

$\sum (a_1) = a_1$
$\prod (a_1) = a_1$
$\bigcup (A_1) = A_1$
$\bigcap (A_1) = A_1$

さて、n = 0 の場合はどうなるのでしょうか？

$\sum () = ?$
$\prod () = ?$
$\bigcup () = ?$
$\bigcap () = ?$

[補足]
ここで言っている零項演算は、最初に二項演算があり、その二項演算から作ったn項演算において、n = 0 としたものです。つまり、「二項演算ありき」の状況設定です。二項演算がなくて、いきなり集合X上の零項演算〈無項演算 | nullary operation〉と言った場合は、X⁰→X という写像のことです。集合Xの零乗は単元集合なので、1→X となり、（いきなりの）零項演算はXの特定要素と同一視できます。例えば、付点集合〈poited set〉は、零項演算〈無項演算〉をひとつ備えた構造になります。
[/補足]

リストの連接から考える

2つのリスト (a₁, ..., a_n), (b₁, ..., b_m) に対してその連接〈concatenation〉を次のように定義します。

(a₁, ..., a_n) # (b₁, ..., b_m) := (a₁, ..., a_n, b₁, ..., b_m)

'#'が連接演算の演算子記号です。連接の単位元〈中立元〉は空リスト () になります。

() # (a₁, ..., a_n) = (a₁, ..., a_n)
(a₁, ..., a_n) # () = (a₁, ..., a_n)

リストは太字で書くことにすれば、

() # a = a
a # () = a

前節の「リストの要素全部をナニカする」演算と、リストの連接には次の関係があります。

$\sum ({\bf a} \;\#\; {\bf b}) = \sum {\bf a} \,+\, \sum {\bf b}$
$\prod ({\bf a} \;\#\; {\bf b}) = \prod {\bf a} \,\times\, \prod {\bf b}$
$\bigcup ({\bf A} \;\#\; {\bf B}) = \bigcup {\bf A} \,\cup\, \bigcup {\bf A}$
$\bigcap ({\bf A} \;\#\; {\bf B}) = \bigcap {\bf A} \,\cap\, \bigcap {\bf A}$

足し算に関して、連接の片側を空リストに置いてみると：

$\sum {\bf a} = \sum (() \;\#\; {\bf a}) = \sum () \,+\, \sum {\bf a}$
$\sum {\bf a} = \sum ({\bf a} \;\#\; ()) = \sum {\bf a} \,+\, \sum ()$

これより、 $\sum ()$ は足し算の単位元〈中立元 | 零元〉でなければならないことが分かります。足し算以外も同様で：

$\sum () = 0$
$\prod () = 1$
$\bigcup () = \emptyset$
$\bigcap () = X$

ここで、Xは部分集合の親となる全体集合です。

集合演算の定義から直接導く

集合演算の場合は、その定義から直接に零項演算の結果が何であるかが分かります。

Iをインデックスセットとします。I = {1, 2, ..., n} だと思ってもかまいません。Iでインデックス付けられた集合族〈I-indexed family of sets〉の合併と共通部分は、次の論理同値で定義されます：

$\mbox{For} \;x \in X,\: (x \in \bigcup_{i \in I} A_i) \:\Leftrightarrow\: \exists k \in I.(x \in A_k)$
$\mbox{For} \;x \in X,\: (x \in \bigcap_{i \in I} A_i) \:\Leftrightarrow\: \forall k \in I.(x \in A_k)$

ここで、インデックスセットIを空集合に置いてみると：

$\mbox{For} \;x \in X,\: (x \in \bigcup_{i \in \emptyset} A_i) \:\Leftrightarrow\: \exists k \in \emptyset.(x \in A_k)$
$\mbox{For} \;x \in X,\: (x \in \bigcap_{i \in \emptyset} A_i) \:\Leftrightarrow\: \forall k \in \emptyset.(x \in A_k)$

「i∈ $\emptyset$ に対する A_i」が不思議ですが、空集合をインデックスセットとするような部分集合の族は（ただ一つだけ）存在し、それがAなのです -- Aは空リストのことだと思ってもいいです。さて、上記の同値の右側の条件を変型すると：

$\mbox{For} \;x \in X,\: \exists k \in \emptyset.(x \in A_k) \:\Leftrightarrow\: \exists k.(k \in \emptyset \land x \in A_k)$
$\mbox{For} \;x \in X,\: \forall k \in \emptyset.(x \in A_k) \:\Leftrightarrow\: \forall k.(k \in \emptyset \Rightarrow x \in A_k)$

$k \in \emptyset$ は偽ですから：

$\mbox{For} \;x \in X,\: \exists k.(k \in \emptyset \land x \in A_k) \:\Leftrightarrow\: \exists k.(False \land x \in A_k) \:\Leftrightarrow\: False$
$\mbox{For} \;x \in X,\: \forall k.(k \in \emptyset \Rightarrow x \in A_k) \:\Leftrightarrow\: \forall k.(False \Rightarrow x \in A_k) \:\Leftrightarrow\: True$

下側（二番目）の同値では、含意の前件（左側）が偽なら含意命題は問答無用に真になることを使っています。

以上より：

$\mbox{For} \;x \in X,\: (x \in \bigcup_{i \in \emptyset} A_i) \:\Leftrightarrow\: False$
$\mbox{For} \;x \in X,\: (x \in \bigcap_{i \in \emptyset} A_i) \:\Leftrightarrow\: True$

つまり、次が言えます。

$\forall x \in X.(x \notin \bigcup_{i \in \emptyset} A_i)$
$\forall x \in X.(x \in \bigcap_{i \in \emptyset} A_i)$

結局：

$\bigcup_{i \in \emptyset} A_i = \emptyset$
$\bigcap_{i \in \emptyset} A_i = X$

順序集合の上限と下限

前節の議論を、少し別な観点から見てみましょう。インデックスセットIでインデックス付けられたXの部分集合族〈I-indexed family of subsets of X〉Aは、A:I→Pow(X) という写像のことです（Pow(X)はXのベキ集合）。

写像Aが単射の場合は、写像Aの代わりにその像集合

{S∈Pow(X) | S = A_i （A_i = A(i)）となる i∈I が在る}

を考えても同じことです。また、部分集合族の表現として、単射な写像を選ぶことができるので、「Iでインデックス付けられたXの部分集合族 ←→ Pow(X)の部分集合」という相互変換（1：1ではない*1）が出来ます。

話を一般化して、ベキ集合Pow(X)とは限らない順序集合 L = (L, ≦) を考えます。Lの部分集合Aに対して、Aの上限〈supremum | 最小上界 | least upper bound〉とAの下限〈infimum | 最大下界 | greatest lower bound〉を定義しましょう。

a∈L が A⊆L の上限だとは、aが次の条件を満たすことです。

x∈A ならば x ≦ a
「x∈A ならば x ≦ b」となるbに対して、a ≦ b

下限の定義は順序関係をひっくり返すだけです。aがAの下限だとは：

x∈A ならば a ≦ x
「x∈A ならば x ≦ b」となるbに対して、b ≦ a

勝手に選んだAに対して上限・下限が存在することは（一般には）保証されませんが、在るならそれらを sup(A), inf(A) と書きます。

さて、空集合 $\emptyset$ に対して sup( $\emptyset$ ), inf( $\emptyset$ ) が在るとして、それはどんなものでしょうか？上限の定義のAのところに $\emptyset$ を入れると：

x∈ $\emptyset$ ならば x ≦ a
「x∈ $\emptyset$ ならば x ≦ b」となるbに対して、a ≦ b

一番目の条件は常に真（前件が偽だから）なので、二番目だけ考えればいいですね。二番目の条件内の「x∈ $\emptyset$ ならば x ≦ b」も常に真なので、bに関する縛りは何もなくなって：

任意のbに対して、a ≦ b

論理式で書くなら：

∀b∈L.(a ≦ b)

これは a = sup( $\emptyset$ ) がLの最小元〈least element〉であることを意味します。同様に、inf( $\emptyset$ ) はLの最大元〈greatest element〉になります。

sup( $\emptyset$ ) = least(L)
inf( $\emptyset$ ) = greatest(L)

(L, ≦) として (Pow(X), ⊆) を取ったときは：

sup( $\emptyset$ ) = least(Pow(X)) = $\emptyset$
inf( $\emptyset$ ) = greatest(Pow(X)) = X

ここで、 $\emptyset$ が、 $\emptyset$ ⊆Pow(X) と $\emptyset$ ⊆X の意味で登場することに注意してください。

前節の話との関連性は：

$sup(\emptyset) = \bigcup_{i \in \emptyset} A_i$
$inf(\emptyset) = \bigcap_{i \in \emptyset} A_i$

*1:インデキシングの写像を全射・単射に分解して、その単射部分を取り出せば、像集合と同一視できます。