Tolerance relation: Difference between revisions - Wikipedia
Line 14:
=== As covers ===
A '''tolerance relation''' on an [[algebraic structure]] <math>(A,F)</math> is a [[cover (topology)|cover]] <math>\mathcal C</math> of <math>A</math> that satisfies the following three conditions.<ref name="ChajdaNiederle">{{cite journal|date=1976|doi=10.21136/CMJ.1976.101403|first1=Ivan|first2=Josef|first3=Bohdan|issn=0011-4642|issue=101|journal=Czechoslovak Mathematical Journal|language=en|last1=Chajda|last2=Niederle|last3=Zelinka|mr=0401561|pages=304–311|title=On existence conditions for compatible tolerances|volume=26|zbl=0333.08006|doi-access=free}}</ref>{{rp|page 307, Theorem 3}}
* For every <math>C\in\mathcal C</math> and <math>\mathcal S\subseteq\mathcal C</math>, if <math>\textstyle C\subseteq\bigcup\mathcal S</math>, then <math>\textstyle\bigcap\mathcal S\subseteq C</math>.
** In particular, no two distinct elements of <math>\mathcal C</math> are comparable. (To see this, take <math>\mathcal S=\{D\}</math>.)
Line 22:
=== Equivalence of the two definitions ===
Let <math>\sim</math> be a tolerance [[binary relation]] on an [[algebraic structure]] <math>(A,F)</math>. Let <math>A/{\sim}</math> be the family of [[maximal element|maximal]] subsets <math>C\subseteq A</math> such that <math>c\sim d</math> for every <math>c,d\in C</math>. Using graph theoretical terms, <math>A/{\sim}</math> is the set of all [[maximal clique]]s of the [[graph (discrete mathematics)|graph]] <math>(A,\sim)</math>. If <math>\sim</math> is a [[congruence relation]], <math>A/{\sim}</math> is just the [[quotient set]] of [[equivalence class]]es. Then <math>A/{\sim}</math> is a [[cover (topology)|cover]] of <math>A</math> and satisfies all the three conditions in the cover definition. (The last condition is shown using [[Zorn's lemma]].) Conversely, let <math>\mathcal C</math> be a [[cover (topology)|cover]] of <math>A</math> and suppose that <math>\mathcal C</math> forms a tolerance on <math>A</math>. Consider a [[binary relation]] <math>\sim_{\mathcal C}</math> on <math>A</math> for which <math>a\sim_{\mathcal C}b</math> if and only if <math>a,b\in C</math> for some <math>C\in\mathcal C</math>. Then <math>\sim_{\mathcal C}</math> is a tolerance on <math>A</math> as a [[binary relation]]. The map <math>{\sim}\mapsto A/{\sim}</math> is a [[one-to-one correspondence]] between the tolerances as [[binary relations]] and as [[cover (topology)|cover]]s whose inverse is <math>\mathcal C\mapsto{\sim_{\mathcal C}}</math>. Therefore, the two definitions are equivalent. A tolerance is [[transitive relation|transitive]] as a [[binary relation]] if and only if it is a [[partition of a set|partition]] as a [[cover (mathematics)|cover]]. Thus the two characterizations of [[congruence relation]]s also agree.
=== Quotient algebras over tolerance relations ===
Line 38:
== Examples ==
=== Sets ===
A [[set (mathematics)|set]] is an [[algebraic structure]] with no opeartionsoperations at all. In this case, tolerance relations are simply [[reflexive relation|reflexive]] [[symmetric relation]]s and it is trivial that the variety of sets is strongly tolerance factorable.
=== Groups ===
On a [[group (mathematics)|group]], every tolerance relation is a [[congruence relation]]. In particular, this is true for all [[algebraic structure]]s equippedthat withare groupgroups substructureswhen some of their operations are forgot, e.g. [[ring (mathematics)|ring]]s, [[vector space]]s, [[module (mathematics)|module]]s, [[Boolean algebra]]s, etc.<ref name="Schein">{{cite journal|date=1987|doi=10.1016/0012-365X(87)90194-4|first1=Boris M.|issn=0012-365X|journal=Discrete Mathematics|language=en|last1=Schein|mr=0887364|pages=253–262|title=Semigroups of tolerance relations|volume=64|zbl=0615.20045|doi-access=free}}</ref>{{rp|pages 261–262}} Therefore, the varieties of [[group (mathematics)|group]]s, [[ring (mathematics)|ring]]s, [[vector space]]s, [[module (mathematics)|module]]s and [[Boolean algebra]]s are also strongly tolerance factorable trivially.
=== Lattices ===
Line 50:
* If <math>a\sim b</math> and <math>a\le c,d\le b</math>, then <math>c\sim d</math>.
The variety of [[lattice (order)|lattice]]s is strongly tolerance factorable. That is, forgiven any [[lattice (order)|lattice]] <math>(L,\vee_L,\wedge_L)</math> and any tolerance relation <math>\sim</math> on <math>L</math>, for each <math>A,B\in L/{\sim}</math> there exist unique <math>A\vee_{L/{\sim}}B,A\wedge_{L/{\sim}}B\in L/{\sim}</math> such that
:<math>\{a\vee_Lb\colon a\in A,\;b\in B\}\subseteq A\vee_{L/{\sim}}B</math>
:<math>\{a\wedge_Lb\colon a\in A,\;b\in B\}\subseteq A\wedge_{L/{\sim}}B</math>
Line 83:
|zbl=1233.06001
|lccn=2011921250
}}</ref>{{rp|page 44, Theorem 22}}
In particular, we can form quotient lattices of [[distributive lattice]]s and [[modular lattice]]s over tolerance relations. However, unlike in the case of [[congruence relation]]s, the quotient lattices need not be distributive or modular again. In other words, the varieties of [[distributive lattice]]s and [[modular lattice]]s are tolerance factorable, but not strongly tolerance factorable.<ref name="Czédli" />{{rp|page 40}}<ref name="ChajdaRadeleczki" /> Actually, every subvariety of the variety of lattices is tolerance factorable, and the only strongly tolerance factorable subvariety other than itself is the trivial subvariety (consisting of one-element lattices),.<ref sincename="Czédli" />{{rp|40}} This is because every [[lattice (order)|lattice]] is [[isomorphic]] to a sublattice of a tolerancethe quotient lattice over a tolerance relation of a sublattice of a [[direct product]] of two-element lattices.<ref name="Czédli" />{{rp|page 40, Theorem 3}}
== See also ==