Subsection 7.1.2 (00TV): The Reflexive Closure of a Relation

Preferences

Font:

PDF Style:

Here's a breakdown of the differences between each PDF style:

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

*To be replaced with Linus Romer's Elemaints when it is released.

Table of Contents
Part 2: Relations
Chapter 7: Equivalence Relations and Apartness Relations
Section 7.1: Reflexive Relations
Subsection 7.1.2: The Reflexive Closure of a Relation (cite)

7.1.2 The Reflexive Closure of a Relation

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

Definition 7.1.2.1.1 ▶ The Reflexive Closure of a Relation

The reflexive closure of $\mathord {\sim }_{R}$ is the relation $\smash {\mathord {\sim }^{\mathrm{refl}}_{R}}$^[1] satisfying the following universal property:^[2]

Given another reflexive relation $\mathord {\sim }_{S}$ on $A$ such that $R\subset S$, there exists an inclusion $\smash {\mathord {\sim }^{\mathrm{refl}}_{R}}\subset \mathord {\sim }_{S}$.

Construction 7.1.2.1.2 ▶ The Reflexive Closure of a Relation

Concretely, $\smash {\mathord {\sim }^{\mathrm{refl}}_{R}}$ is the free pointed object on $R$ in $\webleft (\mathbf{Rel}\webleft (A,A\webright ),\chi _{A}\webright )$^[3], being given by

\begin{align*} R^{\mathrm{refl}} & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R\mathbin {\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}^{\mathbf{Rel}\webleft (A,A\webright )}}\Delta _{A}\\ & = R\cup \Delta _{A}\\ & = \webleft\{ \webleft (a,b\webright )\in A\times A\ \middle |\ \text{we have $a\sim _{R}b$ or $a=b$}\webright\} .\end{align*}

Proof of Construction 7.1.2.1.2.

Clear.

Proposition 7.1.2.1.3 ▶ Properties of the Reflexive Closure of a Relation

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

Adjointness. We have an adjunction
witnessed by a bijection of sets
\[ \mathbf{Rel}^{\mathsf{refl}}\webleft (R^{\mathrm{refl}},S\webright ) \cong \mathbf{Rel}\webleft (R,S\webright ), \]

natural in $R\in \text{Obj}\webleft (\mathbf{Rel}^{\mathsf{refl}}\webleft (A,A\webright )\webright )$ and $S\in \text{Obj}\webleft (\mathbf{Rel}\webleft (A,A\webright )\webright )$.
The Reflexive Closure of a Reflexive Relation. If $R$ is reflexive, then $R^{\mathrm{refl}}=R$.
Idempotency. We have
\[ \webleft (R^{\mathrm{refl}}\webright )^{\mathrm{refl}} = R^{\mathrm{refl}}. \]
Interaction With Inverses. We have
Interaction With Composition. We have

Proof of Proposition 7.1.2.1.3.

Item 1: Adjointness

This is a rephrasing of the universal property of the reflexive closure of a relation, stated in Definition 7.1.2.1.1.

Item 2: The Reflexive Closure of a Reflexive Relation

Clear.

Item 3: Idempotency

This follows from Item 2.

Item 4: Interaction With Inverses

Clear.

Item 5: Interaction With Composition

This follows from Item 2 of Proposition 7.1.1.1.4.

Footnotes

[1] Further Notation: Also written $R^{\mathrm{refl}}$.

[2] Slogan: The reflexive closure of $R$ is the smallest reflexive relation containing $R$.

[3] Or, equivalently, the free $\mathbb {E}_{0}$-monoid on $R$ in $\webleft (\mathrm{N}_{\bullet }\webleft (\mathbf{Rel}\webleft (A,A\webright )\webright ),\chi _{A}\webright )$.

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

You can also use the contact form below: