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

定義 関係代数とは組 (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁, ˘) であって、以下の条件を満たすものである: (L, ∧, ∨, •, I, ▷, ◁) は剰余付きブール代数である。 単項演算 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 ◁ が対合であることを要請するものである。 はもしどちらかが対合ならば他方も対合なので両者は同一の操作で、つまりどちらも逆を与えることを示した。このような考察の下

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

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

剰余付きブール代数は有限個の等式で公理化されるので、関係代数もそうで、それゆえ関係代数全体の成すこれは位相多様体や代数多様体などとは異なる概念であることに注意。 RA は有限公理化多様体を形成する。

公理

以下にあげる公理 B1-B10 は元々タルスキが 1948年に提唱したものTarski, A.: Abstract: Representation Problems for Relation Algebras, Bulletin of the AMS 54: (1948)80.を Givant が 2006年に修正したものであるGivant, S.: The calculus of relations as a foundation for mathematics, Journal of Automated Reasoning 37(2006): 277-322.。この公理化は、項数 〈2,2,1,1,0〉-型の算号 〈L,∨, •,-, ˘, I〉 を持つ、ある二項直積 L = X2 の上の代数的構造としての関係代数をもとにして作られたものである。

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 の本Suppes, P. : Axiomatic Set Theory Van Nostrand, 1960. (Dover reprint, 1972.)の第三章で紹介されている。

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

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

この種の記述の最も完全に近いリストは Carnap の本Carnap, R.: Introdution to Symbolic Logic and its Applications, Dover Publications, 1958の第 C章にある(記号がここで用いているものと若干異なるので注意)。Suppes の本の第 3.2節に少数の結果が挙げられているが、それらはここで用いているものと似た記号を用いてZFC上の定理として示されている。 いずれにせよRAの枠組みでの（つまり等式を使った）定式化はなされていない。

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

表現力 RAの超数学は1987年のタルスキとGivantによる本Tarski, A., Givant, S.:A Formalization of Set Theory Without Variables, AMS, 1987.の中で大きな分量を割いて議論されている。また Givant の論文でも簡潔に述べられている。

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は定義から有限公理化される）。この、全ての関係代数が表現可能ではないということは、つねに表現可能であるブール代数と関係代数との差異を表す基本的な手段となっている。

例 任意のブール代数は、連言 ∧ を合成 • とすることで関係代数になる。この場合逆は恒等写像(y˘ = y)となり、剰余 y\x と y/x は共に含意 y→x となる(つまり ￢y ∨ x)。 動機付けとなるような関係代数の例は、集合 X の上の二項関係 R を部分集合 R ⊂ X2 とみなせることによる。X 上の全ての二項関係から成るべき集合 Pow(X2) はブール代数をなす。よって、一番目の例のようにそれだけで Pow(X2) は関係代数であるが、標準的には、合成を 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) からなる二項関係として定義できる。 集合 X 上の同値関係 E ⊂ X2 のべき集合 Pow(E) は直前の例の重要な一般化になっている（X2 はそれ自身同値関係である）。Pow(E) は E ≠ X2 であるとき Pow(X2) の部分代数にはならないが(Pow(X) の最大元である X2 を Pow(E) は含まない)、各演算に Pow(X2) と同じものをとれば関係代数となる。任意の関係代数はある集合のある同値関係からつくられる関係代数の部分代数で、この例は表現可能性(前節をみよ)の観点から重要である。 群の直積または直和を合成とし、逆元をとる操作を逆とし、単位元を I として、更に R が一対一対応であるとき、R˘ • R = R • R˘ = ITarski, A. :On the calculus of relations, Journal of Symbolic Logic 6 (1941) 73-89. が成り立つ。よって、このとき 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年に出版した論文Loewenheim L.: Über Möglichkeiten im Relativkalkül, Mathematische Annalen 76(1915): 447–470. (英訳版) Heijenoort, J. :On possibilities in the calculus of relatives, A Source Book in Mathematical Logic, 1879–1931, Harvard Univ. Press (1967), 228–251.)に拠る。この事実は RA への興味を失わさせ、それはタルスキが 1941年に論文を執筆するまで続いた。彼の学生は現在まで RA の研究を続けている。タルスキは 1970年代に S. Givant の助けを借りて RA の研究に復帰し、彼らの共同研究は1987年に出版されたモノグラフにまとめられた。この本はこの分野における決定的な参考文献となっている。より詳細な RA の歴史については，Maddux の本Maddux, R. : The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations, Studia Logica 50(3/4) (1991), 421-55. http://orion.math.iastate.edu/maddux/papers/Maddux1991.pdf Maddux, R. : Relation Algebras, Studies in Logic and the Foundations of Mathematics 150, Elsevier Science 2006.を参照すること。

ソフトウェア RelMICS / Relational Methods in Computer Science maintained by Wolfram Kahl Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras

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

注

出典

参考文献 Halmos, P. R., 1960. Naive Set Theory. Van Nostrand. Leon Henkin, Alfred Tarski, and Monk, J. D., 1971. Cylindric Algebras, Part 1, and 1985, Part 2. North Holland. Hirsch R., and Hodkinson, I., 2002, Relation Algebra by Games, vol. 147 in Studies in Logic and the Foundations of Mathematics. Elsevier Science. Bjarni Jonsson and Constantine Tsinakis, 1993, "Relation algebras as residuated Boolean algebras," Algebra Universalis 30: 469-78.

Roger Maddux, 1991, "The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations," Studia Logica 50(3/4): 421-55.

外部リンク Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa, "Constructing Allegory from Relation Algebra and Representation Theorems." Richard Bird, Oege de Moor, Paul Hoogendijk, "Generic Programming with Relations and Functors." R.P. de Freitas and Viana, "A Completeness Result for Relation Algebra with Binders." Peter Jipsen: Relation algebras. In Mathematical structures. If there are problems with LaTeX, see an old HTML versionhere. "Foundations of Relations and Kleene Algebra." "Computer Aided Investigations of Relation Algebras." "A Gentzen System And Decidability For Residuated Lattices." Vaughan Pratt: "Origins of the Calculus of Binary Relations." A historical treatment. "The Second Calculus of Binary Relations." Priss, Uta, "An FCA interpretation of Relation Algebra." Kahl, Wolfram, and Schmidt, Gunther, "Exploring (Finite) Relation Algebras Using Tools Written in Haskell." See homepage of the whole project.