On a decomposition of pairs in the transitive closure $T$ of an arbitrary relation $R$

Question

Let $S$ be some set, and let $R$ be a relation with $\operatorname{dom}(R) = \operatorname{ran}(R) = S$. Hence $R \subseteq S \times S$. Let $T$ be the transitive closure of $R$, defined as the smallest transitive relation that contains $R$. Or, symbolically: $$T = \bigcap\, \{U: R \subseteq U\subseteq S\times S \; \wedge \; U\,\mathrm{is\;transitive} \}.$$

(Since $S \times S$ itself is a transitive relation, the argument of the $\bigcap$ operator above is nonempty.)

I recently came across the following assertion, which I think is correct, but have a hard time proving.

Claim: If $x, y \in S$ and $xTy$, then either $xRy$ or there exists a $z \in S$ such that $xTz$ and $zRy$.

I think that this claim is true, because I visualize the process of creating the transitive closure of a relation as one of "recursively adding the pair $(a, c)$ whenever the pairs $(a, b)$ and $(b, c)$ are available, until no more pairs can be added." Therefore, if (1) the transitive closure $T$ of $R$ includes the pair $(a, c)$, and (2) it is not the case that $a R c$, then there must exist some $b \in S$ such that $aTb$ and $bTc$. This is not too far from the stronger claim that the $b$ is such that not only $bTc$, but that $bRc$.

But this is all hand-waving, based on my intuitive vision of some imaginary "process" whereby one "generates" the transitive closure of a relation.

The problem of proving the claim above is made all the more difficult by the fact that I came across it in the course of solving a problem on Zermelo ordinals in a textbook of set theory, and this problem occurred before the autor had gotten around describing even an order relation for Zermelo ordinals, let alone a well-ordering for them, or any notion of induction or recursion based on them¹.

In fact, for the textbook's problem, all one could assume were Zermelo's original Axiom of Infinity (i.e. $\exists w [\varnothing \in w \ \wedge \ \forall x\in w (\{x\} \in w)]$) together with the remaining currently standard ZF axioms².

Without recursion, induction, well-ordering, etc. I don't know even where to begin proving the claim above.

Of course, I understand that $(R \subseteq T) \leftrightarrow ((x, y) \in R \to (x, y) \in T) \leftrightarrow (xRy \to xTy)$. Therefore, I see that if $xTy$, one possibility is that $xRy$. My problem is to show that $$(xTy \wedge \lnot xRy)\to \exists z \in S(xTz \wedge zRy)$$

---

EDIT: A different way to phrase the same problem uses the notion of composition of relations. The composition $G \circ F$ of relations $G$ and $F$ is defined as $$G \circ F := \{(x, y) \in \operatorname{dom}(F) \times \operatorname{ran}(G): \exists z[(x, z) \in F \wedge (z, y) \in G]\}.$$

This notation allows the following characterization of transitivity: a relation $U$ is transitive iff $U\circ U \subseteq U$.

This notation also can also be used to give an equivalent formulation of the claim above as an assertion about set inclusion: $$ T \subseteq R \cup (R \circ T).$$

It is not hard to show the opposite inclusion: $$R \subseteq T \to R\circ T \subseteq T \circ T = T \to R \cup (R \circ T) \subseteq T,$$

...so proving the desired conclusion amounts to proving that

$$ T = R \cup (R \circ T).$$

---

^{1 In fact, the claim about transitive closures that this post is about arose in the context of proving that the transitive closure of the $\in$ relation could serve as a well-ordering for the set $z$ of Zermelo ordinals. In contrast to what is the case with the now-standard von Neumman ordinals, where for any two distinct ones of them, $m$ and $n$, either $m \in n$ or $n \in m$, with Zermelo ordinals, the $\in$ relation holds only between such an ordinal $n$ and its successor $\{n\}$. Hence, $\in\!\!|_z\subseteq z \times z$ is not even an partial order for $z$ (since it is not transitive), let alone a well-ordering for it.}

^{2 Extensionality, Foundation, Comprehension/Separation, Pairing, Union, Replacement, and Power Set.}

Answer 1

Let $U$ be the set of pairs $(x,y)\in S\times S$ such that either $xRy$ or there exists $z\in S$ such that $xTz$ and $zRy$. We wish to show that $T\subseteq U$, so by definition of $T$, it suffices to show that $R\subseteq U\subseteq S\times S$ and $U$ is transitive. The first part is trivial. For transitivity, suppose $aUb$ and $bUc$. Note first that $aUb$ implies $aTb$ since $T$ is transitive and contains $R$. Also, either $bRc$ or there is some $z$ such that $bTz$ and $zRc$. Letting $z=b$ in the first case, either way we can conclude that $aTz$ and $zRc$ and thus $aUc$, as desired.