Home page for accesible maths 6 Equivalence relations and their applications 6 Equivalence relations and their applications 6.2 Equivalence relations

Style control - access keys in brackets

Font (2 3) - + Letter spacing (4 5) - + Word spacing (6 7) - + Line spacing (8 9) - +

6.1 Introduction to relations

We begin with a fundamental definition.

Definition 6.1.1

Let $S$ be a non-empty set. A relation on $S$ is a statement concerning pairs of elements of $S$ , which may be true for some pairs and false for others.

Example 6.1.2

(i)

If $S=\mathbb{R}$ , we could take the relation ‘‘ $a\leqslant b$ ’’ on $S$ .
(ii)

If $S=\mathbb{R}$ , we could take the relation ‘‘ $|a|=|b|$ ’’ on $S$ .
(iii)

If $S=\mathbb{Z}$ , we could take the relation ‘‘ $a|b$ ’’ on $S$ .
(iv)

If $S=\mathbb{N}$ , we could take the relation ‘‘ $a$ has one more prime factor than $b$ ’’ on $S$ .
(v)

If $S=\mathbb{Z}$ , we could take the relation ‘‘ $a\equiv b\bmod 5$ ’’ on $S$ .
(vi)

If $S$ is the set of first-year MATH modules taught here, we could take the relation ‘‘ $a$ is lectured earlier in the year than $b$ ’’ on $S$ .
(vii)

If $S$ is the set of all people in the world, we could take the relation ‘‘ $a$ is related (in the usual sense of the word) to $b$ ’’ on $S$ .

In general, we write ‘‘ $a\sim b$ ’’ to mean ‘‘ $a$ is related to $b$ ’’ (that is, the relation holds for the pair $(a,b)$ ), and we write ‘‘ $a\not\sim b$ ’’ to mean ‘‘ $a$ is not related to $b$ ’’ (i.e., the relation does not hold for the pair $(a,b)$ ). For instance, in Example 6.1.2(iii) above, we have the following:

3{}\sim{}12,\qquad 3{}\not\sim{}14,\qquad 2{}\sim{}2,\qquad 1{}\sim{}n\hbox{ % for all }n\in S.

There are certain properties that a relation may or may not possess. We shall define each in turn; for convenience we take three examples of relations on the set $S=\mathbb{Z}$ , and for each we decide whether or not it has the property, giving either a (short) proof that it does or exhibiting a case which shows that it does not (a counterexample). The three examples we take are the following:

(i)

$a\sim b$ if $a+b>7$ ;
(ii)

$a\sim b$ if $a|b$ ;
(iii)

$a\sim b$ if $a\equiv b\bmod 5$ .

Definition 6.1.3

A relation $\sim$ on a non-empty set $S$ is reflexive if $a\sim a$ for each $a\in S$ ; in symbols

(\forall\,a\in S)(a\sim a).

Example 6.1.4

(i)

$a+a>7$ is true for some $a\in\mathbb{Z}$ (e.g., $a=4$ ), but not for all $a\in\mathbb{Z}$ ; indeed, it is false for $a=1$ because $1+1=2<7$ . Hence the relation is not reflexive.
(ii)

$a|a$ is true for all $a\in\mathbb{Z}$ because $a=a\cdot 1$ , so the relation is reflexive.
(iii)

$a\equiv a\bmod 5$ is true for all $a\in\mathbb{Z}$ because $5$ divides $a-a=0$ , so the relation is reflexive.

This property actually requires the relation to hold between certain pairs of elements of $S$ (those where the two elements are the same). The other properties are a little different; they require that if certain pairs of elements are related, then something must follow.

Definition 6.1.5

A relation $\sim$ on a non-empty set $S$ is symmetric if, whenever $a,b\in S$ satisfy $a\sim b$ , we have $b\sim a$ ; in symbols

(\forall\,a,b\in S)\bigl((a\sim b)\Rightarrow(b\sim a)\bigr).

Example 6.1.6

(i)

If $a+b>7$ , then certainly $b+a>7$ ; so the relation is symmetric.
(ii)

If $a|b$ it need not be the case that $b|a$ ; indeed, we have $3\sim 6$ because $6=2\cdot 3$ , but $6\!\!\!\!\;\not\!\!\!\;|\!\;3$ , so $6\not\sim 3$ , and thus the relation is not symmetric.
(iii)

If $a\equiv b\bmod 5$ , then Lemma 5.1.7 implies that $b\equiv a\bmod 5$ ; so the relation is symmetric.

The third property concerns trios of elements.

Definition 6.1.7

A relation $\sim$ on a non-empty set $S$ is transitive if, whenever $a,b,c\in S$ satisfy $a\sim b$ and $b\sim c$ , we have $a\sim c$ ; in symbols

(\forall\,a,b,c\in S)\bigl(\bigl((a\sim b)\ \&\ (b\sim c)\bigr)\Rightarrow(a% \sim c)\bigr).

Example 6.1.8

(i)

If $a+b>7$ and $b+c>7$ , we cannot deduce that $a+c>7$ , as the example $a=3$ , $b=6$ and $c=2$ shows; so the relation is not transitive.
(ii)

If $a|b$ and $b|c$ , Proposition 4.1.6(i) gives that $a|c$ ; so the relation is transitive.
(iii)

If $a\equiv b\bmod 5$ and $b\equiv c\bmod 5$ , then $a\equiv c\bmod 5$ by Lemma 5.1.9; so the relation is transitive.

We now take two further examples and examine them for all our three properties together.

Example 6.1.9

Define the relation $\sim$ on $\mathbb{R}$ by $a\sim b$ if $|a-b|\leqslant 1$ . Then:

(i)

For each $a\in\mathbb{R}$ we have $|a-a|=0\leqslant 1$ , so $a\sim a$ . Thus the relation is reflexive.
(ii)

If $a\sim b$ then $|a-b|\leqslant 1$ , so $|b-a|=|a-b|\leqslant 1$ and $b\sim a$ . Thus the relation is symmetric.
(iii)

If $a=2$ , $b=1$ and $c=0$ , then $|a-b|=1$ so $a\sim b$ , $|b-c|=1$ so $b\sim c$ , but $|a-c|=2$ so $a\not\sim c$ . Thus the relation is not transitive.

Example 6.1.10

Define the relation $\sim$ on $\mathbb{R}$ by $a\sim b$ if $a\leqslant b$ . Then:

(i)

For all $a\in\mathbb{R}$ we have $a\leqslant a$ , so $a\sim a$ — thus the relation is reflexive.
(ii)

If $a\leqslant b$ , we cannot deduce that $b\leqslant a$ , as the example $a=1$ and $b=3$ shows. Thus the relation is not symmetric.
(iii)

If $a\leqslant b$ and $b\leqslant c$ , then we know that $a\leqslant c$ . Thus the relation is transitive.

We summarize our findings so far and consider further examples in the following table.

b

In the next section we shall consider a special type of relation which is defined in terms of these properties.