Does the concept of "cograph of a function" have natural generalisations / extensions?

Question

First, definitions:

• The graph of a function $f : A \to B$ is a subset of $A \times B$, namely the set $\{(x,y) : x \in A, y \in B, f(x) = y\}$.
• The cograph of a function $f : A \to B$ is the quotient of $A \sqcup B$ by the equivalence relation that identifies $x$ with $f(x)$ for all $x$ (and so basically identifies each element of the codomain with its entire preimage under $f$).

These are categorical duals, in the sense that the graph is the pullback of $f$ along the identity, and the cograph is the pushout of $f$ along the identity.

From either the graph or cograph of a function, the original function can be recovered. We can even precisely specify the condition on a subset of $A \times B$ to be a graph of a function, or on a quotient of $A \sqcup B$ to be a cograph.

If we relax that condition on graphs, we get something else interesting, with a rich theory behind it: general relations between $A$ and $B$, including partial functions or multi-valued functions and many other things besides, with various possible properties, of which being "functional" is only one.

If we relax the condition on cographs, I can't as easily see what we get out of it. General quotients of $A \sqcup B$ can represent some relations between $A$ and $B$, but e.g. can't do multivalued functions in full generality, and the treatment of partial functions is less natural (e.g. suppose a partial $f$ is not defined at either $x$ or $y$, should we identify $x$ and $y$ in the quotient?).

So, I can't see that the cograph has as many "places to go" as the graph does, it doesn't seem to expose as many characterisations, variations, or generalisations of the concept of a function. Is there some useful perspective I'm missing here, or is the cograph just not as important mathematically as the graph is?

Answer 1

You can get arbitrary relations by generalising the notion of the graph of a function, but you have to do it slightly differently.

Suppose that, instead of generalising the notion of "graph of a function $A \to B$" to "subset of $A \times B$", we generalise it to: triple $(A', B', \Gamma)$, where $\Gamma \subseteq A' \times B'$ and the projection maps $\Gamma \to A'$ and $\Gamma \to B'$ are surjective.

The corresponding 'cograph' would be the quotient of $A' \sqcup B'$ by the least equivalence relation identifying $a \in \iota_1(A')$ and $b \in \iota_2(B')$ if $\langle a,b \rangle \in \Gamma$, where $\iota_1$ and $\iota_2$ are the inclusion maps.

In this way we obtain a three-way equivalence, between:

1. Relations from $A$ to $B$;
2. Triples $(A',B',\Gamma)$, where $A' \subseteq A$ and $B' \subseteq B$ and $\Gamma \subseteq A' \times B'$ with surjective projection maps;
3. Triples $(A',B',E)$, where $A' \subseteq A$ and $B' \subseteq B$ and $E$ is an equivalence relation on $A' \sqcup B'$.

Indeed:

• ($1 \to 2$) send $R$ to $(\mathrm{dom}(R), \mathrm{im}(R), \mathrm{graph}(R))$.
• ($2 \to 1$) given $(A',B',\Gamma)$, declare $a\; R\; b$ if and only if $\langle a,b \rangle \in \Gamma$.
• ($1 \to 3$) send $R$ to $(\mathrm{dom}(R), \mathrm{im}(R), E_R)$, where $E_R$ is the least equivalence relation containing $\langle \iota_1(a), \iota_2(b) \rangle$ for all $a,b$ with $a\; R\; b$, where $\iota_1,\iota_2$ are the inclusion maps.
• ($3 \to 1$) given $(A',B',E)$, declare $a\; R\; b$ if and only if $\iota_1(a)$ and $\iota_2(b)$ lie in the same $E$-equivalence class.

---

Here are the generalisations of the notions you mention in your question:

1. Functions

• Functions $f : A \to B$;
• Subsets $\Gamma \subseteq A \times B'$ such that $B' \subseteq B$, the projection map $\Gamma \to B'$ is surjective and, for all $a \in A$, there exists a unique $b \in B'$ such that $\langle a,b \rangle \in \Gamma$.
• Equivalence relations on $A \sqcup B'$, such that $B' \subseteq B$ and each equivalence class contains exactly one element of $B'$ and at least one element of $A$.

2. Partial functions

• Partial functions $f : A \to B$;
• Subsets $\Gamma \subseteq A' \times B'$ such that $A' \subseteq A$, $B' \subseteq B$, the projection maps $A' \leftarrow \Gamma \to B'$ are surjective and, for all $a \in A'$, there exists a unique $b \in B'$ such that $\langle a,b \rangle \in \Gamma$.
• Equivalence relations on $A' \sqcup B'$, such that $A' \subseteq A$, $B' \subseteq B$, and each equivalence class contains exactly one element of $B'$ and at least one element of $A'$.

3. Multi-valued functions

• Multi-valued functions from $A$ to $B$;
• Subsets $\Gamma \subseteq A' \times B'$ such that $A' \subseteq A$, $B' \subseteq B$, the projection maps $A' \leftarrow \Gamma \to B'$ are surjective and, for all $a \in A'$, there exists at least one $b \in B'$ with $\langle a,b \rangle \in \Gamma$.
• Equivalence relations on $A' \sqcup B'$ such that $A' \subseteq A$, $B' \subseteq B$, and each equivalence class contains at least one element of $A'$ and one element of $B'$.