データ領域 (A26)

RSS練習問題

※この記事は「記事26」

プログラムで扱うデータの集合について述べます。ひとつ前の記事は読んでいるものとします。

内容：

高々可算集合

有限集合または可算無限集合を高々可算集合〈at most countable set〉といいます。「可算集合」を「高々可算集合」の意味で使う人もいます（檜山も、口頭では「可算集合＝高々可算集合」です）。高々可算集合の基本的な性質：

  1. 有限集合は高々可算集合である。（定義より明らかだけど。）
  2. Nは高々可算集合である。（定義より明らかだけど。）
  3. A, B が高々可算集合のとき A×B（集合の直積）も高々可算集合である。
  4. A1, A2, ..., An が高々可算集合のとき A1×A2×...×An（集合の直積）も高々可算集合である。（すぐ上の一般化）
  5. Aが高々可算集合、B⊆A のとき、Bも高々可算集合である。

さらに次も言えます。

  1. A, B が高々可算集合のとき A + B（集合の直和）も高々可算集合である。
  2. A1, A2, ..., An が高々可算集合のとき A1 + A2 + ... + An（集合の直和）も高々可算集合である。
  3. A1, A2, ..., （無限列） のAiが高々可算集合のとき A1 + A2 + ... （無限和）も高々可算集合である。
  4. A1 ⊆ A2 ⊆ ..., （増加する無限列） のAiが高々可算集合のとき \bigcup_{i=1}^{\infty} A_i も高々可算集合である。

これらを精密化した結果を次節で述べます。

列挙子付き集合

n∈N に対して、次の定義をしておきます。

  • N[n] := {k∈N | k < n}

不等号にイコールがないことに注意してください。N[n]は、区間記法では [0, n) と書けますが、実数区間ではないので区間記法は使いません。

  • N[0] = {} = ∅ = 0
  • N[1] = {0} = 1
  • N[2] = {0, 1} = 2 = B （Bは「ブーリアン」から）
  • N[3] = {0, 1, 2}
  • ...

記号'∞' に対しては、

  • N[∞] := N

とします。

集合Xがあり、適当なn（n = ∞ も認める）に対する f:N[n]→X が全単射のとき、fをXの列挙子〈enumerator | iterator〉または列挙関数〈enumerating function〉と呼びます。全単射ではなくても、全射であれば十分ですが、議論が面倒になるので全単射を要求しておきます。全単射の要求がかえって邪魔になることもあります（一長一短）。集合の基数の定義から、列挙子を持つ集合は高々可算無限集合です。

集合Xとその列挙子fの組 (X, f) を列挙子付き集合〈set with enumerator〉と呼びます。列挙子付き集合から新しい列挙子付き集合を構成できます。以下に出てくる「述語」は、述語記号ではなくて、述語関数＝値が二値であるほんとの関数のことです。

  1. 有限集合は列挙子を持つ（列挙子を具体的に作れる）。
  2. Nは列挙子を持つ。id:N→N を標準的列挙子とする。
  3. (A, f), (B, g) が列挙子付き集合のとき A×B（集合の直積）は列挙子を持つ。
  4. (A1, f1), (A2, f2), ..., (An, fn) が列挙子付き算集合のとき A1×A2×...×An（集合の直積）も列挙子を持つ。
  5. (A, f) が列挙子付き集合、B⊆A かつ B を定義するA上の全域述語があるとき、Bは列挙子を持つ。

また：

  1. (A f), (B, g) が列挙子付き集合のとき A + B（集合の直和）も列挙子を持つ。
  2. (A1, f1), (A2, f2), ..., (An, fn) が列挙子付き集合のとき A1 + A2 + ... + An（集合の直和）も列挙子を持つ。
  3. (A1, f1), (A2, f2), ..., （無限列） のAiが列挙子付き集合のとき A1 + A2 + ... （無限和）も列挙子を持つ。
  4. A1 ⊆ A2 ⊆ ..., （増加する無限列） のAiが列挙子付き集合で、Aiを定義するAi+1上の全域述語があるとき、 \bigcup_{i=1}^{\infty} A_i も列挙子を持つ。

新しく作った集合に対する列挙子の作り方は一意的ではありませんが、「こう作る」と決めれば、集合の構成法ごとに、列挙子付き集合を具体的に構成することが出来ます。

列挙子付き集合の別な見方

集合Aが可算無限集合のときは、列挙子付き集合を別な形で定義できます。特定の要素 i∈A と、写像 s:A→(A＼{i}) が指定されていて、sが可逆なとき、(A, i, s) をサクセッサ付き集合〈set with successor〉と呼びます。sをサクセッサ、sの逆写像 p:(A＼{i})→A をプレデセッサ〈predecessor〉と呼びます。

Aが有限集合のときは、終端記号'$'を追加してサクセッサを定義できます。

  1. s:A∪{$}→A∪{$}
  2. s($) = $ （終端記号の次はないのでループ、エラーにする案もある）

プレデセッサは、p:(A＼{i})∪{$}→A です。終端記号がある分、可逆性が歪んで複雑化しますが、無限集合のときと同様にサクセッサ付き有限集合を定義できます。

i∈A を要求しているので、サクセッサ付き集合は空ではありません。高々可算集合Aが空でない場合は、Aの列挙子とAのサクセッサは1：1に対応します。別な言い方をすると、列挙子付き集合とサクセッサ付き集合は同じとみなしてかまいません。

データ領域

データ領域に関する多少立ち入った議論をします。面倒なら、飛ばし読みでもいいです（読み飛ばし≠飛ばし読み）。

人やコンピュータが計算の対象にできるモノ（＝データ）全体の集合を計算的データ領域〈computational data domain〉、あるいはより短くデータ領域、さらにもっと短く領域とも呼びます。データ領域の定義は、目的により、好みにより、人により色々ありますが、ここでは、列挙子とタプリング写像を持つ集合として定義します。列挙子は既に述べました。

データ領域を単に集合として定義するのは無理で、プログラミングシステムの組み込み関数〈基本関数〉と共に定義することになります。データ領域は、プログラミングシステムと共にあるのです*1。

実用性を持つデータ領域／組み込み関数をチャンと定義するのは面倒（相互再帰的定義が山のように登場）なので、詳細は割愛して大雑把に述べます。

Dをデータ領域とすると、B = (二値の集合) = {0, 1} ⊆ D であり、システムに組み込みの全域述語（Bに値を持つ全域関数）がいくつか準備されているとします。組み込み述語から、プログラミング言語の手続き定義機能を使って新しい述語を定義できます。定義した述語手続き（名前付きプログラム）は、実行環境の上で実行して述語関数（数学的なB値部分関数）を定義します。

Dは可算無限集合として*2、Dの部分集合Xが、全域計算可能述語関数pにより

  • X = {x∈D | p(x) = 1}

と定義できるとき、計算的に確定する〈決定可能な〉部分集合〈computationally fullly-decidable subset〉 -- 長いので確定的部分集合〈decidable subset〉と呼びます。ほとんどの関数が計算可能ではないのと同様に、ほとんどの部分集合は確定的部分集合ではありません。データ領域の確定的部分集合は、プログラミング言語の“型”の領域として使えます。

さて、データ領域の条件として、タプリング写像を持っていることを要求します。これにより、n引数（n = 0, 1, 2, ...）のプログラムを一律に1引数のプログラムとして扱えます。タプリング写像の具体例は、この節の最後にあります。

タプリング写像〈tupling map〉とは、

  • t0:D0→D
  • t1:D1→D
  • t1:D2→D
  • t1:D3→D
  • 以下同様

という写像の列 t0, t1, t2, t3, ... で：

  1. すべての tkは、当該のプログラミングシステムの計算可能関数である。
  2. すべての tk:Dk→D が単射である。
  3. すべての tkの像集合 tk(Dk) は確定的部分集合である。
  4. tk(Dk) 上で定義されたk個の計算可能関数 πk, 1, πk, 2, ..., πk, k で、タプルの成分を取り出すことができる。写像 πk, i は、タプリング写像に対する射影〈projection〉と呼びます。

tk と πk, 1, πk, 2, ..., πk, k の関係は：

  • πk,i(tk(x1, x2, ..., xk)) = xi

簡略化のために次の記号を使います。

  • t0() = t0(()) = <>,
    t0(D0) = D<0>
  • t1(x) = t1((x)) = <x>,
    t1(D1) = D<1>
  • t2(x1, x2) = t2((x1, x2)) = <x1, x2>,
    t2(D2) = D<2>
  • t3(x1, x2, x3) = t3((x1, x2, x3)) = <x1, x2, x3>,
    t3(D3) = D<3>
  • 以下同様
タプリング写像と成分取り出し〈射影〉写像の例

D = N で、tk:Nk→N を以下の箇条書きのように定義します。piはi番目の素数、p1 = 2, p2 = 3, ... などとします。nを素因数分解したときの pi の肩に乗る指数を γi(n) で表します。0, 1以外のnは、n = p1γ1(n)×p2γ2(n)×...×pkγk(n) （γk(n) > 0）のように書けます。nごとにkは確定します。

  • t0() = <> := 0
  • tk(n1, ..., nk) = <n1, ..., nk> := p1n1 + 1×p2n2 + 1×...×pknk + 1
  • i ≦ k ⇒ γi(n) > 0 である素因数分解を持つ整数nはタプリングの像となっている。タプルの長さkは、素因数分解に現れた素数の個数により与えられる。
  • πk, i(n) := γi(n) - 1

次の関係があります。

πk, i(<n1, ..., nk>) = ni

データの検索

データ領域の部分集合Xで次の条件を満たすものを型領域〈type domain〉と呼ぶことにします。「型領域」は一般的な言葉ではありませんが、プログラミング言語のデータ型に相当する集合です。

  1. Xは確定的部分集合である。つまり、計算可能な全域述語関数でXへの所属（'∈'の真偽）を確実に判断できる。
  2. Xは列挙子fを持っている。したがって、(X, f) は列挙子付き集合になる。

型領域の定義より：

  1. データ領域D（全体集合）は型領域である。
  2. 空集合は型領域である。

現実のプログラミングでは意外と使われてないのですが：

  1. X, Y が型領域なら、X∩Y は型領域である（型領域にできる）。
  2. X, Y が型領域なら、X∪Y は型領域である（型領域にできる）。

X, Y に対して、

  • X\otimesY := t2(X×Y)

とすると、X\otimesY⊆D。集合としては、X\otimesY \stackrel{\sim}{=} X×Y。X\otimesY への所属を判定する全域述語と、列挙子を構成可能なので、X\otimesY も型領域になります。X\otimesY と X×Y は、気持ちの上では同一視してもかまいません。

我々のプログラミング言語と実行環境に、次の機能を要求します。

  • 型領域X上では全域である述語関数pに対して、Xの要素xで p(x) = 1 となるものを探すことができる。

上記の検索を行う構文を

  • find 変数 in 型領域 st (変数に関する論理式、述語を表す式)

とします。

例えば、D = N として Even⊆N は偶数の集合とします。このとき例えば、

  • find n in Even st n2 = 144

は、偶数のなかで144の平方根を探すものです。次も同様です。

  • find n in Even st n2 = 225

このような検索を可能とするために、データ領域と型領域に列挙子（またはサクセッサ）の存在を要求したのです。

上記のfind構文のプログラムは、最初に見つかったデータを値として出力します。例えば、

  • E("find n in Even st n2 = 144", ()) = 12
  • E("find n in Even st n2 ≧ 50", ()) = 8

データが見つからない場合は、永久に探し続けて無限走行します。

  • E("find n in Even st n2 = 225", ()) = ⊥

データ検索をするfindは、演算の組み合わせを超える唯一のプログラミング機能です。findは、存在限量子を計算的に実現するメカニズムです。超越的な（普通の）数学では、存在命題の真偽は神様のレベルで決まっていますが、計算的にはみつかるまで探すしかないのです。これが、超越的（普通の）真偽判定と、計算的（システムで実行する）真偽判定の大きな違いです。

*1:データ領域を単体・単独で定義はできません。他の集合や写像と一緒に、関係性によって定義されます。「生成系を持つ圏のなかで計算万能性を持つ対象」がデータ領域のモダンな定義です。

*2:データ領域Dが有限集合では、まともなプログラミングは出来ません。