关系代数 (抽象代数)

这里的关系代数不同于 Edgar F. Codd 在1970年为关系数据库开发的关系代数。

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

定义

关系代数 (L, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁, ^{${\displaystyle {\breve {\ }}}$} ) 是代数结构使得

(i) (L, ∧, ∨, ·, I, ▷, ◁) 是剩余布尔代数，并且

(ii) 一元运算 x^{${\displaystyle {\breve {\ }}}$}  满足 x^{${\displaystyle {\breve {}}}$} ▷I = x = I◁x^{${\displaystyle {\breve {}}}$} 。

因为 x▷y 可以使用复合和逆反而定义为 x^{${\displaystyle {\breve {\ }}}$} ·y，对偶的 x◁y 定义为 x·y^{${\displaystyle {\breve {}}}$} ，在标识(signature)中不必需包括 ▷ 或 ◁，因为它可以简化为 (L, ∧, ∨, ¬, 0, 1, ·, I, ^{${\displaystyle {\breve {\ }}}$} )，这是关系代数的更常见的标识。在另一方面，x^{${\displaystyle {\breve {}}}$}  可定义为要么 x▷I 要么 I◁x，从而关系代数可以有同剩余布尔代数一样的标识。对于这个定义公理变成了 (x▷I)▷I = x = I◁(I◁x)。但是这简单的断言了 ▷I 和 I◁ 是对合。Jónsson 和 Tsinakis 已经证明了如果任何一个是对合则另一个也是并且它们是同一个运算，也就是逆反。这导致了一个特别直接的定义:

关系代数是剩余布尔代数 (L, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁) 使得 I◁ 是对合。

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

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

例子

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

2. 激发关系代数的例子依赖于在集合 X 上的二元关系 R 作为任何子集 R ⊆ X² 的定义。由在 X 上的所有二元关系构成的幂集 ${\displaystyle 2^{X^{2}}}$  是布尔代数。尽管通过如前面例子那样选用 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^{${\displaystyle {\breve {\ }}}$}  为构成自所有有序对 (y,x) 使得 (x,y) ∈ R。

3. 这个例子的重要推广是幂集 2^E，这里的 E ⊆ X² 是在集合 X 上任何等价关系。这是个推广因为 X² 自身是等价关系，也就是由所有有序对构成的完全关系。而 2^E 在 E ≠ X² 的时候，不是 ${\displaystyle 2^{X^{2}}}$  的子代数(因为在这种情况下，它不包含关系 X²，顶元素 1 是 E 而不是 X²)，它仍可作为使用相同运算定义的关系代数。它的重要性在于这个“可表示的关系代数”作为同构于在某个集合上的某个等价关系 E 的关系代数 2^E 的子代数的任何关系的定义中。可直接证明所有可表示的关系代数的类 RRA 是准簇，它生成自对某个集合 X 的形如 ${\displaystyle 2^{X^{2}}}$  的关系代数。Tarski 在 1955 年证明了 RRA 事实上是个簇，Lyndon 更早的(在1950年)证明了 RRA 是簇 RA 的真子类。尽管 RA 可有限公理化定义，Monk 在 1964 年证明了 RRA 不能被有限公理化。

在关系代数中表达二元关系的性质

很多二元关系的性质可以简洁的表达为使用 RA 运算的等式或不等式，如下面所展示的。

R 是完全的当且仅当 I ≤ R·R^{${\displaystyle ^{\breve {\ }}}$} 。

R 是确定性的当且仅当 R^{${\displaystyle ^{\breve {\ }}}$} ·R ≤ I。

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

R 是满射的当且仅当 I ≤ R^{${\displaystyle {\breve {\ }}}$} ·R (等价的如果 R^{${\displaystyle {\breve {\ }}}$}  是完全的)。

R 是单射的当且仅当 R·R^{${\displaystyle ^{\breve {\ }}}$}  ≤ I (等价的如果 R^{${\displaystyle {\breve {\ }}}$}  是确定性的)。

R 是自反的当且仅当 I ≤ R。

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

R 是反对称的当且仅当 R ∧ R^{${\displaystyle ^{\breve {\ }}}$}  ≤ I。偏序是反对称预序。

R 是对称的当且仅当 R ≤ R^{${\displaystyle ^{\breve {\ }}}$} 。等价关系是对称预序。

表达能力

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

参见

• 剩余格
• 剩余布尔代数
• 一元布尔代数
• 圆柱代数
• 关系代数
• 关系演算

引用

• Carnap, Rudolf, 1958. Introduction to Symbolic Logic with Applications, Dover.
• Halmos, P. R., 1960. Naive Set Theory. Van Nostrand.
• Bjarni Jónsson and Constantine Tsinakis, Relation algebras as residuated Boolean algebras, Algebra Universalis, 30 (1993) 469-478.
• Lucas, John Randolph, 1999. Conceptual Roots of Mathematics. Routledge.
• Roger Maddux, 2006. Relation Algebras, vol. 150 in Studies in Logic and the Foundations of Mathematics. Elsevier Science.
• Leon Henkin, Alfred Tarski, and Monk, J. D., Cylindric Algebras Part 1 (1971) and Part 2 (1985). North Holland.
• Hirsch R., and Hodkinson, I., 2002 "Relation Algebra by Games," v. 147 in Studies in Logic and the Foundations of Mathematics. Elsevier Science.
• Alfred Tarski,1941, "On the calculus of relations," Journal of Symbolic Logic 6: 73-89.
• ------, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. Providence RI: American Mathematical Society.

软件

• RelMICS / 计算机科学中的关系方法 （页面存档备份，存于互联网档案馆） 由 Wolfram Kahl （页面存档备份，存于互联网档案馆） 维护
• Carsten Sinz:

外部链接

• . In by Peter Jipsen （页面存档备份，存于互联网档案馆）. If there are problems with LaTeX, .
• An FCA interpretation of Relation Algebra （页面存档备份，存于互联网档案馆） by Uta Priss
• Origins of the Calculus of Binary Relations（页面存档备份，存于互联网档案馆） by Vaughan Pratt — a historical treatment
• The Second Calculus of Binary Relations（页面存档备份，存于互联网档案馆） by Vaughan Pratt
• Exploring (Finite) Relation Algebras Using Tools Written in Haskell （页面存档备份，存于互联网档案馆） written by Wolfram Kahl （页面存档备份，存于互联网档案馆） and Gunther Schmidt（页面存档备份，存于互联网档案馆） (see homepage of the whole project RATH - Relation Algebra Tools in Haskell （页面存档备份，存于互联网档案馆）)
• Foundations of Relations and Kleene Algebra （页面存档备份，存于互联网档案馆） by Peter Jipsen （页面存档备份，存于互联网档案馆）
• Peter Jipsen: Computer Aided Investigations of Relation Algebras （页面存档备份，存于互联网档案馆）
• A Gentzen System And Decidability For Residuated LatticesArchive.is的存檔，存档日期2007-06-21 by Peter Jipsen
• by Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa.
• Generic Programming with Relations and Functors（页面存档备份，存于互联网档案馆） by Richard Bird, Oege de Moor, Paul Hoogendijk
• R.P. de Freitas and Viana: