In
mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) is a
homogeneous binary relation that is
symmetric
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 definiti ...
and
transitive. If the relation is also
reflexive, then the relation is an
equivalence relation.
Definition
Formally, a relation
on a set
is a PER if it holds for all
that:
# if
, then
(symmetry)
# if
and
, then
(transitivity)
Another more intuitive definition is that
on a set
is a PER if there is some subset
of
such that
and
is an
equivalence relation on
. The two definitions are seen to be equivalent by taking
.
Properties and applications
The following properties hold for a partial equivalence relation
on a set
:
*
is an equivalence relation on the subset
.
[By construction, is reflexive on and therefore an equivalence relation on .]
*
difunctional: the relation is the set
for two
partial function
In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
s
and some indicator set
* right and left
Euclidean: For
,
and
implies
and similarly for left Euclideanness
and
imply
*
quasi-reflexive: If
and
, then
and
.
[This follows since if , then by symmetry, so and by transitivity. It is also a consequence of the Euclidean properties.]
None of these properties is sufficient to imply that the relation is a PER.
[For the equivalence relation, consider the set and the relation . is an equivalence relation on but not a PER on since it is neither symmetric (, but not ) nor transitive ( and , but not ). For Euclideanness, ''xRy'' on natural numbers, defined by 0 ≤ ''x'' ≤ ''y''+1 ≤ 2, is right Euclidean, but neither symmetric (since e.g. 2''R''1, but not 1''R''2) nor transitive (since e.g. 2''R''1 and 1''R''0, but not 2''R''0).]
In non-set-theory settings
In
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a fou ...
,
constructive mathematics
In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...
and their applications to
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, constructing analogues of subsets is often problematic—in these contexts PERs are therefore more commonly used, particularly to define
setoid
In mathematics, a setoid (''X'', ~) is a set (or type) ''X'' equipped with an equivalence relation ~. A setoid may also be called E-set, Bishop set, or extensional set.
Setoids are studied especially in proof theory and in type-theoretic fou ...
s, sometimes called partial setoids. Forming a partial setoid from a type and a PER is analogous to forming subsets and quotients in classical set-theoretic mathematics.
The algebraic notion of
congruence can also be generalized to partial equivalences, yielding the notion of
subcongruence, i.e. a
homomorphic relation that is symmetric and transitive, but not necessarily reflexive.
Examples
A simple example of a PER that is ''not'' an equivalence relation is the
empty relation
In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
, if
is not empty.
Kernels of partial functions
If
is a
partial function
In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
on a set
, then the relation
defined by
:
if
is defined at
,
is defined at
, and
is a partial equivalence relation, since it is clearly symmetric and transitive.
If
is undefined on some elements, then
is not an equivalence relation. It is not reflexive since if
is not defined then
— in fact, for such an
there is no
such that
. It follows immediately that the largest subset of
on which
is an equivalence relation is precisely the subset on which
is defined.
Functions respecting equivalence relations
Let ''X'' and ''Y'' be sets equipped with equivalence relations (or PERs)
. For
, define
to mean:
:
then
means that ''f'' induces a well-defined function of the quotients
. Thus, the PER
captures both the idea of ''definedness'' on the quotients and of two functions inducing the same function on the quotient.
Equality of IEEE floating point values
The IEEE 754:2008
floating point standard defines an "EQ" relation for floating point values. This predicate is symmetrical and transitive, but is not reflexive because of the presence of
NaN
Nan or NAN may refer to:
Places China
* Nan County, Yiyang, Hunan, China
* Nan Commandery, historical commandery in Hubei, China
Thailand
* Nan Province
** Nan, Thailand, the administrative capital of Nan Province
* Nan River
People Given name
...
values that are not EQ to themselves.
Notes
References
{{DEFAULTSORT:Partial Equivalence Relation
Symmetric relations
Transitive relations
Equivalence (mathematics)