関係代数 (数学)

数学の抽象代数学の分野において 関係代数 (relation algebra) は、"逆" と呼ばれる対合を持つのことである。動機付けとなるような関係代数の例は、集合 "X" 上の全ての二項関係からなる集合 Pow("X"2) であって、演算 "R" • "S" を通常の関係の合成とし、"R" の逆を逆関係で定義する。関係代数は 19世紀の オーガスタス・ド・モルガン とチャールズ・サンダース・パースの結果から現れ、の代数的論理学において全盛となった。現在の、関係代数の等式による定式化は、1940年代に始まるアルフレト・タルスキと彼の弟子たちの研究によってなされた。
定義.
関係代数とは組 ("L", ∧, ∨, ¬, 0, 1, •, I, ▷, ◁, ˘) であって、以下の条件を満たすものである:
"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 ◁ が対合であることを要請するものである。 はもしどちらかが対合ならば他方も対合であるので両者は同一の操作であり、つまりどちらも逆を与えることを示した。このような考察のもと
という直接的な定義が導かれる。I を乗法単位元に対応させ、"x" ◁ "y" を "x" の "y" による商だと思えば、構文論的に 1/"x" に該当するものは "x"˘ = I ◁ "x" であるという意味で、これを "x" の "逆数" あるいは "逆" として理解することができる。
剰余付きブール代数は有限個の等式で公理化されるので、関係代数もそうであり、それがゆえに関係代数全体の成す RA は有限公理化多様体を形成する。
公理.
以下にあげる公理 B1-B10 は元々タルスキが 1948年に提唱したものを Givant が 2006年に修正したものである。この公理化は、項数 〈2,2,1,1,0〉-型の算号 〈"L",∨, •,-, ˘, I〉 を持つ、ある二項直積 "L" = "X"2 の上の代数的構造としての関係代数をもとにして作られたものである。
これらの公理は ZFC 上の定理である。ブール代数に関する B1-B3 についてはこの事実は自明であり、またそれ以外のものについては 1960年に出版された Suppes の本の第三章で紹介されている。
RA を使った二項関係の性質の記述.
次の表は、二項関係に関して通常扱われる性質のうちのどれくらいが，RA の演算を用いて簡潔な（不）等式で記述できるかを一覧にしたものである。以下不等式 "A" ≤ "B" は "A" ∨ "B" = "B" の略記である。
この種の記述の最も完全に近いリストは Carnap の本の第 C章にある(記号がここで用いているものと若干異なるので注意)。Suppes の本の第 3.2節に少数の結果が挙げられているが、それらはここで使われているものと似た記号を用いてZFC上の定理として示されている。
どちらにしてもRAの枠組みでの（つまり等式を使った）定式化はなされていない。
表現力.
RAの超数学は1987年のタルスキとGivantによる本の中で大きな分量を割いて議論されている。また 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は定義から有限公理化される）。この、全ての関係代数が表現可能ではないということは、つねに表現可能であるブール代数と関係代数との差異を表す基本的な手段となっている。
歴史的注意.
1860年にド・モルガンは RA の基盤を与えたが、パースはそれをより発展させ、その哲学的な強力さに魅了されるようになった。彼らの結果は E. Schröder() が著書 "Vorlesungen über die Algebra der Logik" (1890-1905)の第三巻で取り上げ、拡張された決定的な形として知られるようになった。「プリンキピア・マテマティカ」では Schröder の RA について記しているが、記法の発明者としてしか認めていない。1912年、Alwin Korselt は、量化子が四回入れ子になっている、ある論理式が RA で同値なものをもたないことを証明した(Korselt は彼の発見を出版しなかった。出版物の形で公開されたのは L. Loewenheim が 1915年に出版した論文)においてである。この事実は RA への興味を失わさせ、それはタルスキが 1941年に論文を執筆するまで続いた。彼の学生は現在まで RA の研究を続けている。タルスキは 1970年代に S. Givant の助けを借りて RA の研究に復帰し、彼らの共同研究は1987年に出版されたモノグラフにまとめられた。この本はこの分野における決定的な参考文献となっている。より詳細な RA の歴史については，Maddux の本を参照すること。