關係代數 (抽象代數)

"這裡的關係代數不同於 Edgar F. Codd 在1970年為關係資料庫開發的關係代數。"在數學中，關係代數是支援叫做逆反(converse)的對合一元運算的剩餘布林代數。激發關係代數的例子是在集合 "X" 上的所有二元關係的代數 formula_1，帶有 "R"·"S" 被解釋為平常的二元關係複合。關係代數的早期形式形成於十九世紀德·摩根、皮爾士和 Ernst Schröder 的工作。它今日的純等式形式是阿爾弗雷德·塔斯基和他的學生在 1940 年代開發的。定義.關係代數 ("L", ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁, formula_2) 是代數結構使得(i) ("L", ∧, ∨, ·, I, ▷, ◁) 是剩餘布林代數，並且(ii) 一元運算 "x"formula_2 滿足 "x"formula_4▷I = "x" = I◁"x"formula_4。因為 "x"▷"y" 可以使用複合和逆反而定義為 "x"formula_2·"y"，對偶的 "x"◁"y" 定義為 "x"·"y"formula_4，在標識(signature)中不必需包括 ▷ 或 ◁，因為它可以簡化為 ("L", ∧, ∨, ¬, 0, 1, ·, I, formula_2)，這是關係代數的更常見的標識。在另一方面，"x"formula_4 可定義為要麼 "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"2 的定義。由在 "X" 上的所有二元關係構成的冪集 formula_1 是布林代數。儘管透過如前面例子那樣選用 "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"formula_2 為構成自所有有序對 ("y","x") 使得 ("x","y") ∈ "R"。3. 這個例子的重要推廣是冪集 2"E"，這裡的 "E" ⊆ "X"2 是在集合 "X" 上任何等價關係。這是個推廣因為 "X"2 自身是等價關係，也就是由所有有序對構成的完全關係。而 2"E" 在 "E" ≠ "X"2 的時候，不是 formula_1 的子代數(因為在這種情況下，它不包含關係 "X"2，頂元素 1 是 "E" 而不是 "X"2)，它仍可作為使用相同運算定義的關係代數。它的重要性在於這個“可表示的關係代數”作為同構於在某個集合上的某個等價關係 "E" 的關係代數 2"E" 的子代數的任何關係的定義中。可直接證明所有可表示的關係代數的類 RRA 是準簇，它生成自對某個集合 "X" 的形如 formula_1 的關係代數。Tarski 在 1955 年證明了 RRA 事實上是個簇，Lyndon 更早的(在1950年)證明了 RRA 是簇 RA 的真子類。儘管 RA 可有限公理化定義，Monk 在 1964 年證明了 RRA 不能被有限公理化。在關係代數中表達二元關係的性質.很多二元關係的性質可以簡潔的表達為使用 RA 運算的等式或不等式，如下面所展示的。"R" 是完全的當且僅當 I ≤ "R"·"R"formula_14。"R" 是確定性的當且僅當 "R"formula_14·"R" ≤ I。函式是不是完全和確定性的二元關係。下兩個性質概括了通常只適用於函式的所有二元關係性質。"R" 是滿射的當且僅當 I ≤ "R"formula_2·R (等價的如果 "R"formula_2 是完全的)。"R" 是單射的當且僅當 "R"·"R"formula_14 ≤ I (等價的如果 "R"formula_2 是確定性的)。"R" 是自反的當且僅當 I ≤ "R"。"R" 是傳遞的當且僅當 "R"·"R" ≤ "R"。預序是自反傳遞二元關係。"R" 是反對稱的當且僅當 "R" ∧ "R"formula_14 ≤ I。偏序是反對稱預序。"R" 是對稱的當且僅當 "R" ≤ "R"formula_14。等價關係是對稱預序。表達能力.在 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)。