Function composition according to relation

Question

• Let $f: A \rightarrow A \ $ and a relation $R_f$ over $A$ $\, $s.t.: $R_f = \left\{(x,y) \in A \times A \mid y=f(x)\right\}$

• Show if the following statements are true or false and explain your choice:

  1. If $\ R_f \ $ is transitive $\implies$ $f \circ f \circ f = f$

  2. If $\ R_f \ $ is symmetric $\implies$ $f \circ f \circ f = f$

  3. If $f \circ f \circ f = f$ $\implies$ $R_f$ is symmetric or $R_f$ is transitive

  4. If $R_f$ is anti-symmetric $\implies$ $f$ is one-to-one or there is $x \in A \ \ s.t. \ f(x)=x$

• So my attempts:

  1. $R_f$ is transitive $\implies$ $x, y, z \in A \ \ s.t. \ \ (x, y), (y, z), (x, z) \in R_f. \ \ $ Then we know $y=f(x) \ \ z=f(y) \ \ z=f(x) \implies z=f(y) = f(f(x)) \implies f = f \circ f$ $\ $ but not three compositions as required.

  2. The same process goes with this.

• About the rest - have no idea.

Answer 1

You made a good start on 1. In fact, you showed that for any $x$: $f(f(x))=f(x)$. But if that is true, then $f(f(f(x)))=f(f(x))=f(x)$, and so indeed $f \circ f \circ f = f$

For 2, if $R_f$ is symmetric, then if $f(x)=y$, then $f(y)=x$. Hence: $f(f(f(x)))=f(f(y))=f(x)$. And so again: $f \circ f \circ f = f$

For 3: OK, so we know $f(f(f(x)))=f(x)$. OK, so let $y=f(x)$ and $z=f(y)=f(f(x))$. So, $f(f(f(x)))=f(z)=f(x)$. Well, how can $f(x)=f(z)$?