nLab
graph of a function

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×Yf(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!

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 determins 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 }

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

Discussion

Eric: I think it might be neat to take the opportunity here to relate graph of a function more explicitly to other things here on the nLab. As I read this, I thought of a category with one object (monoid in Set?) and one morphism

f.\bullet\righttoleftarrow f.

Then a graph (or is it cograph?) is a category of elements of this category.

Then you could maybe talk more generally about graph of a morhism. Or something

Toby: The above graph of a function definitely generalises to the graph of a morphism; I didn't say anything about it, because I didn't want to have to think about what categories it's possible to do this in. (Probably a regular category or something like that.)

I don't understand what you're saying above. You seem to introduce the trivial category and then ask for its category of elements. Categories don't have categories of elements, objects of categories do; but this category has just one object, so I'll use that. But the category of elements of that one object is also trivial. The real problem is that nothing in this category has to do with any function f:XYf: X \to Y; all you've done is label an abstract morphism with the same name ‘ff’. Can you try to explain again what you mean?

Eric: What I had in mind was to think of that one object \bullet as a set (but didn’t want to pin it down too much so I didn’t say “set”). The morphism ff is a nontrivial endomorphism.

When we explode that simple category, we get one object (which will be a node of the graph) for each element in \bullet. We also get one morphism for any two elements aa and bb for which f:abf:a\to b.

As usual, it is just an idea and I was hoping that if it made any sense at all we could clean it up and include it in the main text.

For example, let ={x,y,z}\bullet = \{x,y,z\} and f:f:\bullet\to\bullet with

f(x) =y f(y) =z f(z) =x.\begin{aligned} f(x) &= y \\ f(y) &= z \\ f(z) &= x. \end{aligned}

When we “explode” this simple category

Explode(f)Explode\left(\bullet\righttoleftarrow f\right)

we get a graph with three nodes and three directed edges forming a ring.

I guess, to be a little more explicit, I can call that concrete category CC, i.e.

C=fC = \bullet\righttoleftarrow f

and we have a functor F:CSetF:C\to Set. Then F()F(\bullet) is really a set and F(f)F(f) is really a function.

Then

Explode(C)=Elem(F,C).Explode(C) = Elem(F,C).

This category of elements seems to warrant being associated with the graph of a function ff. Furthermore, this allows us to consider the graph of an endomorphism. But then, I could be confused.

Toby: Ah, I understand now! CC is equipped with a functor to SetSet (or potentially to something else); I should have guessed this, since you'd linked to category of elements, and I interpreted the phrase differently. Also, ff is not an identity morphism of CC; instead, CC is freely generated by an endomorphism ff, so its morphisms are in fact f nf^n for n=0,1,2,n = 0, 1, 2, \ldots. The a functor from CC to SetSet is a set equipped with an endofunction, and a functor from CC to DD is an object of DD equipped with an endomorphism.

OK, so if we explode this functor, then an object of the explosion is an element xx of F()F(\bullet), and a morphism xxx \to x' is a natural number nn such that F(f) n(x)=xF(f)^n(x) = x'. You seem to have wanted a morphism xxx \to x' to exist only if F(f)(x)=xF(f)(x) = x', but this won't work, since then you won't be able to compose morphisms xxxx \to x' \to x''. My way, you can compose them, by adding the nns.

Then I get this result: If we take this function F(f):F()F()F(f): F(\bullet) \to F(\bullet), treat a function as a special kind of relation, convert between relations and directed loop graphs (see today's graph for the definition), treat a directed loop graph as a special directed pseudograph aka digraph, and form the quiver of that digraph, then the result is the same as the above category of elements!

Eric: Neat! :) You are right. My category f\bullet\righttoleftarrow f wasn’t even a category. Oops! But it generates a category the way you outlined. However, an endofunction f:XXf:X\to X does generate a digraph in the obvious way, i.e. each element of XX is a node and we have a directed edge xxx\to x' if f(x)=xf(x) = x'. This digraph generates a quiver and this quiver corresponds to the category of elements obtained from the category generated by the endofunction. Phew! :)

Let me recap to make sure I got it

Given an endofunction f:XXf:X\to X, we can do two things with it:

  1. Construct a digraph G fG_f
  2. Construct a category C fC_f with one object XX and morphisms being powers of ff.

The quiver Q(G f)Q(G_f) and the category of elements Explode(C f)Explode(C_f) coincide. That is cool, unfortunately, I don’t know if it is relevant to graph of a function.

Doh! Now, I think I know what I did wrong. In trying to make things simpler by considering just one object, I made them more complicated.

What we really want is a concrete category XfYX\stackrel{f}{\to} Y with TWO objects XX and YY and one morphism f:XYf:X\to Y. Now, composition does not come into the picture.

Now, I think,

Explode(XfY)Explode(X\stackrel{f}{\to} Y)

is the graph of a morphism ff.

If there is any truth to that, then this can be applied to any morphism of any concrete (or regular?) category.

PS: By the way, I think I’m confused and should probably remove this discussion unless you think there is anything worth extracting from it.

Toby: I was going to say something about what if f:XYf: X \to Y without X=YX = Y, but I also fell into the trap of trying the simpler one first. Yes, let's take the abstract general category 2\mathbf{2} (the interval category) and make it a concrete category with F:2SetF: \mathbf{2} \to Set representing an arbitrary arrow in SetSet. Then the category of elements El F(2)El_F(\mathbf{2}) has the disjoint union X+YX + Y as its set of objects, with the only nonidentity morphisms being arrows aba \to b such that f(a)=bf(a) = b. Then this looks like a (simple) directed graph on the vertex set X+YX + Y; if we mod X+YX + Y out by the equivalence relation generated by the adjacency relation of this graph, then we get the cograph in the sense of Lawvere. To get the graph as a subset of X×YX \times Y, we can think of X×YX \times Y as a subset of (X+Y) 2=X 2+2X×Y+Y 2(X + Y)^2 = X^2 + 2 X \times Y + Y^2, note that every (non-loop) edge of the directed graph above (which can be thought of as a subset of (X+Y) 2(X + Y)^2) belongs to the first X×YX \times Y summand, and restrict the target to get a subset of X×YX \times Y, which is the graph of ff.

Eric: I was thinking about adding the category theoretic version in your last comment as the main definition above. It is the one most suitable to the nLab I think.

Toby: What do you mean, ‘the one’? the one definition? or the one concept? What you wrote above is not a definition of what most people call the ‘graph’ of a function, which is a subset of the cartesian product X×YX \times Y. It's an interesting concept, but I don't see why it's more suitable for the nLab than the subset of X×YX \times Y, or the other ideas (the quotient set of X+YX + Y and the simple directed graph on X+YX + Y, which your definition at least mentions).

Eric: Moved the definition back down here. Sorry. I thought I was just transcribing what you had written.

Definition

Consider a function f:XYf:X\to Y to be the image of the interval category 2\mathbf{2} of a functor F:2SetF:\mathbf{2}\to Set with

f=F(), X=F(0), Y=F(1).\begin{aligned} &f = F(\to),\\ &X = F(0),\\ &Y = F(1). \end{aligned}

The graph of ff is the category of elements El F(2)El_F(\mathbf{2}).

The graph of ff has the disjoint union X+YX + Y as its set of objects, with the only nonidentity morphisms being arrows aba \to b such that f(a)=bf(a) = b. This is a (simple) directed graph on the vertex set X+YX + Y.

If we mod X+YX + Y out by the equivalence relation generated by the adjacency relation of this graph, then we get the cograph in the sense of Lawvere as a quotient set.

I’m probably making a combination of mistakes. I thought you were suggesting this category of elements was the same thing as the graph of a function. My time allotted to thinking about this is 15 second spurts every 3-4 hours, so I’m bound to get confused.

Maybe what I’m after is a nice arrow theoretic definition of graph of a morphism and then a graph of a function becomes a special case. It’s obviously not a requirement, but I tend to try to rethink standard definitions here on the nLab arrow theoretically.

What I saw in the original version of this page is something that would be at home in a standard text and was hoping to nLab-ify it. Probably misguided.

Toby: It was all correct except for the claim that what it defines is the graph of the function!

Part of the problem is that the graph of a function isn't really a concept that we can try to turn around and see from another, more categorial, point of view. That's because it is itself just a way of looking at the function itself! Compare how they do it in material set theory: the function is its graph, literally. When I started this page, I didn't think that there was anything very nn-categorial to do in it; it was just something obvious to write in contrast to graph.

But now that you've brought up this bit with the category of elements, I do think that there is a place for it. I'll try to rewrite the page to make things clearer: that a function (or even relation) might be viewed as being given by a ‘graph’ in various senses, which we are describing here. Then we can mention all of them.

Urs Schreiber: have only had a chance to look at your conversation here now. I think that the notion of both graph as well as cograph of a function are usefully regarded as special cases of graph of a functor and cograph of a functor. I have created these entries and added more details there, and I have now also expanded the discussion above, incorporating your discussion here as well as indicating the way this fits into the more general picture.

Toby: Thanks, Urs, that's great!

Revised on May 30, 2013 13:09:04 by Urs Schreiber (82.113.121.121)