Let fABbe a function Define a relation R on A by xyR if and

Let f:ABbe a function. Define a relation R on A by (x,y)R if and only if f(x)=f(y)

a) Prove that R is an equivalence relation

b) In the particular case f = {(a, 5), (b, 3), (c, 2), (d, 3), (e, 5), (f, 1), (g, 3)} find the equivalence classes associated with R defined in this problem

c) Identify the associated canonical map

Solution

Solution :

( a )

Proof : We shall show that R is reflexive, symmetric, and transitive.

Reflexive: If x A, then f(x) = f(x) so (x,x) R.

Symmetric: If (x,y) R, then f(x) = f(y) and f(y) = f(x). It follows that (y,x) R.

Transitive: If (x,y) R and (y,z) R, then f(x) = f(y) and f(y) = f(z). It follows that f(x) = f(z) and (x,z) R.