\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{graph of a function}

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{graph_of_a_function}{Graph of a function}\dotfill \pageref*{graph_of_a_function} \linebreak
\noindent\hyperlink{graph_of_a_binary_relation}{Graph of a binary relation}\dotfill \pageref*{graph_of_a_binary_relation} \linebreak
\noindent\hyperlink{relation_to_graph_theory}{Relation to graph theory}\dotfill \pageref*{relation_to_graph_theory} \linebreak
\noindent\hyperlink{graph_of_an_ary_relation}{Graph of an $n$-ary relation}\dotfill \pageref*{graph_of_an_ary_relation} \linebreak
\noindent\hyperlink{cograph}{Cograph of a function}\dotfill \pageref*{cograph} \linebreak
\noindent\hyperlink{relation_to_graph_theory_2}{Relation to graph theory}\dotfill \pageref*{relation_to_graph_theory_2} \linebreak
\noindent\hyperlink{generalization}{Generalization}\dotfill \pageref*{generalization} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{discussion}{Discussion}\dotfill \pageref*{discussion} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

The \emph{graph of a function} $f : X \to Y$ is the subset that $f$ ``carves out'' of the [[cartesian product]] $X \times Y$.

\hypertarget{definition}{}\subsection*{{Definition}}\label{definition}

\hypertarget{graph_of_a_function}{}\subsubsection*{{Graph of a function}}\label{graph_of_a_function}

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

\begin{udefn}
The \textbf{graph} $graph(f)$ of a [[function]] $f: X \to Y$ is that [[subset]] $graph(f) \hookrightarrow X \times Y$ of the [[cartesian product]] $X \times Y$ defined by the property that $(a,b) \in X \times Y$ belongs to the graph of $f$ if and only if $f(a) = b$:

\begin{displaymath}
graph(f) = \{(a,b) \in X \times Y | f(a) = b\}
  \,.
\end{displaymath}
\end{udefn}
This can be understood as a special case of a [[graph of a functor]] by the following observation

\begin{ulemma}
For $f : X \to Y$ a [[function]], define a function

\begin{displaymath}
\chi_f : X \times Y \to \{0,1\}
\end{displaymath}
by regarding a [[set]] as a [[0-category]] and a 0-category as a [[(-1)-category]]-[[enriched category]] and then setting

\begin{displaymath}
\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\}
  \,.
\end{displaymath}
Then $\chi_f$ is the [[characteristic function]] of $graph(f)$ in that the diagram

\begin{displaymath}
\itexarray{
     graph(f) &\to& {*}
     \\
     \downarrow && \downarrow
     \\
     X \times Y &\stackrel{\chi_f}{\to}& \{0,1\}
  }
\end{displaymath}
is a [[pullback]] diagram.

\end{ulemma}
In other words this means that in the context of [[(-1)-category]]-[[enriched category theory]] the graph of a function $f$, regarded as an [[enriched functor]] is the [[category of elements]] of the corresponding [[profunctor]]. More on this at [[graph of a functor]].

\begin{uremark}
It is easy to identify the properties of those subsets of $X \times Y$ that are the graphs of functions, and $f = g$ if they have the same graph (given $X$ and $Y$). Consequently, it is common, especially (but not only) in [[material set theory]], to \emph{define} a function from $X$ to $Y$ 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]]!

\end{uremark}
\hypertarget{graph_of_a_binary_relation}{}\subsubsection*{{Graph of a binary relation}}\label{graph_of_a_binary_relation}

More generally, we can say that the \textbf{graph} of a [[binary relation]] from $X$ to $Y$ is a subset of $X \times Y$; $(a,b)$ belongs to the graph if and only if $a$ is related to $b$. (Note that \emph{every} subset of $X \times Y$ defines a unique relation; such a subset is the graph of a function if and only if the relation is both [[functional relation|functional]] and [[entire relation|entire]].)

Notice that with a function $f : X \to Y$ regarded as a [[profunctor]] $X \times Y \to (-1)Cat$ as described above, a relation $R \subset X \times Y$ corresponds to a general such [[profunctor]]. More precisely we have a [[pullback]] square

\begin{displaymath}
\itexarray{
    R &\to& {*}
    \\
    \downarrow && \downarrow
    \\
    X \times Y &\stackrel{\chi_R}{\to}& \{0,1\}
  }
\end{displaymath}
where

\begin{itemize}%
\item $R \subset X \times Y$ is the relation $R$ regarded as a subset of $X \times Y$ in the traditional sense;


\item $\chi_R : X \times Y \to \{0,1\}$ is the [[characteristic function]] of this subset.



\end{itemize}
So in this sense the ordinary notion of relation as a subset does really define the \emph{graph of the relation}, while the relation itself is more naturally understood as the corresponding 0-[[profunctor]]/[[characteristic function]] $\chi_f$.

\hypertarget{relation_to_graph_theory}{}\paragraph*{{Relation to graph theory}}\label{relation_to_graph_theory}

The graph of a binary relation from $X$ to $X$ 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 $X$, and either can be defined as a subset of $X^2$. In a similar way, [[spans]] from $X$ to $X$ correspond to [[digraph|directed pseudographs]] with vertex set $X$.

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

\hypertarget{graph_of_an_ary_relation}{}\subsubsection*{{Graph of an $n$-ary relation}}\label{graph_of_an_ary_relation}

The \textbf{graph} of a [[relation]] of arbitrary arity is similarly a subset of an arbitrary [[cartesian product]]; see [[relation theory]] for more on this.

\hypertarget{cograph}{}\subsubsection*{{Cograph of a function}}\label{cograph}

[[Bill Lawvere]] has also considered the \textbf{cograph} of a function, which is dually a [[quotient set]] of the [[disjoint union]] $X \uplus Y$; $a$ is identified with $b$ if $f(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) $X \uplus Y$; we declare $a \lt b$ if $f(a) = b$ (and \emph{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 : X \to Y$ determines a [[functor]] $\bar f : I \to Set$ from the [[interval category]] $I = \mathbf{2} = \{a \to b\}$ to [[Set]] by setting $\bar f(a) = X$, $\bar f(b) = Y$ and $\bar f(a \to b) = f$.

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

\begin{displaymath}
\itexarray{
     cograph(f) &\to& {*}
     \\
     \downarrow && \downarrow
     \\
     I &\stackrel{\bar f}{\to}& Set
  }
\end{displaymath}
wich is computed by the strict [[pullback]]

\begin{displaymath}
\itexarray{
     cograph(f) &\to& Set_{*}
     \\
     \downarrow && \downarrow
     \\
     I &\stackrel{\bar f}{\to}& Set
  }
  \,.
\end{displaymath}
The cograph of $f$ in the sense of Lawvere is the set of [[connected component]]s of this category, i.e. $\pi_0(cograph(f))$.

\hypertarget{relation_to_graph_theory_2}{}\paragraph*{{Relation to graph theory}}\label{relation_to_graph_theory_2}

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 \emph{multipartite graphs}; in particular, directed bipartite graphs with vertex set broken up as $X + Y$ correspond precisely to binary relations from $X$ to $Y$.

\hypertarget{generalization}{}\subsection*{{Generalization}}\label{generalization}

The notion of \emph{graph of a function} is a special case of the notion [[graph of a functor]] obtained for functors between [[0-category|0-categories]].

Accordingly, the notion of \emph{cograph of a function} is a special case of the notion of [[cograph of a functor]].

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[graph morphism]]

\end{itemize}
\hypertarget{discussion}{}\subsection*{{Discussion}}\label{discussion}

[[Eric]]: I think it might be neat to take the opportunity here to relate \textbf{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

\begin{displaymath}
\bullet\righttoleftarrow f.
\end{displaymath}
Then a graph (or is it cograph?) is a [[category of elements]] of this category.

Then you could maybe talk more generally about \textbf{graph of a morhism}. Or something\ldots{}

\emph{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: X \to Y$; all you've done is label an abstract morphism with the same name `$f$'. 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 $f$ is a nontrivial [[endomorphism]].

When we [[category of elements|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 $a$ and $b$ for which $f: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 $\bullet = \{x,y,z\}$ and $f:\bullet\to\bullet$ with

\begin{displaymath}
\begin{aligned}
f(x) &= y \\
f(y) &= z \\
f(z) &= x.
\end{aligned}
\end{displaymath}
When we ``explode'' this simple category

\begin{displaymath}
Explode\left(\bullet\righttoleftarrow f\right)
\end{displaymath}
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]] $C$, i.e.

\begin{displaymath}
C = \bullet\righttoleftarrow f
\end{displaymath}
\emph{and} we have a functor $F:C\to Set$. Then $F(\bullet)$ is really a set and $F(f)$ is really a function.

Then

\begin{displaymath}
Explode(C) = Elem(F,C).
\end{displaymath}
This [[category of elements]] seems to warrant being associated with the \textbf{graph of a function} $f$. Furthermore, this allows us to consider the \textbf{graph of an endomorphism}. But then, I could be confused.

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

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

Then I get this result: If we take this function $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 $\bullet\righttoleftarrow f$ wasn't even a category. Oops! But it generates a category the way you outlined. However, an endofunction $f:X\to X$ does generate a [[digraph]] in the obvious way, i.e. each element of $X$ is a node and we have a directed edge $x\to x'$ if $f(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\ldots{}

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

\begin{enumerate}%
\item Construct a digraph $G_f$
\item Construct a category $C_f$ with one object $X$ and morphisms being powers of $f$.

\end{enumerate}
The quiver $Q(G_f)$ and the category of elements $Explode(C_f)$ coincide. That is cool, unfortunately, I don't know if it is relevant to \textbf{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 $X\stackrel{f}{\to} Y$ with TWO objects $X$ and $Y$ and one morphism $f:X\to Y$. Now, composition does not come into the picture.

Now, \emph{I think},

\begin{displaymath}
Explode(X\stackrel{f}{\to} Y)
\end{displaymath}
is the \textbf{graph of a morphism} $f$.

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.

\emph{Toby}: I was going to say something about what if $f: X \to Y$ without $X = Y$, but I also fell into the trap of trying the simpler one first. Yes, let's take the abstract general category $\mathbf{2}$ (the [[interval category]]) and make it a concrete category with $F: \mathbf{2} \to Set$ representing an arbitrary arrow in $Set$. Then the category of elements $El_F(\mathbf{2})$ has the disjoint union $X + Y$ as its set of objects, with the only nonidentity morphisms being arrows $a \to b$ such that $f(a) = b$. Then this looks like a (simple) directed graph on the vertex set $X + Y$; if we mod $X + 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 \times Y$, we can think of $X \times Y$ as a subset of $(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$) belongs to the first $X \times Y$ summand, and restrict the target to get a subset of $X \times Y$, which is the graph of $f$.

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

\emph{Toby}: What do you mean, `the one'? the one definition? or the one concept? What you wrote above is \emph{not} a definition of what most people call the `graph' of a function, which is a subset of the cartesian product $X \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 \times Y$, or the other ideas (the quotient set of $X + Y$ and the simple directed graph on $X + 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.

\begin{udefn}
Consider a function $f:X\to Y$ to be the image of the [[interval category]] $\mathbf{2}$ of a functor $F:\mathbf{2}\to Set$ with

\begin{displaymath}
\begin{aligned}
&f = F(\to),\\
&X = F(0),\\
&Y = F(1).
\end{aligned}
\end{displaymath}
The \textbf{graph} of $f$ is the [[category of elements]] $El_F(\mathbf{2})$.

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

If we mod $X + Y$ out by the [[equivalence relation]] generated by the adjacency relation of this graph, then we get the \textbf{cograph} in the sense of Lawvere as a [[quotient set]].

\end{udefn}
I'm probably making a combination of mistakes. I \emph{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 \textbf{graph of a morphism} and then a \textbf{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.

\emph{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 \emph{is} its graph, literally. When I started this page, I didn't think that there was anything very $n$-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.

\emph{Toby}: Thanks, Urs, that's great!

[[!redirects graph of a relation]] [[!redirects cograph of a function]] [[!redirects cograph]] [[!redirects Cograph]]



\end{document}