2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What a beautiful proof! My upvote and acceptance don't get to convey how impressed I am by it. $\endgroup$
    – kjo
    May 30 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.