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é. A tolerance relation on an algebraic structure is usually defined to be a reflexive symmetric relation on that is compatible with every operation in . A tolerance relation can also be seen as a cover of 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 form an algebraic lattice under inclusion. Since every congruence relation is a tolerance relation, the congruence lattice is a subset of the tolerance lattice , but is not necessarily a sublattice of . A tolerance relation on an algebraic structure is a binary relation on that satisfies the following conditions. (Reflexivity) for all (Symmetry) if then for all (Compatibility) for each -ary operation and , if for each then . That is, the set is a subalgebra of the direct product of two . A congruence relation is a tolerance relation that is also transitive. A tolerance relation on an algebraic structure is a cover of that satisfies the following three conditions. For every and , if , then . In particular, no two distinct elements of are comparable. (To see this, take .) For every , if is not contained in any set in , then there is a two-element subset such that is not contained in any set in .