Item 2 (02AS) — The Clowder Project

8.2.2 The Graph of a Function

Let $f\colon A\to B$ be a function.

Definition 8.2.2.1.1 ▶ The Graph of a Function

The graph of $f$ is the relation $\operatorname {\mathrm{Gr}}(f)\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ defined as follows:¹

•
Viewing relations from $A$ to $B$ as subsets of $A\times B$, we define

\[ \operatorname {\mathrm{Gr}}(f)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ (a,f(a))\in A\times B\ \middle |\ a\in A\right\} . \]
•
Viewing relations from $A$ to $B$ as functions $A\times B\to \{ \mathsf{true},\mathsf{false}\} $, we define

\[ \operatorname {\mathrm{Gr}}(f)^{b}_{a}\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\begin{cases} \mathsf{true}& \text{if $b=f(a)$,}\\ \mathsf{false}& \text{otherwise} \end{cases} \]

for each $(a,b)\in A\times B$.
•
Viewing relations from $A$ to $B$ as functions $A\to \mathcal{P}(B)$, we define

\[ [\operatorname {\mathrm{Gr}}(f)](a)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ f(a)\right\} \]

for each $a\in A$, i.e. we define $\operatorname {\mathrm{Gr}}(f)$ as the composition

\[ A \overset {f}{\to } B \overset {\chi _{B}}{\hookrightarrow } \mathcal{P}(B). \]

¹Further Terminology and Notation: When $f=\operatorname {\mathrm{id}}_{A}$, we write $\operatorname {\mathrm{Gr}}(A)$ for $\operatorname {\mathrm{Gr}}(\operatorname {\mathrm{id}}_{A})$, calling it the graph of $A$.

Proposition 8.2.2.1.2 ▶ Properties of Graphs of Functions

Let $f\colon A\to B$ be a function.

1.
Functoriality. The assignment $A\mapsto \operatorname {\mathrm{Gr}}(A)$ defines a functor

\[ \operatorname {\mathrm{Gr}}\colon \mathsf{Sets}\to \mathrm{Rel} \]

where
- •
  Action on Objects. For each $A\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$, we have
  
  \[ \operatorname {\mathrm{Gr}}(A)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}A. \]
- •
  Action on Morphisms. For each $A,B\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$, the action on $\operatorname {\mathrm{Hom}}$-sets
  
  \[ \operatorname {\mathrm{Gr}}_{A,B}\colon \mathsf{Sets}(A,B) \to \underbrace{\mathrm{Rel}(\operatorname {\mathrm{Gr}}(A),\operatorname {\mathrm{Gr}}(B))}_{\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\mathrm{Rel}(A,B)} \]
  
  of $\operatorname {\mathrm{Gr}}$ at $(A,B)$ is defined by
  
  \[ \operatorname {\mathrm{Gr}}_{A,B}(f) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {\mathrm{Gr}}(f), \]
  
  where $\operatorname {\mathrm{Gr}}(f)$ is the graph of $f$ as in Definition 8.2.2.1.1.
In particular, the following statements are true:
- •
  Preservation of Identities. We have
  
  \[ \operatorname {\mathrm{Gr}}(\operatorname {\mathrm{id}}_{A})=\Delta _{A} \]
  
  for each $A\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$.
- •
  Preservation of Composition. We have
  
  \[ \operatorname {\mathrm{Gr}}(g\circ f)=\operatorname {\mathrm{Gr}}(g)\mathbin {\diamond }\operatorname {\mathrm{Gr}}(f) \]
  
  for each pair of functions $f\colon A\to B$ and $g\colon B\to C$.
2.
Adjointness. We have an adjunction
witnessed by a bijection of sets

\[ \mathrm{Rel}(\operatorname {\mathrm{Gr}}(A),B) \cong \mathsf{Sets}(A,\mathcal{P}(B)) \]

natural in $A\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$ and $B\in \operatorname {\mathrm{Obj}}(\mathrm{Rel})$.
3.
Cocontinuity. The functor $\operatorname {\mathrm{Gr}}\colon \mathsf{Sets}\to \mathrm{Rel}$ of Item 1 preserves colimits.
4.
Adjointness Inside $\boldsymbol {\mathsf{Rel}}$. We have an internal adjunction
in $\boldsymbol {\mathsf{Rel}}$, where $f^{-1}$ is the inverse of $f$ of Definition 8.2.3.1.1.
5.
Interaction With Converses. We have

\begin{align*} \operatorname {\mathrm{Gr}}(f)^{\dagger } & = f^{-1},\\ (f^{-1})^{\dagger } & = \operatorname {\mathrm{Gr}}(f). \end{align*}
6.
Characterisations. Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation. The following conditions are equivalent:
1. (a)
  There exists a function $f\colon A\to B$ such that $R=\operatorname {\mathrm{Gr}}(f)$.
2. (b)
  The relation $R$ is total and functional.
3. (c)
  The inverse and coinverse images of $R$ agree, i.e. we have $R^{-1}=R_{-1}$.
4. (d)
  The relation $R$ has a right adjoint $R^{\dagger }$ in $\mathrm{Rel}$.

Proof of Proposition 8.2.2.1.2.

Item 1: Functoriality

The well-definedness follows from Definition 8.2.2.1.1. Next, we need to show that $\operatorname {\mathrm{Gr}}$ preserves identities and compositions.

•
Preservation of Identities. Let $A$ be a set. Given $a,b\in A$, we have

\[ a \sim _{\operatorname {\mathrm{Gr}}(\operatorname {\mathrm{id}}_{A})} b \iff \operatorname {\mathrm{id}}_{A}(a) = b \iff a = b \iff a \sim _{\Delta _{A}} b, \]

so $\operatorname {\mathrm{Gr}}(\operatorname {\mathrm{id}}_{A}) = \Delta _{A}.$
•
Preservation of Composition. Let $A$, $B$, and $C$ be sets and let $f \colon A \to B$ and $g \colon B \to C$ be functions. For each $a\in A$ and each $c \in C$, we have

\begin{align*} a \sim _{\operatorname {\mathrm{Gr}}(g \circ f)} c & \iff [g \circ f](a) = c\\ & \iff g(f(a)) = c\\ & \iff \text{there exists $b \in B$ such that $f(a) = b$ and $(b) = c$}\\ & \iff \text{there exists $b \in B$ such that $a \sim _{\operatorname {\mathrm{Gr}}(f)} b$ and $b \sim _{\operatorname {\mathrm{Gr}}(g)} c$} \\ & \iff a \sim _{\operatorname {\mathrm{Gr}}(g) \mathbin {\diamond }\operatorname {\mathrm{Gr}}(f)} c \end{align*}

so $\operatorname {\mathrm{Gr}}(g \circ f) = \operatorname {\mathrm{Gr}}(g) \mathbin {\diamond }\operatorname {\mathrm{Gr}}(f)$.

Item 2: Adjointness

This is a repetition of Chapter 4: Constructions With Sets, Proposition 4.4.4.1.1, and is proved there.

Item 3: Cocontinuity

This follows from Item 2 and

Item 4: Adjointness Inside $\boldsymbol {\mathsf{Rel}}$

We need to check that there are inclusions

\begin{gather*} \chi _{A} \subset f^{-1}\mathbin {\diamond }\operatorname {\mathrm{Gr}}(f),\\ \operatorname {\mathrm{Gr}}(f)\mathbin {\diamond }f^{-1} \subset \chi _{B}. \end{gather*}

These correspond respectively to the following conditions:

1.
For each $a\in A$, there exists some $b\in B$ such that $a\sim _{\operatorname {\mathrm{Gr}}(f)}b$ and $b\sim _{f^{-1}}a$.

2.
For each $a,b\in A$, if $a\sim _{\operatorname {\mathrm{Gr}}(f)}b$ and $b\sim _{f^{-1}}a$, then $a=b$.

In other words, the first condition states that the image of any $a\in A$ by $f$ is nonempty, whereas the second condition states that $f$ is not multivalued. As $f$ is a function, both of these statements are true, and we are done.

Item 5: Interaction With Converses

Omitted.

Item 6: Characterisations

We claim that Item 6a, Item 6b, Item 6c, and Item 6d are indeed equivalent:

•
Item 6a$\iff $Item 6b. This is shown in the proof of Proposition 8.5.2.1.2.
•
Item 6b$\implies $Item 6c. If $R$ is total and functional, then, for each $a\in A$, the set $R(a)$ is a singleton. Since the conditions
- •
  $R(a)\cap V\neq \text{Ø}$;
- •
  $R(a)\subset V$;
are equivalent when $R(a)$ is a singleton, it follows that the sets

\begin{align*} R^{-1}(V) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A \ \middle |\ R(a)\cap V\neq \text{Ø}\right\} ,\\ R_{-1}(V) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ R(a)\subset V\right\} \end{align*}

are equal for all $V\in \mathcal{P}(B)$.
•
Item 6c$\implies $Item 6b. We claim that $R$ is indeed total and functional:
- •
  Totality. We proceed in a few steps:
  - •
    If we had $R(a)=\text{Ø}$ for some $a\in A$, then we would have $a\in R_{-1}(\text{Ø})$, so that $R_{-1}(\text{Ø})\neq \text{Ø}$.
  - •
    But since $R^{-1}(\text{Ø})=\text{Ø}$, this would imply $R_{-1}(\text{Ø})\neq R^{-1}(\text{Ø})$, a contradiction.
  - •
    Thus $R(a)\neq \text{Ø}$ for all $a\in A$ and $R$ is total.
- •
  Functionality. If $R^{-1}=R_{-1}$, then we have
  
  \begin{align*} \left\{ a\right\} & = R^{-1}(\left\{ b\right\} )\\ & = R_{-1}(\left\{ b\right\} ) \end{align*}
  
  for each $b\in R(a)$ and each $a\in A$, and thus $R(a)\subset \left\{ b\right\} $. But since $R$ is total, we must have $R(a)=\left\{ b\right\} $, so $R$ is functional.
•
Item 6a$\iff $Item 6d. This follows from Chapter 8: Relations, Proposition 8.5.3.1.1.

This finishes the proof.

Statistics Cite

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

•Email
•Discord

You can also use the contact form below: