Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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$

share|improve this question
4  
Please consider reading this meta-thread on asking homework questions: How to ask a homework question?. Specifically, we are not a homework-answering service, but rather a community of people who'd like to help you learn. If you can show us what you've tried and where you're stuck, we'd be able to help you a lot better. Also, please limit yourself to one question (or if they're very similar, maybe two) per thread--this helps things stay organized. –  anorton Apr 11 '13 at 0:33
1  
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
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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