Let A = {1,2,3,4} Let F be the set of all functions from A to A. (check the parts) Let $\operatorname{S}$ be a relation on $F$ defined by: $\forall f, g \in F, f\,\operatorname{S}\,g \iff f(i) = g(i), \exists i \in A$.
(a) Recall that the identity function $I_A : A \mapsto A$ is defined by $I_A(x)= x, \forall x \in A$. Find two different functions $f, g : A \mapsto A$ so that $f \neq I_A \neq g \;\land\; f\,\operatorname{S}\,I_A \;\land\; g\,\operatorname{S}\,I_A$.
(b) Is $\operatorname{S}$ reflexive? ... symmetric? ... transitive? Prove your answer.
(c) Let $h: A \mapsto A$ be the function defined by $h(x) = 1, \forall x \in A$. How many functions $g \in F$ are there so that $g\,\operatorname{S}\,h$?
(d) With the function $h$ as in part (c), how many one-to-one functions $g\in F$ are there so that $g\,\operatorname{S}\,h$? 
Note: I can't figure out anything in any of the parts in this question, any help will be highly appreciated, I'm totally lost. 
 A: If $f$ and $g$ are functions from $A$ to $A$, we say that $fSg$ if $f(i)=g(i)$ for some $i$, that is, if $f$ and $g$ agree somewhere. 
(a) The question is not quite typed out correctly. But it looks as if we want functions $f$ and $g$, which each agree with the identity somewhere, but are different in some sense. For example, we can let $f(a)=1$ for all $a$, and $g(a)=2$ for all $a$.
(b) Is $S$ reflexive? Does $f$ agree with $f$ somewhere? Sure, $f$ agrees with $f$ everywhere. 
Is $S$ symmetric? If $f$ agrees with $g$ somewhere, does $g$ agree with $f$ somewhere? Sure. 
Is $S$ transitive? No. For example, let $f(a)=1$ for all $a$. Let $g(1)=1$, and $g(a)=2$ if $a\ne 1$. Let $h(a)=2$ for all $a$. Then $f$ and $g$ agree somewhere, and $g$ and $h$ agree somewhere, but $f$ and $h$ agree nowhere.
(c) We want to find out how many functions agree with $h$ somewhere. Call such a function good. Note that there are $4^4$ functions from $A$ to $A$. We will count the bad ones, the ones that do not take the value $1$ anywhere. So the permitted values are $2$, $3$, and $4$, three of them. It follows that there are $3^4$ bad functions, and therefore $4^4-3^4$ good functions. 
(d) Your turn. Please give it a good try, and leave a message if there remain uncertainties. There are not a lot of one to one functions, so at worst you can produce an explicit list for (d) and count.  
