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 and transitive. If the relation is also reflexive, then the relation is an equivalence relation.

Definition

that:

1. (symmetry)

2. (transitivity)

is an equivalence relation.

Properties and applications

:

• .

• is difunctional for two partial functions

• is right Euclidean

• is quasi-reflexive.

None of these properties alone is sufficient to imply that the relation is a PER. is both left and is an equivalence relation, and hence a PER.

In non-set-theory settings

In type theory, constructive mathematics and their applications to computer science, constructing analogues of subsets is often problematic—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.

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 is not empty.

Kernels of partial functions

is a partial function defined by

is a partial equivalence relation, since it is clearly symmetric and transitive.

is defined.

Functions respecting equivalence relations

Let X and Y to mean:

means that f 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 standard for floating-point numbers defines an "EQ" relation for floating point values. This predicate is symmetric and transitive, but is not reflexive because of the presence of NaN values that are not EQ to themselves.

Notes

References