I've read all the stack threads I can find on transitive functions and want to pull together the ideas/questions it leaves me with. This all started because as per this thread I wrongly thought functions could never be transitive:
- I've put a number of questions/topics in this thread as they are interrelated.
- Please feel free just to bite off individual questions.
- Huge thanks in advance to anyone who answers/corrects/comments on any of the following!
An ordered pair is represented as (INPUT, OUTPUT): e.g. (1,2), (a,b), (x,y)
[Q1: Can I define an ordered pair of vectors as (x,y)?]
Relation: A relation tells us the relationship between an input and an output.
- If our relation is < we have $_1R_2$ as $1<2$
- If our relation was x•y $= 0$ we could have $_{[1,2]}R_{[-2,1]}$
Function: A function is also a relation, but one in which there is only one output for each given input. I.e. the vertical line test (If a graph has two y values for one x value it's not a function).
- We could view $y = f(x)=x^2$ as a relation $_xR_y$ e.g. $_2R_4$
[Q2 How could we define this Relation? E.g. $R = \left\{(x,y)|x^2 = y\right\}$]
[Q3: And how do we write a function as a relation?]: In this thread the top answer has written a function as a relation as "$aRf(a)$" where I assume we can just define $b=f(a)$?
- I'm sure this is correct and makes sense but it bothers me because: With other relations e.g. < we have $_1R_2$ as $1<2$. The relation goes in the middle i.e. the analogue here would be $_2f_4$.
- I assume $_2f_4$ makes no sense. But I find It weird that the function $f$ is both the relation $R$ and also the output $f(a)$.
- Perhaps the answer is, that I need to mentally separate $f$ and $f(a)$ where the latter is actually just $b$?
Transitive relations: A relation $R$ is transitive if $\forall a, b, c,\in X$, $aRb \land bRc \implies aRc$, where e.g. $R \subset X \times X$,
Transitive Functions: By the definition of a function, and the notation discussed earlier, a transitive function $f$ satisfies:
$aRf(a) \land f(a)Rc \implies aRc$, $f(a) = b, f(b) = c$, where e.g. $f:\mathbb{R} \to \mathbb{R}$,
- This tells us that $b = f(a) = c = f(b)$
- $\therefore b = c \implies f(b) = b, \forall b\in \mathbb{R}$
- $\therefore f(x) = x$ and Hence $f(f(x)) = f(x) = x$ so the function $f$ is idempotent?
[Q4: $f$ is Idempotent $\iff$ $f$ is Transitive – I'm unsure about this, see next section]
Examples of these transitive functions?
This post the answer gives an example of a function as a Transitive Relation: "$f:X \to X$ defined by $f(x)=x$"
- The author of the answer kindly confirmed that this was just the Identity function. He also says:
"$f$ is a Transitive Relation $\iff f \circ f = f$."
[Q5: Is he saying the same as my point in Q4, i.e. for a function $f$, Transitive $\iff$ Idempotent?]
[Q6: If $f$ is Idempotent $\iff$ $f$ is Transitive, were true, then surely $f$ is Transitive $\iff$ $f$ is Identity function. As by definition $f(x) = x, \forall x$ is always the identity function? Surely this can't be the case]
[Q7: $f$ is idempotent $\iff$ $f$ is identity? I know projection matrices are Idempotent, so not only the Identity Matrix is Idempotent, but it's less clear to me when looking at functions].
The approved answer to this post provided an example of a function that is transitive, non-reflexive and non-symmetric i.e. it can't be idempotent, or the identity I believe:
- The author said the following, and then gave the preceding example:
Suppose $f$ makes $R_a$ transitive. Let $y,z\in \mathbb{N}$ such that $$f(x)=y, f(y)=z$$ for some $x \in \mathbb{N}.$ Transitivity now implies $f(x)=z.$ So $y=z.$
So $f(y)=y$ for every $y \in f[\mathbb{N}].$
$f(n)=\begin{cases}1, \text{if }n \text{ is odd}\\2, \text{ if }n \text{ is even}\end{cases}$
[Q8 I was confused by this as $f(y)=y$ for every $y \in f[\mathbb{N}].$ seems to imply $f$ is Idempotent? But, is $f(x)=x$, not the same as $f(y) = y$ because the second equation is only using the range as inputs. If this is correct, can you say something like $f$ is Idempotent $\forall x\in f[\mathbb{N}]$. I believe [Q11] might be referring to this].
- I believe $f(x) = |x|$ could also be anther example of a function that is Transitive, and not Idempotent, similar to above?
- $f(-2) = 2 \land f(2) = 2 \implies _{-2}R_2$
[Q9 Here we have shown: $aRb \land bRc \implies aRc$, but $b=c$ Is $b=C$ valid for a Transitive Relation? I assume it is and the conclusion is as above i.e. $f(y) = y, \forall y \in \mathbb{R^+} $]
[Q10 A function $f$ is a Congruence Relation $\iff f$ is the Identity function]
How many functions $f:\left \{ a,b,c,d \right \}\rightarrow \left \{ a,b,c,d \right \}$ are also transitive relations?
This question has appeared in Post 1 and Post 2, but both are super old:
I'm not concerned with the answer, but with some of the comments:
- Post 1 says:
"I've been told to use the fact that "a function is transitive iff it's restriction to it's image is the identity function on it's image".
- Post 2 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)}$
[Q11: Are all three conditions across Post 1 and Post 2, saying the same thing? Can someone unpack this for me please?]
- I think it's getting at what we previously discussed regarding $f(y) = y$ i.e. if the function is evaluated with objects in it's range, it becomes it's own identity function? Something like that?
The author of the approved answer to Post 1 stated that:
If we take $R$ to be the relation which has $aRf(a)$, then it will be transitive if $aRf(a)$ and $f(a)Rb$ implies $aRb$. But since $f()$ is a function that means $b$ must equal $f(a)$. In other words, the point $f(a)$ which belongs to the image of $f()$ is fixed.
That explains the terminology. Answering the question requires careful counting. Let us count functions with 1,2,3,4 fixed points. Note that the image has at least one point and that is fixed, so those are the only possibilities.
Taking the easiest first, suppose it has 4 fixed points….
[Q12: As with Q11 I think I'm super close to understanding this idea that the point, belonging to the image which is fixed. And there being multiple fixed points, but clarification would be appreciated].
A huge thanks to anyone who has got this far. All thoughts, clarification and grillings are welcome!
Best Answer
Q1: Can I define an ordered pair of vectors as $(x,y)$?
Yes. For instance, let x $ = (1,2) \in \mathbb{R}^2$ and y $ = (3,5) \in \mathbb{R}^2$.Then, $($ x $,$ y $)$ $ = ((1,2),(3,5)) \in \mathbb{R}^2 \times \mathbb{R}^2$.
Q2: How could we define this relation $R = \{ (x,y) | x^2 = y \}$?
You offer an (almost) perfectly satisfactory definition in the very question you pose. The expression $R = \{ (x,y) | x^2 = y \}$ defines the set $R$ of all ordered pairs $(x,y)$ such that $x^2 = y$. However, it is unclear where the $x$'s and $y$'s are coming from. Are they coming from the set of the integers? Are they coming from the set of the reals? To be perfectly clear, you could specify $R = \{ (x,y) \in \mathbb{R}^2 | x^2 = y \}$ or $R = \{ (x,y) \in \mathbb{Z}^2 | x^2 = y \}$.