Suppose that A is a nonempty set, and f is a function that has A as its domain. Let R be the relation on A consisting of all ordered pairs (x, y) such that f (x) = f (y). (a) Show that R is an equivalence relation on A.

See proof below

Step-by-step explanation:

Let xRy denote the statement " (x, y) ∈A". To prove that R is an equivalence relation on A, we must prove that R

is reflexive, that is, xRx for all x∈A. is symmetric, that is, for all x, y∈A if xRy then yRx. is transitive, that is, fot all x, y, z∈A if xRy and yRz then xRy.

For the first one, we know that equality is reflexive, and for all x, f (x) is unique because f is a function, then f (x) = f (x), that is, xRX. So R is reflexive.

For symmetry, suppose that xRy. Then, by definition of R, f (x) = f (y) (again, this value is unique for all x, y). Equality is symmetric, then f (y) = f (x), hence yRx. We have that R is symmetric.

For the last one, suppose that xRy and yRz. Then f (x) = f (y) and f (y) = f (z). f (x), f (y) and f (z) are uniquely determined by the function f. Moreover, equality is transitive, then f (x) = f (y) = f (z) implies that f (x) = f (z), that is, xRz. Hence R is transitive.

R is reflexive, symmetric and transitive, therefore R is a equivalence relation on A.

The hypothesis on f is important. If f wasn't a function, f (x) could represent than one element, so it would be ambiguous and the properties of equality wouldn't necessarily hold.