partial equivalence relation

Formally, a relation $R$ on a set $X$ is a PER if it holds for all $a,\; b,\; c\; \backslash in\; X$ that:

1. if $a\; R\; b$, then $b\; R\; a$ (symmetry)
2. 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\; \backslash subseteq\; Y\; \backslash times\; Y$ and $R$ is an equivalence relation on $Y$. The two definitions are seen to be equivalent by taking $Y\; =\; \backslash \{\; x\; \backslash in\; X\; \backslash mid\; x\backslash ,R\backslash ,x\backslash \}$.{{cite book |last1=Mitchell |first1=John C. |title=Foundations for programming languages |date=1996 |publisher=MIT Press |location=Cambridge, Mass. |isbn=0585037892 |pages=364–365}}

The following properties hold for a partial equivalence relation $R$ on a set $X$:

• $R$ is an equivalence relation on the subset $Y\; =\; \backslash \{\; x\; \backslash in\; X\; \backslash mid\; x\backslash ,R\backslash ,x\backslash \}\; \backslash subseteq\; X$.By construction, $R$ is reflexive on $Y$ and therefore an equivalence relation on $Y$.
• difunctional: the relation is the set $\backslash \{(a,b)\; \backslash mid\; f\; a\; =\; g\; b\; \backslash \}$ for two partial functions $f,g\; :\; X\; \backslash rightharpoonup\; Y$ and some indicator set $Y$
• right and left Euclidean: For $a,b,c\; \backslash 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\; \backslash in\; X$ and $x\; R\; y$, then $x\; R\; x$ and $y\; R\; y$.[https://www.britannica.com/topic/formal-logic/Logical-manipulations-in-LPC#ref534730 Encyclopaedia Britannica] (EB); although EB's notion of quasi-reflexivity is Wikipedia's notion of left quasi-reflexivity, they coincide for symmetric relations.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=\backslash \{a,b,c,d\backslash \}$ and the relation $R=\backslash \{a,b,c\backslash \}^2\backslash cup\backslash \{(d,a)\backslash \}$. $R$ is an equivalence relation on $\backslash \{a,b,c\backslash \}$ 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. 2R1, but not 1R2) nor transitive (since e.g. 2R1 and 1R0, but not 2R0).

In type theory, constructive mathematics and their applications to computer science, constructing analogues of subsets is often problematic{{Cite book|chapter-url=https://ieeexplore.ieee.org/document/5135|doi=10.1109/LICS.1988.5135|chapter=The strength of the subset type in Martin-Lof's type theory|title=[1988] Proceedings. Third Annual Information Symposium on Logic in Computer Science|year=1988|last1=Salveson|first1=A.|last2=Smith|first2=J.M.|pages=384–391|isbn=0-8186-0853-6|s2cid=15822016}}—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.{{cite book|editor1=Aldo Ursini |editor2=Paulo Agliano|title=Logic and Algebra|year=1996|publisher=CRC Press|isbn=978-0-8247-9606-8|pages=161–180|author=J. Lambek|chapter=The Butterfly and the Serpent}}

A simple example of a PER that is not an equivalence relation is the empty relation $R=\backslash emptyset$, if $X$ is not empty.

If $f$ is a partial function on a set $A$, then the relation $\backslash approx$ defined by

: $x\; \backslash 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 $\backslash approx$ is not an equivalence relation. It is not reflexive since if $f(x)$ is not defined then $x\; \backslash not\backslash approx\; x$ — in fact, for such an $x$ there is no $y\; \backslash in\; A$ such that $x\; \backslash approx\; y$. It follows immediately that the largest subset of $A$ on which $\backslash approx$ is an equivalence relation is precisely the subset on which $f$ is defined.

Let X and Y be sets equipped with equivalence relations (or PERs) $\backslash approx\_X,\; \backslash approx\_Y$. For $f,g\; :\; X\; \backslash to\; Y$, define $f\; \backslash approx\; g$ to mean:

: $\backslash forall\; x\_0\; \backslash ;\; x\_1,\; \backslash quad\; x\_0\; \backslash approx\_X\; x\_1\; \backslash Rightarrow\; f(x\_0)\; \backslash approx\_Y\; g(x\_1)$

then $f\; \backslash approx\; f$ means that f induces a well-defined function of the quotients $X\; /\; \{\backslash approx\_X\}\; \backslash ;\; \backslash to\; \backslash ;\; Y\; /\; \{\backslash approx\_Y\}$. Thus, the PER $\backslash approx$ captures both the idea of definedness on the quotients and of two functions inducing the same function on the quotient.

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.{{cite journal

| last = Goldberg | first = David

| doi = 10.1145/103162.103163

| issue = 1

| journal = ACM Computing Surveys

| pages = 5–48

| title = What Every Computer Scientist Should Know About Floating-Point Arithmetic

| volume = 23

| year = 1991}} See page 33.

{{reflist|group=note}}

{{reflist}}

{{DEFAULTSORT:Partial Equivalence Relation}}

Category:Symmetric relations

Category:Transitive relations

Category:Equivalence (mathematics)