**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Partial equivalence relation

Summary

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 .

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (10)

Related concepts (5)

Related courses (23)

Related lectures (50)

Homogeneous 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 X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.

Reflexive relation

In mathematics, a binary relation R on a set X is reflexive if it relates every element of X to itself. An example of a reflexive relation is the relation "is equal to" on the set of real numbers, since every real number is equal to itself. A reflexive relation is said to have the reflexive property or is said to possess reflexivity. Along with symmetry and transitivity, reflexivity is one of three properties defining equivalence relations.

Transitive relation

In mathematics, a relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive. A homogeneous relation R on the set X is a transitive relation if, for all a, b, c ∈ X, if a R b and b R c, then a R c. Or in terms of first-order logic: where a R b is the infix notation for (a, b) ∈ R. As a non-mathematical example, the relation "is an ancestor of" is transitive.

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

HUM-228: Musical studies B

Ce cursus particulier - dont l'admission est sujette à l'acceptation d'un dossier de candidature - offre à l'étudiant engagé dans des études en musique de haut niveau en parallèle à ses études EPFL la

HUM-415: Musical studies II

Ce cursus particulier - dont l'admission est sujette à l'acceptation d'un dossier de candidature - offre à l'étudiant engagé dans des études en musique de haut niveau en parallèle à ses études EPFL la

Understanding Chaos in Quantum Field Theories

Explores chaos in quantum field theories, focusing on conformal symmetry, OPE coefficients, and random matrix universality.

2D Potential Flows

Explores 2D potential flows in fluid dynamics, focusing on stream function and velocity potential relationships and visualization techniques.

Linear Regression: Statistical Inference Perspective

Explores linear regression from a statistical inference perspective, covering probabilistic models, ground truth, labels, and maximum likelihood estimators.

Christos Comninellis, Stéphane Fierro

In the first part of this paper, IrO2 electrodes produced by thermal decomposition of H2IrCl6 precursor were manufactured using the spin coating deposition technique, where centrifugal forces spread the precursor solution with simultaneous evaporation of t ...

This work is dedicated to the study of Borel equivalence relations acting on Borel fields of CAT(0) metric spaces over a standard probability space. In this new framework we get similar results to some theorems proved recently by S. Adams-W. Ballmann or N. ...

Giovanni De Micheli, Paolo Ienne, Mathias Soeken, Ana Petkovska

Two Boolean functions are NPN equivalent if one can be ob- tained from the other by negating inputs, permuting inputs, or negating the output. NPN equivalence is an equivalence relation and the number of equivalence classes is significantly smaller than th ...