In
universal algebra and
lattice theory, a tolerance relation on an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
is a
reflexive symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X ...
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
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
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é.
Definitions
A tolerance relation on an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
is usually defined to be a
reflexive symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X ...
on
that is compatible with every operation in
. A tolerance relation can also be seen as a
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
of
that satisfies certain conditions. The two definitions are equivalent, since for a fixed
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
, the tolerance relations in the two definitions are in
one-to-one correspondence. The tolerance relations on an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
form an
algebraic lattice {{Unreferenced, date=December 2008
In the mathematical area of order theory, the compact elements or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not ...
under inclusion. Since every
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
is a tolerance relation, the congruence lattice
is a subset of the tolerance lattice
, but
is not necessarily a sublattice of
.
As binary relations
A tolerance relation on an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
on
that satisfies the following conditions.
* (
Reflexivity)
for all
* (
Symmetry) if
then
for all
* (
Compatibility
Compatibility may refer to:
Computing
* Backward compatibility, in which newer devices can understand data generated by older devices
* Compatibility card, an expansion card for hardware emulation of another device
* Compatibility layer, compon ...
) for each
-ary operation
and
, if
for each
then
. That is, the set
is a subalgebra of the
direct product
In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
of two
.
A
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
is a tolerance relation that is also
transitive.
As covers
A tolerance relation on an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
is a
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
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
.
* 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
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
is a tolerance relation that also forms a set partition.
Equivalence of the two definitions
Let
be a tolerance
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
on an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
. Let
be the family of
maximal subsets
such that
for every
. Using graph theoretical terms,
is the set of all
maximal clique
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is compl ...
s of the
graph . If
is a
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
,
is just the
quotient set
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of
equivalence classes. Then
is a
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
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
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
of
and suppose that
forms a tolerance on
. Consider a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
on
for which
if and only if
for some
. Then
is a tolerance on
as a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
. The map
is a
one-to-one correspondence between the tolerances as
binary relations
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
and as
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
s whose inverse is
. Therefore, the two definitions are equivalent. A tolerance is
transitive as a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
if and only if it is a
partition as a
cover
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of copy ...
. Thus the two characterizations of
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
s also agree.
Quotient algebras over tolerance relations
Let
be an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
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 relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
s, the uniqueness condition always holds true and the quotient algebra defined here coincides with the usual one.
A main difference from
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
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 that
belongs to, so that the quotient algebra may fail to be a member of the variety again. Therefore, for a
variety of
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
s, we may consider the following two conditions.
* (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
Sets
A
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
is an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
with no operations at all. In this case, tolerance relations are simply
reflexive symmetric relation
A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if:
:\forall a, b \in X ...
s and it is trivial that the variety of sets is strongly tolerance factorable.
Groups
On a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
, every tolerance relation is a
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
. In particular, this is true for all
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set ...
s that are groups when some of their operations are forgot, e.g.
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
s,
vector spaces,
module
Module, modular and modularity may refer to the concept of modularity. They may also refer to:
Computing and engineering
* Modular design, the engineering discipline of designing complex devices using separately designed sub-components
* Modul ...
s,
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
s, etc.
Therefore, the varieties of
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
s,
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
s,
vector spaces,
module
Module, modular and modularity may refer to the concept of modularity. They may also refer to:
Computing and engineering
* Modular design, the engineering discipline of designing complex devices using separately designed sub-components
* Modul ...
s and
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
s are also strongly tolerance factorable trivially.
Lattices
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.
In particular, we can form quotient lattices of
distributive lattices and
modular lattices over tolerance relations. However, unlike in the case of
congruence relation
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
s, 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
In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...
of two-element lattices.
See also
*
Dependency relation
*
Quasitransitive relation
The mathematical notion of quasitransitivity is a weakened version of transitivity that is used in social choice theory and microeconomics. Informally, a relation is quasitransitive if it is symmetric for some values and transitive elsewhere. The ...
—a generalization to formalize indifference in social choice theory
*
Rough set
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. {{doi, 10.1007/s10559-008-9007-y
*Hryniewiecki, K. 1991
Relations of Tolerance FORMALIZED MATHEMATICS, Vol. 2, No. 1, January–February 1991.
Universal algebra
Lattice theory
Reflexive relations
Symmetric relations
Approximations