Question

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.

Answer 1

See proof below

Explanation:

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

1. is reflexive, that is, xRx for all x∈A.
2. is symmetric, that is, for all x,y∈A if xRy then yRx.
3. 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.