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

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?

• How about a co-cacola while you wait for a reply? Jul 5, 2015 at 22:18
• Inst the cograph the same as the mapping torus? Jul 5, 2015 at 22:33
• @Gary: If my intuition serves me correctly, the mapping torus would be the homotopy colimit of the diagram $A \xleftarrow{\mathrm{id}_A} A \xrightarrow{f} B$, whereas the cograph is the actual colimit. So although the mapping torus is homotopic to the cograph in $\mathrm{Top}$, it is not the same thing (especially since we're working in $\mathrm{Set}$ instead of $\mathrm{Top}$). Jul 5, 2015 at 23:26
• This would be the mapping cylinder, not the mapping torus (which is the case $A=B$), and Clive Newstead is right in saying that it is the homotopy pushout of $f$ and $\operatorname{id}$, where the "cograph" is the actual pushout. Jul 6, 2015 at 8:47

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'$.
• I'm sure I decided this was correct a year ago but I've lost that certainty now. Suppose I have $aRx$, $aRy$, and $bRx$ but not $bRy$. What's $E_R$? Doesn't it identify $a$ and $b$, and thus force me to identify $b$ and $y$? Aug 18, 2017 at 2:35
• @BenMillwood Hi! You're right. In fact, looking back, there are purely combinatorial reasons why it's suspicious that relations between sets should correspond with equivalence relations on (=partitions of) a disjoint union. The number of relations from $A$ to $B$ is $2^{|A| \cdot |B|}$, but the number of partitions of $A' \sqcup B'$ as $A'$ and $B'$ vary over subsets of $A$ and $B$, respectively, is something like $$\sum_{A' \subseteq A} \sum_{B' \subseteq B} (\mathrm{B}_{|A|} \cdot \mathrm{B}_{|B|})$$ where $\mathrm{B}_n$ is (cont...) Aug 18, 2017 at 14:34
• the $n^{\text{th}}$ Bell number. This looks kind of suspect to me. Certainly, if there is a way of generalising the cograph of a function to arbitrary relations, this isn't the way to do it. As far as I know, it does still work for partial functions and multi-valued functions. Aug 18, 2017 at 14:35