# Find the number of distinct equivalence classes $[f]$ of $R$.

Let $A$ and $B$ be subsets of the set $\Bbb Z$ for all integers, and let $\mathscr F$ denote the set of all functions $f:A\rightarrow B.$

Define a relation $R$ on $\mathscr F$ by : for any $f,g \in \mathscr F$, $\;fRg\;$ if and only if $f - g$ is a constant function (i.e. there is a constant $c$ so that $f(x) - g(x) =c$ for all $x\in A$).

(a) Suppose that $A = B =\Bbb Z$. Let $I_Z$ be the identity function on $\Bbb Z$. Find a function $f\neq I_Z$ which belongs to the equivalence class $[I_Z].$

Assume $A = \{1,2,3\}$ and $B=\{1,2,...,n\}$ where $n\ge 2$ is a fixed integer.

(b) Find the number of functions $f \in \mathscr F$ so that $[f]=${$f$ }

(c) Find the number of distinct equivalence classes $[f]$ of $R$.

• (a) What about $f(x)=x+17$? – Julien Apr 9 '13 at 23:52
• Nitpicking: when one defines something in mathematics (unlike in logic or in philosophy), one should use "if", and not "if and only if". See the paragraph on definitions here. – Julien Apr 9 '13 at 23:56
• @julien: I completely disagree here. When defining a piece of terminology, "if" is standard (although I still wouldn't call "if and only if" wrong). But here we are defining a specific set (namely the relation $R$); so we should specify exactly when something is in the set, not just a necessary condition. – Greg Martin Apr 10 '13 at 0:13
• @GregMartin When one defines something in mathematics, and here it is explicit that what is after $fRg$ is a definition, the use of "if" means an equivalence between the word, the symbol, the set, whatever is being defined, and the subsequent assertion. Not a sufficient (where you said necessary) condition. It goes like that in a majority of written mathematical works. And so you completely disagree with these. Not with me. But you can use "if and only if" in your definitions, I will still understand. – Julien Apr 10 '13 at 0:20
• @GregMartin See this thread. Or that thread. You'll be happy to see that Arturo Magidin uses "if and only if" in his definitions. – Julien Apr 10 '13 at 0:33

$(b)$ Hint $g \in [f]$ if and only if $g=f+c$.

The only way in which $[f]=\{ f \}$ is if no other $f+c$ works. $f+c$ is a function on $A$, but might not have the range $\{ 1,2,3,..,n \}$

This tells you that $[f]=\{ f \}$ if and only if for all real numbers $c \neq 0$ the image of $f+c$ is not inside $\{ 1,2,3,..,n \}$. This tells you something about $f$ [ think which are the smallest and largest values $f$ can take].

(c) If $f$ is any function, then you can prove that there exists an unique function $f \in [f]$ so that $1 \in Im(g)$. That should help you find the answer....

Hints:

(a) You've defined $R$ by saying two functions are related when they differ by a constant. So try adding a constant to $I_{\mathbb Z}$.

(b) If $[f] = \{f\}$ then it must be that you can't shift $f$ up or down, so it must take the values $1$ and $n$ somewhere...

(c) You can always shift down so that $1$ is in the image of $f$. This gives you a unique representative for the equivalence class of $f$. So you need to count the number of functions $A \to B$ with $1$ in the image.