Partial equivalence relation

Short description: Mathematical concept for comparing objects

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

Formally, a relation [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math] is a PER if it holds for all [math]\displaystyle{ a, b, c \in X }[/math] that:

1. if [math]\displaystyle{ a R b }[/math], then [math]\displaystyle{ b R a }[/math] (symmetry)
2. if [math]\displaystyle{ a R b }[/math] and [math]\displaystyle{ b R c }[/math], then [math]\displaystyle{ a R c }[/math] (transitivity)

Another more intuitive definition is that [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math] is a PER if there is some subset [math]\displaystyle{ Y }[/math] of [math]\displaystyle{ X }[/math] such that [math]\displaystyle{ R \subseteq Y \times Y }[/math] and [math]\displaystyle{ R }[/math] is an equivalence relation on [math]\displaystyle{ Y }[/math]. The two definitions are seen to be equivalent by taking [math]\displaystyle{ Y = \{ x \in X \mid x\,R\,x\} }[/math].

Properties and applications

The following properties hold for a partial equivalence relation [math]\displaystyle{ R }[/math] on a set [math]\displaystyle{ X }[/math]:

• [math]\displaystyle{ R }[/math] is an equivalence relation on the subset [math]\displaystyle{ Y = \{ x \in X \mid x\,R\,x\} \subseteq X }[/math].
• difunctional: the relation is the set [math]\displaystyle{ \{(a,b) \mid f a = g b \} }[/math] for two partial functions [math]\displaystyle{ f,g : X \rightharpoonup Y }[/math] and some indicator set [math]\displaystyle{ Y }[/math]
• right and left Euclidean: For [math]\displaystyle{ a,b,c \in X }[/math], [math]\displaystyle{ a R b }[/math] and [math]\displaystyle{ a R c }[/math] implies [math]\displaystyle{ b R c }[/math] and similarly for left Euclideanness [math]\displaystyle{ b R a }[/math] and [math]\displaystyle{ c R a }[/math] imply [math]\displaystyle{ b R c }[/math]
• quasi-reflexive: If [math]\displaystyle{ x, y \in X }[/math] and [math]\displaystyle{ x R y }[/math], then [math]\displaystyle{ x R x }[/math] and [math]\displaystyle{ y R y }[/math].

None of these properties is sufficient to imply that the relation is 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 [math]\displaystyle{ R=\emptyset }[/math], if [math]\displaystyle{ X }[/math] is not empty.

Kernels of partial functions

If [math]\displaystyle{ f }[/math] is a partial function on a set [math]\displaystyle{ A }[/math], then the relation [math]\displaystyle{ \approx }[/math] defined by

[math]\displaystyle{ x \approx y }[/math] if [math]\displaystyle{ f }[/math] is defined at [math]\displaystyle{ x }[/math], [math]\displaystyle{ f }[/math] is defined at [math]\displaystyle{ y }[/math], and [math]\displaystyle{ f(x) = f(y) }[/math]

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

If [math]\displaystyle{ f }[/math] is undefined on some elements, then [math]\displaystyle{ \approx }[/math] is not an equivalence relation. It is not reflexive since if [math]\displaystyle{ f(x) }[/math] is not defined then [math]\displaystyle{ x \not\approx x }[/math] — in fact, for such an [math]\displaystyle{ x }[/math] there is no [math]\displaystyle{ y \in A }[/math] such that [math]\displaystyle{ x \approx y }[/math]. It follows immediately that the largest subset of [math]\displaystyle{ A }[/math] on which [math]\displaystyle{ \approx }[/math] is an equivalence relation is precisely the subset on which [math]\displaystyle{ f }[/math] is defined.

Functions respecting equivalence relations

Let X and Y be sets equipped with equivalence relations (or PERs) [math]\displaystyle{ \approx_X, \approx_Y }[/math]. For [math]\displaystyle{ f,g : X \to Y }[/math], define [math]\displaystyle{ f \approx g }[/math] to mean:

[math]\displaystyle{ \forall x_0 \; x_1, \quad x_0 \approx_X x_1 \Rightarrow f(x_0) \approx_Y g(x_1) }[/math]

then [math]\displaystyle{ f \approx f }[/math] means that f induces a well-defined function of the quotients [math]\displaystyle{ X / {\approx_X} \; \to \; Y / {\approx_Y} }[/math]. Thus, the PER [math]\displaystyle{ \approx }[/math] 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 values that are not EQ to themselves.