デジタル・ノルム付き集合と列挙

「ノルム付き集合」の続きです。ある条件を課したノルム付き集合に対する列挙の定義を与えます。列挙アルゴリズムは述べていません。

内容：

デジタルなノルム付き集合

「ノルム付き集合」では、一般的な設定でノルム付き集合を定義しました。この定義を少し制限することにします。ノルム付き集合 (A, Z, ν) が次の条件を満たすとき、デジタルなノルム付き集合と呼ぶことにします。

1. ノルムの値は有限な（非負の）整数である。
2. 任意の非負整数kに対して、{a∈A | ν(a) ≦ k} は有限集合である。

この条件から、ノルムが値をとる集合を、P_∞からNに置き換えることができます。ここで、Nは非負整数の集合 N = {0, 1, 2, ...} です。

以下では、出てくるノルム付き集合はすべてデジタルなものだと仮定します。導入する概念は、一般的なノルム付き集合でも通用するものもありますが、ここではデジタルなノルム付き集合の範囲で考えます。

ノルム球面とノルム球体

ノルム付きベクトル空間の場合、ノルムによる球面と球体を定義することができます。同様なことをノルム付き集合に対しても考えましょう。「球」という感じはあまりしないのですが、まーいいとしましょう。

Aはノルム付き集合（デジタルなものです）として、kを非負整数だとして、Aのk-ノルム球面とk-ノルム球体を次のように定義します。

• {a∈A | ν(a) = k}
• {a∈A | ν(a) ≦ k}

正確に言うと、{a∈A | ν(a) ≦ k} は閉じたノルム球体です。開いたk-ノルム球体は {a∈A | ν(a) ＜ k} と、イコールなしの不等号で定義されます。デジタルな（離散的）ノルムの場合は、開いたk-ノルム球体は閉じた(k-1)-ノルム球体と同じになります。

記述を簡略にするために、次の記法を導入します。

1. A[= k] := {a∈A | ν(a) = k}
2. A[≦ k] := {a∈A | ν(a) ≦ k}
3. A[＜ k] := {a∈A | ν(a) ＜ k}

それぞれ、ノルム付き集合Aの、k-ノルム球面、閉じたk-ノルム球体、開いたk-ノルム球体です。ノルム付き集合の定義から、Zero(A) = A[= 0] = A[≦ 0] です。A[＜ 0] は空集合です。便宜上、A[＜ ∞] という書き方も許してA全体を表すことにすると便利です。

体積関数と表面積関数

Aはノルム付き集合として、Aの体積関数V_Aを定義しましょう。与えられた半径の球体の体積みたいな量を与える関数が体積関数です。具体的な定義は次のようになります。cardは集合の基数（cardinality）です。

• V_A(k) := card(A[≦ k])

デジタルなノルム付き集合の定義から、card(A[≦ k]) は常に有限な正整数なので、V_A:N→N となります。k ≦ k' ならば A[≦ k] ⊆ A[≦ k'] なので、体積関数V_Aは、単調増加（正確には非減少）関数です。

Nを、(N, {0}, λk.k) としてノルム付き集合と考えることができます。このノルム付き集合Nの体積関数V_Nは次のようになります。

• V_N(k) = k + 1

直積集合 N×N もノルム付き集合にできますが、ノルムの入れ方は一意的ではなくて、選んだノルムにより体積関数も変わります。直積や直和に適当なノルムを入れて、その体積関数を計算することは、組み合わせ的な練習問題になります。

Aのノルム球面の表面積みたいな量を与える関数S_Aを次のように定義します。

• S_A(k) := V_A(k) - V_A(k - 1)

S_A(k)がAの表面積関数です。この定義から、次も成立します。

• V_A(k) = S_A(0) + S_A(1) + ... + S_A(k)

V_A(k)が0になることはありませんが、S_A(k)が0になることはあります。

列挙の定義

ノルム付き集合Aに対する列挙とは、Aの要素をノルムが小さい順に全部数え上げる操作です。この操作を、ある程度はフォーマルに定義していきます。

非負整数nに対して、Range(n) = {k∈N | k ＜ n} と定義します。Range(n) = {0, 1, ..., n-1} ですね。n自体はRange(n)に入ってない点に注意してください。Range(0)は空集合になります。for (i = 0; i < n; i++) という、よくあるfor文の変数iが走る範囲がRange(n)です。nとして∞も許すとして、Range(∞) = N とします。

適当なn（n = ∞ でもよい）に対するRange(n)からノルム付き集合Aへの写像fが次の条件を満たすとき、列挙（enumeration）と呼びます。

1. f:Range(n)→A は、集合のあいだの写像として全単射である。
2. i, i'∈Range(n)、i ＜ i' ならば、ν(f(i)) ≦ ν(f(i'))

fが全単射であることから、card(A) = n です。これは n = ∞ のケースも含むので、Aは無限集合でもかまいません。が、可算無限を超える基数は持てません。

二番目の条件から、fの定義域の要素を番号だと思うと、番号が増えると値のノルムもだんだんに増えます。正確に言えば「番号が増えるのに、ノルムが減ることはない」です。ν(f(i)) = ν(f(i+1)) のように、ノルムは停滞してもかまいません。

与えられたノルム付き集合Aに対して、列挙が一意的に決まるわけではなくて、たくさんの列挙が存在するでしょう。それらの列挙に理論的な優劣はありません。状況に応じて、使いやすい／作りやすい列挙を構成するばよいのです。

ニ変数関数としての列挙

fがノルム付き集合の列挙のとき、fは1つの非負整数変数を取りますが、F(k, i) というニ変数の関数を考えることも有効です。ニ変数関数Fは次の特徴を持ちます。

1. kを固定した λi.F(k, i) は、Range(n)→A[≦ k] の列挙となっている。
2. F(k, i) と F(k', i) が定義されているなら、F(k, i) = F(k', i)

Fは二変数なので、N×N 上で定義されますが、全域関数ではなく部分関数です。car(A[≦ k]) = n = V_A(k) なので、kを固定した λi.F(k, i) に定義域（iの動ける範囲）は、0 ≦ i ＜ V_A(k) となります。つまり、Fの定義域は次の形に書けます。

• {0}×Range(V_A(0)) + {1}×Range(V_A(1)) + ... + {k}×Range(V_A(k)) + ...

無限の直和を総和記号Σで書けば：

• Σ(k∈N : {k}×Range(V_A(k)))

一変数の列挙 f(i) を得たいときは、(k, i) がFの定義域となるようなkを選んで、f(i) := F(k, i) とします。kとk'が異なっても F(k, i) = F(k', i) であることから、f(i) はkの選び方によらずwell-definedです。

fとFは本質的に同じものなので、わざわざ二変数のFを考えるのは無駄なようですが、実際の列挙を構成するときは、二変数のFのほうが扱いやすいように感じます。

まだ足りないこと

列挙の定義から、Aのノルム球面A[= k]に対する列挙 Range(S_A(k))→A[= k] を、k = 0, 1, ... に対して積み上げていけば、A全体の列挙ができ上がることがわかります。ノルム球面上では、ノルムの大小がないので、Range(S_A(k))→A[= k] という全単射なら何でも列挙になります。

全単射なら何でもいいのですが、「何でもいい」は難しいのです。ノルム球面の列挙を与えることは、ノルム球面に線形順序を与えることと同じです。各ノルム球面上に線形順序があれば、ノルムの大小と組み合わせて、A全体に線形順序が入ります。

結局、ノルム付き集合Aの列挙の問題は、A上に、ノルムの大小と協調した線形順序を入れる問題になります。「何でもいい」では具体性がないので、ノルム付き集合の構成法に沿って、帰納的に「列挙＝線形順序」を構成する具体的な方法が必要です。これについては、またいずれ。