Partial equivalence relation
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, 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 () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
and transitive. If the relation is also reflexive, then the relation is an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...
.


Definition

Formally, a relation R on a set X is a PER if it holds for all a, b, c \in X that: # if a R b, then b R a (symmetry) # if a R b and b R c, then a R c (transitivity) Another more intuitive definition is that R on a set X is a PER if there is some subset Y of X such that R \subseteq Y \times Y and R is an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...
on Y. The two definitions are seen to be equivalent by taking Y = \.


Properties and applications

The following properties hold for a partial equivalence relation R on a set X: * R is an equivalence relation on the subset Y = \ \subseteq X.By construction, R is reflexive on Y and therefore an equivalence relation on Y. * 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 the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
s f,g : X \rightharpoonup Y and some indicator set Y * right and left Euclidean: For a,b,c \in X, a R b and a R c implies b R c and similarly for left Euclideanness b R a and c R a imply b R c * quasi-reflexive: If x, y \in X and x R y, then x R x and y R y.This follows since if x R y, then y R x by symmetry, so x R x and y R y 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 E=\ and the relation R=\^2\cup\. R is an equivalence relation on \ but not a PER on E since it is neither symmetric (dRa, but not aRd) nor transitive (dRa and aRb, but not dRb). 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 and theoretical computer science, a type theory is the formal presentation of a specific type system. Type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundation of ...
,
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, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, 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 foun ...
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) on a set ''X'' is a binary relation between ''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 ...
R=\emptyset, if X is not empty.


Kernels of partial functions

If f is a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain ...
on a set A, then the relation \approx defined by : x \approx y if f is defined at x, f is defined at y, and f(x) = f(y) is a partial equivalence relation, since it is clearly symmetric and transitive. If f is undefined on some elements, then \approx is not an equivalence relation. It is not reflexive since if f(x) is not defined then x \not\approx x — in fact, for such an x there is no y \in A such that x \approx y. It follows immediately that the largest subset of A on which \approx is an equivalence relation is precisely the subset on which f is defined.


Functions respecting equivalence relations

Let ''X'' and ''Y'' be sets equipped with equivalence relations (or PERs) \approx_X, \approx_Y. For f,g : X \to Y, define f \approx g to mean: : \forall x_0 \; x_1, \quad x_0 \approx_X x_1 \Rightarrow f(x_0) \approx_Y g(x_1) then f \approx f means that ''f'' induces a well-defined function of the quotients X / \; \to \; Y / . Thus, the PER \approx 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 In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a signed sequence of a fixed number of digits in some base) multiplied by an integer power of that base. Numbers of this form ...
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. See page 33.


Notes


References

{{DEFAULTSORT:Partial Equivalence Relation Symmetric relations Transitive relations Equivalence (mathematics)