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

Question

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$.

Answer 1

$(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....

Answer 2

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.