关系代数 (抽象代数)

例子

1. 任何布尔代数都可作为关系代数，通过选用复合(幺半群乘法)为合取。这种复合的解释唯一的确定逆反为恒等(ў = y)，而剩余y\x 和 x/y 二者都是蕴涵y→x，也就是¬y∨x。
2. 激发关系代数的例子依赖于在集合X 上的二元关系R 作为任何子集R ⊆ X² 的定义。由在X 上的所有二元关系构成的幂集 是布尔代数。尽管通过如前面例子那样选用R·S = R∧S 它可以成为关系代数，给出的· 的标准解释是x(R·S)z = ∃y.xRySz。就是说，有序对(x,z) 属于关系R·S， 只有在存在y ∈ X 使得 (x,y) ∈ R 并且 (y,z) ∈ S 的时候。这种解释唯一的确定R\S 构成自所有有序对(y,z) 使得对于所有x ∈ X，如果 xRy 则 xSz。对偶的说S/R 构成自所有有序对(x,y) 使得对于所有z ∈ X，如果 yRz 则 xSz。转换 ў = ¬(y\¬I) 接着建立R 的逆反R 为构成自所有有序对(y,x) 使得 (x,y) ∈ R。
3. 这个例子的重要推广是幂集2ᴱ，这里的E ⊆ X² 是在集合X 上任何等价关系。这是个推广因为X² 自身是等价关系，也就是由所有有序对构成的完全关系。而 2ᴱ 在 E ≠ X² 的时候，不是  的子代数(因为在这种情况下，它不包含关系X²，顶元素1 是 E 而不是X²)，它仍可作为使用相同运算定义的关系代数。它的重要性在于这个“可表示的关系代数”作为同构于在某个集合上的某个等价关系E 的关系代数2ᴱ 的子代数的任何关系的定义中。可直接证明所有可表示的关系代数的类RRA 是准簇，它生成自对某个集合X 的形如 的关系代数。Tarski 在 1955 年证明了RRA 事实上是个簇，Lyndon 更早的(在1950年)证明了RRA 是簇RA 的真子类。尽管 RA 可有限公理化定义，Monk 在 1964 年证明了RRA 不能被有限公理化。

表达能力

在 Tarski 和 Givant (1987)的著作中详细讨论了RA 的元数学。RA 完全构成自只使用一致替换和对相等者的相等代入操纵的等式。二者的规则常见于对于学校的数学教育和一般的抽象代数。所以 RA 证明可以让所有数学用更熟悉的方式来完成，而不像一般的数理逻辑那样。
RA 可以表达任何(精确地说逻辑等价于)包含不多于三个变量的一阶逻辑(FOL)公式(一个给定的变量可被量化多次只要量词不嵌套)。另人惊讶，这个 FOL 片段足够表达皮亚诺算术和几乎所有已经提议的公理化集合论。所以 RA 在效果上是代数化几乎所有数学的一种方式，而免除了FOL 和它的连结词、量词、十字转门和肯定前件。因为 RA 可以表达皮亚诺算术和集合论，哥德尔不完备性定理适用于它， RA 是不完备的、不可完备的和不可判定性的。(N.B. 这些性质不能描述RA 的布尔逻辑片段。)
形成的类RRA 的可表示的关系代数是同构于构成自在某个集合上的二元关系并闭合于RA 运算的标准解释的某个关系代数的那些关系代数。比如使用伪基本类的方法就可轻易证明，就是 RRA 是个准簇，也就是可用全称Horn 理论公理化。在 1950 年 Roger Lyndon 证明了成立于RRA 而不成立于RA 的等式的存在，就是说RRA 生成的簇是簇RA 的真子簇。在 1955 年 Alfred Tarski 证明了RRA 自身是个簇，但是 Donald Monk 在 1964 年证明它没有有限公理化，不像RA 可以通过定义有限公理化。不是所有关系代数都是可表示的是它同布尔代数之间的根本区别，它可以表示为某个集合的闭合在并集、交集和补集下的子集的集合。

历史注记

德·摩根在 1860 年创立了RA，而皮尔士深化了它并着迷于它的哲学力量。德·摩根和皮尔士的工作主要为人所知于Ernst Schröder 在他的《Vorlesungen über die Algebra der Logik》(1890-1905) 中给出的扩展和终极形式中。《数学原理》受到 Schröder 的 RA 的强烈影响，但他却只被认可为这个概念的发明者。这里提供RA 的基础论文是Tarski (1941) 给出的；他设计了上述公理，他和他的学生直到今天仍在持续致力于RA。Tarski 和 Givant (1987) 的很多内容是Tarski 在 1940 年代独自完成，他在1970 年代随着Steven Givant 的帮助而重返这个主题。RA 的更详细的历史请参见Maddux (2006)。