許容関係

普遍代数学と格子理論において、代数構造上の許容関係は、その構造のすべての演算と両立する反射対称関係である。したがって、許容関係は、推移性の仮定が取り除かれる点を除けば、合同関係に似ている。 ^{[1]演算の族が空である}代数構造である集合上では、許容関係は単に反射対称関係である。許容関係を持つ集合は、許容空間として記述できる。^{[2]許容関係は、}識別不能性/判別不能現象を研究するための便利な一般ツールとなる。数学におけるそれらの重要性は、ポアンカレによって初めて認識された。^[3]

定義

代数構造上の公差関係は通常、上の反射対称関係で のすべての演算と互換性があるものとして定義されます。公差関係は、特定の条件を満たすの被覆として見ることもできます。2つの定義は同値です。なぜなら、固定された代数構造に対して、2つの定義の公差関係は1対1 で対応しているからです。代数構造上の公差関係は、包含に関して代数格子を形成します。すべての合同関係は公差関係であるため、合同格子は公差格子 のサブセットですが、の部分格子とは必ずしもなりません。^[4] ${\displaystyle (A,F)}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle (A,F)}$ ${\displaystyle \operatorname {トール} (A)}$ ${\displaystyle \operatorname {Cong} (A)}$ ${\displaystyle \operatorname {トール} (A)}$ ${\displaystyle \operatorname {Cong} (A)}$ ${\displaystyle \operatorname {トール} (A)}$

二項関係として

代数構造上の許容関係は、次の条件を満たす 2 項関係です。 ${\displaystyle (A,F)}$ ${\displaystyle \sim}$ ${\displaystyle A}$

• （反射性）すべてに対して${\displaystyle a\sim a}$ ${\displaystyle a\in A}$
• （対称性）ならば、すべての${\displaystyle a\sim b}$ ${\displaystyle b\sim a}$ ${\displaystyle a,b\in A}$
• （互換性）各 - 項演算に対して が成り立ち、各 に対して が成り立つならば が成り立つ。つまり、この集合は2つの の直積の部分代数である。${\displaystyle n}$ ${\displaystyle f\in F}$ ${\displaystyle a_{1},\dots ,a_{n},b_{1},\dots ,b_{n}\in A}$ ${\displaystyle a_{i}\sim b_{i}}$ ${\displaystyle i=1,\dots ,n}$ ${\displaystyle f(a_{1},\dots ,a_{n})\sim f(b_{1},\dots ,b_{n})}$ ${\displaystyle \{(a,b)\colon a\sim b\}}$ ${\displaystyle A^{2}}$ ${\displaystyle A}$

合同関係は、推移的な許容関係でもあります。

カバーとして

代数構造上の許容関係とは、次の3つの条件を満たす被覆である。 ^{[5] ：307、定理3} ${\displaystyle (A,F)}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A}$

• あらゆるおよびについて、 であれば、 となります。 ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {C}}}$ ${\displaystyle \textstyle C\subseteq \bigcup {\mathcal {S}}}$ ${\displaystyle \textstyle \bigcap {\mathcal {S}}\subseteq C}$
  • 特に、 の 2 つの異なる要素は比較できません。(これを確認するには、 を例に挙げます。)${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {S}}=\{D\}}$
• 任意の について、が のどの集合にも含まれない場合、が のどの集合にも含まれない2要素の部分集合が存在します。${\displaystyle S\subseteq A}$ ${\displaystyle S}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle \{s,t\}\subseteq S}$ ${\displaystyle \{s,t\}}$ ${\displaystyle {\mathcal {C}}}$
• すべての-aryおよびに対して、となる が存在します。(このような は一意である必要はありません。)${\displaystyle n}$ ${\displaystyle f\in F}$ ${\displaystyle C_{1},\dots ,C_{n}\in {\mathcal {C}}}$ ${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})\in {\mathcal {C}}}$ ${\displaystyle \{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})}$ ${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})}$

の分割はすべて最初の2つの条件を満たしますが、その逆は成り立ちません。合同関係は、集合分割も形成する許容関係です。 ${\displaystyle A}$

2つの定義の同等性

を代数構造上の許容二項関係とします。を任意の に対してとなる極大部分集合の族とします。グラフ理論の用語を用いると、はグラフのすべての極大クリークの集合です。が合同関係である場合、は同値類の商集合に過ぎません。次にはの被覆であり、被覆定義の 3 つの条件をすべて満たします。(最後の条件はツォルンの補題を用いて示されます。)逆に、を の被覆とし、 が上に許容範囲を形成するとします。について であり、ある について である場合に限りとなる上の二項関係を考えます。次に は二項関係として上の許容範囲です。写像は、二項関係としての許容範囲と、その逆が となる被覆としての許容範囲との間の1対 1 対応です。したがって、2 つの定義は同値です。許容範囲が二項関係として推移的である場合、かつそれが被覆として分割である場合に限ります。したがって、合同関係の 2 つの特徴付けも一致します。 ${\displaystyle \sim}$ ${\displaystyle (A,F)}$ ${\displaystyle A/{\sim}}$ ${\displaystyle C\subseteq A}$ ${\displaystyle c\sim d}$ ${\displaystyle c,d\in C}$ ${\displaystyle A/{\sim}}$ ${\displaystyle (A,\sim )}$ ${\displaystyle \sim}$ ${\displaystyle A/{\sim}}$ ${\displaystyle A/{\sim}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A}$ ${\displaystyle \sim _{\mathcal {C}}}$ ${\displaystyle A}$ ${\displaystyle a\sim_{\mathcal {C}}b}$ ${\displaystyle a,b\in C}$ ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle \sim _{\mathcal {C}}}$ ${\displaystyle A}$ ${\displaystyle {\sim }\mapsto A/{\sim }}$ ${\displaystyle {\mathcal {C}}\mapsto {\sim _{\mathcal {C}}}}$

許容関係上の商代数

を代数構造とし、を上の許容関係とする。各- 項演算およびに対して、 が唯一存在し、 ${\displaystyle (A,F)}$ ${\displaystyle \sim}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle f\in F}$ ${\displaystyle C_{1},\dots ,C_{n}\in A/{\sim}}$ ${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})\in A/{\sim }}$

${\displaystyle \{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})}$

すると、これは商代数の自然な定義を与える。

${\displaystyle (A/{\sim},F/{\sim})}$

の を超える。合同関係の場合、一意性条件は常に成り立ち、ここで定義される商代数は通常のものと一致する。 ${\displaystyle (A,F)}$ ${\displaystyle \sim}$

合同関係との主な違いは、許容関係においては一意性条件が満たされない可能性があること、また、満たされない場合でも、商代数はその多様体を定義する恒等式を継承しない可能性があり、その結果、商代数は再びその多様体の元となることができない可能性があることである。したがって、代数構造多様体については、以下の2つの条件を考慮することができる。^[4]${\displaystyle (A,F)}$ ${\displaystyle {\mathcal {V}}}$

• (許容差因数分解可能) 任意のおよび 上の任意の許容差関係に対して、一意性条件が真であるため、商代数が定義されます。${\displaystyle (A,F)\in {\mathcal {V}}}$ ${\displaystyle \sim}$ ${\displaystyle (A,F)}$ ${\displaystyle (A/{\sim},F/{\sim})}$
• (強い許容差因数分解可能)および上の任意の許容差関係に対して、一意性条件は真であり、 です。${\displaystyle (A,F)\in {\mathcal {V}}}$ ${\displaystyle \sim}$ ${\displaystyle (A,F)}$ ${\displaystyle (A/{\sim},F/{\sim})\in {\mathcal{V}}}$

すべての強く許容差因数分解可能な多様体は許容差因数分解可能ですが、その逆は当てはまりません。

例

セット

集合は演算を全く含まない代数構造である。この場合、許容関係は単なる反射 対称関係であり、集合の多様体が強許容因数分解可能であることは自明である。

グループ

群上では、すべての許容関係は合同関係である。特に、環、ベクトル空間、加群、ブール代数など、いくつかの演算を省略した場合に群となるすべての代数構造について、このことが成り立つ。 ^{[6] : 261–262}したがって、群、環、ベクトル空間、加群、ブール代数の多様体もまた、自明に強許容因数分解可能である。

格子

格子上の公差関係 に対して、 内の任意の集合はの凸部分格子である。したがって、任意の に対して、 ${\displaystyle \sim}$ ${\displaystyle L}$ ${\displaystyle L/{\sim}}$ ${\displaystyle L}$ ${\displaystyle A\in L/{\sim}}$

${\displaystyle A=\mathop {\uparrow } A\cap \mathop {\downarrow } A}$

特に、以下の結果が当てはまります。

• ${\displaystyle a\sim b}$ の場合に限ります。${\displaystyle a\vee b\sim a\wedge b}$
• かつならば。​${\displaystyle a\sim b}$ ${\displaystyle a\leq c,d\leq b}$ ${\displaystyle c\sim d}$

格子多様体は強許容因数分解可能である。つまり、任意の格子 と上の任意の許容関係が与えられたとき、それぞれに対して、 ${\displaystyle (L,\vee _{L},\wedge _{L})}$ ${\displaystyle \sim}$ ${\displaystyle L}$ ${\displaystyle A,B\in L/{\sim}}$ ${\displaystyle A\vee _{L/{\sim }}B,A\wedge _{L/{\sim }}B\in L/{\sim }}$

${\displaystyle \{a\vee _{L}b\colon a\in A,\;b\in B\}\subseteq A\vee _{L/{\sim }}B}$

${\displaystyle \{a\wedge _{L}b\colon a\in A,\;b\in B\}\subseteq A\wedge _{L/{\sim }}B}$

そして商代数

${\displaystyle (L/{\sim },\vee _{L/{\sim }},\wedge _{L/{\sim }})}$

は再び格子である。^{[7] [8] [9] : 44、定理22}

特に、分配格子とモジュラー格子の商格子を許容関係上に作ることができる。しかし、合同関係の場合とは異なり、商格子は再び分配的またはモジュラーである必要はない。言い換えれば、分配格子とモジュラー格子の多様体は許容因数分解可能であるが、強く許容因数分解可能ではない。^{[7] : 40  [4]}実際には、格子多様体のすべての部分多様体は許容因数分解可能であり、それ自身以外の唯一の強く許容因数分解可能な部分多様体は（1要素格子からなる）自明部分多様体である。^{[7] : 40}これは、すべての格子が、2要素格子の直積の部分格子の許容関係上の商格子の部分格子に同型であるためである。^{[7] : 40、定理3}

参照

• 近似
• 依存関係
• 準推移関係— 社会選択理論における無関心を形式化する一般化
• ラフセット

参考文献

1. カーンズ、キース、キス、エミル・W. (2013).合同格子の形状. アメリカ数学会. p. 20. ISBN 978-0-8218-8323-5。
2. Sossinsky, Alexey (1986-02-01). 「許容空間理論といくつかの応用」. Acta Applicandae Mathematicae . 5 (2): 137– 167. doi :10.1007/BF00046585. S2CID  119731847.
3. ポアンカレ, H. (1905). 『科学と仮説』（J.ラーモア編序文付き）, ニューヨーク: 3 East 14th Street: The Walter Scott Publishing Co., Ltd., pp. 22-23.
4. チャジダ、イワン;ラデレツキ、サンダー (2014)。 「代数の公差因数分解クラスに関するメモ」。Acta Scientiarum 数学。80 ( 3–4 ): 389– 397.土井:10.14232/actasm-012-861-x。ISSN  0001-6969。MR  3307031。S2CID 85560830。Zbl 1321.08002  。 ​
5. チャジダ、イワン;ニーダーレ、ヨーゼフ。ゼリンカ、ボーダン (1976)。 「互換公差の存在条件について」。チェコスロバキアの数学ジャーナル。26 (101): 304–311。土井: 10.21136/CMJ.1976.101403。ISSN  0011-4642。MR  0401561。Zbl 0333.08006  。EuDML  12943。
6. Schein, Boris M. (1987). 「許容関係の半群」.離散数学. 64 ( 2–3 ): 253–262 . doi : 10.1016/0012-365X(87)90194-4 . ISSN  0012-365X. MR  0887364. Zbl  0615.20045.
7. チェドリ、ガボール (1982)。 「公差による格子の因数分解」。Acta Scientiarum 数学。44 : 35–42。ISSN 0001-6969  。​ MR  0660510。Zbl 0484.06010  。
8. ジョージ・グレーツァー;ウェンゼル、GH (1990)。 「格子の公差関係に関する注意事項」。Acta Scientiarum 数学。54 ( 3–4  ) : 229–240。ISSN 0001-6969 。MR  1096802。Zbl 0727.06011  。
9. Grätzer, George (2011). Lattice Theory: Foundation . Basel: Springer. doi :10.1007/978-3-0348-0018-1. ISBN 978-3-0348-0017-4LCCN  2011921250. MR  2768581. Zbl  1233.06001 .

さらに読む

• Gerasin, SN, Shlyakhov, VV, Yakovlev, SV 2008. 集合被覆と許容関係. サイバネティクスとシステム. アナル. 44, 3 (2008年5月), 333–340. doi :10.1007/s10559-008-9007-y
• Hryniewiecki, K. 1991、「許容関係」、FORMALIZED MATHEMATICS、第2巻、第1号、1991年1月～2月。