# Tolerance relation

Last updated

In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption of transitivity is dropped. [1] On a set, an 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. [2] Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré. [3]

## Definitions

A tolerance relation on an algebraic structure ${\displaystyle (A,F)}$ is usually defined to be a reflexive symmetric relation on ${\displaystyle A}$ that is compatible with every operation in ${\displaystyle F}$. A tolerance relation can also be seen as a cover of ${\displaystyle A}$ that satisfies certain conditions. The two definitions are equivalent, since for a fixed algebraic structure, the tolerance relations in the two definitions are in one-to-one correspondence. The tolerance relations on an algebraic structure ${\displaystyle (A,F)}$ form an algebraic lattice ${\displaystyle \operatorname {Tolr} (A)}$ under inclusion. Since every congruence relation is a tolerance relation, the congruence lattice ${\displaystyle \operatorname {Cong} (A)}$ is a subset of the tolerance lattice ${\displaystyle \operatorname {Tolr} (A)}$, but ${\displaystyle \operatorname {Cong} (A)}$ is not necessarily a sublattice of ${\displaystyle \operatorname {Tolr} (A)}$. [4]

### As binary relations

A tolerance relation on an algebraic structure ${\displaystyle (A,F)}$ is a binary relation ${\displaystyle \sim }$ on ${\displaystyle A}$ that satisfies the following conditions.

• (Reflexivity) ${\displaystyle a\sim a}$ for all ${\displaystyle a\in A}$
• (Symmetry) if ${\displaystyle a\sim b}$ then ${\displaystyle b\sim a}$ for all ${\displaystyle a,b\in A}$
• (Compatibility) for each ${\displaystyle n}$-ary operation ${\displaystyle f\in F}$ and ${\displaystyle a_{1},\dots ,a_{n},b_{1},\dots ,b_{n}\in A}$, if ${\displaystyle a_{i}\sim b_{i}}$ for each ${\displaystyle i=1,\dots ,n}$ then ${\displaystyle f(a_{1},\dots ,a_{n})\sim f(b_{1},\dots ,b_{n})}$. That is, the set ${\displaystyle \{(a,b)\colon a\sim b\}}$ is a subalgebra of the direct product ${\displaystyle A^{2}}$ of two ${\displaystyle A}$.

A congruence relation is a tolerance relation that is also transitive.

### As covers

A tolerance relation on an algebraic structure ${\displaystyle (A,F)}$ is a cover ${\displaystyle {\mathcal {C}}}$ of ${\displaystyle A}$ that satisfies the following three conditions. [5] :307,Theorem 3

• For every ${\displaystyle C\in {\mathcal {C}}}$ and ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {C}}}$, if ${\displaystyle \textstyle C\subseteq \bigcup {\mathcal {S}}}$, then ${\displaystyle \textstyle \bigcap {\mathcal {S}}\subseteq C}$.
• In particular, no two distinct elements of ${\displaystyle {\mathcal {C}}}$ are comparable. (To see this, take ${\displaystyle {\mathcal {S}}=\{D\}}$.)
• For every ${\displaystyle S\subseteq A}$, if ${\displaystyle S}$ is not contained in any set in ${\displaystyle {\mathcal {C}}}$, then there is a two-element subset ${\displaystyle \{s,t\}\subseteq S}$ such that ${\displaystyle \{s,t\}}$ is not contained in any set in ${\displaystyle {\mathcal {C}}}$.
• For every ${\displaystyle n}$-ary ${\displaystyle f\in F}$ and ${\displaystyle C_{1},\dots ,C_{n}\in {\mathcal {C}}}$, there is a ${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})\in {\mathcal {C}}}$ such that ${\displaystyle \{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})}$. (Such a ${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})}$ need not be unique.)

Every partition of ${\displaystyle A}$ satisfies the first two conditions, but not conversely. A congruence relation is a tolerance relation that also forms a set partition.

### Equivalence of the two definitions

Let ${\displaystyle \sim }$ be a tolerance binary relation on an algebraic structure ${\displaystyle (A,F)}$. Let ${\displaystyle A/{\sim }}$ be the family of maximal subsets ${\displaystyle C\subseteq A}$ such that ${\displaystyle c\sim d}$ for every ${\displaystyle c,d\in C}$. Using graph theoretical terms, ${\displaystyle A/{\sim }}$ is the set of all maximal cliques of the graph ${\displaystyle (A,\sim )}$. If ${\displaystyle \sim }$ is a congruence relation, ${\displaystyle A/{\sim }}$ is just the quotient set of equivalence classes. Then ${\displaystyle A/{\sim }}$ is a cover of ${\displaystyle A}$ and satisfies all the three conditions in the cover definition. (The last condition is shown using Zorn's lemma.) Conversely, let ${\displaystyle {\mathcal {C}}}$ be a cover of ${\displaystyle A}$ and suppose that ${\displaystyle {\mathcal {C}}}$ forms a tolerance on ${\displaystyle A}$. Consider a binary relation ${\displaystyle \sim _{\mathcal {C}}}$ on ${\displaystyle A}$ for which ${\displaystyle a\sim _{\mathcal {C}}b}$ if and only if ${\displaystyle a,b\in C}$ for some ${\displaystyle C\in {\mathcal {C}}}$. Then ${\displaystyle \sim _{\mathcal {C}}}$ is a tolerance on ${\displaystyle A}$ as a binary relation. The map ${\displaystyle {\sim }\mapsto A/{\sim }}$ is a one-to-one correspondence between the tolerances as binary relations and as covers whose inverse is ${\displaystyle {\mathcal {C}}\mapsto {\sim _{\mathcal {C}}}}$. Therefore, the two definitions are equivalent. A tolerance is transitive as a binary relation if and only if it is a partition as a cover. Thus the two characterizations of congruence relations also agree.

### Quotient algebras over tolerance relations

Let ${\displaystyle (A,F)}$ be an algebraic structure and let ${\displaystyle \sim }$ be a tolerance relation on ${\displaystyle A}$. Suppose that, for each ${\displaystyle n}$-ary operation ${\displaystyle f\in F}$ and ${\displaystyle C_{1},\dots ,C_{n}\in A/{\sim }}$, there is a unique ${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})\in A/{\sim }}$ such that

${\displaystyle \{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})}$

Then this provides a natural definition of the quotient algebra

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

of ${\displaystyle (A,F)}$ over ${\displaystyle \sim }$. In the case of congruence relations, the uniqueness condition always holds true and the quotient algebra defined here coincides with the usual one.

A main difference from congruence relations 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 that ${\displaystyle (A,F)}$ belongs to, so that the quotient algebra may fail to be a member of the variety again. Therefore, for a variety ${\displaystyle {\mathcal {V}}}$ of algebraic structures, we may consider the following two conditions. [4]

• (Tolerance factorability) for any ${\displaystyle (A,F)\in {\mathcal {V}}}$ and any tolerance relation ${\displaystyle \sim }$ on ${\displaystyle (A,F)}$, the uniqueness condition is true, so that the quotient algebra ${\displaystyle (A/{\sim },F/{\sim })}$ is defined.
• (Strong tolerance factorability) for any ${\displaystyle (A,F)\in {\mathcal {V}}}$ and any tolerance relation ${\displaystyle \sim }$ on ${\displaystyle (A,F)}$, the uniqueness condition is true, and ${\displaystyle (A/{\sim },F/{\sim })\in {\mathcal {V}}}$.

Every strongly tolerance factorable variety is tolerance factorable, but not vice versa.

## Examples

### Sets

A set is an algebraic structure with no operations at all. In this case, tolerance relations are simply reflexive symmetric relations and it is trivial that the variety of sets is strongly tolerance factorable.

### Groups

On a group, every tolerance relation is a congruence relation. In particular, this is true for all algebraic structures that are groups when some of their operations are forgot, e.g. rings, vector spaces, modules, Boolean algebras, etc. [6] :261–262 Therefore, the varieties of groups, rings, vector spaces, modules and Boolean algebras are also strongly tolerance factorable trivially.

### Lattices

For a tolerance relation ${\displaystyle \sim }$ on a lattice ${\displaystyle L}$, every set in ${\displaystyle L/{\sim }}$ is a convex sublattice of ${\displaystyle L}$. Thus, for all ${\displaystyle A\in L/{\sim }}$, we have

${\displaystyle A=\mathop {\uparrow } A\cap \mathop {\downarrow } A}$

In particular, the following results hold.

• ${\displaystyle a\sim b}$ if and only if ${\displaystyle a\vee b\sim a\wedge b}$.
• If ${\displaystyle a\sim b}$ and ${\displaystyle a\leq c,d\leq b}$, then ${\displaystyle c\sim d}$.

The variety of lattices is strongly tolerance factorable. That is, given any lattice ${\displaystyle (L,\vee _{L},\wedge _{L})}$ and any tolerance relation ${\displaystyle \sim }$ on ${\displaystyle L}$, for each ${\displaystyle A,B\in L/{\sim }}$ there exist unique ${\displaystyle A\vee _{L/{\sim }}B,A\wedge _{L/{\sim }}B\in L/{\sim }}$ such that

${\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}$

and the quotient algebra

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

is a lattice again. [7] [8] [9] :44,Theorem 22

In particular, we can form quotient lattices of distributive lattices and modular lattices over tolerance relations. However, unlike in the case of congruence relations, the quotient lattices need not be distributive or modular again. In other words, the varieties of distributive lattices and modular lattices are tolerance factorable, but not strongly tolerance factorable. [7] :40 [4] 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). [7] :40 This is because every lattice is isomorphic to a sublattice of the quotient lattice over a tolerance relation of a sublattice of a direct product of two-element lattices. [7] :40,Theorem 3

## Related Research Articles

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.

In mathematics, when the elements of some set have a notion of equivalence, then one may naturally split the set into equivalence classes. These equivalence classes are constructed so that elements and belong to the same equivalence class if, and only if, they are equivalent.

In mathematics, a filter or order filter is a special subset of a partially ordered set (poset). Filters appear in order and lattice theory, but can also be found in topology, from which they originate. The dual notion of a filter is an order ideal.

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

In mathematics, specifically abstract algebra, the isomorphism theorems are theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules, Lie algebras, and various other algebraic structures. In universal algebra, the isomorphism theorems can be generalized to the context of algebras and congruences.

In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure in the sense that algebraic operations done with equivalent elements will yield equivalent elements. Every congruence relation has a corresponding quotient structure, whose elements are the equivalence classes for the relation.

In mathematics, a Heyting algebra is a bounded lattice equipped with a binary operation ab of implication such that ≤ b is equivalent to c ≤. From a logical standpoint, AB is by this definition the weakest proposition for which modus ponens, the inference rule AB, AB, is sound. Like Boolean algebras, Heyting algebras form a variety axiomatizable with finitely many equations. Heyting algebras were introduced by Arend Heyting (1930) to formalize intuitionistic logic.

In mathematics, a quotient algebra is the result of partitioning the elements of an algebraic structure using a congruence relation. Quotient algebras are also called factor algebras. Here, the congruence relation must be an equivalence relation that is additionally compatible with all the operations of the algebra, in the formal sense described below. Its equivalence classes partition the elements of the given algebraic structure. The quotient algebra has these classes as its elements, and the compatibility conditions are used to give the classes an algebraic structure.

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets

In group theory, an inverse semigroupS is a semigroup in which every element x in S has a unique inversey in S in the sense that x = xyx and y = yxy, i.e. a regular semigroup in which every element has a unique inverse. Inverse semigroups appear in a range of contexts; for example, they can be employed in the study of partial symmetries.

In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum of denoted and similarly, the meet of is the infimum, denoted In general, the join and meet of a subset of a partially ordered set need not exist. Join and meet are dual to one another with respect to order inversion.

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

In mathematics, in the realm of group theory, a countable group is said to be SQ-universal if every countable group can be embedded in one of its quotient groups. SQ-universality can be thought of as a measure of largeness or complexity of a group.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

In mathematics, the congruence lattice problem asks whether every algebraic distributive lattice is isomorphic to the congruence lattice of some other lattice. The problem was posed by Robert P. Dilworth, and for many years it was one of the most famous and long-standing open problems in lattice theory; it had a deep impact on the development of lattice theory itself. The conjecture that every distributive lattice is a congruence lattice is true for all distributive lattices with at most 1 compact elements, but F. Wehrung provided a counterexample for distributive lattices with ℵ2 compact elements using a construction based on Kuratowski's free set theorem.

In abstract algebra, a skew lattice is an algebraic structure that is a non-commutative generalization of a lattice. While the term skew lattice can be used to refer to any non-commutative generalization of a lattice, since 1989 it has been used primarily as follows.

In mathematics, a cardinal function is a function that returns cardinal numbers.

In abstract algebra, a partially ordered ring is a ring, together with a compatible partial order, that is, a partial order on the underlying set A that is compatible with the ring operations in the sense that it satisfies:

In order theory, a continuous poset is a partially ordered set in which every element is the directed supremum of elements approximating it.

## References

1. Kearnes, Keith; Kiss, Emil W. (2013). The Shape of Congruence Lattices. American Mathematical Soc. p. 20. ISBN   978-0-8218-8323-5.
2. Sossinsky, Alexey (1986-02-01). "Tolerance space theory and some applications". Acta Applicandae Mathematicae . 5 (2): 137–167. doi:10.1007/BF00046585. S2CID   119731847.
3. Poincare, H. (1905). Science and Hypothesis (with a preface by J.Larmor ed.). New York: 3 East 14th Street: The Walter Scott Publishing Co., Ltd. pp.  22-23.{{cite book}}: CS1 maint: location (link)
4. Chajda, Ivan; Radeleczki, Sándor (2014). "Notes on tolerance factorable classes of algebras". Acta Scientiarum Mathematicarum. 80 (3–4): 389–397. doi:10.14232/actasm-012-861-x. ISSN   0001-6969. MR   3307031. S2CID   85560830. Zbl   1321.08002.
5. Chajda, Ivan; Niederle, Josef; Zelinka, Bohdan (1976). "On existence conditions for compatible tolerances". Czechoslovak Mathematical Journal. 26 (101): 304–311. doi:10.21136/CMJ.1976.101403. ISSN   0011-4642. MR   0401561. Zbl   0333.08006.
6. Schein, Boris M. (1987). "Semigroups of tolerance relations". Discrete Mathematics. 64: 253–262. doi:10.1016/0012-365X(87)90194-4. ISSN   0012-365X. MR   0887364. Zbl   0615.20045.
7. Czédli, Gábor (1982). "Factor lattices by tolerances". Acta Scientiarum Mathematicarum. 44: 35–42. ISSN   0001-6969. MR   0660510. Zbl   0484.06010.
8. Grätzer, George; Wenzel, G. H. (1990). "Notes on tolerance relations of lattices". Acta Scientiarum Mathematicarum. 54 (3–4): 229–240. ISSN   0001-6969. MR   1096802. Zbl   0727.06011.
9. Grätzer, George (2011). Lattice Theory: Foundation. Basel: Springer. doi:10.1007/978-3-0348-0018-1. ISBN   978-3-0348-0017-4. LCCN   2011921250. MR   2768581. Zbl   1233.06001.
• Gerasin, S. N., Shlyakhov, V. V., and Yakovlev, S. V. 2008. Set coverings and tolerance relations. Cybernetics and Sys. Anal. 44, 3 (May 2008), 333340. doi : 10.1007/s10559-008-9007-y
• Hryniewiecki, K. 1991, Relations of Tolerance, FORMALIZED MATHEMATICS, Vol. 2, No. 1, January–February 1991.