関係代数 (数学)
(Jonsson & Tsinakis 1993) はもしどちらかが対合ならば他方も対合であるので両者は同一の操作であり、つまりどちらも逆を与えることを示した。このような考察のもと
"関係代数とは剰余付きブール代数 (L, ∧, ∨, ¬, 0, 1, •, I, ▷, ◁) であって I ◁ が対合となるものである"
という直接的な定義が導かれる。I を乗法単位元に対応させ、x ◁ y を x の y による商だと思えば、構文論的に 1/x に該当するものは x ̆ = I ◁ x であるという意味で、これを x の "逆数" あるいは "逆" として理解することができる。
剰余付きブール代数は有限個の等式で公理化されるので、関係代数もそうであり、それがゆえに関係代数全体の成す多様体(英語版) RA は有限公理化多様体を形成する。
数学の抽象代数学の分野において 関係代数 (relation algebra) は、"逆" と呼ばれる対合を持つ剰余付きブール代数(英語版)のことである。動機付けとなるような関係代数の例は、集合 X 上の全ての二項関係からなる集合 Pow(X) であって、演算 R • S を通常の関係の合成とし、R の逆を逆関係で定義する。関係代数は 19世紀の オーガスタス・ド・モルガン とチャールズ・サンダース・パースの結果から現れ、エルンスト・シュレーダー(英語版)の代数的論理学において全盛となった。現在の、関係代数の等式による定式化は、1940年代に始まるアルフレト・タルスキと彼の弟子たちの研究によってなされた。
R ̆ は x R y をみたす組 (y,x) からなる二項関係として定義できる。
集合 X 上の同値関係 E ⊂ X のべき集合 Pow(E) は直前の例の重要な一般化になっている(X はそれ自身同値関係である)。Pow(E) は E ≠ X であるとき Pow(X) の部分代数にはならないが(Pow(X) の最大元である X を Pow(E) は含まない)、各演算に Pow(X) と同じものをとれば関係代数となる。任意の関係代数はある集合のある同値関係からつくられる関係代数の部分代数であり、この例は表現可能性(前節をみよ)の観点から重要である。
群の直積または直和を合成とし、逆元をとる操作を逆とし、単位元を I として、更に R が一対一対応であるとき、R ̆ • R = R • R ̆ = I が成り立つ。よってこのとき L はモノイドであるだけでなく群になる。定義の B4-B7 は群論においてよく知られた定理であり、関係代数は群論(とブール代数)の真の拡大になる。このことは関係代数の強い表現力を示唆する事実である。
以下にあげる公理 B1-B10 は元々タルスキが 1948年に提唱したものを Givant が 2006年に修正したものである。この公理化は、項数 ⟨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