0
$\begingroup$

I want to understand/unpack this definition of a transitive function:

"A function is transitive iff it's restriction to it's image is the identity function on it's image" (From This post).

I believe it's saying that if we have $f: X \to Y$, then $\forall y \in Y, f(y) = y$.

  • Essentially the function is idempotent If evaluated at it's image, but not in general i.e. we do not necessarily have $f(x) = x, \forall x \in X$. Otherwise surely the only transitive function would be the identity function. Am I close?

Example

A transitive function $f: X \to Y$, satisfies:

$aRf(a) \land f(a)Rc \implies aRc$, where $f(a) = b, f(b) = c$

  • This tells us that $b = f(a) = c = f(b)$
  • $\therefore b = c \implies f(b) = b, \forall b\in Y$
  • $\therefore f(y) = y$, $\forall y \in Y$.

Similar Definitions:

  • This post about transitive relations has a comment saying:

"The condition [$<a,b>\in f \implies <b,b>\in f$] is equivalent to $f|_{\operatorname{im}(f)}=\operatorname{id}_{\operatorname{im}(f)}$

"$f$ is a Transitive Relation $\iff f \circ f = f$."

  1. Are these all saying the same thing?
  2. Are they saying the same as my explanation or am I wrong?

Thanks!

$\endgroup$

1 Answer 1

3
$\begingroup$

I'm not used to transitive meaning this, but I can comment on your interpretations.

I believe it's saying that if we have $f:X\to Y$ then $\forall y\in Y,\,f(y)=y$

There are two things wrong with this. Firstly, for generic sets $X,Y$, it makes no sense (it is undefined) to write $f(y)$ for $y\in Y$ when the function $f$ is defined on $X$. It does make sense if, say, $Y\subseteq X$, but not in general. So, we should have $f:X\to X$. The other problem is that you want, for all $y\in Y$, $f(y)=y$. But they only want $f$ to be the identity on its image, so you should have quantified: $\forall y\in Y,\,\exists x\in X,\,y=f(x),\,f(y)=y$ - if you like symbolic descriptions, that is.

Now if we wish to interpret a function as a relation - which is the standard 'implementation' of function - then these posts call functions transitive if the associated relation is transitive. Notice that relations are only said to be transitive when they are also endorelations, i.e. a subset of $X\times X$ for some set $X$. This is another reason why we need $f:X\to X$.

The associated relation $R$ is $(a,b)\in R$ iff. $b=f(a)$. For this to be transitive, $a\sim b$ and $b\sim c$ should mean $a\sim c$. Unwinding definitions, if $b=f(a)$ and $c=f(b)$, then $c=f(a)$. So $f(a)=c=f(b)=f(f(a))$ for all $a\in X$.

Now you should see that the relation induced by $f$ is transitive if and only if the function $f$ satisfies $f\circ f=f$, i.e. it is idempotent. That is the exact same thing as saying "$f$ is the identity on its image."

The comment about $(a,b)\in f$ is abuse of notation, let's rather say, $(a,b)\in R\implies(b,b)\in R$. That's saying $b=f(a)\implies b=f(b)$, which is the same as: $f(f(a))=f(a)$ (for all $a$) hence $f\circ f=f$.

$\endgroup$
8
  • $\begingroup$ Hi @FShrike, thanks for the answer and detail, and thanks for correcting my early thinking. Most of it makes sense to me, the bit I'm having trouble with is the Idempotence. This was my initial assumption I made, but now I'm not sure. For example the post linked in next comment includes transitive functions that are not idempotent, I think the absolute value function would also be an example? Surely identity on the image, would mean that, when the function is evaluated at points that are in it's image i.e. y, then it returns that same value y? Please elaborate if you have time! Thanks! $\endgroup$ Commented Jan 6, 2023 at 18:32
  • $\begingroup$ See for example the accepted answer here. I'm happy to be wrong, I just can't square what you are saying with the answers in this post: math.stackexchange.com/questions/3666464/… $\endgroup$ Commented Jan 6, 2023 at 18:33
  • $\begingroup$ @CormJack The absolute value function is idempotent. $|(|x|)|=|x|$ for all real $x$ $\endgroup$ Commented Jan 6, 2023 at 18:42
  • $\begingroup$ Okay in that case I think I've miss-understood idempotence then. I assumed idempotence would mean that we would also need $f(x) = x$, but that's wrong I assume. It just means $f(fx) = f(x)$. Is that correct? $\endgroup$ Commented Jan 6, 2023 at 18:44
  • 1
    $\begingroup$ @CormJack Identity is $f(x)=x$ for all $x$. Idempotence is $f(f(x))=f(x)$ for all $x$! $\endgroup$ Commented Jan 6, 2023 at 18:45

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.