關係代數 (抽象代數)

這裏的關係代數不同於 Edgar F. Codd 在1970年為關係數據庫開發的關係代數。

在數學中，關係代數是支持叫做逆反(converse)的對合一元運算的剩餘布爾代數。激發關係代數的例子是在集合 X 上的所有二元關係的代數 $2^{X^{2}}$ ，帶有 R·S 被解釋為平常的二元關係複合。關係代數的早期形式形成於十九世紀德·摩根、皮爾士和 Ernst Schröder 的工作。它今日的純等式形式是阿爾弗雷德·塔斯基和他的學生在 1940 年代開發的。

定義

關係代數 (L, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁, ^{${\breve {\ }}$}) 是代數結構使得

(i) (L, ∧, ∨, ·, I, ▷, ◁) 是剩餘布爾代數，並且

(ii) 一元運算 x^{${\breve {\ }}$} 滿足 x^{${\breve {}}$}▷I = x = I◁x^{${\breve {}}$}。

因為 x▷y 可以使用複合和逆反而定義為 x^{${\breve {\ }}$}·y，對偶的 x◁y 定義為 x·y^{${\breve {}}$}，在標識(signature)中不必需包括 ▷ 或 ◁，因為它可以簡化為 (L, ∧, ∨, ¬, 0, 1, ·, I, ^{${\breve {\ }}$})，這是關係代數的更常見的標識。在另一方面，x^{${\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 上的所有二元關係構成的冪集 $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^{${\breve {\ }}$} 為構成自所有有序對 (y,x) 使得 (x,y) ∈ R。

3. 這個例子的重要推廣是冪集 2^E，這裏的 E ⊆ X² 是在集合 X 上任何等價關係。這是個推廣因為 X² 自身是等價關係，也就是由所有有序對構成的完全關係。而 2^E 在 E ≠ X² 的時候，不是 $2^{X^{2}}$ 的子代數(因為在這種情況下，它不包含關係 X²，頂元素 1 是 E 而不是 X²)，它仍可作為使用相同運算定義的關係代數。它的重要性在於這個「可表示的關係代數」作為同構於在某個集合上的某個等價關係 E 的關係代數 2^E 的子代數的任何關係的定義中。可直接證明所有可表示的關係代數的類 RRA 是准簇，它生成自對某個集合 X 的形如 $2^{X^{2}}$ 的關係代數。Tarski 在 1955 年證明了 RRA 事實上是個簇，Lyndon 更早的(在1950年)證明了 RRA 是簇 RA 的真子類。儘管 RA 可有限公理化定義，Monk 在 1964 年證明了 RRA 不能被有限公理化。

在關係代數中表達二元關係的性質

很多二元關係的性質可以簡潔的表達為使用 RA 運算的等式或不等式，如下面所展示的。

R 是完全的若且唯若 I ≤ R·R^{$^{\breve {\ }}$}。

R 是確定性的若且唯若 R^{$^{\breve {\ }}$}·R ≤ I。

函數是不是完全和確定性的二元關係。下兩個性質概括了通常只適用於函數的所有二元關係性質。

R 是滿射的若且唯若 I ≤ R^{${\breve {\ }}$}·R (等價的如果 R^{${\breve {\ }}$} 是完全的)。

R 是單射的若且唯若 R·R^{$^{\breve {\ }}$} ≤ I (等價的如果 R^{${\breve {\ }}$} 是確定性的)。

R 是自反的若且唯若 I ≤ R。

R 是傳遞的若且唯若 R·R ≤ R。預序是自反傳遞二元關係。

R 是反對稱的若且唯若 R ∧ R^{$^{\breve {\ }}$} ≤ I。偏序是反對稱預序。

R 是對稱的若且唯若 R ≤ R^{$^{\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: ARA / 針對關係代數的一個自動定理證明器

外部連結

Relation algebras. In Mathematical structures by Peter Jipsen （頁面存檔備份，存於互聯網檔案館）. If there are problems with LaTeX, see an old HTML version here.
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 Lattices Archive.is的存檔，存檔日期2007-06-21 by Peter Jipsen
Constructing Allegory from Relation Algebra and Representation Theorems 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: A Completeness Result for Relation Algebra with Binders