# Definition:Equivalence Relation

## Contents

## Definition

Let $\mathcal R$ 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

$\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 $\tuple {x, y} \in \RR$.

Examples are:

- $x \equiv \map y \RR$
- $x \equiv y \pmod \RR$
- $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.

### 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 $\mathcal R$ denote the relation on $\Z$ defined as:

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

Then $\mathcal R$ is an equivalence relation.

The equivalence classes are:

- $\eqclass 0 {\mathcal R}$
- $\eqclass 1 {\mathcal R}$

## Also see

- Definition:Equivalence Class
- Definition:Quotient Set
- Definition:Quotient Mapping, also known as the Definition:Canonical Surjection

- Results about
**equivalence relations**can be found here.

## Sources

- 1975: W.A. Sutherland:
*Introduction to Metric and Topological Spaces*... (previous) ... (next): Notation and Terminology - 1978: John S. Rose:
*A Course on Group Theory*... (previous) ... (next): $0$: Some Conventions and some Basic Facts - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**equivalence relation** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**equivalence relation**