Item 3 (00V5) — The Clowder Project

Table of Contents
Part 3: Relations
Chapter 10: Conditions on Relations
Section 10.4: Transitive Relations
Subsection 10.4.2: The Transitive Closure of a Relation
Item 3 (cite)

1 tag refers to this tag

10.4.2 The Transitive Closure of a Relation

Let $R$ be a relation on $A$.

Definition 10.4.2.1.1 ▶ The Transitive Closure of a Relation

The transitive closure of $\mathord {\sim }_{R}$ is the relation $\smash {\mathord {\sim }^{\mathrm{trans}}_{R}}$¹ satisfying the following universal property:²

(★)

¹Further Notation: Also written $R^{\mathrm{trans}}$.
²Slogan: The transitive closure of $R$ is the smallest transitive relation containing $R$.

Construction 10.4.2.1.2 ▶ The Transitive Closure of a Relation

Concretely, $\smash {\mathord {\sim }^{\mathrm{trans}}_{R}}$ is the free non-unital monoid on $R$ in $\webleft (\mathbf{Rel}\webleft (A,A\webright ),\mathbin {\diamond }\webright )$¹, being given by

\begin{align*} R^{\mathrm{trans}} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\coprod _{n=1}^{\infty }R^{\mathbin {\diamond }n}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{n=1}^{\infty }R^{\mathbin {\diamond }n}\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ \webleft (a,b\webright )\in A\times B\ \middle |\ \begin{aligned} & \text{there exists some $\webleft (x_{1},\ldots ,x_{n}\webright )\in R^{\times n}$}\\ & \text{such that $a\sim _{R}x_{1}\sim _{R}\cdots \sim _{R}x_{n}\sim _{R}b$}\end{aligned} \right\} .\end{align*}

¹Or, equivalently, the free non-unital $\mathbb {E}_{1}$-monoid on $R$ in $\webleft (\mathrm{N}_{\bullet }\webleft (\mathbf{Rel}\webleft (A,A\webright )\webright ),\mathbin {\diamond }\webright )$.

Proof of Construction 10.4.2.1.2.

Clear.

Proposition 10.4.2.1.3 ▶ Properties of the Transitive Closure of a Relation

Let $R$ be a relation on $A$.

1.
Adjointness. We have an adjunction
witnessed by a bijection of sets

\[ \mathbf{Rel}^{\mathsf{trans}}\webleft (R^{\mathrm{trans}},S\webright ) \cong \mathbf{Rel}\webleft (R,S\webright ), \]

natural in $R\in \operatorname {\mathrm{Obj}}\webleft (\mathbf{Rel}^{\mathsf{trans}}\webleft (A,A\webright )\webright )$ and $S\in \operatorname {\mathrm{Obj}}\webleft (\mathbf{Rel}\webleft (A,B\webright )\webright )$.
2.
The Transitive Closure of a Transitive Relation. If $R$ is transitive, then $R^{\mathrm{trans}}=R$.

3.
Idempotency. We have

\[ \webleft (R^{\mathrm{trans}}\webright )^{\mathrm{trans}} = R^{\mathrm{trans}}. \]

Interaction With Inverses. We have

Interaction With Composition. We have

Proof of Proposition 10.4.2.1.3.

Item 1: Adjointness

This is a rephrasing of the universal property of the transitive closure of a relation, stated in Definition 10.4.2.1.1.

Item 2: The Transitive Closure of a Transitive Relation

Clear.

Item 3: Idempotency

This follows from Item 2.

Item 4: Interaction With Inverses

We have

\begin{align*} \webleft (R^{\dagger }\webright )^{\mathrm{trans}} & = \bigcup _{n=1}^{\infty }\webleft (R^{\dagger }\webright )^{\mathbin {\diamond }n}\\ & = \bigcup _{n=1}^{\infty }\webleft (R^{\mathbin {\diamond }n}\webright )^{\dagger }\\ & = \webleft (\bigcup _{n=1}^{\infty }R^{\mathbin {\diamond }n}\webright )^{\dagger }\\ & = \webleft (R^{\mathrm{trans}}\webright )^{\dagger }, \end{align*}

where we have used, respectively:

•
Construction 10.4.2.1.2.
•
Chapter 9: Constructions With Relations, of .
•
Chapter 9: Constructions With Relations, of Proposition 9.3.3.1.2.
•
Construction 10.4.2.1.2.

This finishes the proof.

Item 5: Interaction With Composition

This follows from Item 2 of Proposition 10.4.1.1.4.

Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

•Email
•Discord

You can also use the contact form below: