The Syntax of Some Typical Relations

Let $P$$P$ be a poset. We know that $\mathsf{Set}(X,P)$$\mathsf{Set}(X,P)$ is a poset as well.

So the syntax of a poset should be given by a finite limit sketch.

Let us begin with the finite limit sketch of monomorphism.

In a category with finite limits, $f$$f$ is mono iff the following diagram is a pullback.

Hence we can define the sketch of monomorphism, denoted by $(\mathfrak{m},L)$$(\mathfrak m,L)$.

By duality we can define the sketch of epimorphism, denoted by $(\mathfrak{e},C)$$(\mathfrak e,C)$.

Here is a simple application.

In all concrete categories with a free-forgetful adjunction, such as $\mathsf{Grp},\mathsf{Ring},\mathsf{Top},\mathsf{Haus},\dots$$\mathsf{Grp},\mathsf{Ring},\mathsf{Top},\mathsf{Haus},\dots$

all monomorphisms are injective functions, but epimorphisms are not necessarily surjective.

Here is the reason: the forgetful functor, as a right adjoint, preserves limits. Hence it maps a model of a finite limit sketch to another model. But in general, it does not need to preserve colimits.

An interesting example is $\mathsf{Top}$$\mathsf{Top}$. The forgetful functor admits both a left and a right adjoint, i.e. the discrete topology and the trivial topology. Hence the forgetful functor preserves both limits and colimits. However, for $\mathsf{Haus}$$\mathsf{Haus}$, the forgetful functor does not admit a right adjoint anymore. Also, epimorphisms should not be surjective there either.

For example, a dense inclusion is epi but not surjective. Here is the reason: click here

A binary relation is a monomorphism $m:R\hookrightarrow X\times X$$m:R\hookrightarrow X\times X$.

Hence we can define the sketch of a relation, denoted by $(\mathcal{R},L)$$(\mathcal R,L)$.

Now we would like to describe the pre-order relation $m:R\to P\times P$$m:R\to P\times P$.

What is reflexivity?

$$\mathrm{\exists }r:X\to R,\mathrm{\Delta }=m\circ r,\text{ i.e. }\mathrm{\Delta }:X\stackrel{r}{\to }R\stackrel{m}{\to }P\times P$$

In other words, $\mathrm{\Delta }$$\Delta$ is a subobject of $R$$R$.

What is transitivity? Consider $Q=R{\times }_{P}R$$Q=R\times_{P} R$; it represents something like $((x,y),(y,z))$$((x,y),(y,z))$.

Let $q_1,q_2:Q\to R$$q_1,q_2:Q\to R$ be the two projections, and also let ${\pi }_1,{\pi }_2:P\times P\to P$$\pi_1,\pi_2:P\times P\to P$.

Transitivity claims that there exists a map $t:Q\to R$$t:Q\to R$ such that

To express transitivity, write the relation as a map $m:R\to P\times P$$m:R\to P\times P$, and let $d_0={\pi }_1\circ m$$d_0=\pi_1\circ m$ and $d_1={\pi }_2\circ m$$d_1=\pi_2\circ m$. Then form the pullback

$$Q=R{\times }_{P}R$$

along $d_1:R\to P$$d_1:R\to P$ and $d_0:R\to P$$d_0:R\to P$, so that a point of $Q$$Q$ represents a composable pair $x\le y$$x\le y$ and $y\le z$$y\le z$.

Let the two projections be $q_1,q_2:Q\to R$$q_1,q_2:Q\to R$. Transitivity is expressed by requiring a morphism $c:Q\to R$$c:Q\to R$ such that

$$d_0\circ c=d_0\circ q_1,d_1\circ c=d_1\circ q_2$$

Equivalently,

$$m\circ c=⟨d_0\circ q_1,d_1\circ q_2⟩:Q\to P\times P$$

This means that from a composable pair $(x\le y,y\le z)$$(x\le y,\ y\le z)$ we obtain a relation $x\le z$$x\le z$.

Hence we get the sketch of a pre-order. Let us denote it by $(\mathfrak{p},L)$$(\mathfrak p,L)$.

To express antisymmetry, consider the opposite relation $R^{\mathrm{op}}\to P\times P$$R^{\mathrm{op}}\to P\times P$, obtained by composing $m:R\to P\times P$$m:R\to P\times P$ with the symmetry map $\tau :P\times P\to P\times P$$\tau:P\times P\to P\times P$.

Then form the pullback

$$A=R{\times }_{P\times P}{R}^{\mathrm{op}}$$

which represents pairs $(x,y)$$(x,y)$ such that both $x\le y$$x\le y$ and $y\le x$$y\le x$ hold. Antisymmetry means that such a pair must lie on the diagonal. In other words, the map $A\to P\times P$$A\to P\times P$ factors through the diagonal ${\mathrm{\Delta }}_P:P\to P\times P$$\Delta_P:P\to P\times P$, i.e. $A$$A$ is a subobject of ${\mathrm{\Delta }}_P$$\Delta_P$.

Equivalently, there is a morphism $d:A\to P$$d:A\to P$ such that

$${\mathrm{\Delta }}_P\circ d=A\to P\times P$$

This expresses precisely that whenever $x\le y$$x\le y$ and $y\le x$$y\le x$, one must have $x=y$$x=y$.

Hence we get the sketch of a poset, denoted by $(\mathcal{P},L)$$(\mathcal P,L)$.

To express symmetry, let $\tau :P\times P\to P\times P$$\tau:P\times P\to P\times P$ be the symmetry map exchanging the two factors. Then the opposite relation is the composite

$$R\stackrel{m}{\to }P\times P\stackrel{\tau }{\to }P\times P$$

Symmetry means that whenever $xRy$$xRy$, we also have $yRx$$yRx$. Equivalently, the opposite relation factors through $R$$R$ itself. In other words, there is a morphism $s:R\to R$$s:R\to R$ such that

$$m\circ s=\tau \circ m.$$

This says that every relation $(x,y)$$(x,y)$ in $R$$R$ is sent to the reversed relation $(y,x)$$(y,x)$, so the relation is symmetric.

Hence we get the sketch of an equivalence relation, denoted by $(E,L)$$(E,L)$.

We could consider the sketch of a kernel pair as well.

In general, let $\mathcal{C}$$\mathcal C$ be a locally small category with finite limits, and let $X$$X$ be a model of a finite limit sketch $(S,L)$$(S,L)$.

Then

$${\mathrm{Hom}}_{\mathcal{C}}(-,X)$$

is a model of $(S,L)$$(S,L)$ in $[{\mathcal{C}}^{\mathrm{op}},\mathsf{Set}]$$[\mathcal C^{\mathrm{op}},\mathsf{Set}]$, since the Yoneda embedding preserves limits.

Hence, if $X$$X$ is an internal poset, then ${\mathrm{Hom}}_{\mathcal{C}}(-,X)$$\mathrm{Hom}_\mathcal{C}(-,X)$ is a poset-valued functor.