Tolerance relation

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. 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. Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré.

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. 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. Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré. (Compatibility) for each n -ary operation f\in F and a_1,\dots,a_n,b_1,\dots,b_n\in A , if a_i\sim b_i for each i=1,\dots,n then f(a_1,\dots,a_n)\sim f(b_1,\dots,b_n) . That is, the set \{(a,b)\colon a\sim b\} is a subalgebra of the direct product A^2 of two A . A congruence relation is a tolerance relation that is also transitive. In particular, no two distinct elements of \mathcal C are comparable. (To see this, take \mathcal S=\{D\} .) For every S\subseteq A , if S is not contained in any set in \mathcal C , then there is a two-element subset \{s,t\}\subseteq S such that \{s,t\} is not contained in any set in \mathcal C . For every n -ary f\in F and C_1,\dots,C_n\in\mathcal C , there is a (f/{\sim})(C_1,\dots,C_n)\in\mathcal C such that \{f(c_1,\dots,c_n)\colon c_i\in C_i\}\subseteq(f/{\sim})(C_1,\dots,C_n) . (Such a (f/{\sim})(C_1,\dots,C_n) need not be unique.) Every partition of A satisfies the first two conditions, but not conversely. A congruence relation is a tolerance relation that also forms a set partition. A=\mathop\uparrow A\cap\mathop\downarrow A In particular, the following results hold. a\sim b if and only if a\vee b\sim a\wedge b . If a\sim b and a\le c,d\le b , then c\sim d . The variety of lattices is strongly tolerance factorable. That is, given any lattice (L,\vee_L,\wedge_L) and any tolerance relation \sim on L , for each A,B\in L/{\sim} there exist unique A\vee_{L/{\sim}}B,A\wedge_{L/{\sim}}B\in L/{\sim} such that \{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 and the quotient algebra (L/{\sim},\vee_{L/{\sim}},\wedge_{L/{\sim}}) is a lattice again. 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. 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). 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. ==References== ==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–340. Hryniewiecki, K. 1991, Relations of Tolerance, FORMALIZED MATHEMATICS, Vol. 2, No. 1, January–February 1991.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1351310525 under CC BY-SA 4.0; modifications have been made.