In
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
and
lattice theory
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 (also called a least upper bou ...
, 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 of ...
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 of ...
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
The identity of indiscernibles is an ontological principle that states that there cannot be separate objects or entities that have all their properties in common. That is, entities ''x'' and ''y'' are identical if every predicate possessed by ''x'' ...
/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 of ...
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 co ...
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 of ...
, the tolerance relations in the two definitions are in
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
. 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 of ...
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 of ...
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
on
that satisfies the following conditions.
* (
Reflexivity)
for all
* (
Symmetry
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
) 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
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 ta ...
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 of ...
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 co ...
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
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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 of ...
. 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 comple ...
s of the
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
. 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 a ...
of
equivalence class
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 a ...
es. 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 co ...
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 co ...
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
. The map
is a
one-to-one correspondence
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
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 in ...
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 co ...
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 Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
if and only if it is a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
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 co ...
. 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 of ...
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
Variety may refer to:
Arts and entertainment Entertainment formats
* Variety (radio)
* Variety show, in theater and television
Films
* ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont
* ''Variety'' (1935 film), ...
that
belongs to, so that the quotient algebra may fail to be a member of the variety again. Therefore, for a
variety
Variety may refer to:
Arts and entertainment Entertainment formats
* Variety (radio)
* Variety show, in theater and television
Films
* ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont
* ''Variety'' (1935 film), ...
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 of ...
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 of ...
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 of ...
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 space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s,
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
* Mo ...
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 in e ...
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 space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s,
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
* Mo ...
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 in e ...
s are also strongly tolerance factorable trivially.
Lattices
For a tolerance relation
on a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
, 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
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
s is strongly tolerance factorable. That is, given any
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
and any tolerance relation
on
, for each
there exist unique
such that
:
:
and the quotient algebra
:
is a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
again.
In particular, we can form quotient lattices of
distributive lattice
In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...
s and
modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice (order), lattice that satisfies the following self-duality (order theory), dual condition,
;Modular law: implies
where are arbitrary elements in the lattice, &nbs ...
s 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 lattice
In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...
s and
modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice (order), lattice that satisfies the following self-duality (order theory), dual condition,
;Modular law: implies
where are arbitrary elements in the lattice, &nbs ...
s 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
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
is
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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 ta ...
of two-element lattices.
See also
*
Dependency relation
In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain \Sigma, symmetric, and reflexive; i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs D, such t ...
*
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. Th ...
—a generalization to formalize indifference in social choice theory
*
Rough set
In computer science, a rough set, first described by Polish computer scientist Zdzisław I. Pawlak, is a formal approximation of a crisp set (i.e., conventional set) in terms of a pair of sets which give the ''lower'' and the ''upper'' approximati ...
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