Definition:Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

Definition

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


Definition 1

Let $\RR$ be:

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

Then $\RR$ is an equivalence relation on $S$.


Definition 2

$\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$


Examples

Equality

Let $S$ be a set.

Let the relation $\RR$ on $S$ be defined as:

$\forall x, y \in S: x \mathrel \RR y \iff x = y$

that is, the equality relation on $S$.

Then $\RR$ is an equivalence relation.


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.


Same Parents 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 { both of the parents of $x$ and $y$ are the same}$

Then $\sim$ is an equivalence relation.


People with Same First Name

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 { $x$ and $y$ have the same first name}$

Then $\sim$ is an equivalence relation.


Books with Same Number of Pages

Let $P$ be the set of books.

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

$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text { $x$ and $y$ have the same number of pages}$

Then $\sim$ is an equivalence relation.


Even Sum Relation

Let $\Z$ denote the set of integers.

Let $\RR$ denote the relation on $\Z$ defined as:

$\forall x, y \in \Z: x \mathrel \RR y \iff x + y \text { is even}$

Then $\RR$ is an equivalence relation.

The equivalence classes are:

$\eqclass 0 \RR$
$\eqclass 1 \RR$


Also see

  • Results about equivalence relations can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Equivalence_Relation&oldid=674002"