10.4.1 Foundations

    Let $A$ be a set.

    Definition 10.4.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 )$.

    1. 1Note that since $\mathbf{Rel}\webleft (A,A\webright )$ is posetal, transitivity is a property of a relation, rather than extra structure.

    Remark 10.4.1.1.2 ▶ Unwinding Definition 10.4.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 10.4.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 10.4.1.1.4 ▶ Properties of Transitive Relations

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

    1. 1.

      Interaction With Inverses. If $R$ is transitive, then so is $R^{\dagger }$.

    2. 2.

      Interaction With Composition. If $R$ and $S$ are transitive, then $S\mathbin {\diamond }R$ may fail to be transitive.

    Proof of Proposition 10.4.1.1.4.

    Item 1: Interaction With Inverses
    Clear.

    Item 2: Interaction With Composition
    See [Weinberger, Is composition of two transitive relations transitive? If not, can you give me a counterexample?].1

    1. 1Intuition: 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:
      • •

        If $a\sim _{S\mathbin {\diamond }R}c$ and $c\sim _{S\mathbin {\diamond }r}e$, then:

        • •

          There is some $b\in A$ such that:

          • •

            $a\sim _{R}b$;

          • •

            $b\sim _{S}c$;

        • •

          There is some $d\in A$ such that:

          • •

            $c\sim _{R}d$;

          • •

            $d\sim _{S}e$.

Up

View Item 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: