関係代数 (数学)

数学の抽象代数学の分野において 関係代数 (relation algebra) は、"逆" と呼ばれる対合を持つ剰余付きブール代数（英語版）のことである。動機付けとなるような関係代数の例は、集合 X 上の全ての二項関係からなる集合 Pow(X²) であって、演算 R • S を通常の関係の合成とし、R の逆を逆関係で定義する。関係代数は 19世紀の オーガスタス・ド・モルガン とチャールズ・サンダース・パースの結果から現れ、エルンスト・シュレーダーの代数的論理学において全盛となった。現在の、関係代数の等式による定式化は、1940年代に始まるアルフレト・タルスキと彼の弟子たちの研究によってなされた。

定義

関係代数とは組 (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁, ˘) であって、以下の条件を満たすものである:

1. (L, ∧, ∨, •, I, ▷, ◁) は剰余付きブール代数である。
2. 単項演算 x˘ は x˘ ▷ I = x = I ◁ x˘ を満たす。

x ▷ y は合成と逆を使って x˘ • y と定義可能で、双対的に x ◁ y を x • y˘ と定義できるので演算 ▷ や ◁ を関係代数の算号系 (signature) に含める必要はなく、通常そうされているように組 (L, ∧, ∨, ¬, 0, 1, •, I, ˘) として定めることができる。一方、x˘ は x ▷ I または I ◁ x として定義することができて、そうした場合に関係代数は剰余付きブール代数と同じ算号系を持つことになる。この定義のもとで公理は (x ▷ I)▷ I = x = I ◁(I ◁ x) の形に書けるが、これは単に ▷ I と I ◁ が対合であることを要請するものである。(Jonsson & Tsinakis 1993) はもしどちらかが対合ならば他方も対合であるので両者は同一の操作であり、つまりどちらも逆を与えることを示した。このような考察のもと

"関係代数とは剰余付きブール代数 (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) であって I ◁ が対合となるものである"

という直接的な定義が導かれる。I を乗法単位元に対応させ、x ◁ y を x の y による商だと思えば、構文論的に 1/x に該当するものは x˘ = I ◁ x であるという意味で、これを x の "逆数" あるいは "逆" として理解することができる。

剰余付きブール代数は有限個の等式で公理化されるので、関係代数もそうであり、それがゆえに関係代数全体の成す多様体（英語版）^{[注 1]} RA は有限公理化多様体を形成する。

公理

以下にあげる公理 B1-B10 は元々タルスキが 1948年に提唱したもの^[1]を Givant が 2006年に修正したものである^[2]。この公理化は、項数 ⟨2,2,1,1,0⟩-型の算号 ⟨L,∨, •,^-, ˘, I⟩ を持つ、ある二項直積 L = X² の上の代数的構造としての関係代数をもとにして作られたものである。

• L は二項演算である選言 ∨ と単項演算である補元 ‾ の下でブール代数である。ブール代数のこの種の公理化は Huntington (en) による(1933年)。

B1: A ∨ B = B ∨ A

B2: A ∨ (B ∨ C) = (A ∨ B) ∨ C

B3: (A‾ ∨ B)‾ ∨ (A‾ ∨ B‾)‾ = A

• L は二項演算である合成 • と零項演算である I を恒等元としてモノイドをなす:

B4: A •(B • C) = (A • B)• C

B5: A • I = A

• 単項演算である逆 ˘ は合成に関する対合である:

B6: A˘˘ = A

B7: (A • B)˘ = B˘ • A˘

• 逆と合成は選言について分配的である:

B8: (A ∨ B)˘ = A˘ ∨ B˘

B9: (A ∨ B)• C = (A • C) ∨ (B • C)

• B10 はド・モルガンに発見された事実 A • B ≤ C‾ ⇔ A˘ • C ≤ B‾ ⇔ C • B˘ ≤ A¯ を等式表示したものである:

B10: (A˘ •(A • B)‾) ∨ B‾ = B‾

これらの公理は ZFC 上の定理である。ブール代数に関する B1-B3 についてはこの事実は自明であり、またそれ以外のものについては 1960年に出版された Suppes の本^[3]の第三章で紹介されている。

RA を使った二項関係の性質の記述

次の表は、二項関係に関して通常扱われる性質のうちのどれくらいが，RA の演算を用いて簡潔な（不）等式で記述できるかを一覧にしたものである。以下不等式 A ≤ B は A ∨ B = B の略記である。

この種の記述の最も完全に近いリストは Carnap の本^[4]の第 C章にある(記号がここで用いているものと若干異なるので注意)。Suppes の本^[3]の第 3.2節に少数の結果が挙げられているが、それらはここで使われているものと似た記号を用いてZFC上の定理として示されている。 どちらにしてもRAの枠組みでの（つまり等式を使った）定式化はなされていない。

R の性質	RAでの定式化:
全射的	R˘ • R ≤ I
単射的 (R˘ が全射的)	R • R˘ ≤ I
全単射的	R が全射かつ単射
完全	I ≤ R ∨ R˘
関数的
関数	R が完全かつ関数的
全単射	R˘ • R = I かつ R • R˘ = I. つまり R は完全、関数的、かつ単射的
反射律	I ≤ R
非反射律	R ∧ I = 0. (0 = I‾)
推移律	R • R ≤ R
擬順序	R が反射律と推移律をみたす
反対称律	R ∧ R˘ ≤ I
順序関係	R が反対称律をみたす擬順序
全順序関係	R は完全な順序関係
強半順序関係	R が推移律と非反射律をみたす
強全順序関係	R が完全な強半順序関係
対称律	R = R˘
同値関係	R が対称律をみたす擬順序：R • R˘ = R
非対称律	R ≠ R˘
稠密	R ∧ 0 ≤ (R ∧ 0) • (R∧0)

表現力

RAの超数学は1987年のタルスキとGivantによる本^[5]の中で大きな分量を割いて議論されている。また Givant の論文^[2]においても簡潔に述べられている。

RA は全体として等式から成り、それらは一様な置き換えと代入だけで操作される。この二種類の操作規則は、学校教育でも扱われ、抽象代数でも扱われ、一般的に慣れ親しまれた操作である。よって RA の証明は一般の数理論理学における証明と異なり数学者が慣れ親しんでいる形で進められる。

→「等式クラス」も参照

RA は三つ未満の変数をもつ一階述語論理(FOL と記す)の論理式(もしくはそれと論理的に同値なもの)を記述することができる。与えられた変数は三回を越えない範囲で繰り返し量化子を用いて量化されうる。驚くべきことに、このような FOL の一部分だけでもペアノの公理を記述することができ、現在提唱されている中で殆ど全ての公理的集合論を記述することができる。よって、 RA は FOL とその結合子、量化子、ターンスタイルと三段論法を使わずに、数学全てを代数化する手段となる。RA はペアノの算術と集合論を記述するのでゲーデルの不完全性定理が適用され、RA は不完全であり完全化不能であり決定不能である（一方、RA におけるブール代数は完全で決定可能）。

表現可能関係代数 (representable relation algebra) とは、ある集合上の二項関係からなる関係代数と同型で、RA の演算を通常の二項関係間の演算として解釈できるものをいう。表現可能な関係代数からなるクラスを RRA と書くことにする。RRA は準多様体 (quasivariety) であることが、例えば擬基本類 (pseudoelementary class) の手法を以って、簡単に示される。即ち、普遍ホーン理論により公理化可能である。1950年にリンドンはRA では成立しないが RRA では成立する方程式が存在することを証明した。つまり、RRA から生成される多様体は RA から生成される多様体の真の部分多様体になっている。1955年にタルスキは RRA それ自体が多様体であることを示したが、それは 1964年にモンクが示したように有限公理化を持たない（RAは定義から有限公理化される）。この、全ての関係代数が表現可能ではないということは、つねに表現可能であるブール代数と関係代数との差異を表す基本的な手段となっている。

例

1. 任意のブール代数は、連言 ∧ を合成 • とすることで関係代数になる。この場合逆は恒等写像(y˘ = y)となり、剰余 y\x と y/x は共に含意 y→x となる(つまり ￢y ∨ x)。
2. 動機付けとなるような関係代数の例は、集合 X の上の二項関係 R を部分集合 R ⊂ X² とみなせることに拠っている。X 上の全ての二項関係から成るべき集合 Pow(X²) はブール代数をなす。よって一番目の例のようにそれだけで Pow(X²) は関係代数であるが、標準的には、合成を x(R ·S)z = ∃y. x R y ∧y S z と定義する。この解釈で R\S は、任意の x∈ X に対して、 x R y ならば x S z をみたす組 (y, z) からなる集合として一意に定まる。双対的に S/R は任意の z∈ X に対して y R z ならば x S z をみたす組 (x,y) からなる二項関係である。R˘ = ￢(R\￢I) という翻訳によって、R に対する逆 R˘ が定義される。 R˘ は x R y をみたす組 (y,x) からなる二項関係として定義できる。
3. 集合 X 上の同値関係 E ⊂ X² のべき集合 Pow(E) は直前の例の重要な一般化になっている（X² はそれ自身同値関係である）。Pow(E) は E ≠ X² であるとき Pow(X²) の部分代数にはならないが(Pow(X) の最大元である X² を Pow(E) は含まない)、各演算に Pow(X²) と同じものをとれば関係代数となる。任意の関係代数はある集合のある同値関係からつくられる関係代数の部分代数であり、この例は表現可能性(前節をみよ)の観点から重要である。
4. 群の直積または直和を合成とし、逆元をとる操作を逆とし、単位元を I として、更に R が一対一対応であるとき、R˘ • R = R • R˘ = I^[6] が成り立つ。よってこのとき L はモノイドであるだけでなく群になる。定義の B4-B7 は群論においてよく知られた定理であり、関係代数は群論（とブール代数）の真の拡大になる。このことは関係代数の強い表現力を示唆する事実である。

歴史的注意

1860年にド・モルガンは RA の基盤を与えたが、パースはそれをより発展させ、その哲学的な強力さに魅了されるようになった。彼らの結果は E. Schröder(en) が著書 Vorlesungen über die Algebra der Logik (1890-1905)の第三巻で取り上げ、拡張された決定的な形として知られるようになった。「プリンキピア・マテマティカ」では Schröder の RA について記しているが、記法の発明者としてしか認めていない。1912年、Alwin Korselt は、量化子が四回入れ子になっている、ある論理式が RA で同値なものをもたないことを証明した(Korselt は彼の発見を出版しなかった。出版物の形で公開されたのは L. Loewenheim が 1915年に出版した論文^[7])においてである。この事実は RA への興味を失わさせ、それはタルスキが 1941年に論文を執筆するまで続いた。彼の学生は現在まで RA の研究を続けている。タルスキは 1970年代に S. Givant の助けを借りて RA の研究に復帰し、彼らの共同研究は1987年に出版されたモノグラフ^[5]にまとめられた。この本はこの分野における決定的な参考文献となっている。より詳細な RA の歴史については，Maddux の本^[8][9]を参照すること。

ソフトウェア

• RelMICS / Relational Methods in Computer Science maintained by Wolfram Kahl
• Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras

関連項目

• 代数的論理学
• 二項関係
• 直積集合

注

1. これは位相多様体や代数多様体などとは異なる概念であることに注意。