Jump to content

Tolerance relation

From Wikipedia, the free encyclopedia

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

[edit]

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 .[4]

As binary relations

[edit]

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.

As covers

[edit]

A tolerance relation on an algebraic structure is a cover of that satisfies the following three conditions.[5]: 307, Theorem 3 

  • 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 .
  • For every -ary and , there is a such that . (Such a need not be unique.)

Every partition of 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

[edit]

Let be a tolerance binary relation on an algebraic structure . Let be the family of maximal subsets such that for every . Using graph theoretical terms, is the set of all maximal cliques of the graph . If is a congruence relation, is just the quotient set of equivalence classes. Then is a cover of and satisfies all the three conditions in the cover definition. (The last condition is shown using Zorn's lemma.) Conversely, let be a cover of and suppose that forms a tolerance on . Consider a binary relation on for which if and only if for some . Then is a tolerance on as a binary relation. The map is a one-to-one correspondence between the tolerances as binary relations and as covers whose inverse is . 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

[edit]

Let be an algebraic structure and let be a tolerance relation on . Suppose that, for each -ary operation and , there is a unique such that

Then this provides a natural definition of the quotient algebra

of over . 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 belongs to, so that the quotient algebra may fail to be a member of the variety again. Therefore, for a variety of algebraic structures, we may consider the following two conditions.[4]

  • (Tolerance factorability) for any and any tolerance relation on , the uniqueness condition is true, so that the quotient algebra is defined.
  • (Strong tolerance factorability) for any and any tolerance relation on , the uniqueness condition is true, and .

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

Examples

[edit]

Sets

[edit]

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

[edit]

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

[edit]

For a tolerance relation on a lattice , every set in is a convex sublattice of . Thus, for all , we have

In particular, the following results hold.

  • if and only if .
  • If and , then .

The variety of lattices is strongly tolerance factorable. That is, given any lattice and any tolerance relation on , for each there exist unique such that

and the quotient algebra

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 

See also

[edit]

References

[edit]
  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. ^ a b c 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. ^ a b c d 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.

Further reading

[edit]
  • 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. doi:10.1007/s10559-008-9007-y
  • Hryniewiecki, K. 1991, Relations of Tolerance, FORMALIZED MATHEMATICS, Vol. 2, No. 1, January–February 1991.