1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (a) What about $f(x)=x+17$? $\endgroup$ – Julien Apr 9 '13 at 23:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Julien Apr 9 '13 at 23:56
  • $\begingroup$ @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. $\endgroup$ – Greg Martin Apr 10 '13 at 0:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Julien Apr 10 '13 at 0:20
  • $\begingroup$ @GregMartin See this thread. Or that thread. You'll be happy to see that Arturo Magidin uses "if and only if" in his definitions. $\endgroup$ – Julien Apr 10 '13 at 0:33
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.