查看“︁关系代数 (抽象代数)”︁的源代码

:''这里的关系代数不同于 [[Edgar F. Codd]] 在1970年为[[关系数据库]]开发的[[关系代数 (数据库)|关系代数]]。''

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

== 定义 ==

'''关系代数''' (''L'', ∧, ∨, ¬, 0, 1, ·, '''I''', ▷, ◁, <sup><math>\breve{\ }</math></sup>) 是代数结构使得
:(i) (''L'', ∧, ∨, ·, '''I''', ▷, ◁) 是[[剩余布尔代数]]，并且
:(ii) 一元运算 ''x''<sup><math>\breve{\ }</math></sup> 满足 ''x''<sup><math>\breve{ }</math></sup>▷'''I''' = ''x'' = '''I'''◁''x''<sup><math>\breve{ }</math></sup>。

因为 ''x''▷''y'' 可以使用复合和逆反而定义为 ''x''<sup><math>\breve{\ }</math></sup>·''y''，对偶的 ''x''◁''y'' 定义为 ''x''·''y''<sup><math>\breve{ }</math></sup>，在标识(signature)中不必需包括 ▷ 或 ◁，因为它可以简化为 (''L'', ∧, ∨, ¬, 0, 1, ·, '''I''', <sup><math>\breve{\ }</math></sup>)，这是关系代数的更常见的标识。在另一方面，''x''<sup><math>\breve{ }</math></sup> 可定义为要么 ''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''<sup>2</sup> 的定义。由在 ''X'' 上的所有二元关系构成的幂集 <math>2^{X^2}</math> 是布尔代数。尽管通过如前面例子那样选用 ''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''<sup><math>\breve{\ }</math></sup> 为构成自所有有序对 (''y'',''x'') 使得 (''x'',''y'') ∈ ''R''。

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

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

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

''R'' 是完全的当且仅当 '''I''' ≤ ''R''·''R''<sup><math>^\breve{\ }</math></sup>。

''R'' 是确定性的当且仅当 ''R''<sup><math>^\breve{\ }</math></sup>·''R'' ≤ '''I'''。

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

:''R'' 是[[满射]]的当且仅当 '''I''' ≤ ''R''<sup><math>\breve{\ }</math></sup>·R (等价的如果 ''R''<sup><math>\breve{\ }</math></sup> 是完全的)。

:''R'' 是[[单射]]的当且仅当 ''R''·''R''<sup><math>^\breve{\ }</math></sup> ≤ '''I''' (等价的如果 ''R''<sup><math>\breve{\ }</math></sup> 是确定性的)。

''R'' 是[[自反关系|自反]]的当且仅当 '''I''' ≤ ''R''。

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

''R'' 是[[反对称关系|反对称]]的当且仅当 ''R'' ∧ ''R''<sup><math>^\breve{\ }</math></sup> ≤ '''I'''。[[偏序关系|偏序]]是反对称预序。

''R'' 是[[对称关系|对称]]的当且仅当 ''R'' ≤ ''R''<sup><math>^\breve{\ }</math></sup>。[[等价关系]]是对称预序。

== 表达能力 ==

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

== 参见 ==
* [[剩余格]]
* [[剩余布尔代数]]
* [[一元布尔代数]]
* [[圆柱代数]]
* [[关系代数]]
* [[关系演算]]

== 引用 ==
* [[Rudolf Carnap|Carnap, Rudolf]], 1958. ''Introduction to Symbolic Logic with Applications'', Dover. 
* [[Paul Richard Halmos|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.
* [[John Lucas (philosopher)|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.

== 软件 ==
* [http://relmics.mcmaster.ca/html/index.html RelMICS / 计算机科学中的关系方法] {{Wayback|url=http://relmics.mcmaster.ca/html/index.html |date=20200201075339 }} 由 [http://www.cas.mcmaster.ca/~kahl/ Wolfram Kahl] {{Wayback|url=http://www.cas.mcmaster.ca/~kahl/ |date=20201025172013 }} 维护
* Carsten Sinz: [https://web.archive.org/web/20070627003141/http://www-sr.informatik.uni-tuebingen.de/~sinz/ARA/ ARA / 针对关系代数的一个自动定理证明器]

== 外部链接 ==
* [https://web.archive.org/web/20070330011135/http://math.chapman.edu/structuresold/files/Relation_algebras.pdf Relation algebras]. In [https://web.archive.org/web/20060515231126/http://math.chapman.edu/cgi-bin/structures Mathematical structures] by [http://www1.chapman.edu/~jipsen/ Peter Jipsen] {{Wayback|url=http://www1.chapman.edu/~jipsen/ |date=20200829071247 }}. If there are problems with LaTeX, [https://web.archive.org/web/20060516003610/http://math.chapman.edu/cgi-bin/structures.pl?Relation_algebras see an old HTML version here].
* [http://citeseer.ist.psu.edu/739624.html An FCA interpretation of Relation Algebra] {{Wayback|url=http://citeseer.ist.psu.edu/739624.html |date=20080725235303 }} by Uta Priss
* [http://boole.stanford.edu/pub/ocbr.pdf Origins of the Calculus of Binary Relations]{{Wayback|url=http://boole.stanford.edu/pub/ocbr.pdf |date=20110927161616 }} by [[Vaughan Pratt]] — a historical treatment
* [http://boole.stanford.edu/pub/scbr.pdf The Second Calculus of Binary Relations]{{Wayback|url=http://boole.stanford.edu/pub/scbr.pdf |date=20110927161625 }} by [[Vaughan Pratt]]
* [http://relmics.mcmaster.ca/~kahl/Publications/TR/2000-02/ Exploring (Finite) Relation Algebras Using Tools Written in Haskell] {{Wayback|url=http://relmics.mcmaster.ca/~kahl/Publications/TR/2000-02/ |date=20160303184500 }} written by [http://www.cas.mcmaster.ca/~kahl/ Wolfram Kahl] {{Wayback|url=http://www.cas.mcmaster.ca/~kahl/ |date=20201025172013 }} and [http://ist.unibw-muenchen.de/People/schmidt/ Gunther Schmidt]{{Wayback|url=http://ist.unibw-muenchen.de/People/schmidt/ |date=20030606231954 }} (see homepage of the whole project [http://relmics.mcmaster.ca/tools/RATH/index.html RATH - Relation Algebra Tools in Haskell] {{Wayback|url=http://relmics.mcmaster.ca/tools/RATH/index.html |date=20191001223659 }})
* [http://math.chapman.edu/~jipsen/talks/RelMiCS2006/JipsenRAKAtutorial.pdf Foundations of Relations and Kleene Algebra] {{Wayback|url=http://math.chapman.edu/~jipsen/talks/RelMiCS2006/JipsenRAKAtutorial.pdf |date=20160303185706 }} by [http://www1.chapman.edu/~jipsen/ Peter Jipsen] {{Wayback|url=http://www1.chapman.edu/~jipsen/ |date=20200829071247 }}
* Peter Jipsen: [http://www1.chapman.edu/~jipsen/dissertation/ Computer Aided Investigations of Relation Algebras] {{Wayback|url=http://www1.chapman.edu/~jipsen/dissertation/ |date=20160304025743 }}
* [http://citeseer.ist.psu.edu/337149.html A Gentzen System And Decidability For Residuated Lattices]{{Webarchive|url=https://archive.today/20070621102523/http://citeseer.ist.psu.edu/337149.html |date=2007-06-21 }} by Peter Jipsen
* [https://web.archive.org/web/19980713070139/http://nicosia.is.s.u-tokyo.ac.jp/pub/staff/akama/repr.ps Constructing Allegory from Relation Algebra and Representation Theorems] by Yohji AKAMA, Yasuo Kawahara, and Hitoshi Furusawa.
* [http://citeseer.ist.psu.edu/bird99generic.html Generic Programming with Relations and Functors]{{Wayback|url=http://citeseer.ist.psu.edu/bird99generic.html |date=20050122234418 }} by Richard Bird, Oege de Moor, Paul Hoogendijk
* R.P. de Freitas and Viana: [https://web.archive.org/web/20070927201527/http://www.cos.ufrj.br/~naborges/fv02.ps A Completeness Result for Relation Algebra with Binders]

[[Category:代数逻辑|G]]
[[Category:数学关系|G]]
[[Category:关系代数|*]]