Definition:Equivalence Relation

From ProofWiki
Jump to: navigation, search

Definition

Let $\mathcal R$ be a relation on a set $S$.


Definition 1

Let $\mathcal R$ be:

$(1): \quad$ reflexive
$(2): \quad$ symmetric
$(3): \quad$ transitive

Then $\mathcal R$ is an equivalence relation on $S$.


Definition 2

$\mathcal R$ is an equivalence relation if and only if:

$\Delta_S \cup \mathcal R^{-1} \cup \mathcal R \circ \mathcal R \subseteq \mathcal R$

where:

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


Also known as

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


Also denoted as

When discussing equivalence relations, various notations are used for $\left({x, y}\right) \in \mathcal R$.

Examples are:

$x \equiv y \left({\mathcal R}\right)$
$x \equiv y \pmod {\mathcal R}$
$x \sim y$

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$


Examples

Same Age Relation

Let $P$ be the set of people.

Let $\sim$ be the relation on $P$ defined as:

$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text { the age of $x$ and $y$ on their last birthdays was the same}$

That is, that $x$ and $y$ are the same age.

Then $\sim$ is an equivalence relation.


Also see

  • Results about equivalence relations can be found here.


Sources