Answer to Question #267866 in Discrete Mathematics for Jaishree

Question

Which of these relations on the set of all functions from Z to Z are equivalence

relations? Determine the properties of an equivalence relation that the others

lack.

a) {(f, g) | f (1) = g(1)}

b) {(f, g) | f (0) = g(0) or f (1) = g(1)}

c) {(f, g) | f (x) − g(x) = 1 for all x ∈ Z}

d) {(f, g) | for some C ∈ Z, for all x ∈ Z, f (x) − g(x) = C}

e) {(f, g) | f (0) = g(1) and f (1) = g(0)

Answer 1

equivalence relation is a binary relation that is reflexive, symmetric and transitive

a)

equivalence relation

reflexive:  f (1) = f(1)

symmetric: if f (1) = g(1) then g(1) = f(1)

transitive: if f (1) = g(1) and g(1) = h (1) then f(1) = h(1)

b)

not equivalence relation

reflexive: f (0) = f(0) or f (1) = f(1)

symmetric: if f(0) = g(0) or f (1) = g(1) then g(0) = f(0) or g(1) = f(1)

not transitive: if f(0) = g(0) and g(1) = h(1) then not f(0) = h(0)

c)

not equivalence relation

Not reflexive: f(x)−f(x) = 0

Not symmetric: if f(x)−g(x) = 1, then g(x)−f(x) = −1

Not transitive: if f(x) − g(x) = 1 and g(x) − h(x) = 1, then f(x) − h(x) = 2

d)

equivalence relation

reflexive: f (x) − f(x) = 0 = const

symmetric: if f (x) − g(x) = C then g(x) − f(x) = -C = const

transitive: if f f (x) − g(x) = C₁ and g(x) − h(x) = C₂ then f(x) − h(x) = C₁+C₂ = const

e)

not equivalence relation

not reflexive: f(0) = f(1) isn’t always true

not symmetric: if f (0) = g(1) and f (1) = g(0) then not g(0) = f(1) and g(1) = f(0)

not transitive: for example, let f(x) = h(x) = x and g(x) = 1−x. Then f ≡ g and g ≡ h, but not f ≡ h