2005年 9月 1日 作成 自己言及と複合定義域 >> 目次 (テーマ ごと)
2009年10月 1日 補遺  


 
2項関係

 集合 A および集合 B のあいだで、直積 A×B の部分集合 R を、A から B への 2項関係 (あるいは、単に、A から B への関係 [ relation ])といい、R: A → B というふうに記述する。そして、(a, b)∈ R であるとき、a と b は、関係 R にあるといい、aRb とも記述する。
 とくに、A から A 自身への関係を 「A の上の関係」 ともいう。

 
恒等関係

 R を A の上の 2項関係とする。R の ベキ 乗を、以下のように定義する。

 (1) R0 = idA = { (a, a) | a ∈ A }.
 (2) Rn+1 = Rn・R  { n = 0, 1, 2,・・・}.

 idA を、A の上の恒等関係という。

 
同値関係

 R を A の上の 2項関係とする。同値関係は、以下の 3つの性質を満たす 2項関係として定義される。

 (1) 反射律 (aRa)
 (2) 対称律 (aRb → bRa)
 (3) 推移律 (aRb ∧ bRc → aRc)

 
全関係、同値関係および恒等関係

 R = A × A は、A上の 2項関係である。これを、A 上の全関係ともいう。
 R は、同値関係であり、A/R = { A } である。
 また、A 上の恒等関係 {(a, a)| a ∈ A } は同値関係であり、A/R0 ={{a}| a ∈ A } である。

 
順序 (半順序)

 R を A 上の 2項関係とする。数の大小関係は、以下の 3つを満たす 2項関係である。

 (1) 反射律 (aRa)
 (2) 推移律 (aRb ∧ bRc → aRc)
 (3) 反対称律 (aRb ∧ bRa → a = b)

 反射的、推移的かつ反対称的である 2項関係を、半順序 (partial order) あるいは、単に、順序という。半順序は、「等号付きの不等号 (≦)」 の一般化である。

 
擬順序

 R を A 上の半順序とする。
 xRy において、x ≠ y を、xR’y とする。つまり、反射律が成立しない、とする (したがって、R’= R − idA)。
 xR’y において、以下が成り立つ。

 (1)’ 反-反射律 (aR’a は成立しない)
 (2)’ 推移律 (aR’b ∧ bR’c → aR’c)
 (3)’ 非対称律 (aR’b → bR’a)

 (1)’、(2)’および(3)’を満たす関係 R’を、擬順序という (ただし、R’を半順序といい、R を順序という人もいるので注意されたい)。

 擬順序 R’に対して、xR’y において、x = y であれば、xRy とする、というふうに定義すれば──R = R' ∨ idA とすれば──、前述した半順序が成立する。つまり、「等号 (=)」 をふくむかどうかの違いである──半順序は、「≦」 という 「等号付きの不等号」 を使い、擬順序は、「<」 という不等号を使う。

 
半順序集合

 半順序 (≦) として定義された集合のことを、半順序集合といい、(A, ≦) を使って記述する。
 A の メンバー { a, b } に対して、a ≦ b (あるいは、b ≦ a) が成立するとき、a と b は比較可能である、という。任意の 2つの メンバー が比較可能である半順序のことを、全順序 (total order) という (あるいは、線形順序ともいう)。

 集合のあいだに成立する包摂関係 (⊆) は、半順序である。
 ベキ 集合 (集合族) は、半順序である──そして、(2A, ⊆) は、半順序集合である。ただし、|A| ≧ 2 であれば──A の濃度 (メンバー の数) が 2以上であれば──、比較不能な部分集合があるので、⊆ は、2A 上の全順序ではない。

 
関係 データベース と n項関係

 コッド 関係 モデル では、n項関係が重視される──つまり、A1×A2×・・・An という直積が重視される。
 たとえば、以下を考えてみる──A1 を学生番号の セット、A2 を科目名の セット、A3 を合格判断の セット とする。

   A1 = { 001, 002 }.
   A2 = { 英語、数学、哲学 }.
   A3 = { 合格、不合格 }.

 そうすれば、A1、A2 および A3 の直積は以下のようになる。

 (001, 英語, 合格), (001, 英語, 不合格),
 (001, 数学, 合格), (001, 数学, 不合格),
 (001, 哲学, 合格), (001, 哲学, 不合格),
 (002, 英語, 合格), (002, 英語, 不合格),
 (002, 数学, 合格), (002, 数学, 不合格),
 (002, 哲学, 合格), (002, 哲学, 不合格)

 ( )のなかの値は、それぞれの セット から、ひとつずつ メンバー を選んで並べた組である。この組 (n-組) を「タプル (tuple)」という。

 そして、それらの部分集合 R として、以下が成り立つ、とする。

 R ={(001, 英語, 合格), (001, 数学, 合格), (001, 哲学, 不合格), (002, 数学, 合格)}.

 この部分集合を、関係 R という。
 なお、タプル のなかの属性値の並びは、半順序であるが、関係 R のなかの タプル には、順序付けはない。

 また、セット A1、A2 および A3 を、関係 R の属性値集合という。そして、関係 モデル では、属性値集合は、「単純 (simple)、原子的 (atomic)」 でなければならない、とされる。言い換えれば、「値の集合」 や、「構成された」 レコード であってはいけない、ということになる。つまり、属性値集合は、正規形として、単純定義域でなければならず、「集合を組とする」 構成 (複合定義域) であってはいけない、ということである。

 さて、たとえば、A1 を部品番号の セット とし、A2 を数量の セット とする。そして、A1上の 2項関係を考えてみる。すなわち、部品番号のあいだに、親子関係 (半順序) が成立する部品構成を考えてみる。

  A1={001, 002, ...}.
  A2={10, ...}.
  R ={((001, 002), 10), ((001, 003), 10),...}.

 関係 R において、たとえば、(001, 002) は、(親-部品番号、子-部品番号) という 「集合を組とする オブジェクト (組 オブジェクト)」 である。

 部品表番号を付与して、部品構成表のなかで、階数 (縦列の階) と次数 (横列の類) を考えて、以下のように、関係 R を作ることもできる。なお、A1 は部品構成表番号の セット であり、A2 は部品番号の セット であり、A3 は階数であり、A4 は次数であり、A5 を数量とする。

  A1={01, 02, ...}.
  A2={001, 002, ...}.
  A3={0, 1, 2, ...}.
  A4={0, 1, 2, ...}.
  A5={10, ...}.
  R ={(01, 001, 0, 0, 0), (01, 002, 1, 1, 10), (01, 003, 2, 1, 10)...}.

 そうすれば、部品構成表を、単純定義域として、テーブル 構成にすることはできる。(参考)
 しかし、自己言及的な セット (A の上の関係) では、半順序を意識した 「親子関係」 を考えるほうが──すなわち、n-項関係のなかで、2項関係として、「組 オブジェクト」 を考えたほうが──、データ を演算しやすいのではないか。そして、「組 オブジェクト」 を前提にした複合定義域では、それぞれの属性値集合は、「単純かつ原子的な」 構成ではない──つまり、「階層的な構成」 を作り、非正規形になる。{部品番号}のなかを、(親-部品番号、子-部品番号) として複合的に構成する。

 ただし、どの程度まで、この複合的構成を許すか、という点は、悩ましい論点にはなるが、、、。

 
(参考)

 これを、グラフ 理論の観点に立って考えれば──グラフ 上の巡回として考えれば──、(u, v)∈ E であるとき、u を v の 「親」 といい、v を u の 「子」 という。そして、(u, v1)∈ E かつ (u, v 2)∈ E のとき、v1 と v2 を 「兄弟」 である、という。
 グラフ 上を巡回する手順として、以下の 2つの基本法がある。

  (1) DFS (縦検索法)
  (2) BFS (横検索法)

 DFS は、「深さ」 優先検索法であって、v を起点にして、v の子、そして、v の子の子、というふうに親子関係を優先して巡回する やりかた である。いっぽう、BFS は、「幅」 優先検索法であって、兄弟関係を優先して巡回する やりかた である。
 なお、DFS や BFS のほかにも、(DFS を変形して、) 「中順序」 とか 「後順序」 という やりかた もある。
 それらの詳細な説明については、数学の文献を参照されたい。



[ 補遺 ] (2009年10月 1日)

 本 エッセー は、2005年 9月 1日に綴られているので、拙著 「赤本」 を脱稿した直後に綴られました (「赤本」 は、2009年 9月に出版されています)。

 本 エッセー を綴ったときには、私は、「直積と関係」 「順序」 の通説を単に まとめるつもりでいたようです。言い換えれば、本 エッセー で綴ったことが さほど (TM において) 争点になるとは思っていなかったようです。ところが、「いざない」 を脱稿したときに、「順序 (半順序、全順序)」 が TM において際だって争点になることが明らかになりました。

 「順序」 が TM において際だって争点になることに気づいた契機は、「いざない」 のなかで、ゲーデル 氏の 「不完全性定理」 を まとめていたときに、その定理の基底で使われている 「ツォルン の補題」 を強く意識したときでした。「ツォルン の補題」 そのものについては、数学の書物を読んでいただくとして──あるいは、本 ホームページ の 「反 コンピュータ 的断章」 を読んでいただくとして──、私は、「全順序」 「半順序」 を強く意識しました。

 TM では、entity を 「event (あるいは、CASE、行為・できごと)」 と 「resource (あるいは、subject)」 の ふたつに切断していますが、それらを定義するときに、「関係の対称性・非対称性」 を前提にしてきました。すなわち、「関係の非対称性」 を示す entity が 「event」 で、「関係の対称性」 を示す entity が 「resource」 である、と。そして、「いざない」 では、「関係の対称性・非対称性」 を べつの観点で──帰納的関数を用いて、「閉包」 「特徴関数」 および 「外点」 の観点で──検討しました。

 「いざない」 を出版したあとで、「閉包」 「特徴関数」 および 「外点」 は、「ツォルン の補題」 を前提にして、「全順序」 「半順序」 の観点で単純に説明できることに気づきました。すなわち、「全順序」 のなかで構成される (並べられる) entity 群が 「event」 で、「半順序」 のなかで構成される (並べられる) entity 群が 「resource」 である、と。そうすれば、TM の 「関係文法」 は、以下のように単純に体系化できる、と。

 (1) 全順序の文法 (≦ の先行・後続 関係) [ event の文法 ]

 (2) 半順序の文法 [ resource の文法 ]

 (3) 再帰 (A×A、つまり A 上の関係)

 以上のように、きわめて エレガント な体系になると思われるのですが、ここで争点になるのが、「全順序と半順序とのあいだの文法」──言い換えれば、「全順序と半順序とのあいだに写像集合を考えることができるかどうか」ということ──です。つまり、「event と resource のあいだの文法」 の説明が争点になる、ということ。TM では、「resource が event に侵入する [ 関与する ]」という文法を適用していますが、この文法は、ホワイトヘッド 氏の形而上学を流用していて、数学的 ソリューション になっていない。というのは、「全順序 (で並ぶ entity) と半順序 (で並ぶ entity) のあいだに写像集合を構成する正当性 [ 正当化条件 ]」 を数学的に証明できないので。せいぜい、現実的事態を形式化するときに、「そうしたほうが構成しやすい [ 現実的事態と形式的構成の対比がやりやすい」 というだけのことだから。この点が争点となるでしょうね。私は、今後、この点を追究したいと思っています。





  << もどる ベーシックス すすむ >>
  データベースの基礎知識