相容关系

在泛代数和格理论中，相容关系（tolerance relation）是指被代数结构的每个运算所保持的自反对称关系。是同余关系去掉传递性的要求而得到的概念。

具体内容参考：左孝凌离散数学，石纯一数理逻辑与集合论，对“相容关系与覆盖”的再认识。注意，左孝凌和再认识一文对完全覆盖的定义是不同的，左文定义的完全覆盖和相容关系是一一对应的，而再认识一文定义的完全覆盖和相容关系不是一一对应的。

定义

代数结构${\displaystyle (A,F)}$ 上的相容关系通常定义为与${\displaystyle (A,F)}$ 的所有运算都兼容的自反对称关系，也可视为满足某些条件的${\displaystyle A}$ 的覆盖。可以证明两个定义是相互等价的。代数结构${\displaystyle (A,F)}$ 上的相容关系关于蕴涵构成代数格${\displaystyle \operatorname {Tolr} (A)}$ 。每个同余关系是相容关系，因此同余关系格${\displaystyle \operatorname {Cong} (A)}$ 是相容关系格${\displaystyle \operatorname {Tolr} (A)}$ 的一个子集，但${\displaystyle \operatorname {Cong} (A)}$ 不必是${\displaystyle \operatorname {Tolr} (A)}$ 的子格。^[1]

作为二元关系

代数结构${\displaystyle (A,F)}$ 上的相容关系定义为满足以下条件的${\displaystyle A}$ 上的二元关系${\displaystyle \sim }$ 。

• （自反性）对于任意${\displaystyle a\in A}$ ，有${\displaystyle a\sim a}$ 。
• （对称性）对于任意${\displaystyle a,b\in A}$ ，如果${\displaystyle a\sim b}$ ，那么有${\displaystyle b\sim a}$ 。
• （相容性）${\displaystyle \{(a,b)\colon a\sim b\}}$ 构成两个${\displaystyle A}$ 的直积${\displaystyle 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,F)}$ 上的相容关系定义为满足以下条件的${\displaystyle A}$ 的覆盖。^{[2]:307, Theorem 3}

• 对于任意${\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}$ 。
  • 特别地，${\displaystyle {\mathcal {C}}}$ 的任何两个不同元素是不可比较的。（取${\displaystyle {\mathcal {S}}=\{D\}}$ 。）
• 对于任意${\displaystyle S\subseteq A}$ ，如果${\displaystyle S}$ 不是${\displaystyle {\mathcal {C}}}$ 的元素的子集，存在二元素子集${\displaystyle \{s,t\}\subseteq S}$ 使得${\displaystyle \{s,t\}}$ 不是${\displaystyle {\mathcal {C}}}$ 的元素的子集。
• 对于每个${\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})}$ 不一定唯一。）

集合分划满足定义中的前两个条件，但是反之不然。同余关系定义为构成分划的相容关系。

两种定义的等价

相容关系作为二元关系和作为覆盖的定义是等价的。具体地，设${\displaystyle (A,F)}$ 是一个代数结构，${\displaystyle \sim }$ 是${\displaystyle A}$ 上的二元关系，并且是${\displaystyle A}$ 上的相容关系。记${\displaystyle A/{\sim }}$ 是由极大子集${\displaystyle C\subseteq }$ 使得对于每个${\displaystyle c,d\in C}$ 有${\displaystyle c\sim d}$ 所构成的集合。使用图论术语，${\displaystyle A/{\sim }}$ 是图${\displaystyle (A,\sim )}$ 的极大团的集合。在同余关系的情形下${\displaystyle A/{\sim }}$ 就是等价类组成的商集。那么，${\displaystyle A/{\sim }}$ 是${\displaystyle A}$ 的覆盖，并且满足作为覆盖定义中的三个条件。（最后一个条件可以使用佐恩引理予以证明。）反之，设${\displaystyle {\mathcal {C}}}$ 是${\displaystyle A}$ 的覆盖，并且作为覆盖构成相容关系。定义${\displaystyle A}$ 上的二元关系${\displaystyle \sim _{\mathcal {C}}}$ ，使得${\displaystyle a\sim _{\mathcal {C}}b}$ 当且仅当存在${\displaystyle C\in {\mathcal {C}}}$ 使得${\displaystyle a,b\in C}$ 。那么${\displaystyle \sim _{\mathcal {C}}}$ 作为二元关系构成${\displaystyle (A,F)}$ 上的相容关系。因此两种定义等价。一个相容关系作为二元关系是传递关系当且仅当作为覆盖是分划。所以同余关系的两种刻画也是一致的。

关于相容关系的商代数

设${\displaystyle (A,F)}$ 是代数结构，${\displaystyle \sim }$ 是其上的相容关系，并且设对于每个${\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,F)}$ 关于${\displaystyle \sim }$ 的商代数

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

对于同余关系，上面的唯一性条件必然成立，并且上面定义的商代数与通常的商代数是一致的。

与同余关系不同，对于相容关系，上面的唯一性条件不一定成立；即使成立，商代数${\displaystyle (A/{\sim },F/{\sim })}$ 不一定继承用来定义${\displaystyle (A,F)}$ 所属簇的恒等式，于是${\displaystyle (A/{\sim },F/{\sim })}$ 不一定仍然落入这个簇。因此，对于代数结构簇${\displaystyle {\mathcal {V}}}$ ，我们需要考虑它可能满足的以下两个条件。^[1]

• （相容可分解性）对于所有${\displaystyle (A,F)\in {\mathcal {V}}}$ 以及其上的相容关系${\displaystyle \sim }$ ，上面表述的唯一性条件成立。（从而可以定义商代数${\displaystyle (A/{\sim },F/{\sim })}$ 。)
• （强相容可分解性）对于所有${\displaystyle (A,F)\in {\mathcal {V}}}$ 以及其上的相容关系${\displaystyle \sim }$ ，上面表述的唯一性条件成立，并且有${\displaystyle (A/{\sim },F/{\sim })\in {\mathcal {V}}}$ 。

前者蕴涵后者，但是反之不一定成立。

例

集合

集合是没有任何运算的代数结构。此时，相容关系无非是集合上的自反对称关系。显然，集合簇是强相容可分解的。

群

在群中，所有相容关系是同余关系。特别地，对于那些具有群子结构的代数结构，如环、向量空间、模、布尔代数也是如此。^{[3]:261–262}因此，这些代数结构的簇也是强相容可分解的。

格

设${\displaystyle L}$ 是格，${\displaystyle \sim }$ 是其上的相容关系。那么${\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 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 }})}$ 

仍然构成格。^{[4][5][6]:44, Theorem 22}

特别地，分配格和模格关于相容关系的商格总是存在。但是这种商格不一定仍然构成分配格或模格。也就是说，分配格簇和模格簇是相容可分解的，但不是强相容可分解的。^[4]:40[1]其实，格簇的所有子簇是相容可分解的，但是格簇的强相容可分解子簇只有自身和由单元素格构成的平凡子簇。这是因为，所有格都同构于二元素格的直积的子格关于相容关系的商格的子格。^{[4]:40, Theorem 3}

参考文献

1. Chajda, Ivan; Radeleczki, Sándor. Notes on tolerance factorable classes of algebras. Acta Scientiarum Mathematicarum. 2014, 80 (3-4): 389–397. ISSN 0001-6969. MR 3307031. S2CID 85560830. Zbl 1321.08002. doi:10.14232/actasm-012-861-x （英语）. 
2. Chajda, Ivan; Niederle, Josef; Zelinka, Bohdan. On existence conditions for compatible tolerances. Czechoslovak Mathematical Journal. 1976, 26 (101): 304–311. ISSN 0011-4642. MR 0401561. Zbl 0333.08006. doi:10.21136/CMJ.1976.101403 （英语）. 
3. Schein, Boris M. Semigroups of tolerance relations. Discrete Mathematics. 1987, 64: 253–262. ISSN 0012-365X. MR 0887364. Zbl 0615.20045. doi:10.1016/0012-365X(87)90194-4 （英语）. 
4. Czédli, Gábor. Factor lattices by tolerances. Acta Scientiarum Mathematicarum. 1982, 44: 35–42. ISSN 0001-6969. MR 0660510. Zbl 0484.06010 （英语）. 
5. Grätzer, George; Wenzel, G. H. Notes on tolerance relations of lattices. Acta Scientiarum Mathematicarum. 1990, 54 (3-4): 229–240. ISSN 0001-6969. MR 1096802. Zbl 0727.06011 （英语）. 
6. Grätzer, George. Lattice Theory: Foundation. Basel: Springer. 2011. ISBN 978-3-0348-0017-4. LCCN 2011921250. MR 2768581. Zbl 1233.06001. doi:10.1007/978-3-0348-0018-1 （英语）.