Definition:Equivalence Relation/Definition 2

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\RR \subseteq S \times S$ be a relation on a set $S$.


$\RR$ is an equivalence relation if and only if:

$\Delta_S \cup \RR^{-1} \cup \RR \circ \RR \subseteq \RR$

where:

$\Delta_S$ denotes the diagonal relation on $S$
$\RR^{-1}$ denotes the inverse relation
$\circ$ denotes composition of relations


Also known as

An equivalence relation is frequently referred to just as an equivalence.

However, this usage is not recommended on $\mathsf{Pr} \infty \mathsf{fWiki}$, as it can obscure clarity.


Also denoted as

When discussing equivalence relations, various notations are used for $\tuple {x, y} \in \RR$.

Examples are:

$x \mathrel \RR y$
$x \equiv \map y \RR$
$x \equiv y \pmod \RR$

and so on.

Specialised equivalence relations generally have their own symbols, which can be defined as they are needed.

Such symbols include:

$\cong$, $\equiv$, $\sim$, $\simeq$, $\approx$


Also see

  • Results about equivalence relations can be found here.


Sources