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

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 them1.

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 axioms2.

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.

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.