Which of the following is an equivalence relation on the set of all functions…

Concept

A relation R on a set S is an equivalence relation when it satisfies all three of the following properties, each quantified over every element of S:

• Reflexive: a R a holds for every a ∈ S.

• Symmetric: whenever a R b holds, b R a holds as well.

• Transitive: whenever a R b and b R c both hold, a R c holds.

The three are independent, so a relation qualifies only if all three survive; a single counterexample to any one of them settles the matter. Here S is the set of all functions from Z to Z, so the objects being related are whole functions f, g, h : Z → Z, and each property must be checked for every input x, not just for one convenient input.

Application

Take the relation defined by: f is related to g when there exists an integer k with f(x) − g(x) = k for every x ∈ Z — one and the same constant k across all inputs.

Reading the notation: this relation is printed as "f(x) − g(x) = k for some k ∈ Z" and leaves the quantifier on x implicit, exactly as the original paper prints it. The intended reading, used throughout the check above, is that a single k ∈ Z works for every x ∈ Z. Under the looser reading, in which k may be picked afresh for each x, the condition is met by every pair of functions from Z to Z, because the difference of two integers is always an integer; that relation relates everything to everything, and the everything-to-everything relation is reflexive, symmetric and transitive too. So the implicit quantifier changes the equivalence classes but not the verdict on this relation.

1. Reflexivity. Given any f, choose k = 0. Then f(x) − f(x) = 0 for every x ∈ Z, and 0 ∈ Z, so the required integer exists and f is related to itself.

2. Symmetry. Suppose f(x) − g(x) = k for every x. Multiplying through by −1 gives g(x) − f(x) = −k for every x. Since k ∈ Z implies −k ∈ Z, the witness −k works and g is related to f.

3. Transitivity. Suppose f(x) − g(x) = k₁ and g(x) − h(x) = k₂ for every x. Adding the two equations, the g(x) terms cancel: f(x) − h(x) = k₁ + k₂ for every x. Z is closed under addition, so k₁ + k₂ ∈ Z is the required witness and f is related to h.

All three properties hold, so this relation partitions the function space. Its equivalence class of a function f is { f + c : c ∈ Z }, the family of all integer vertical shifts of f.

Cross-check against the other three relations

The counterexamples behind the "No" entries:

• f(x) − g(x) = 1 ∀ x. Reflexivity already collapses: f(x) − f(x) = 0 and 0 ≠ 1, so no function is related to itself. Symmetry fails too, because f − g = 1 forces g − f = −1; and f − g = 1 together with g − h = 1 gives f − h = 2, so transitivity fails as well. Fixing the constant at a single non-zero value destroys all three properties.

• f(0) = g(0) or f(1) = g(1). Describe functions by the pair of values (value at 0, value at 1). Let f be (0, 0), g be (0, 1) and h be (1, 1). Then f and g agree at input 0, and g and h agree at input 1, so both pairs are related; but f and h agree at neither input, so f is not related to h. Transitivity fails because the "or" lets each link be earned at a different input.

• f(0) = g(1) and f(1) = g(0). Reflexivity would demand f(0) = f(1) for every f, which already fails for the identity function f(x) = x. Transitivity fails for the same swapping reason: with f = h given by (0, 1) and g given by (1, 0), f is related to g and g is related to h, yet f is not related to h = f, because that would again require f(0) = f(1).

Result: among the four, only the relation "f and g differ by one fixed integer constant at every input" is reflexive, symmetric and transitive, so it is the equivalence relation.