Subsection 6.3.13 (00R2): The Collage of a Relation

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$.

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`

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

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

\[ \mathrm{Coll}\webleft (R\webright )\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}\webleft (R\webright )}\colon \mathrm{Coll}\webleft (R\webright )\times \mathrm{Coll}\webleft (R\webright )\to \{ \mathsf{true},\mathsf{false}\} \]

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

\[ \mathord {\preceq }\webleft (a,b\webright )\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} \]

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$.

Functoriality I. The assignment $R\mapsto \mathbf{Coll}\webleft (R\webright )$ defines a functor ^[2]
\[ \mathbf{Coll}\colon \mathbf{Rel}\webleft (A,B\webright )\to \mathsf{Pos}_{/\Delta ^{1}}\webleft (A,B\webright ), \]

where
- Action on Objects. For each $R\in \text{Obj}\webleft (\mathbf{Rel}\webleft (A,B\webright )\webright )$, we have
  
  \[ \webleft [\mathbf{Coll}\webright ]\webleft (R\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\webleft (\mathbf{Coll}\webleft (R\webright ),\phi _{R}\webright ) \]
  
  for each $R\in \mathbf{Rel}\webleft (A,B\webright )$, where
  - The poset $\mathbf{Coll}\webleft (R\webright )$ is the collage of $R$ of Definition 6.3.13.1.1.
  - The morphism $\phi _{R}\colon \mathbf{Coll}\webleft (R\webright )\to \Delta ^{1}$ is given by
    
    \[ \phi _{R}\webleft (x\webright )\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}\webleft (R\webright )$.
- Action on Morphisms. For each $R,S\in \text{Obj}\webleft (\mathbf{Rel}\webleft (A,B\webright )\webright )$, the action on $\textup{Hom}$-sets
  
  \[ \mathbf{Coll}_{R,S}\colon \textup{Hom}_{\mathbf{Rel}\webleft (A,B\webright )}\webleft (R,S\webright ) \to \mathsf{Pos}\webleft (\mathbf{Coll}\webleft (R\webright ),\mathbf{Coll}\webleft (S\webright )\webright ) \]
  
  of $\mathbf{Coll}$ at $\webleft (R,S\webright )$ is given by sending an inclusion
  
  \[ \iota \colon R\subset S \]
  
  to the morphism
  
  \[ \mathbf{Coll}\webleft (\iota \webright )\colon \mathbf{Coll}\webleft (R\webright )\to \mathbf{Coll}\webleft (S\webright ) \]
  
  of posets over $\Delta ^{1}$ defined by
  
  \[ \webleft [\mathbf{Coll}\webleft (\iota \webright )\webright ]\webleft (x\webright )\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}x \]
  
  for each $x\in \mathbf{Coll}\webleft (R\webright )$.^[3]
Equivalence. The functor of Item 1 is an equivalence of categories.

Item 1: Functoriality

Clear.

Item 2: Equivalence

Omitted.

Footnotes

[1] Further Terminology: Also called the cograph of $R$.

[2] Here $\mathsf{Pos}_{/\Delta ^{1}}\webleft (A,B\webright )$ is the category defined as the pullback

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

as in the diagram

Explicitly, an object of $\mathsf{Pos}_{/\Delta ^{1}}\webleft (A,B\webright )$ is a pair $\webleft (X,\phi _{X}\webright )$ consisting of

A poset $X$;
A morphism $\phi _{X}\colon X\to \Delta ^{1}$;

such that $\phi ^{-1}_{X}\webleft (0\webright )=A$ and $\phi ^{-1}_{X}\webleft (0\webright )=B$, with morphisms between such objects being morphisms of posets over $\Delta ^{1}$.

[3] Note that this is indeed a morphism of posets: if $x\preceq _{\mathbf{Coll}\webleft (R\webright )}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}\webleft (S\webright )}y$.

The Clowder Project

6.3.13 The Collage of a Relation

Footnotes