The Gateway to Computer Science Excellence
+1 vote
Which of these relations on the set of all functions from Z to Z are equivalence relations?

(a) $\{(f,g) \mid f(1)=g(1)\}$

(b) $\{(f,g) \mid f(0)=g(0) \text{ or } f(1)=g(1)\}$

(c) $\{(f,g) \mid f(x)-g(x)=1 \text{ for all } x \in \textbf{ Z} \}$

In this question, what does it mean by f(1) = g(1) and f(1) - g(1)? And how it satisfies all the conditions (Symmetric, Transitive and Reflexive) of equivalence relation. Actually I cannot able to analyze when the relations defined on set of function. If anyone describe a bit it would helpful.
in Set Theory & Algebra by (301 points)
edited by | 904 views

1 Answer

+1 vote
(a) equivalence relation

f has one element ,say i.e. 1 . Two function (f and g) merging in one element . Relation will be (1,1)

(b) not reflexive

f  has 2 elements , say i.e. 1,2 .But relation is (1,1) or (2,2) , but may not both

(c) not reflexive, not symmetric

distance between same element of f to g is 1 . But distance between g to f is -ve , which is not possible. So, it is not even symmetric
by Veteran (119k points)
edited by
$f$ is a function rt? So, $f$ has one element means?
for eg. f(0)=1 means f(0) is mapping on element 1.

here f(1)=g(1)

means if f(1)=1, then g(1)=1.

then relation will be {(1,1) | f(1)=g(1)} [putting value of f and g]

right sir?
mostly correct. It just says a relation based on mapping for element '1'. All other integers can be mapped to anything- like f(2) = 3, g(2) = 4 etc. To check the satisfiability of the relation we just see the mapping of element 1. But we cannot write it like {(1,1)} because then first we have to define what the ordered pair represents- even if we say it is f(1) and g(1), f(1) = g(1) = 2 is also possible.
"All other integers can be mapped to anything"

doubt in this line.

may be there are all elements present , but mapping is not possible in such a manner. Otherwise equivalence relation will be violated.

but yes f(1)=g(1)=2 or f(1)=g(1)=3.......these are possible
All element must be present- otherwise it won't be a function. And in a set definition if we don't restrict anything (of course from the co-domain set which is $Z$ here), it can take any value. i.e., $f(2) = 5, g(2) = 10, f(3) = 104, g(3) = 65$ etc. are all valid and $f$ and $g$ still satisfy the relation as long as $f(1) = g(1) = a$, where $a \in Z$.
That is where my question belongs. f(1)=(g(1) means two functions f and g are mapped into same element, of course we can't say for all element it is true. But how do I check (1,1) i.e reflexivity from this.
$f = g$, means for any $x, f(x) = g(x)$. $f(1) = g(1)$ means mapping is same for element 1, may or may not be for others.

Now, reflexivity requires $f$ related to $f$. $f=f$ is true here and this implies $f(1) = f(1)$ and hence $f$ related to $f$.
(b) is reflexive and symmetric but not transitive
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,384 answers
105,340 users