相容关系

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

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

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

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

• （自反性）对于任意a\in A，有a\sim a。
• （对称性）对于任意a,b\in A，如果a\sim b，那么有b\sim a。
• （相容性）\{(a,b)\colon a\sim b\}构成两个A的直积A^2的子代数。也就是说，对于每个n元运算f\in F以及a_1,\dots,a_n,b_1,\dots,b_n\in A，如果a_i\sim b_i对每个i=1,\dots,n成立，那么有f(a_1,\dots,a_n)\sim f(b_1,\dots,b_n)。

同余关系定义为传递的相容关系。

作为覆盖
代数结构(A,F)上的相容关系定义为满足以下条件的A的覆盖。

• 对于任意C\in\mathcal C以及\mathcal S\subseteq\mathcal C，如果\textstyle C\subseteq\bigcup\mathcal S，那么有\textstyle\bigcap\mathcal S\subseteq C。

** 特别地，\mathcal C的任何两个不同元素是不可比较的。（取\mathcal S=\{D\}。）

• 对于任意S\subseteq A，如果S不是\mathcal C的元素的子集，存在二元素子集\{s,t\}\subseteq S使得\{s,t\}不是\mathcal C的元素的子集。
• 对于每个n元运算f\in F以及C_1,\dots,C_n\in\mathcal C，存在(f/{\sim})(C_1,\dots,C_n)\in\mathcal C使得\{f(c_1,\dots,c_n)\colon c_i\in C_i\}\subseteq(f/{\sim})(C_1,\dots,C_n)。（这样的(f/{\sim})(C_1,\dots,C_n)不一定唯一。）

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

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

关于相容关系的商代数
设(A,F)是代数结构，\sim是其上的相容关系，并且设对于每个n元运算f\in F以及C_1,\dots,C_n\in A/{\sim}，存在唯一的(f/{\sim})(C_1,\dots,C_n)\in A/{\sim}使得有
:\{f(c_1,\dots,c_n)\colon c_i\in C_i\}\subseteq(f/{\sim})(C_1,\dots,C_n)
那么，这就自然地定义了(A,F)关于\sim的商代数
:(A/{\sim},F/{\sim})
对于同余关系，上面的唯一性条件必然成立，并且上面定义的商代数与通常的商代数是一致的。

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

格
设L是格，\sim是其上的相容关系。那么L/{\sim}的每个元素是L的凸子格。因此，对于每个A\in L/{\sim}，我们有
:A=\mathop\uparrow A\cap\mathop\downarrow A
特别地，下面结果成立。

• a\sim b当且仅当a\vee b\sim a\wedge b。
• 如果a\sim b并且a\le c,d\le b，那么c\sim d。

格簇是强相容可分解的。也就是说，给定格(L,\vee_L,\wedge_L)以及其上的相容关系\sim，对于任意A,B\in L/{\sim}，存在唯一的A\vee_{L/{\sim}}B,A\wedge_{L/{\sim}}B\in L/{\sim}满足
:\{a\vee_Lb\colon a\in A,\;b\in B\}\subseteq A\vee_{L/{\sim}}B
:\{a\wedge_Lb\colon a\in A,\;b\in B\}\subseteq A\wedge_{L/{\sim}}B
并且商代数
:(L/{\sim},\vee_{L/{\sim}},\wedge_{L/{\sim}})
仍然构成格。

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

参考文献