関係代数 (数学)
表現可能関係代数 (representable relation algebra) とは、ある集合上の二項関係からなる関係代数と同型で、RA の演算を通常の二項関係間の演算として解釈できるものをいう。表現可能な関係代数からなるクラスを RRA と書くことにする。RRA は準多様体 (quasivariety) であることが、例えば擬基本類 (pseudoelementary class) の手法を以って、簡単に示される。即ち、普遍ホーン理論により公理化可能である。1950年にリンドンはRA では成立しないが RRA では成立する方程式が存在することを証明した。つまり、RRA から生成される多様体は RA から生成される多様体の真の部分多様体になっている。1955年にタルスキは RRA それ自体が多様体であることを示したが、それは 1964年にモンクが示したように有限公理化を持たない(RAは定義から有限公理化される)。この、全ての関係代数が表現可能ではないということは、つねに表現可能であるブール代数と関係代数との差異を表す基本的な手段となっている。
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 の本の第三章で紹介されている。
次の表は、二項関係に関して通常扱われる性質のうちのどれくらいが,RA の演算を用いて簡潔な(不)等式で記述できるかを一覧にしたものである。以下不等式 A ≤ B は A ∨ B = B の略記である。
この種の記述の最も完全に近いリストは Carnap の本の第 C章にある(記号がここで用いているものと若干異なるので注意)。Suppes の本の第 3.2節に少数の結果が挙げられているが、それらはここで使われているものと似た記号を用いてZFC上の定理として示されている。 どちらにしてもRAの枠組みでの(つまり等式を使った)定式化はなされていない。