関係代数

Type of residuated Boolean algebra with extra structure

数学および抽象代数において、関係代数とは、単項演算である逆関数と呼ばれる反転によって拡張された剰余ブール代数 である。関係代数の代表的な例としては、集合（つまり直交座標の部分集合）上のすべての二項関係の代数が挙げられる。この場合、 は二項関係との通常の合成として解釈され、 の逆は逆関係として解釈される。 ${\displaystyle 2^{X^{2}}}$ ${\displaystyle X}$ ${\displaystyle X^{2}}$ ${\displaystyle R\bullet S}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle R}$

関係代数は、19世紀のオーガスタス・ド・モルガンとチャールズ・パースの研究で出現し、エルンスト・シュレーダーの代数論理学に結実しました。ここで扱う関係代数の方程式形式は、 1940年代からアルフレッド・タルスキとその弟子たちによって発展しました。タルスキとジヴァント（1987）は、関係代数を公理的集合論の変数フリーな扱いに適用し、集合論に基づく数学自体が変数なしで扱えることを示唆しました。

意味

関係代数は、 ブール演算の連言、選言、否定、ブール定数と、関係演算の合成と逆、関係定数を備えた代数構造であり、これらの演算と定数は、関係の計算の公理化を構成する特定の方程式を満たします。おおよそ、関係代数は、空( )、普遍( )、および恒等関係を含む集合上の2項関係の体系であり、これら5つの演算で閉じているのと同様に、群は、恒等置換を含み、合成と逆置換で閉じている集合の置換の体系です。ただし、関係代数の1階理論は、このような2項関係の体系に対しては完全ではありません。 ${\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} }$

Jónsson と Tsinakis (1993) に従うと、追加の演算、および双対的にを定義するのが便利です。Jónsson と Tsinakis は、 であり、両方とも に等しいことを示しました。したがって、関係代数は代数構造 としても同じように定義できます。通常のシグネチャに対するこのシグネチャの利点は、関係代数を が反転である剰余ブール代数、つまり として完全に定義できることです。後者の条件は、通常の算術逆数 の方程式の関係版と考えることができ、一部の著者は逆数を逆数の同義語として使用しています。 ${\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を形成する。上記の定義を方程式として展開すると、次の有限公理化が得られる。

公理

以下の公理B1-B10はGivant（2006: 283）から引用したもので、1948年にTarskiによって初めて提示されたものである^。[1]

${\displaystyle L}$は、二項論理和、、および単項補集合の下でのブール代数である。 ${\displaystyle \vee }$ ${\displaystyle ()^{-}}$

B1 : ${\displaystyle A\vee B=B\vee A}$

B2 : ${\displaystyle (A\vee B)\vee C=A\vee (B\vee C)}$

B3 : ${\displaystyle (A^{-}\vee B)^{-}\vee (A^{-}\vee B^{-})^{-}=A}$

このブール代数の公理化はハンティントン（1933）によるものです。暗黙のブール代数の は（のように に対して分配するにもかかわらず）作用素ではなく、ブール代数のも定数ではないことに注意してください。 ${\displaystyle \bullet }$ ${\displaystyle \vee }$ ${\displaystyle 1}$ ${\displaystyle \mathbf {I} }$

${\displaystyle L}$は二項合成（）と零項単位元のもとでモノイドである： ${\displaystyle \bullet }$ ${\displaystyle \mathbf {I} }$

B4 : ${\displaystyle (A\bullet B)\bullet C=A\bullet (B\bullet C)}$

B5 : ${\displaystyle A\bullet \mathrm {I} =A}$

単項逆は 合成に関する反転です。 ${\displaystyle (){\breve {}}}$

B6 : ${\displaystyle A{\breve {}}{\breve {}}=A}$

B7 : ${\displaystyle (A\bullet B){\breve {}}=B{\breve {}}\bullet A{\breve {}}}$

公理B6は転換を反転として定義し、公理B7は合成に対する転換の反分配的性質を表現している。 ^[2]

逆元と合成は選言に対して分配される：

B8 : ${\displaystyle (A\vee B){\breve {}}=A{\breve {}}\vee B{\breve {}}}$

B9 : ${\displaystyle (A\vee B)\bullet C=(A\bullet C)\vee (B\bullet C)}$

B10は、オーガスタス・ド・モルガンによって発見された事実のタルスキ方程式である。 ${\displaystyle A\bullet B\leq C^{-}\ \Leftrightarrow \ A{\breve {}}\bullet C\leq B^{-}\ \Leftrightarrow \ C\bullet B{\breve {}}\leq A^{-}}$

B10 : ${\displaystyle (A{\breve {}}\bullet (A\bullet B)^{-})\vee B^{-}=B^{-}}$

これらの公理はZFC定理である。純粋にブール的なB1-B3については、この事実は自明である。以下の公理の後に、ZFCの解説書であるSuppes (1960)の第3章における対応する定理の番号が示されている：B4 27、B5 45、B6 14、B7 26、B8 16、B9 23。

RAにおける二項関係の性質の表現

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

この種の結果の最も包括的なセットはCarnap (1958)のC章であるが、その表記法は本項目のものとはかなり異なっている。Suppes (1960)の第3.2章には、より少ない結果が含まれており、ZFC定理として提示され、本項目の表記法に近いものとなっている。CarnapもSuppesも、本項目のRAや方程式を用いて結果を定式化していない。

${\displaystyle R}$は	場合のみ：
機能的	${\displaystyle R{\breve {}}\bullet R\leq \mathbf {I} }$
左合計	${\displaystyle \mathbf {I} \leq R\bullet R{\breve {}}}$（は全射です） ${\displaystyle R{\breve {}}}$
関数	${\displaystyle R}$機能的かつ左合計です。
単射	${\displaystyle R\bullet R{\breve {}}\leq \mathbf {I} }$（機能的である） ${\displaystyle R{\breve {}}}$
射影的	${\displaystyle \mathbf {I} \leq R{\breve {}}\bullet R}$（左合計） ${\displaystyle R{\breve {}}}$
全単射	${\displaystyle R{\breve {}}\bullet R=R\bullet R{\breve {}}=\mathbf {I} }$（単射関数）
推移的	${\displaystyle R\bullet R\leq R}$
反射的	${\displaystyle \mathbf {I} \leq R}$
コア反射	${\displaystyle R\leq \mathbf {I} }$
非反射的	${\displaystyle R\wedge \mathbf {I} =0}$
対称的	${\displaystyle R=R{\breve {}}}$
反対称	${\displaystyle R\wedge R{\breve {}}\leq \mathbf {I} }$
非対称	${\displaystyle R\wedge R{\breve {}}=0}$
強くつながっている	${\displaystyle R\vee R{\breve {}}=1}$
接続	${\displaystyle \mathbf {I} \vee R\vee R{\breve {}}=1}$
べき等性	${\displaystyle R\bullet R=R}$
予約注文	${\displaystyle R}$推移的かつ再帰的です。
等価	${\displaystyle R}$対称的な先行順序です。
半順序	${\displaystyle R}$は反対称順序です。
合計注文	${\displaystyle R}$強く連結されており、半順序です。
厳密な半順序	${\displaystyle R}$推移的かつ非反射的です。
厳密な全順序	${\displaystyle R}$連結されており、厳密な半順序です。
密集	${\displaystyle R\wedge \mathbf {I} ^{-}\leq (R\wedge \mathbf {I} ^{-})\bullet (R\wedge \mathbf {I} ^{-})}$

表現力

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には有限の公理化がないことを示しました。

Q関係代数

RAがQ 関係代数 ( QRA ) であるとは、 B1-B10に加えて、次のようなものとが存在する場合です(Tarski and Givant 1987: §8.4)。 ${\displaystyle A}$ ${\displaystyle B}$

質問0： ${\displaystyle A{\breve {}}\bullet A\leq \mathbf {I} }$

質問1： ${\displaystyle B{\breve {}}\bullet B\leq \mathbf {I} }$

質問2： ${\displaystyle A{\breve {}}\bullet B=1}$

これらの公理は本質的に、宇宙が（非射影的な）対関係を持ち、その射影が とであることを示唆している。すべてのQRAはRRAであるという定理がある（証明：Maddux、Tarski & Givant 1987: 8.4(iii)参照）。 ${\displaystyle A}$ ${\displaystyle B}$

すべてのQRAは表現可能である（Tarski and Givant 1987）。すべての関係代数が表現可能ではないという点は、 RAがQRAやブール代数と根本的に異なる点である。ストーンのブール代数表現定理によれば、ブール代数は、和集合、積集合、補集合に関して閉じた、ある集合の部分集合の集合として常に表現可能である。

例

1. 任意のブール代数は、連言 を合成（モノイド乗法）と解釈することでRAに変換できます。つまり、 はと定義されます。この解釈では、逆元 が恒等式（ ）を解釈し、残差 と の両方が条件文 （ ）を解釈することが必要です。 ${\displaystyle \bullet }$ ${\displaystyle x\bullet y}$ ${\displaystyle x\wedge y}$ ${\displaystyle y{\breve {}}=y}$ ${\displaystyle y\backslash x}$ ${\displaystyle x/y}$ ${\displaystyle y\to x}$ ${\displaystyle \neg y\vee x}$
2. 関係代数の動機となる例は、集合 上の二項関係を任意の部分集合 として定義することに依存し、ここで はの直角二乗である。上のすべての二項関係からなるべき集合 はブール代数である。 は、上記の例 (1) のようにを取ることで関係代数にすることができるが、 の標準的な解釈は ではなく である。つまり、順序付きペアは、かつ が存在するときにのみ関係に属する。この解釈により、 は、すべての に対して のとき となるすべてのペアから成ると一意に決定される。双対的に、 は、に対してのときとなるすべてのペアから成る。次に、変換によりの逆がとなるすべてのペアから成ると確立される。 ${\displaystyle R}$ ${\displaystyle X}$ ${\displaystyle R\subseteq X^{2}}$ ${\displaystyle X^{2}}$ ${\displaystyle X}$ ${\displaystyle 2^{X^{2}}}$ ${\displaystyle X}$ ${\displaystyle 2^{X^{2}}}$ ${\displaystyle R\bullet S=R\wedge S}$ ${\displaystyle \bullet }$ ${\displaystyle x(R\bullet S)z=\exists y:xRy.ySz}$ ${\displaystyle (x,z)}$ ${\displaystyle R\bullet S}$ ${\displaystyle y\in X}$ ${\displaystyle (x,y)\in R}$ ${\displaystyle (y,z)\in S}$ ${\displaystyle R\backslash S}$ ${\displaystyle (y,z)}$ ${\displaystyle x\in X}$ ${\displaystyle xRy}$ ${\displaystyle xSz}$ ${\displaystyle S/R}$ ${\displaystyle (x,y)}$ ${\displaystyle z\in X}$ ${\displaystyle yRz}$ ${\displaystyle xSz}$ ${\displaystyle R{\breve {}}=\neg (R\backslash \neg \mathbf {I} )}$ ${\displaystyle R{\breve {}}}$ ${\displaystyle R}$ ${\displaystyle (y,x)}$ ${\displaystyle (x,y)\in R}$
3. 前の例の重要な一般化は、集合 上の任意の同値関係であるべきべき集合 です。 はそれ自身同値関係、すなわちすべてのペアからなる完全な関係であるため、一般化となります。 は のとき部分代数ではありませんが(その場合、関係 は含まれず、最上位要素はの代わりに になるため)、それでも同じ演算定義を使用して関係代数に変換されます。 その重要性は、表現可能な関係代数を、何らかの集合上の何らかの同値関係に対する関係代数の部分代数に同型な任意の関係代数として定義することにあります。 前のセクションでは、関連するメタ数学についてさらに詳しく説明しました。 ${\displaystyle 2^{E}}$ ${\displaystyle E\subseteq X^{2}}$ ${\displaystyle X}$ ${\displaystyle X^{2}}$ ${\displaystyle 2^{E}}$ ${\displaystyle 2^{X^{2}}}$ ${\displaystyle E\neq X^{2}}$ ${\displaystyle X^{2}}$ ${\displaystyle 1}$ ${\displaystyle E}$ ${\displaystyle X^{2}}$ ${\displaystyle 2^{E}}$ ${\displaystyle E}$
4. を群とする。すると、冪集合は、明らかなブール代数演算を伴う関係代数となる。すなわち、合成は群部分集合の積によって与えられ、逆は逆部分集合( )によって与えられ、恒等演算は単集合部分集合によって与えられる。には、各部分集合を関係 に送る関係代数準同型埋め込みが存在する。この準同型の像は、 上のすべての右不変関係の集合である。 ${\displaystyle G}$ ${\displaystyle 2^{G}}$ ${\displaystyle A^{-1}=\{a^{-1}\!:a\in A\}}$ ${\displaystyle \{e\}}$ ${\displaystyle 2^{G}}$ ${\displaystyle 2^{G\times G}}$ ${\displaystyle A\subset G}$ ${\displaystyle R_{A}=\{(g,h)\in G\times G:h\in Ag\}}$ ${\displaystyle G}$
5. 群の和や積が合成を解釈し、群の逆が逆を解釈し、群の恒等が を解釈し、が1対1対応である場合、となるので、^[3]は群である。B4 - B7は群論のよく知られた定理となり、RA は群論だけでなくブール代数の適切な拡張となる。 ${\displaystyle \mathbf {I} }$ ${\displaystyle R}$ ${\displaystyle R{\breve {}}\bullet R=R\bullet R{\breve {}}=\mathbf {I} }$ ${\displaystyle L}$

歴史的考察

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

ソフトウェア

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

参照

• 代数論理
• 寓話（カテゴリー理論）
• 二項関係
• デカルト積
• デカルト正方形
• 円筒代数
• 論理の拡張
• 退縮
• 親族の論理
• 論理マトリックス
• 述語関数論理
• クアンターレ
• 関係
• 関係構築
• 関係計算
• 関係代数
• 剰余ブール代数
• 空間的・時間的推論
• 関係理論
• 三者関係

脚注

1. Alfred Tarski (1948)「概要:関係代数の表現問題」、 Bulletin of the AMS 54: 80。
2. クリス・ブリンク;ヴォルフラム・カール。ギュンター・シュミット (1997)。コンピューターサイエンスにおけるリレーショナル手法。スプリンガー。ページ 4 および8。ISBN 978-3-211-82971-4。
3. タルスキ、A.（1941）、87ページ。
4. コーセルト氏は自身の発見を公表しなかった。この理論は、 Leopold Loewenheim (1915)「Über Möglichkeiten im Relativkalkül」、 Mathematische Annalen 76: 447–470に初めて掲載されました。 Jean van Heijenoort、1967 年に「親戚の微積分における可能性について」として翻訳。数学的論理のソースブック、1879 ～ 1931 年。ハーバード大学押す: 228–251。

参考文献

• カルナップ、ルドルフ（1958年）『記号論理学とその応用入門』ドーバー出版。
• ギヴァント、スティーブン (2006). 「数学の基礎としての関係計算」.自動推論ジャーナル. 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巻. エルゼビア・サイエンス.
• 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). 『変数を使わない集合論の形式化』 プロビデンス RI: アメリカ数学会. ISBN 9780821810415。

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Relation_algebra&oldid=1321592105"