Partielle Äquivalenzrelation

Eine partielle Äquivalenzrelation (oft mit PER abgekürzt von englisch partial eqivalence relation, in älterer Literatur auch restricted equivalence relation) oder vereinfacht partielle Äquivalenz ist eine symmetrische und transitive binäre Relation. Im Unterschied zu einer Äquivalenzrelation ist Reflexivität nicht notwendig.

Definition

Ist $M$ eine Menge, so ist eine zweistellige Relation $\approx$ auf $M$ eine partielle Äquivalenzrelation, falls für alle $a,b,c\in M$ gilt:

$a\approx b\implies b\approx a$	(Symmetrie)
$a\approx b\approx c\implies a\approx c$	(Transitivität)

Elemente $a\in M$ mit $a\approx a$ heißen reflexive Elemente. Sind alle Elemente reflexiv und damit die Relation, so ist sie eine (totale) Äquivalenzrelation.

Eigenschaften und Anwendungen

Reflexive Elemente müssen nicht existieren. In einem mengentheoretischen Kontext ist eine Relation $\approx$ auf $M$ genau dann eine partielle Äquivalenzrelation auf $M$, wenn sie eine Äquivalenzrelation auf den reflexiven Elementen $\operatorname {refl} _{M}(\approx )=\{\,a\in M\mid a\approx a\,\}$ ist. Daher beschäftigt man sich in der klassischen Mathematik selten mit partiellen Äquivalenzrelationen und studiert, wo sie auftreten, stattdessen die Äquivalenzrelation auf den reflexiven Elementen.

In der Typentheorie, der konstruktiven Mathematik und ihren Anwendungen in der Informatik sind Teilmengen oft problematisch. In solchen Kontexten sind partielle Äquivalenzrelationen häufiger und werden konkret verwendet, um partielle extensionale Mengen anzugeben. Eine partielle extensionale Menge ergibt sich aus einem Datentyp und einer partiellen Äquivalenzrelation wie sich Teilmengen und Quotienten in klassischer mengentheoretischer Mathematik ergeben.

Der algebraische Begriff von Kongruenz kann ebenfalls auf partielle Äquivalenzrelationen verallgemeinert werden, was zum Begriff Teilkongruenz führt, also einer homomorphen Relation, die symmetrisch und transitiv, aber nicht notwendigerweise reflexiv ist.

Beispiele

Leere Relation

Für eine nichtleere Trägermenge $M$ ist die leere Relation ein pathologisches Beispiel einer partiellen Äquivalenzrelation, die keine Äquivalenzrelation ist.

Bildgleichheit partieller Funktionen

Betrachte eine partielle Funktion $f\colon A\rightsquigarrow B$, die nicht auf allen Elementen von $A$ definiert ist. Dann ist die Relation $\approx$ mit

$x\approx y$ genau dann, wenn $f$ auf $x$ und $y$ definiert ist und $f(x)=f(y)$ gilt,

eine partielle Äquivalenzrelation, aber nicht reflexiv. Sie ist symmetrisch und transitiv, aber nicht reflexiv, denn wenn $f(x)$ nicht definiert ist, muss $x\not \approx x$ sein. Für solch ein $x$ gibt es überhaupt kein $y\in A$ mit $x\approx y$. Die Gleichheit $f(x)=f(y)$ kann durch eine beliebige partielle Äquivalenzrelation auf $B$ ersetzt werden.

Verträgliche Funktionen

Seien $A$ und $B$ Mengen mit partiellen Äquivalenzrelationen $\approx _{A},\approx _{B}$. Für Funktionen $f,g:A\to B$ definiere $f\approx g$ als:

$f(x)\approx _{B}g(y)$ für alle $x,y\in A$ mit $x\approx _{A}y$.

Dann bedeutet $f\approx f$, dass $f$ mit den partiellen Äquivalenzrelationen verträglich ist, also die induzierte Funktion ${\overline {f}}\colon A/\approx _{A}\to B/\approx _{B}$ auf den Äquivalenzklassen wohldefiniert ist.

Gleichheit auf Gleitkommazahlen

Die Norm IEEE 754 definiert eine partielle Äquivalenzrelation, die in den meisten Programmiersprachen mit == ausgedrückt wird. Sie ist symmetrisch und transitiv, jedoch für undefinierte Werte (NaN-Werte) nicht reflexiv.

Literatur

• John C. Mitchell: Foundations of programming languages. MIT Press, 1996 (englisch, acm.org). 
• Dana Scott: Data types as lattices. Band 3. SIAM Journ. Comput., 1976, S. 523–587 (englisch). 

Siehe auch

• Quasiordnung