Partial equivalence relation

A partial equivalence relation (often with PER abbreviated from English partial equivalence relation , in older literature also restricted equivalence relation ) or simplified partial equivalence is a symmetrical and transitive binary relation . In contrast to an equivalence relation , reflexivity is not necessary.

definition

If there is a set, then a two-digit relation to a partial equivalence relation, if for all applies: ${\ displaystyle M}$ ${\ displaystyle \ approx}$ ${\ displaystyle M}$ ${\ displaystyle a, b, c \ in M}$

${\ displaystyle a \ approx b \ implies b \ approx a}$	(Symmetry)
${\ displaystyle a \ approx b \ approx c \ implies a \ approx c}$	(Transitivity)

Elements with are called reflexive elements . If all elements are reflexive, and thus the relation, then it is a (total) equivalence relation . ${\ displaystyle a \ in M}$ ${\ displaystyle a \ approx a}$

Properties and uses

Reflexive elements don't have to exist. In a set- theoretical context, a relation on is a partial equivalence relation on if and only if it is an equivalence relation on the reflexive elements . Therefore, in classical mathematics one rarely deals with partial equivalence relations and instead studies the equivalence relation on the reflexive elements where they occur. ${\ displaystyle \ approx}$ ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle \ operatorname {refl} _ {M} (\ approx) = \ {\, a \ in M \ mid a \ approx a \, \}}$

In type theory , the constructive mathematics and its applications in computer science subsets are often problematic. In such contexts, partial equivalence relations are more common and are specifically used to indicate partial extensional sets. A partial extensional set results from a data type and a partial equivalence relation, such as subsets and quotients in classical set-theoretical mathematics.

The algebraic concept of congruence can also be generalized to partial equivalence relations, which leads to the concept of partial congruence, i.e. a homomorphic relation that is symmetric and transitive, but not necessarily reflexive.

Examples

Empty relation

For a non-empty carrier set , the empty relation is a pathological example of a partial equivalence relation that is not an equivalence relation. ${\ displaystyle M}$

Image equality of partial functions

Consider a partial function that is not defined on all elements of . Then the relation is with ${\ displaystyle f \ colon A \ rightsquigarrow B}$ ${\ displaystyle A}$ ${\ displaystyle \ approx}$

{\ displaystyle x \ approx y}

if and only if on and is defined and applies,

{\ displaystyle f}

{\ displaystyle x}

{\ displaystyle y}

{\ displaystyle f (x) = f (y)}

a partial equivalence relation, but not reflexive. It is symmetrical and transitive, but not reflexive, because if it is not defined, it must be. For such a thing there is no with at all . The equality can be replaced by any partial equivalence relation on . ${\ displaystyle f (x)}$ ${\ displaystyle x \ not \ approx x}$ ${\ displaystyle x}$ ${\ displaystyle y \ in A}$ ${\ displaystyle x \ approx y}$ ${\ displaystyle f (x) = f (y)}$ ${\ displaystyle B}$

Compatible functions

Let be and sets with partial equivalence relations . For functions define as: ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle \ approx _ {A}, \ approx _ {B}}$ ${\ displaystyle f, g: A \ to B}$ ${\ displaystyle f \ approx g}$

{\ displaystyle f (x) \ approx _ {B} g (y)}

for everyone with .

{\ displaystyle x, y \ in A}

{\ displaystyle x \ approx _ {A} y}

Then means that is compatible with the partial equivalence relations, i.e. the induced function is well-defined on the equivalence classes. ${\ displaystyle f \ approx f}$ ${\ displaystyle f}$ ${\ displaystyle {\ overline {f}} \ colon A / \ approx _ {A} \ to B / \ approx _ {B}}$

Equality on floating point numbers

The IEEE 754 standard defines a partial equivalence relation, which is also expressed in most programming languages ==. It is symmetric and transitive, but not reflexive for undefined values (NaN values).

literature

John C. Mitchell : Foundations of programming languages . MIT Press, 1996.
Dana Scott : Data types as lattices . tape 3 . SIAM Journ. Comput., 1976, pp. 523-587 (English).

Individual evidence

↑ http://ieeexplore.ieee.org/document/5135/
^ Joachim Lambek : The Butterfly and the Serpent . In: Logic and Algebra . Taylor & Francis, 1996, ISBN 978-0-8247-9606-8 (English).