**Definition: **A binary relation on a set, $\mathrm{A}$, is a subset, $\mathrm{R}$, of $\mathrm{A} \times \mathrm{A} .$ Alternatively, we can say that a subset of $\mathrm{A} \times \mathrm{A}$ is a relation on $\mathrm{A}$.

Here is some notation

**Notation: **$\mathrm{a} \sim \mathrm{b}$ if $(a, b) \in R$. In other words, a is related to $\mathrm{b}$ if both $\mathrm{a}$ and $\mathrm{b}$ belong to $\mathrm{R}$.

Here is a simple example. Let's say that we have a set of students in a classroom. Then two students are related if they sit in the same row of seats.

**Definition:** A relation $\sim$ is called an equivalence relation if the following hold:

- $\mathrm{a} \sim \mathrm{a} \forall a \in A$. This is called reflexivity.
- If $a \sim b \Rightarrow b \sim a$. This is called symmetry.
- If $\mathrm{a} \sim \mathrm{b}$ and $\mathrm{b} \sim \mathrm{c}, \Rightarrow \mathrm{a} \sim \mathrm{c}$. This is called transitivity.

and student $c$ are in the same row, then student a and student $c$ are in the same row. Therefore, it is an equivalence relation.

Lets look at another example.

**Example:**

Let $(a, b) \in \mathbb{Z}$. Show $\mathrm{a} \sim \mathrm{b}$ if $2 \mid(\mathrm{a}-\mathrm{b})$. That is, 2 divides $(\mathrm{a}-\mathrm{b})$

- If $\mathrm{a} \sim \mathrm{a}$, then $2 \mid(\mathrm{a}-\mathrm{a}) . \mathrm{So} \sim$ is reflexive.
- If $a \sim b \Rightarrow 2 \mid(a-b)$, then $2 \mid(b-a) \Rightarrow b \sim a .$ So $\sim$ is symmetric.
- If $a \sim b$ and $b \sim c, \Rightarrow 2 \mid(a-b)$ and $2|(b-c) . \Rightarrow 2|[(a-b)+(b-c)]$. That is, $2 \mid(a-c) . \Rightarrow a \sim c .$ So $\sim$ is transitive.

Therefore, $\sim$ is an equivalence relation.

Now we look at another important idea, the equivalence class.