相容關係

在泛代數和格理論中，相容關係（英語：tolerance relation）是指被代數結構的每個運算所保持的自反對稱關係。是同餘關係去掉遞移性的要求而得到的概念。

具體內容參考：左孝凌離散數學，石純一數理邏輯與集合論，對「相容關係與覆蓋」的再認識。注意，左孝凌和再認識一文對完全覆蓋的定義是不同的，左文定義的完全覆蓋和相容關係是一一對應的，而再認識一文定義的完全覆蓋和相容關係不是一一對應的。

定義

代數結構$(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}}$，我們需要考慮它可能滿足的以下兩個條件。

• （相容可分解性）對於所有$(A,F)\in {\mathcal {V}}$以及其上的相容關係$\sim$，上面表述的唯一性條件成立。（從而可以定義商代數$(A/{\sim },F/{\sim })$。)
• （強相容可分解性）對於所有$(A,F)\in {\mathcal {V}}$以及其上的相容關係$\sim$，上面表述的唯一性條件成立，並且有$(A/{\sim },F/{\sim })\in {\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\leq c,d\leq 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 _{L}b\colon a\in A,\;b\in B\}\subseteq A\vee _{L/{\sim }}B$

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

並且商代數

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

仍然構成格。

特別地，分配格和模格關於相容關係的商格總是存在。但是這種商格不一定仍然構成分配格或模格。也就是說，分配格簇和模格簇是相容可分解的，但不是強相容可分解的。其實，格簇的所有子簇是相容可分解的，但是格簇的強相容可分解子簇只有自身和由單元素格構成的平凡子簇。這是因為，所有格都同構於二元素格的直積的子格關於相容關係的商格的子格。