関係代数

数学および抽象代数学において、関係代数とは、逆演算と呼ばれる単項演算で拡張された残余ブール代数 である。関係代数の動機となる例は、代数である。$2X2$集合上のすべての二項関係${\displaystyle X}$すなわち、デカルト正方形の部分集合${\displaystyle X^{2}}$、 と${\displaystyle R\bullet S}$二項関係の通常の構成として解釈される${\displaystyle R}$そして${\displaystyle S}$、そしてその逆は${\displaystyle R}$逆の関係として。

関係代数は、19世紀のオーガスタス・ド・モルガンとチャールズ・パースの研究に端を発し、エルンスト・シュレーダーの代数論理学で頂点に達した。ここで扱う関係代数の等式形式は、 1940年代からアルフレッド・タルスキとその弟子たちによって発展させられた。タルスキとギヴァント（1987）は、関係代数を公理的集合論の変数を用いない扱いに応用し、集合論に基づく数学自体が変数を用いずに実施できる可能性を示唆した。

関係代数${\displaystyle (L,\wedge ,\vee ,^{-},0,1,\bullet ,\mathbf {I} ,{\breve {}})}$は、論理積演算を備えた代数構造である。${\displaystyle x\wedge y}$選言${\displaystyle x\vee y}$、および否定${\displaystyle x^{-}}$ブール定数${\displaystyle 0}$そして${\displaystyle 1}$合成の関連操作${\displaystyle x\bullet y}$そして逆もまた然り${\displaystyle x{\breve {}}}$、そして関係定数${\displaystyle \mathbf {I} }$、これらの演算と定数が、関係計算の公理化を構成する特定の方程式を満たすように。大まかに言うと、関係代数は、空集合(${\displaystyle 0}$）、普遍的（${\displaystyle 1}$）、そしてアイデンティティ${\displaystyle \mathbf {I} }$関係と、これら 5 つの演算に関して閉じている群は、恒等置換を含む集合の置換のシステムであり、合成と逆に関して閉じている。しかし、関係代数の1 階理論は、このような二項関係のシステムには完全ではない。

JónssonとTsinakis（1993）に従って、追加の演算を定義すると便利である。${\displaystyle x\triangleleft y=x\bullet y{\breve {}}}$そして、二重に、${\displaystyle x\triangleright y=x{\breve {}}\bullet y}$ヨンソンとツィナキスは、${\displaystyle \mathbf {I} \triangleleft x=x\triangleright \mathbf {I} }$両者とも等しかった${\displaystyle x{\breve {}}}$したがって、関係代数は代数構造として定義することもできる。${\displaystyle (L,\wedge ,\vee ,^{-},0,1,\bullet ,\mathbf {I} ,\triangleleft ,\triangleright )}$この署名が通常の署名よりも優れている点は、関係代数を単純に残余ブール代数として完全に定義できることである。${\displaystyle \mathbf {I} \triangleleft x}$これは対合、つまり、${\displaystyle \mathbf {I} \triangleleft (\mathbf {I} \triangleleft x)=x}$後者の条件は、等式の相対的な対応物と考えることができる。${\displaystyle 1/(1/x)=x}$通常の算術では逆数、また、一部の著者は逆数を逆数の同義語として使用しています。

残余ブール代数は有限個の恒等式で公理化されているため、関係代数も同様です。したがって、後者は関係代数の多様体RAを形成します。上記の定義を方程式として展開すると、次の有限公理化が得られます。

次の表は、二項関係の一般的な性質の多くが、簡潔なRA等式または不等式として表現できることを示しています。以下に、次の形式の不等式を示します。${\displaystyle A\leq B}$はブール方程式の略記です${\displaystyle A\vee B=B}$。

この種の結果が最も網羅的にまとめられているのは、Carnap (1958) の第 C 章であり、そこで用いられている記法はこの項目の記法とはかなり異なっている。Suppes (1960) の第 3.2 章には、ZFC 定理として提示された、より少ない結果が含まれており、記法はこの項目の記法に似ている。Carnap も Suppes も、この項目のRAや等式を用いて結果を定式化していない。

RAのメタ数学については、TarskiとGivant（1987）で詳しく議論されており、Givant（2006）ではより簡潔に説明されている。

RAは、等号の置換と等号同士の置き換えのみを用いて操作される方程式のみで構成されています。これらの規則はどちらも、学校数学や抽象代数学全般においてよく知られたものです。したがって、RAの証明は、一般的な数理論理学とは異なり、すべての数学者にとって馴染みのある方法で行われます。

RAは、3つ以下の変数を含む任意の（論理的に同値な場合、まさにその）一階述語論理（FOL）式を表現できます。（与えられた変数は複数回量化できるため、変数を「再利用」することで量化子を任意に深く入れ子にすることができます。）驚くべきことに、このFOLの断片だけで、ペアノ算術と、これまで提案されたほぼすべての公理的集合論を表現するのに十分です。したがって、 RAは事実上、FOLとその結合子、量化子、ターンスタイル、モーダス・ポネンスを排除しながら、ほぼすべての数学を代数化する方法です。RAはペアノ算術と集合論を表現できるため、ゲーデルの不完全性定理が適用されます。RAは不完全であり、不完全であり、決定不能です。 （注： RAのブール代数断片は完全であり、決定可能です。）

クラスRRAを構成する表現可能な関係代数は、ある集合上の二項関係からなる関係代数と同型であり、 RA演算の意図された解釈の下で閉じている関係代数である。例えば擬初等クラスの方法を用いると、RRAが準多様体、すなわち普遍ホーン理論によって公理化可能であることが容易に示される。1950 年、ロジャー・リンドンは、 RAでは成り立たないがRRAでは成り立つ方程式の存在を証明した。したがって、 RRAによって生成される多様体は、多様体RAの適切な部分多様体である。1955 年、アルフレッド・タルスキは、 RRA自体が多様体であることを示した。1964 年、ドナルド・モンクは、定義により有限に公理化されているRAとは異なり、RRAには有限の公理化がないことを示した。

1. Any Boolean algebra can be turned into a RA by interpreting conjunction as composition (the monoid multiplication ${\displaystyle \bullet }$), i.e. ${\displaystyle x\bullet y}$ is defined as ${\displaystyle x\wedge y}$. This interpretation requires that converse interpret identity (${\displaystyle y{\breve {}}=y}$), and that both residuals ${\displaystyle y\backslash x}$ and ${\displaystyle x/y}$ interpret the conditional ${\displaystyle y\to x}$ (i.e., ${\displaystyle \neg y\vee x}$).
2. The motivating example of a relation algebra depends on the definition of a binary relation ${\displaystyle R}$ on a set ${\displaystyle X}$ as any subset ${\displaystyle R\subseteq X^{2}}$, where ${\displaystyle X^{2}}$ is the cartesian square of ${\displaystyle X}$. The power set${\displaystyle 2^{X^{2}}}$ consisting of all binary relations on ${\displaystyle X}$ is a Boolean algebra. While ${\displaystyle 2^{X^{2}}}$ can be made a relation algebra by taking ${\displaystyle R\bullet S=R\wedge S}$, as per example (1) above, the standard interpretation of ${\displaystyle \bullet }$ is instead ${\displaystyle x(R\bullet S)z=\exists y:xRy.ySz}$. That is, the ordered pair${\displaystyle (x,z)}$ belongs to the relation ${\displaystyle R\bullet S}$ just when there exists ${\displaystyle y\in X}$ such that ${\displaystyle (x,y)\in R}$ and ${\displaystyle (y,z)\in S}$. This interpretation uniquely determines ${\displaystyle R\backslash S}$ as consisting of all pairs ${\displaystyle (y,z)}$ such that for all ${\displaystyle x\in X}$, if ${\displaystyle xRy}$ then ${\displaystyle xSz}$. Dually, ${\displaystyle S/R}$ consists of all pairs ${\displaystyle (x,y)}$ such that for all ${\displaystyle z\in X}$, if ${\displaystyle yRz}$ then ${\displaystyle xSz}$. The translation ${\displaystyle R{\breve {}}=\neg (R\backslash \neg \mathbf {I} )}$ then establishes the converse ${\displaystyle R{\breve {}}}$ of ${\displaystyle R}$ as consisting of all pairs ${\displaystyle (y,x)}$ such that ${\displaystyle (x,y)\in R}$.
3. An important generalization of the previous example is the power set ${\displaystyle 2^{E}}$ where ${\displaystyle E\subseteq X^{2}}$ is any equivalence relation on the set ${\displaystyle X}$. This is a generalization because ${\displaystyle X^{2}}$ is itself an equivalence relation, namely the complete relation consisting of all pairs. While ${\displaystyle 2^{E}}$ is not a subalgebra of ${\displaystyle 2^{X^{2}}}$ when ${\displaystyle E\neq X^{2}}$ (since in that case it does not contain the relation ${\displaystyle X^{2}}$, the top element ${\displaystyle 1}$ being ${\displaystyle E}$ instead of ${\displaystyle X^{2}}$), it is nevertheless turned into a relation algebra using the same definitions of the operations. Its importance resides in the definition of a representable relation algebra as any relation algebra isomorphic to a subalgebra of the relation algebra ${\displaystyle 2^{E}}$ for some equivalence relation ${\displaystyle E}$ on some set. The previous section says more about the relevant metamathematics.
4. Let ${\displaystyle G}$ be a group. Then the power set ${\displaystyle 2^{G}}$ is a relation algebra with the obvious Boolean algebra operations, composition given by the product of group subsets, the converse by the inverse subset (${\displaystyle A^{-1}=\{a^{-1}\!:a\in A\}}$), and the identity by the singleton subset${\displaystyle \{e\}}$. There is a relation algebra homomorphism embedding ${\displaystyle 2^{G}}$ in ${\displaystyle 2^{G\times G}}$ which sends each subset ${\displaystyle A\subset G}$ to the relation ${\displaystyle R_{A}=\{(g,h)\in G\times G:h\in Ag\}}$. The image of this homomorphism is the set of all right-invariant relations on ${\displaystyle G}$.
5. 群の和または積が合成を解釈する場合、群の逆は逆を解釈し、群の恒等は${\displaystyle \mathbf {I} }$、そしてもし${\displaystyle R}$は一対一対応なので、${\displaystyle R{\breve {}}\bullet R=R\bullet R{\breve {}}=\mathbf {I} }$[ ^{3 ]}すると^​${\displaystyle L}$は群である。B4 - B7は群論のよく知られた定理となり、RA は群論とブール代数の適切な拡張となる。

ド・モルガンは1860 年にRAを創設したが、C.S. パースはそれをさらに発展させ、その哲学的力に魅了された。ド・モルガンとパースの研究は、エルンスト・シュレーダーが『講義録』第 3 巻(1890–1905 年)で与えた拡張され決定的な形で主に知られるようになった。プリンキピア・マテマティカはシュレーダーのRAに大きく依拠したが、彼を記法の発明者としてのみ認めた。1912 年に、アルヴィン・コルセルトは、量化子が 4 重にネストされた特定の式にはRAに相当するものが存在しないことを証明した。^{[ 4 ]}この事実により、タルスキ (1941 年) がそれについて書き始めるまでRAへの関心は薄れた。彼の弟子たちは今日までRAを発展させ続けている。タルスキは1970 年代にスティーブン・ギヴァントの助けを借りてRAに復帰した。この共同研究の結果、タルスキとギヴァントによるモノグラフ（1987年）が出版され、この分野における決定的な参考文献となった。RAの歴史については、マドックス（1991年、2006年）を参照のこと。

• RelMICS / コンピュータサイエンスにおける関係的手法（Wolfram Kahlが管理するWayback Machineに 2020 年 2 月 1 日にアーカイブ済み）
• Carsten Sinz: ARA / 関係代数のための自動定理証明者
• Stef Joosten、「Ampersandコンパイラを使用したプログラミング言語としての関係代数」、Journal of Logical and Algebraic Methods in Programming、第100巻、2018年4月、113～129ページ。（https://ampersandtarski.github.io/も参照）

• カルナップ、ルドルフ（1958）。記号論理学とその応用入門。ドーバー出版。
• Givant, Steven (2006). 「数学の基礎としての関係計算」. Journal of Automated Reasoning . 37 (4): 277–322 . doi : 10.1007/s10817-006-9062-x . S2CID 26324546 . 
• ハルモス、PR (1960)。素朴集合論。ヴァン・ノストランド。
• ヘンキン、レオン；タルスキ、アルフレッド；モンク、JD（1971）。円筒代数、第1部。ノースホランド。
• ヘンキン、レオン；タルスキ、アルフレッド；モンク、JD（1985）。円筒代数、第2部。ノースホランド。
• Hirsch, R.; Hodkinson, I. (2002).ゲームによる関係代数. 論理学と数学の基礎に関する研究. 第 147巻. Elsevier Science.
• Jónsson, Bjarni ; Tsinakis, Constantine (1993). "関係代数を残余ブール代数として扱う". Algebra Universalis . 30 (4): 469–78 . doi : 10.1007/BF01195378 . S2CID 120642402 . 
• マドックス、ロジャー（ 1991）。「関係計算の発展と公理化における関係代数の起源」 （PDF）。Studia Logica。50（3–4）：421–455。CiteSeerX 10.1.1.146.5668。doi ： 10.1007 / BF00370681。S2CID 12165812。  
• マドックス、ロジャー（2006）。関係代数。論理学と数学の基礎に関する研究。第 150巻。エルゼビア・サイエンス。ISBN 9780444520135。
• シャイン、ボリス・M. (1970)「関係代数と関数半群」、セミグループフォーラム1: 1–62
• シュミット、ギュンター（2010）。関係数学。ケンブリッジ大学出版局。
• サップス、パトリック（1972）[1960]。「第3章」。公理的集合論（ドーバー復刻 版）。ヴァン・ノストランド。
• タルスキ、アルフレッド（ 1941）。「関係の計算について」。記号論理学ジャーナル。6 （ 3）：73–89。doi：10.2307 / 2268577。JSTOR 2268577。S2CID 11899579。  
• タルスキ、アルフレッド；ギヴァント、スティーブン（1987）。変数を用いない集合論の形式化。プロビデンス、ロードアイランド州：アメリカ数学会。ISBN 9780821810415。

• 赤間洋二、川原康夫、古澤仁、「関係代数と表現定理から寓話を構築する」
• Richard Bird、Oege de Moor、Paul Hoogendijk、「リレーションとファンクターを使用したジェネリック プログラミング」 。
• RP de FreitasとViana、「結合子を持つ関係代数の完全性に関する結果」
• ピーター・ジプセン：
  • 関係代数
  • 「関係論とクリーネ代数の基礎」
  • 「関係代数のコンピュータ支援による調査」
  • 「残余束に対するゲンツェンシステムと決定可能性」
• ヴォーン・プラット：
  • 「二項関係計算の起源」。歴史的考察。
  • 「二項関係の第二法則」
• プリス、ウタ：
  • 「関係代数のFCA解釈」
  • 「関係代数とFCA」関連出版物およびソフトウェアへのリンク
• Kahl、Wolfram、Gunther Schmidt : Haskellで書かれたツールを使った（有限）関係代数の探求。Wayback Machineに2016年3月3日にアーカイブ済み、およびMcMaster UniversityのHaskellによる関係代数ツール、Wayback Machineに2019年10月1日にアーカイブ済み。