7.3.1 Foundations

Let $A$ be a set.

Definition 7.3.1.1.1 ▶ Transitive Relations

A transitive relation is equivalently:[1]

  • A non-unital $\mathbb {E}_{1}$-monoid in $\webleft (\mathrm{N}_{\bullet }\webleft (\mathbf{Rel}\webleft (A,A\webright )\webright ),\mathbin {\diamond }\webright )$.
  • A non-unital monoid in $\webleft (\mathbf{Rel}\webleft (A,A\webright ),\mathbin {\diamond }\webright )$.

Remark 7.3.1.1.2 ▶ Unwinding Definition 7.3.1.1.1

In detail, a relation $R$ on $A$ is transitive if we have an inclusion

\[ \mu _{R}\colon R\mathbin {\diamond }R\subset R \]

of relations in $\mathbf{Rel}\webleft (A,A\webright )$, i.e. if, for each $a,c\in A$, the following condition is satisfied:

  • If there exists some $b\in A$ such that $a\sim _{R}b$ and $b\sim _{R}c$, then $a\sim _{R}c$.

Definition 7.3.1.1.3 ▶ The Po/Set of Transitive Relations on a Set

Let $A$ be a set.

  1. The set of transitive relations from $A$ to $B$ is the subset $\smash {\mathrm{Rel}^{\mathrm{trans}}\webleft (A\webright )}$ of $\mathrm{Rel}\webleft (A,A\webright )$ spanned by the transitive relations.
  2. The poset of relations from $A$ to $B$ is is the subposet $\smash {\mathbf{Rel}^{\mathsf{trans}}\webleft (A\webright )}$ of $\mathbf{Rel}\webleft (A,A\webright )$ spanned by the transitive relations.

Proposition 7.3.1.1.4 ▶ Properties of Transitive Relations

Let $R$ and $S$ be relations on $A$.

  1. Interaction With Inverses. If $R$ is transitive, then so is $R^{\dagger }$.
  2. Interaction With Composition. If $R$ and $S$ are transitive, then $S\mathbin {\diamond }R$ may fail to be transitive.

Proof of Proposition 7.3.1.1.4.

Footnotes

[1] Note that since $\mathbf{Rel}\webleft (A,A\webright )$ is posetal, transitivity is a property of a relation, rather than extra structure.
[2] Intuition: Transitivity for $R$ and $S$ fails to imply that of $S\mathbin {\diamond }R$ because the composition operation for relations intertwines $R$ and $S$ in an incompatible way:
  1. If $a\sim _{S\mathbin {\diamond }R}c$ and $c\sim _{S\mathbin {\diamond }r}e$, then:
    1. There is some $b\in A$ such that:
      1. $a\sim _{R}b$;
      2. $b\sim _{S}c$;
    2. There is some $d\in A$ such that:
      1. $c\sim _{R}d$;
      2. $d\sim _{S}e$.
Next

View Subsection 7.3.1 as PDF

Statistics Cite

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

You can also use the contact form below: