2001年 8月15日 作成 「直積集合」 と 「写像集合」 >> 目次 (テーマごと)
2006年10月16日 補遺  



 ツェルメロ (Zermelo E.) は、「集合 (set、セット)」 の形を以下の公理を基底にして形成することを提示した。

     {x∈a|A(x)} .  [ これを 「分出公理」 という。]

 「分出公理」 を述語論理式を使って表現すれば、以下のようになる。

     ∀a∃ b∀x[(x∈b)←→(x∈a)∧A(x)].

 すなわち、(カントル の 「集合論の パラドックス」 を回避するために) 1つの部分集合を介在して、あまりに大きくならない集合 (a よりも小さい集合)を導入した。つまり、{x∈a|A(x)} は、集合a の部分集合である。
 しかし、「分出公理」 を使えば、{a,b} とか a∪b とかの集合族を導出できないので、他のいくつかの ルール を導入して、ひとつの公理系を提示した。この公理系を、通常、「ZF の公理系」 という。「ZF の公理系」 は以下の特徴をもつ。

 (1) 等号を含む第一階述語論理を使って形式化されている。
 (2) 9つの公理から構成される形式的 体系である。
 (3) ∈ 以外の述語を使わない。

 以上の公理を使って構成される集合は、以下の集合である (つまり、 どのような モノ が集合として考えられるか、ということである)。

 (1) 無限集合 (自然数全体を集合とする、ということ )
 (2) ベキ 集合 (1つの集合のなかの部分集合全体も集合とする、ということ)
 (3) 直積集合 (2つの集合の 直積 A×B も集合とする、ということ)
 (4) 写像集合 (集合 A から集合 B への写像 f の像全体 f (A) を集合とする、ということ)

 以上の集合のなかから、「写像集合」 を使って、アルゴリズム の構造 (いわゆる「構造化 プログラミング」 のひとつのやりかた、「ワーニエ・メソッド」) を体系化した人物が ワーニエ(Warnier J.D.) 氏であり、「直積集合」 を使って、(データ の構造および) セット・アット・ア・タイム 法を体系化した人物が コッド(Codd E.F.) 氏である。
 次回は、「属する」 と 「含む」 について述べる。□

 



[ 補遺 ] (2006年10月16日)

 「集合と論理」 は、コンピュータ・ソフトウェア に対して、多大な影響を与えている。
 「ベキ 集合 (power set、関数集合ともいう)」 は、集合 S のすべての部分集合からなる集合族のことをいい、(2値論理を前提にした) アルゴリズム では、いわゆる 「場合分け (手続き型言語で言えば、nested-IF として記述される論理) 」 として、2S の可能的様態が記述される。
 たとえば、敦と剛と大地がいっしょに遊ぶとして、3人が遊ぶ編成は、以下の 8通り (23) になる。

 {敦、剛、大地}、{敦、剛}、{敦、大地}、{剛、大地}、{敦}、{剛}、{大地}、{φ}。

 さて、ベキ 集合 2S にふくまれる集合の個数が、集合 S にふくまれる集合の個数に比べて大きいことに注意していただきたい。すなわち、ベキ 集合は、「巨大な集合」 を作ることができる。実は、この点が、以下に述べるように、「カントール の パラドックス」 を起こす原因になる。

 (1) 「すべての集合の集合」 U が U 自身をふくむとすれば、2U ⊆ U となる。

 (2) とすれば、2U にふくまれる集合の個数が U にふくまれる集合の個数に比べて小さいことになる。
    したがって、矛盾が生じる。

 この矛盾を回避するために、ツェルメロ は、「あまり巨大な集合」 を作らないように、「分出公理」 を導入したのである。しかし、「分出公理」 を使えば、{a,b} とか a∪b とかの集合族を導出できないので、ツェルメロ は、他のいくつかの ルール を導入して、ひとつの公理系 (ZF の公理系) を提示した。ZF の公理系で扱われる集合を 「セット (set)」 という。ただし、ZF の公理系では、「みずからをふくまない集合 (セット) の全体」 を考えることはしないが、クラス (class) 概念では、「みずからをふくまない集合の全体」 のクラスを考えることはできる。

 コッド は、ZF の公理系を前提にして、データ・モデル を考えた。ここでいう データ・モデル とは、{データ 構造、データ 演算、制約} の組をいう。コッド は、「直積集合」 を使ったが、小生は、(ZF の公理系を作った ツェルメロ が示している) 「選択公理」 を使ったほうが、tuple を説明しやすいと思っている。「選択公理」 とは、「空でない」 集合の族のそれぞれから 1つずつの メンバー を選ぶ関数 が存在するという公理である。単純に言い切ってしまえば、「それぞれの集合 (セット) から 1つずつ メンバー を選んできて、並べることができる (整列可能)」 ということである。

 以上の説明から すぐに想像できるように、「直積集合」 (あるいは、「選択公理」) を使えば、データ 構造上、以下の 2点が考慮されなければならない。

 (1) 「空でない」 という前提から、「null」 の扱いが論点になる。
 (2) 「整列可能」 という前提から、「並び」 が論点になる。

 コッド は、(1) では、4値論理を使い、(2) では、Relation として、「『並び』 を正確に実現できないので」、relationship という非学術用語を使ってもよいとした。

 ちなみに、コッド 関係 モデル を 「意味論的に拡張するために」、小生がT字形 ER手法を作る際に配慮したのは、以上の 2点であった。すなわち、データ構造では、2値論理のなかで、「null」 を除去する サブセット を考えて、「並び」 に関して、「event と resource」 概念を導入した。




  << もどる ベーシックス すすむ >>
  数学基礎論