Proposition 9.2.8.1.4 (00R4): Properties of Collages of Relations — The Clowder Project

Table of Contents
Part 3: Relations
Chapter 9: Constructions With Relations
Section 9.2: More Constructions With Relations
Subsection 9.2.8: The Collage of a Relation
Proposition 9.2.8.1.4: Properties of Collages of Relations (cite)

1 tag refers to this tag

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

Definition 9.2.8.1.1 ▶ The Collage of a Relation

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

Notation 9.2.8.1.2 ▶ Notation: $\mathsf{Pos}_{/\Delta ^{1}}(A,B)$

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

Remark 9.2.8.1.3 ▶ Unwinding Notation 9.2.8.1.2

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.

Proposition 9.2.8.1.4 ▶ Properties of Collages of Relations

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)$.¹
2.
Equivalence. The functor of Item 1 is an equivalence of categories.

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

Proof of Proposition 9.2.8.1.4.

Item 1: Functoriality

Clear.

Item 2: Equivalence

Omitted.

Statistics Cite

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

•Email
•Discord

You can also use the contact form below: