Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Partial equivalence relation
Résumé
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.
Formally, a relation on a set is a PER if it holds for all that:
if , then (symmetry)
if and , then (transitivity)
Another more intuitive definition is that on a set is a PER if there is some subset of such that and is an equivalence relation on . The two definitions are seen to be equivalent by taking .
The following properties hold for a partial equivalence relation on a set :
is an equivalence relation on the subset .
difunctional: the relation is the set for two partial functions and some indicator set
right and left Euclidean: For , and implies and similarly for left Euclideanness and imply
quasi-reflexive: If and , then and .
None of these properties is sufficient to imply that the relation is a PER.
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.
A simple example of a PER that is not an equivalence relation is the empty relation , if is not empty.
If is a partial function on a set , then the relation defined by
if is defined at , is defined at , and
is a partial equivalence relation, since it is clearly symmetric and transitive.
If is undefined on some elements, then is not an equivalence relation. It is not reflexive since if is not defined then — in fact, for such an there is no such that .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.