# Tolerance relation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Tolerance_relation
> Markdown URL: https://mediated.wiki/source/Tolerance_relation.md
> Source: https://en.wikipedia.org/wiki/Tolerance_relation
> Source revision: 1351310525
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Math relation that is reflexive and symmetric}}
In [universal algebra](/source/universal_algebra) and [lattice theory](/source/lattice_theory), a '''tolerance relation''' on an [algebraic structure](/source/algebraic_structure) is a [reflexive](/source/reflexive_relation) [symmetric relation](/source/symmetric_relation) that is compatible with all operations of the structure. Thus a tolerance is like a [congruence](/source/congruence_relation), except that the assumption of [transitivity](/source/transitive_relation) is dropped.<ref>{{cite book|first1=Keith|last1=Kearnes|first2=Emil W.|last2=Kiss|title=The Shape of Congruence Lattices|year=2013|publisher=American Mathematical Soc.|isbn=978-0-8218-8323-5|page=20}}
</ref> On a [set](/source/set_(mathematics)), an [algebraic structure](/source/algebraic_structure) with empty family of operations, tolerance relations are simply reflexive symmetric relations. A set that possesses a tolerance relation can be described as a '''tolerance space'''.<ref>{{Cite journal|last=Sossinsky|first=Alexey|date=1986-02-01|title=Tolerance space theory and some applications|url=https://www.researchgate.net/publication/225214345|journal=[Acta Applicandae Mathematicae](/source/Acta_Applicandae_Mathematicae)|volume=5|issue=2|pages=137–167|doi=10.1007/BF00046585|s2cid=119731847 }}</ref> Tolerance relations provide a convenient general tool for studying [indiscernibility](/source/indiscernibility)/indistinguishability phenomena. The importance of those for mathematics had been first recognized by [Poincaré](/source/Henri_Poincar%C3%A9).<ref>{{cite book|last1=Poincare|first1=H.|title=Science and Hypothesis|url=https://archive.org/details/scienceandhypoth00poinuoft|date=1905|publisher=The Walter Scott Publishing Co., Ltd.|edition=with a preface by J.Larmor|location=New York: 3 East 14th Street|pages=[https://archive.org/details/scienceandhypoth00poinuoft/page/22 22]-23}}</ref>

== Definitions ==
A '''tolerance relation''' on an [algebraic structure](/source/algebraic_structure) <math>(A,F)</math> is usually defined to be a [reflexive](/source/reflexive_relation) [symmetric relation](/source/symmetric_relation) on <math>A</math> that is compatible with every operation in <math>F</math>. A tolerance relation can also be seen as a [cover](/source/cover_(topology)) of <math>A</math> that satisfies certain conditions. The two definitions are equivalent, since for a fixed [algebraic structure](/source/algebraic_structure), the tolerance relations in the two definitions are in [one-to-one correspondence](/source/one-to-one_correspondence). The tolerance relations on an [algebraic structure](/source/algebraic_structure) <math>(A,F)</math> form an [algebraic lattice](/source/algebraic_lattice) <math>\operatorname{Tolr}(A)</math> under inclusion. Since every [congruence relation](/source/congruence_relation) is a tolerance relation, the congruence lattice <math>\operatorname{Cong}(A)</math> is a subset of the tolerance lattice <math>\operatorname{Tolr}(A)</math>, but <math>\operatorname{Cong}(A)</math> is not necessarily a sublattice of <math>\operatorname{Tolr}(A)</math>.<ref name="ChajdaRadeleczki">{{cite journal|date=2014|doi=10.14232/actasm-012-861-x|first1=Ivan|first2=Sándor|issn=0001-6969|issue=3–4|journal=Acta Scientiarum Mathematicarum|language=en|last1=Chajda|last2=Radeleczki|mr=3307031|pages=389–397|s2cid=85560830|title=Notes on tolerance factorable classes of algebras|volume=80|zbl=1321.08002}}</ref>

=== As binary relations ===
A '''tolerance relation''' on an [algebraic structure](/source/algebraic_structure) <math>(A,F)</math> is a [binary relation](/source/binary_relation) <math>\sim</math> on <math>A</math> that satisfies the following conditions.
* ([Reflexivity](/source/Reflexive_relation)) <math>a\sim a</math> for all <math>a\in A</math>
* ([Symmetry](/source/Symmetric_relation)) if <math>a\sim b</math> then <math>b\sim a</math> for all <math>a,b\in A</math>
* ([Compatibility](/source/Compatible_relation)) for each <math>n</math>-ary operation <math>f\in F</math> and <math>a_1,\dots,a_n,b_1,\dots,b_n\in A</math>, if <math>a_i\sim b_i</math> for each <math>i=1,\dots,n</math> then <math>f(a_1,\dots,a_n)\sim f(b_1,\dots,b_n)</math>. That is, the set <math>\{(a,b)\colon a\sim b\}</math> is a subalgebra of the [direct product](/source/direct_product) <math>A^2</math> of two <math>A</math>. 
A '''[congruence relation](/source/congruence_relation)''' is a tolerance relation that is also [transitive](/source/transitive_relation).

=== As covers ===
A '''tolerance relation''' on an [algebraic structure](/source/algebraic_structure) <math>(A,F)</math> is a [cover](/source/cover_(topology)) <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|id={{EuDML|12943}}|hdl=10338.dmlcz/101403|hdl-access=free}}</ref>{{rp|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>.)
* For every <math>S\subseteq A</math>, if <math>S</math> is not contained in any set in <math>\mathcal C</math>, then there is a two-element subset <math>\{s,t\}\subseteq S</math> such that <math>\{s,t\}</math> is not contained in any set in <math>\mathcal C</math>.
* For every <math>n</math>-ary <math>f\in F</math> and <math>C_1,\dots,C_n\in\mathcal C</math>, there is a <math>(f/{\sim})(C_1,\dots,C_n)\in\mathcal C</math> such that <math>\{f(c_1,\dots,c_n)\colon c_i\in C_i\}\subseteq(f/{\sim})(C_1,\dots,C_n)</math>. (Such a <math>(f/{\sim})(C_1,\dots,C_n)</math> need not be unique.)
Every [partition](/source/partition_of_a_set) of <math>A</math> satisfies the first two conditions, but not conversely. A '''[congruence relation](/source/congruence_relation)''' is a tolerance relation that also forms a set partition.

=== Equivalence of the two definitions ===
Let <math>\sim</math> be a tolerance [binary relation](/source/binary_relation) on an [algebraic structure](/source/algebraic_structure) <math>(A,F)</math>. Let <math>A/{\sim}</math> be the family of [maximal](/source/maximal_element) 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](/source/maximal_clique)s of the [graph](/source/graph_(discrete_mathematics)) <math>(A,\sim)</math>. If <math>\sim</math> is a [congruence relation](/source/congruence_relation), <math>A/{\sim}</math> is just the [quotient set](/source/quotient_set) of [equivalence class](/source/equivalence_class)es. Then <math>A/{\sim}</math> is a [cover](/source/cover_(topology)) of <math>A</math> and satisfies all the three conditions in the cover definition. (The last condition is shown using [Zorn's lemma](/source/Zorn's_lemma).) Conversely, let <math>\mathcal C</math> be a [cover](/source/cover_(topology)) of <math>A</math> and suppose that <math>\mathcal C</math> forms a tolerance on <math>A</math>. Consider a [binary relation](/source/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](/source/binary_relation). The map <math>{\sim}\mapsto A/{\sim}</math> is a [one-to-one correspondence](/source/one-to-one_correspondence) between the tolerances as [binary relations](/source/binary_relations) and as [cover](/source/cover_(topology))s whose inverse is <math>\mathcal C\mapsto{\sim_{\mathcal C}}</math>. Therefore, the two definitions are equivalent. A tolerance is [transitive](/source/transitive_relation) as a [binary relation](/source/binary_relation) if and only if it is a [partition](/source/partition_of_a_set) as a [cover](/source/cover_(mathematics)). Thus the two characterizations of [congruence relation](/source/congruence_relation)s also agree.

=== Quotient algebras over tolerance relations ===
Let <math>(A,F)</math> be an [algebraic structure](/source/algebraic_structure) and let <math>\sim</math> be a tolerance relation on <math>A</math>. Suppose that, for each <math>n</math>-ary operation <math>f\in F</math> and <math>C_1,\dots,C_n\in A/{\sim}</math>, there is a unique <math>(f/{\sim})(C_1,\dots,C_n)\in A/{\sim}</math> such that
:<math>\{f(c_1,\dots,c_n)\colon c_i\in C_i\}\subseteq(f/{\sim})(C_1,\dots,C_n)</math>
Then this provides a natural definition of the '''quotient algebra'''
:<math>(A/{\sim},F/{\sim})</math>
of <math>(A,F)</math> over <math>\sim</math>. In the case of [congruence relation](/source/congruence_relation)s, the uniqueness condition always holds true and the quotient algebra defined here coincides with the usual one.

A main difference from [congruence relation](/source/congruence_relation)s is that for a tolerance relation the uniqueness condition may fail, and even if it does not, the quotient algebra may not inherit the identities defining the [variety](/source/variety_(universal_algebra)) that <math>(A,F)</math> belongs to, so that the quotient algebra may fail to be a member of the variety again. Therefore, for a [variety](/source/variety_(universal_algebra)) <math>\mathcal V</math> of [algebraic structure](/source/algebraic_structure)s, we may consider the following two conditions.<ref name="ChajdaRadeleczki" />
* (Tolerance factorability) for any <math>(A,F)\in\mathcal V</math> and any tolerance relation <math>\sim</math> on <math>(A,F)</math>, the uniqueness condition is true, so that the quotient algebra <math>(A/{\sim},F/{\sim})</math> is defined.
* (Strong tolerance factorability) for any <math>(A,F)\in\mathcal V</math> and any tolerance relation <math>\sim</math> on <math>(A,F)</math>, the uniqueness condition is true, and <math>(A/{\sim},F/{\sim})\in\mathcal V</math>.
Every strongly tolerance factorable variety is tolerance factorable, but not vice versa.

== Examples ==
=== Sets ===
A [set](/source/set_(mathematics)) is an [algebraic structure](/source/algebraic_structure) with no operations at all. In this case, tolerance relations are simply [reflexive](/source/reflexive_relation) [symmetric relation](/source/symmetric_relation)s and it is trivial that the variety of sets is strongly tolerance factorable.

=== Groups ===
On a [group](/source/group_(mathematics)), every tolerance relation is a [congruence relation](/source/congruence_relation). In particular, this is true for all [algebraic structure](/source/algebraic_structure)s that are groups when some of their operations are forgot, e.g. [ring](/source/ring_(mathematics))s, [vector space](/source/vector_space)s, [module](/source/module_(mathematics))s, [Boolean algebra](/source/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|issue=2–3 |zbl=0615.20045|doi-access=free}}</ref>{{rp|261–262}} Therefore, the varieties of [group](/source/group_(mathematics))s, [ring](/source/ring_(mathematics))s, [vector space](/source/vector_space)s, [module](/source/module_(mathematics))s and [Boolean algebra](/source/Boolean_algebra)s are also strongly tolerance factorable trivially.

=== Lattices ===
For a tolerance relation <math>\sim</math> on a [lattice](/source/lattice_(order)) <math>L</math>, every set in <math>L/{\sim}</math> is a [convex sublattice](/source/convex_sublattice) of <math>L</math>. Thus, for all <math>A\in L/{\sim}</math>, we have
:<math>A=\mathop\uparrow A\cap\mathop\downarrow A</math>
In particular, the following results hold.
* <math>a\sim b</math> if and only if <math>a\vee b\sim a\wedge b</math>.
* 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](/source/lattice_(order))s is strongly tolerance factorable. That is, given any [lattice](/source/lattice_(order)) <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>
and the quotient algebra
:<math>(L/{\sim},\vee_{L/{\sim}},\wedge_{L/{\sim}})</math>
is a [lattice](/source/lattice_(order)) again.<ref name="Czédli">{{cite journal|date=1982|first=Gábor|issn=0001-6969|journal=Acta Scientiarum Mathematicarum|language=en|last=Czédli|mr=0660510|pages=35–42|title=Factor lattices by tolerances|volume=44|zbl=0484.06010}}</ref><ref name="GrätzerWenzel">{{cite journal
|first1=George
|last1=Grätzer
|first2=G. H.
|last2=Wenzel
|title=Notes on tolerance relations of lattices
|language=en
|journal=Acta Scientiarum Mathematicarum
|volume=54
|issue=3–4
|pages=229–240
|date=1990
|issn=0001-6969
|mr=1096802
|zbl=0727.06011
}}</ref><ref name="Grätzer">{{cite book
|first1=George
|last1=Grätzer
|title=Lattice Theory: Foundation
|language=en
|publisher=Springer
|location=Basel
|date=2011
|isbn=978-3-0348-0017-4
|doi=10.1007/978-3-0348-0018-1
|mr=2768581
|zbl=1233.06001
|lccn=2011921250
}}</ref>{{rp|44, Theorem 22}}

In particular, we can form quotient lattices of [distributive lattice](/source/distributive_lattice)s and [modular lattice](/source/modular_lattice)s over tolerance relations. However, unlike in the case of [congruence relation](/source/congruence_relation)s, the quotient lattices need not be distributive or modular again. In other words, the varieties of [distributive lattice](/source/distributive_lattice)s and [modular lattice](/source/modular_lattice)s are tolerance factorable, but not strongly tolerance factorable.<ref name="Czédli" />{{rp|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 name="Czédli" />{{rp|40}} This is because every [lattice](/source/lattice_(order)) is [isomorphic](/source/isomorphic) to a sublattice of the quotient lattice over a tolerance relation of a sublattice of a [direct product](/source/direct_product) of two-element lattices.<ref name="Czédli" />{{rp|40, Theorem 3}}

== See also ==
*[Approximation](/source/Approximation)
*[Dependency relation](/source/Dependency_relation)
*[Quasitransitive relation](/source/Quasitransitive_relation)&mdash;a generalization to formalize indifference in social choice theory
*[Rough set](/source/Rough_set)

==References==
{{Reflist}}

==Further reading==
*Gerasin, S. N., Shlyakhov, V. V., and Yakovlev, S. V. 2008. Set coverings and tolerance relations. Cybernetics and Sys. Anal. 44, 3 (May 2008), 333&ndash;340. {{doi|10.1007/s10559-008-9007-y}}
*Hryniewiecki, K. 1991, [http://mizar.org/fm/1991-2/pdf2-1/toler_1.pdf Relations of Tolerance], FORMALIZED MATHEMATICS, Vol. 2, No. 1, January–February  1991.

Category:Universal algebra
Category:Lattice theory
Category:Reflexive relations
Category:Symmetric relations
Category:Approximations

---
Adapted from the Wikipedia article [Tolerance relation](https://en.wikipedia.org/wiki/Tolerance_relation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Tolerance_relation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.