nLab graph of a function

Redirected from "Cograph".
Contents

Contents

Idea

The graph of a function f:XYf : X \to Y is the subset that ff “carves out” of the cartesian product X×YX \times Y.

Definition

Graph of a function

The traditional standard definition of a graph of a function is this:

Definition

The graph graph(f)graph(f) of a function f:XYf: X \to Y is that subset graph(f)X×Ygraph(f) \hookrightarrow X \times Y of the cartesian product X×YX \times Y defined by the property that (a,b)X×Y(a,b) \in X \times Y belongs to the graph of ff if and only if f(a)=bf(a) = b:

graph(f)={(a,b)X×Y|f(a)=b}. graph(f) = \{(a,b) \in X \times Y | f(a) = b\} \,.

This can be understood as a special case of a graph of a functor by the following observation

Lemma

For f:XYf : X \to Y a function, define a function

χ f:X×Y{0,1} \chi_f : X \times Y \to \{0,1\}

by regarding a set as a 0-category and a 0-category as a (-1)-category-enriched category and then setting

χ f:X×Y=X op×Yf op×IdY op×YHom{0,1}. \chi_f : X \times Y \stackrel{=}{\to} X^{op} \times Y \stackrel{f^{op} \times Id}{\to} Y^{op} \times Y \stackrel{Hom}{\to} \{0,1\} \,.

Then χ f\chi_f is the characteristic function of graph(f)graph(f) in that the diagram

graph(f) * X×Y χ f {0,1} \array{ graph(f) &\to& {*} \\ \downarrow && \downarrow \\ X \times Y &\stackrel{\chi_f}{\to}& \{0,1\} }

is a pullback diagram.

In other words this means that in the context of (-1)-category-enriched category theory the graph of a function ff, regarded as an enriched functor is the category of elements of the corresponding profunctor. More on this at graph of a functor.

Remark

It is easy to identify the properties of those subsets of X×YX \times Y that are the graphs of functions, and f=gf = g if they have the same graph (given XX and YY). Consequently, it is common, especially (but not only) in material set theory, to define a function from XX to YY as such a subset, that is to identify a function with its graph. On the other hand, from a more categorial foundation, as discussed above, it's common to define a subset to be a characteristic function!

In dependent type theory, a graph of a function f:ABf:A \to B is the type

x:A y:Bf(x)= Ay\sum_{x:A} \sum_{y:B} f(x) =_A y

Graph of a binary relation

More generally, we can say that the graph of a binary relation from XX to YY is a subset of X×YX \times Y; (a,b)(a,b) belongs to the graph if and only if aa is related to bb. (Note that every subset of X×YX \times Y defines a unique relation; such a subset is the graph of a function if and only if the relation is both functional and entire.)

Notice that with a function f:XYf : X \to Y regarded as a profunctor X×Y(1)CatX \times Y \to (-1)Cat as described above, a relation RX×YR \subset X \times Y corresponds to a general such profunctor. More precisely we have a pullback square

R * X×Y χ R {0,1} \array{ R &\to& {*} \\ \downarrow && \downarrow \\ X \times Y &\stackrel{\chi_R}{\to}& \{0,1\} }

where

  • RX×YR \subset X \times Y is the relation RR regarded as a subset of X×YX \times Y in the traditional sense;

  • χ R:X×Y{0,1}\chi_R : X \times Y \to \{0,1\} is the characteristic function of this subset.

So in this sense the ordinary notion of relation as a subset does really define the graph of the relation, while the relation itself is more naturally understood as the corresponding 0-profunctor/characteristic function χ f\chi_f.

Relation to graph theory

The graph of a binary relation from XX to XX is related to the notion of graph from graph theory; more precisely, such relations correspond to directed loop graphs (in the sense defined at graph) with vertex set XX, and either can be defined as a subset of X 2X^2. In a similar way, spans from XX to XX correspond to directed pseudographs with vertex set XX.

For the case of a relation from XX to YY without X=YX = Y, see under the cograph below.

Graph of an nn-ary relation

The graph of a relation of arbitrary arity is similarly a subset of an arbitrary cartesian product; see relation theory for more on this.

Cograph of a function

Bill Lawvere has also considered the cograph of a function, which is dually a quotient set of the disjoint union XYX \uplus Y; aa is identified with bb if f(a)=bf(a) = b (and additional identifications may follow). However it may make more sense to define the cograph to be a quotient poset of (the discrete poset) XYX \uplus Y; we declare a<ba \lt b if f(a)=bf(a) = b (and no additional relationships follow). By regarding again a set as a 0-category, the latter notion of cograph is a special case of the notion of cograph of a functor, as follows:

A function f:XYf : X \to Y determines a functor f¯:ISet\bar f : I \to Set from the interval category I=2={ab}I = \mathbf{2} = \{a \to b\} to Set by setting f¯(a)=X\bar f(a) = X, f¯(b)=Y\bar f(b) = Y and f¯(ab)=f\bar f(a \to b) = f.

Then let cograph(f)cograph(f) be the corresponding category of elements, given by the 2-pullback

cograph(f) * I f¯ Set \array{ cograph(f) &\to& {*} \\ \downarrow && \downarrow \\ I &\stackrel{\bar f}{\to}& Set }

which is computed by the strict pullback

cograph(f) Set * I f¯ Set. \array{ cograph(f) &\to& Set_{*} \\ \downarrow && \downarrow \\ I &\stackrel{\bar f}{\to}& Set } \,.

The cograph of ff in the sense of Lawvere is the set of connected components of this category, i.e. π 0(cograph(f))\pi_0(cograph(f)).

Relation to graph theory

The notion of cograph of a function may be even more related to the sense of graph in graph theory; although the identifications are not done there, the cograph draws a picture in which any relation (or multispan) of any arity becomes a directed graph (or directed multigraph) whose vertex set is the disjoint union of the relation's domains. When the vertex set is broken up into a disjoint union in this way, graph theorists study this as multipartite graphs; in particular, directed bipartite graphs with vertex set broken up as X+YX + Y correspond precisely to binary relations from XX to YY.

Generalization

The notion of graph of a function is a special case of the notion graph of a functor obtained for functors between 0-categories.

Accordingly, the notion of cograph of a function is a special case of the notion of cograph of a functor.

Last revised on January 30, 2024 at 13:20:52. See the history of this page for a list of all contributions to it.