关系代数 (抽象代数)

在数学中，关系代数是支持叫做逆反(converse)的对合一元运算的剩余布尔代数。激发关系代数的例子是在集合 上的所有二元关系的代数 ${\displaystyle 2^{X^2}}$· 被解释为平常的二元关系复合。关系代数的早期形式形成于十九世纪德·摩根、皮尔士和 Ernst Schröder 的工作。它今日的纯等式形式是阿尔弗雷德·塔斯基和他的学生在 1940 年代开发的。

关系代数 (, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁, ${\displaystyle \stackrel{˘<!--\; ˘\; -->}{}}$▷ 可以使用复合和逆反而定义为 ${\displaystyle \stackrel{˘<!--\; ˘\; -->}{}}$，对偶的 ◁ 定义为 ·${\displaystyle \stackrel{˘<!--\; ˘\; -->}{}}$, ∧, ∨, ¬, 0, 1, ·, I, ${\displaystyle \stackrel{˘<!--\; ˘\; -->}{}}$${\displaystyle \stackrel{˘<!--\; ˘\; -->}{}}$▷I 要么 I◁，从而关系代数可以有同剩余布尔代数一样的标识。对于这个定义公理变成了 (▷I)▷I = = I◁(I◁)。但是这简单的断言了 ▷I 和 I◁ 是对合。Jónsson 和 Tsinakis 已经证明了如果任何一个是对合则另一个也是并且它们是同一个运算，也就是逆反。这导致了一个特别直接的定义:

当 ◁ 被看作某种形式的 对 的商的时候，I 可看作对应的乘法单位元，I◁ 可被理解为类似于 1/ 的 的“倒数”，某些作者使用这个术语作为逆反的同义词。

因为剩余布尔代数是用有限多等式公理化的，所以关系代数也是，因此它形成了一个有限公理化的簇。

1. 任何布尔代数都可作为关系代数，通过选用复合(幺半群乘法)为合取。这种复合的解释唯一的确定逆反为恒等 ( = )，而剩余 \ 和 / 二者都是蕴涵 →，也就是 ¬∨。

2. 激发关系代数的例子依赖于在集合 上的二元关系 作为任何子集 ⊆ 2 的定义。由在 上的所有二元关系构成的幂集 ${\displaystyle 2^{X^2}}$· = ∧ 它可以成为关系代数，给出的 · 的标准解释是 (·) = ∃.。就是说，有序对 (,) 属于关系 ·， 只有在存在 ∈ 使得 (,) ∈ 并且 (,) ∈ 的时候。这种解释唯一的确定 \ 构成自所有有序对 (,) 使得对于所有 ∈ ，如果 则 。对偶的说 / 构成自所有有序对 (,) 使得对于所有 ∈ ，如果 则 。转换 = ¬(y\¬I) 接着建立 的逆反 ${\displaystyle \stackrel{˘<!--\; ˘\; -->}{}}$,) 使得 (,) ∈ 。

3. 这个例子的重要推广是幂集 2，这里的 ⊆ 2 是在集合 上任何等价关系。这是个推广因为 2 自身是等价关系，也就是由所有有序对构成的完全关系。而 2 在 ≠ 2 的时候，不是 ${\displaystyle 2^{X^2}}$2，顶元素 1 是 而不是 2)，它仍可作为使用相同运算定义的关系代数。它的重要性在于这个“可表示的关系代数”作为同构于在某个集合上的某个等价关系 的关系代数 2 的子代数的任何关系的定义中。可直接证明所有可表示的关系代数的类 RRA 是准簇，它生成自对某个集合 的形如 ${\displaystyle 2^{X^2}}$ 是完全的当且仅当 I ≤ ·${\displaystyle {}^{\stackrel{˘<!--\; ˘\; -->}{}}}$ 是确定性的当且仅当 ${\displaystyle {}^{\stackrel{˘<!--\; ˘\; -->}{}}}$ ≤ I。

函数是不是完全和确定性的二元关系。下两个性质概括了通常只适用于函数的所有二元关系性质。

是自反的当且仅当 I ≤ 。

是传递的当且仅当 · ≤ 。预序是自反传递二元关系。

是反对称的当且仅当 ∧ ${\displaystyle {}^{\stackrel{˘<!--\; ˘\; -->}{}}}$ 是对称的当且仅当 ≤ ${\displaystyle {}^{\stackrel{˘<!--\; ˘\; -->}{}}}$。等价关系是对称预序。

在 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)。