Open main menu

Partial equivalence relation

  (Redirected from )

In mathematics, a partial equivalence relation (often abbreviated as PER, in older literature also called restricted equivalence relation) on a set is a relation that is symmetric and transitive. In other words, it holds for all that:

  1. if , then (symmetry)
  2. if and , then (transitivity)

If is also reflexive, then is an equivalence relation.

Contents

Properties and applicationsEdit

In a set-theoretic context, there is a simple structure to the general PER   on  : it is an equivalence relation on the subset  . (  is the subset of   such that in the complement of   ( ) no element is related by   to any other.) By construction,   is reflexive on   and therefore an equivalence relation on  . Notice that   is actually only true on elements of  : if  , then   by symmetry, so   and   by transitivity. Conversely, given a subset Y of X, any equivalence relation on Y is automatically a PER on X. Hence, in set theory one typically studies the equivalence relation associated with a PER, rather than the PER itself.

But in type theory, constructive mathematics and their applications to computer science, constructing analogues of subsets is often problematic[1]—in these contexts PERs are therefore more commonly used, particularly to define setoids, 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.

Every partial equivalence relation is a difunctional relation, but the converse does not hold.

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

Each partial equivalence relation is a right Euclidean relation. The contrary does not hold: for example, xRy on natural numbers, defined by 0 ≤ xy+1 ≤ 2, is right Euclidean, but neither symmetric (since e.g. 2R1, but not 1R2) nor transitive (since e.g. 2R1 and 1R0, but not 2R0). Similarly, each partial equivalence relation is a left Euclidean relation, but not vice versa.

ExamplesEdit

A simple example of a PER that is not an equivalence relation is the empty relation   (unless  , in which case the empty relation is an equivalence relation (and is the only relation on  )).

Kernels of partial functionsEdit

For another example of a PER, consider a set   and a partial function   that is defined on some elements of   but not all. Then the relation   defined by

  if and only if   is defined at  ,   is defined at  , and  

is a partial equivalence relation but not an equivalence relation. It possesses the symmetry and transitivity properties, but 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 subset of   for which   is an equivalence relation is precisely the subset on which   is defined.)

Functions respecting equivalence relationsEdit

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 valuesEdit

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 values that are not EQ to themselves.

ReferencesEdit

  1. ^ http://ieeexplore.ieee.org/document/5135/
  2. ^ J. Lambek (1996). "The Butterfly and the Serpent". In Aldo Ursini, Paulo Agliano (eds.). Logic and Algebra. CRC Press. pp. 161–180. ISBN 978-0-8247-9606-8.CS1 maint: Uses editors parameter (link)

See alsoEdit