Item 2 (00R6) — The Clowder Project

Let $A$ and $B$ be sets and let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation from $A$ to $B$.

The collage of $R$¹ is the poset $\smash {\mathbf{Coll}(R)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(\mathrm{Coll}(R),\preceq _{\mathbf{Coll}(R)})}$ consisting of:

•
The Underlying Set. The set $\mathrm{Coll}(R)$ defined by

\[ \mathrm{Coll}(R)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}A\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}B. \]
•
The Partial Order. The partial order

\[ \preceq _{\mathbf{Coll}(R)}\colon \mathrm{Coll}(R)\times \mathrm{Coll}(R)\to \{ \mathsf{true},\mathsf{false}\} \]

on $\mathrm{Coll}(R)$ defined by

\[ \mathord {\preceq }(a,b)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\begin{cases} \mathsf{true}& \text{if $a=b$ or $a\sim _{R}b$,}\\ \mathsf{false}& \text{otherwise.}\end{cases} \]

¹Further Terminology: Also called the cograph of $R$.

We write $\mathsf{Pos}_{/\Delta ^{1}}(A,B)$ for the category defined as the pullback

\[ \mathsf{Pos}_{/\Delta ^{1}}(A,B)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathsf{pt}\operatorname*{\mathbin {\times }}_{[A],\mathsf{Pos},\mathrm{ev}_{0}}\mathsf{Pos}_{/\Delta ^{1}}\operatorname*{\mathbin {\times }}_{\mathrm{ev}_{1},\mathsf{Pos},[B]}\mathsf{pt}, \]

as in the diagram

In detail, $\mathsf{Pos}_{/\Delta ^{1}}(A,B)$ is the category where:

•
Objects. An object of $\mathsf{Pos}_{/\Delta ^{1}}(A,B)$ is a pair $(X,\phi _{X})$ consisting of
- •
  A poset $X$;
- •
  A morphism $\phi _{X}\colon X\to \Delta ^{1}$;
such that we have

\begin{align*} \phi ^{-1}_{X}(0) & = A,\\ \phi ^{-1}_{X}(1) & = B. \end{align*}
•
Morphisms. A morphism of $\mathsf{Pos}_{/\Delta ^{1}}(A,B)$ from $(X,\phi _{X})$ to $(Y,\phi _{Y})$ is a morphism of posets $f\colon X\to Y$ making the diagram
commute.

Let $A$ and $B$ be sets and let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation from $A$ to $B$.

1.
Functoriality. The assignment $R\mapsto \mathbf{Coll}(R)$ defines a functor

\[ \mathbf{Coll}\colon \mathbf{Rel}(A,B)\to \mathsf{Pos}_{/\Delta ^{1}}(A,B), \]

where
- •
  Action on Objects. For each $R\in \operatorname {\mathrm{Obj}}(\mathbf{Rel}(A,B))$, we have
  
  \[ [\mathbf{Coll}](R) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(\mathbf{Coll}(R),\phi _{R}) \]
  
  for each $R\in \mathbf{Rel}(A,B)$, where
  - •
    The poset $\mathbf{Coll}(R)$ is the collage of $R$ of Definition 9.2.8.1.1.
  - •
    The morphism $\phi _{R}\colon \mathbf{Coll}(R)\to \Delta ^{1}$ is given by
    
    \[ \phi _{R}(x)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\begin{cases} 0 & \text{if $x\in A$,}\\ 1 & \text{if $x\in B$} \end{cases} \]
    
    for each $x\in \mathbf{Coll}(R)$.
- •
  Action on Morphisms. For each $R,S\in \operatorname {\mathrm{Obj}}(\mathbf{Rel}(A,B))$, the action on $\operatorname {\mathrm{Hom}}$-sets
  
  \[ \mathbf{Coll}_{R,S}\colon \operatorname {\mathrm{Hom}}_{\mathbf{Rel}(A,B)}(R,S) \to \mathsf{Pos}(\mathbf{Coll}(R),\mathbf{Coll}(S)) \]
  
  of $\mathbf{Coll}$ at $(R,S)$ is given by sending an inclusion
  
  \[ \iota \colon R\subset S \]
  
  to the morphism
  
  \[ \mathbf{Coll}(\iota )\colon \mathbf{Coll}(R)\to \mathbf{Coll}(S) \]
  
  of posets over $\Delta ^{1}$ defined by
  
  \[ [\mathbf{Coll}(\iota )](x)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}x \]
  
  for each $x\in \mathbf{Coll}(R)$.¹

¹Note that this is indeed a morphism of posets: if $x\preceq _{\mathbf{Coll}(R)}y$, then $x=y$ or $x\sim _{R}y$, so we have either $x=y$ or $x\sim _{S}y$ (as $R\subset S$), and thus $x\preceq _{\mathbf{Coll}(S)}y$.

9.2.8 The Collage of a Relation