# Discrete Math functions and sets

1. Let $A$ and $B$ be subsets of $\Bbb{Z}$, and let $F = \{f : A\to B\}$. Define a relation $R$ on $F$ by: for any $f,g\in F$, $fRg$ if and only if $f - g$ is a constant function; that is, there is a constant $c$ so that $f(x) - g(x) = c$ for all $x\in A$.

Assume that $A=\{1,2,3\}$ and $B=\{1,2,\ldots,n\}$ where $n \geq 2$ is a fixed integer

(a) Let $f_1\in F$ be defined by: $f_1(1) = 2$, $f_1(2) = n$, $f_1(3) = 1$. (As a set of ordered pairs, $f_1 = \{(1,2), (2,n), (3,1)\}$) Suppose that $g\in F$ is arbitrary so that $gRf_1$. Prove that $g = f_1$, and thus the equivalence class $[f_1]$ is just $\{f_1\}$.

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

(c) Prove that for all $f \in F$, there exists $g \in [f]$ so that $1$ is in the range of $g$.

(d) Prove that for all $g,h \in F$ with $gRh$, if there exists $a,b\in A$ such that $g(a) =1$ and $h(b)=1$, then $g=h$

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

-
This is exactly identical to what my assignment is... Try to figure it out yourself first? You can't expect people to do your work for you without showing any effort first. – crazymao Apr 11 '13 at 5:43
You might find it useful (I did) to think in terms of the graphs of these functions, i.e., to view functions as sets of ordered pairs and to plot these ordered pairs as points in the plane. The equivalence relation $R$ can then be visualized as sliding graphs up or down in the plane, but because the functions must map into $B$, the graphs can only slide up and down so far. – Andreas Blass Aug 11 '13 at 5:09

I’ll get you started.

(a) Suppose that $gRf_1$. Then there is a constant $k$ such that $g(n)-f_1(n)=k$ for each $n\in A$. In particular,

\begin{align*} &g(1)-f_1(1)=g(1)-2=k\;,\\ &g(2)-f_1(2)=g(2)-n=k\;,\text{ and }\\ &g(3)-f_1(3)=g(3)-1=k\;, \end{align*}

or

\begin{align*} &g(1)=k+2\;,\\ &g(2)=k+n\;,\text{ and }\\ &g(3)=k+1\;. \end{align*}\tag{1}

Now recall that $B=\{1,2,\dots,n\}$, so that $n$ is the largest element of $B$, and that $g$ is a function from $A$ to $B$; from this and the appropriate part of $(1)$ you can determine exactly what $k$ is and hence what $g$ is.

(b) Once you understand what it is about the function $f_1$ in part (a) that ensures that $[f_1]=\{f_1\}$, you have only to count the functions from $A$ to $B$ that have that same characteristic. The crucial step is identifying the characteristic; part (a) is there to help you do so. If you successfully identify it and then find that you have trouble counting the functions that have it, you should probably ask that as a separate question.

(c) If $1$ is in the range of $f$, you can take $g=f$, so suppose that $1$ is not in the range of $f$. Let $r$ be the smallest number in the range of $f$. What happens if you shift the graph of $f$ down by $r-1$ units?

(d) There really isn’t much point worrying about this one until you’ve worked your way through the first three parts; it depends on the same ideas, but in a slightly more complicated way. Once you’ve done the first three parts, if you still can’t solve this one, make it a new question.

(e) And this is the culmination of the work done in the first four parts; the advice that I gave for (d) applies here at least as strongly.

-