ノルム付き集合

ソフトウェアテスト用データの全数生成について考えたりしています。多くの場合、事実上無限個（膨大な数）のデータが必要なので、「全数」とはいっても、どこかで生成をあきらめることになります。あきらめるタイミングの目安、物差しとなる量が必要です。そのような量をノルムと呼ぶことにします。

内容：

1. ノルムとノルム付き集合
2. ノルム付き集合の例
3. 準同型射
4. 直和と直積
5. リフトと順序付き直和

ノルムとノルム付き集合

これから述べるノルムは、ノルム付きベクトル空間（normed vector space）のノルムと類似のものです。しかし、台集合（underlying set）に代数構造は仮定しません。単なる集合にノルムを持たせます。ただし、零という概念は考えます。

Aを集合として、ZはAの部分集合だとします。そして、次の条件を仮定します。

1. Zは空ではない。（したがって、Aも空ではない）
2. Zは有限集合である。

P_∞を、非負の実数に∞を付け足した集合とします。つまり、P_∞ := {x∈R | x ≧ 0} ∪ {∞} 。ν（ヴイじゃなくてギリシャ文字のニュー）は、A→P_∞ という関数だとして、次の条件を満たすときノルムと呼ぶことにします。

• z∈Z ⇔ ν(z) = 0

Zに属する要素を零と呼ぶことにすれば、「zが零であること」と「zのノルムが0であること」が同値です。これ以外には特に条件はありません。3つ組 (A, Z, ν) をノルム付き集合だと定義します。

[追記]「Zが有限」という条件は、後で定義することになるデジタルなケース（http://d.hatena.ne.jp/m-hiyama/20121015/1350259789）を先取りしていた感じです。一般論では邪魔になる条件かもしれません。[/追記]

ノルム付き集合の例

Aが単元集合、例えば A = {0} とすると、零の集合Zは空ではないので、Z = A = {0} となります。これと、「z∈Z ⇔ ν(z) = 0」から、ν(0) = 0 が出ます。単元集合上のノルムは一意的に決まってしまい、それは唯一の要素に値0を対応付けるものです。

Rの絶対値、より一般にはノルム付きベクトル空間のノルムは、今ここで定義した意味のノルムになっています。零の集合Zは、ベクトル空間の零からなる単元集合 {0} です。

Σを文字（と呼ばれる記号）の集合として、A = Σ^*（上付き星はクリーネスター）、Z = {ε}（イプシロンは空列）とします。文字列の長さをνとすると、(A, Z, ν) はノルム付き集合となります。

Gを有向グラフ、A = Node(G) をGの頂点集合とします。空ではない有限集合 Z⊆A を適当に選びます。任意の頂点 a∈A に対して、ν(a)を次のように定義しましょう。

• ν(a) = (aとZに属する頂点を結ぶ経路の長さで最小の値、そのような経路がないなら∞)

すると、(A, Z, ν) はノルム付き集合となります。文字列の集合と長さの例も、有向グラフの例に帰着できます（考えてみてください）。

準同型射

ノルム付き集合 (A, Z, ν) を、必要なら (A, Z_A, ν_A) とも書いて、単にAだけで (A, Z_A, ν_A) という構造を表すことにします。また、Zero(A) := Z_A、norm(A) := ν_A とも書きます。

AとBがノルム付き集合のとき、集合のあいだの写像 f:A→B が次の条件を満たすとき、ノルム付き集合の準同型射とします。

• z∈Z_A ならば、f(z)∈Z_B

零を零に写すということです。これ以外に、ν(f(x))≦ν(x) （縮小性、より正確には非増加性）とか、適当な定数Cに対する ν(f(x))≦Cν(x) を仮定することもあります。とりあえずは、ノルムの評価条件は課さないことにします。2つのノルム付き集合の同型も、互いに逆な準同型射で結ばれることで定義されます。

直和と直積

AとBがノルム付き集合のとき、台集合の直和 A + B の上に、A, Bそれぞれのノルムを載せると、新しいノルム付き集合ができます。零の集合は、Zero(A + B) := Zero(A) + Zero(B) です。こうして定義した A + B を、ノルム付き集合AとBの直和と呼びます。

同様に、台集合の直積 A×B 上にノルム付き集合の構造を定義できます。Zero(A×B) := Zero(A)×Zero(B) と定義します。しかし、A×B上のノルム norm(A×B) は、一意的に決まるものではありません。ν = ν_A×B = norm(A×B) の候補としては、例えば次があります。

1. ν(a, b) = max(ν_A(a), ν_B(a))
2. ν(a, b) = ν_A(a) + ν_B(a)

A×B上のノルムの定義は用途により選べばよいのですが、テストデータの文脈では、ν(a) + ν(a) を使うことが多くなりそうです。（[追記]いや、そうでもない。maxノルムのほうが便利なことがあります。[/追記]）A×B上に適切なノルムを入れた集合は、2つのノルム付き集合の直積と呼びます。

リフトと順序付き直和

A = (A, Z, ν) をノルム付き集合として、Aのリフトという構成法を考えます。⊥をAに含まれない要素として、集合の直和 A' := {⊥} + A を作って、これを台集合にします。A'上の新しいノルムν'は次のように定義します。

1. ν'(⊥) = 0
2. ν'(a) = ν(a) + 1 （a∈A）

定数1には特に意味がなくて、正実数ならなんでもいいのですけど、なんでもいいなら1でよかろうということです。零の集合は、Z' = {⊥} として、(A', Z', ν') を作るとこれはノルム付き集合となります。(A', Z', ν') を、元の (A, Z, ν) のリフトと呼びしょう。ノルムの値を1だけ下駄をはかせたことになります。

リフトの一般化として、直和に似ているが順序に依存する構成法を導入します。AとBがノルム付き集合として、A +< B を次のように定義します。

1. 台集合は、集合の直和 A + B。
2. 零の集合は Zero(A)。
3. 新しいノルムをν'とすると、ν'(a) = ν_A(a) （a∈A）、ν'(b) = ν_B(b) + 1 （b∈B）。

この定義をちゃんと示すには、台集合と構造全体を同じ記号で表すと混乱するので、構造Aの台集合を U(A) と書くことにします。この記法を使ってもう一度書くと：

1. U(A +< B) := U(A) + U(B)
2. Zro(A +< B) := Zero(A)
3. norm(A +< B) := U(A)上では norm(A)、U(B)では (norm(B) + 1)

ノルム付き集合の列 A₀, A₁, A₂, ..., A_n があったとき、これらの順序付き直和は次のように定義できます。

1. U(A₀ +< ... +< A_n) := U(A₀) + ... + U(A_n)
2. Zro(A₀ +< ... +< A_n) := Zero(A₀)
3. norm(A₀ +< ... +< A_n) := U(A₀)上では norm(A₀)、i = 1, ..., n に対してU(A_i)では (norm(A_i) + i)

A₀ が単元集合のときの順序付き直和がリフトになります。

それから

準同型射の定義に、今回はノルムの量的評価を入れてませんが、それが必要なときもあります。与えられたノルムを変形することもあります。例えば、ノルムに正実数を掛け算して新しノルムを作れます。

有限個のノルム付き集合に対する直和、直積、順序付き直和を扱いましたが、無限個のノルム付き集合をもとにした構成も使います。ただし、単純に「有限→無限」としてもうまくいかないので、工夫が必要です。

データの生成のときは、ノルム付き集合の要素をノルムが小さい順に列挙していきます。「ノルムが小さい順」が線形順序になるわけではないので、ノルムと協調した列挙のアルゴリズムを考える必要があります。「プログラミング課題：第一象限の格子点をたどる」は、これに関係した話です。