Show that each of the relations in the set , given by
(i)
(ii)
is an equivalence relation. Find the set of all elements related to in each case.
Confirming your payment
Exercise 1.1 · Question 9 of 16
Show that each of the relations in the set , given by
(i)
(ii)
is an equivalence relation. Find the set of all elements related to in each case.
Here , which has elements.
Part (i):Reflexive. Let . Then , and is a multiple of . So for every , and is reflexive.
Symmetric. Let , so for some non-negative integer . Since , the number is also a multiple of . Hence , and is symmetric.
Transitive. Let and . Then is a multiple of and is a multiple of (a number is a multiple of exactly when its modulus is). Write and with . Adding,
so is a multiple of . Hence , and is transitive.
Being reflexive, symmetric and transitive, is an equivalence relation.
The set of all elements related to . We must find every for which is a multiple of . Testing all thirteen elements of :
| multiple of ? | ||
|---|---|---|
| no | ||
| yes | ||
| no | ||
| no | ||
| no | ||
| yes | ||
| no | ||
| no | ||
| no | ||
| yes | ||
| no | ||
| no | ||
| no |
So the set of all elements related to is .
Algebraically: is a multiple of exactly when , that is when , and of these only lie in .
Because is a multiple of exactly when and leave the same remainder on division by , the relation splits into four classes, one for each remainder:
![Four boxes [0], [1], [2], [3] holding the remainder classes of A; box [1] = {1, 5, 9} is highlighted as the set related to 1](/_next/image/?url=https%3A%2F%2Fcontent.supalearn.com%2Fstorage%2Fv1%2Fobject%2Fpublic%2Fimages%2F6ee4c150-150e-40df-967b-79c1cbf28d81-m12c140_21202_mod4_classes.png&w=3840&q=75)
The class containing is the box , which is the required set.
Part (ii):This is the identity relation on : and nothing else.
Reflexive. For every we have , so . Hence is reflexive.
Symmetric. If then , and therefore , so . Hence is symmetric.
Transitive. If and then and , so and . Hence is transitive.
Being reflexive, symmetric and transitive, is an equivalence relation.
The set of all elements related to . We need every with , and the only such is itself. So the required set is .
Here every equivalence class is a single element, so this relation splits into one-element classes.
Summary| relation | set of elements related to |
|---|---|
| (i) a multiple of | |
| (ii) |