2

A function by definition is a relation in which no two ordered pairs have the same first element, and every element in domain has an image in codomain. A relaton $R$ is transitive if for all values $a, b, c$: $a R b$ and $b R c$ implies $a R c$. So does it mean a function can never be transitive ?

Andrés E. Caicedo
  • 79,201
Prem Prakash Hessa
  • 21
  • 1
    It requires that if $f(a)=b$ and $f(b)=c$ then $f(a)=c$ but that requires $b=c$. We can have a function $f:{a,b,c,d,e,h}$ where $f(a)=b;f(b)=b; f(c)=d; f(d)=d; f(e)=h;f(h)=h$. And that'd be transitive. – fleablood Jun 19 '20 at 06:54

1 Answers1

2

Not quite, but close. The function $f:X \to X$ defined by $f(x)=x$ is a transitive relation. Your proof fails because you don't know that $b \neq c$.

Edited to add:

I believe your proof does show that $f$ is a transitive relation $\iff f \circ f = f$.

Robert Shore
  • 23,332
  • another counter example is the empty function. – Amit Keinan Jun 19 '20 at 14:17
  • Is this just the identity function you have described @Robert Shore? Thanks! – CormJack Dec 12 '22 at 21:13
  • @CormJack That's correct. That's the only function that is also (considered as a relation) an equivalence relation. – Robert Shore Dec 13 '22 at 00:37
  • Thank you very much @Robert Shore. I've actually just done a bit of a meta post about Transitive Relations and Functions, trying to piece together the input from different threads. And ask unsatisfied questions. Your answer also very helpfully features: https://math.stackexchange.com/questions/4597979/relations-transitive-functions-idempotent-functions – CormJack Dec 13 '22 at 17:14