\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*{walking structure}

\hypertarget{walking_structures}{}\section*{{Walking structures}}\label{walking_structures}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak
\noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak
\noindent\hyperlink{relation_to_initial_objects}{Relation to initial objects}\dotfill \pageref*{relation_to_initial_objects} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


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

Around the nLab and elsewhere, one occasionally sees an expression ``the walking \_\_\_\_\_'' where the blank is some mathematical concept. This is a colloquial way of referring to an archetypal model of the concept or type, and usually refers to a free or initial context in which such a type can be interpreted. The term is believed to have been introduced by [[James Dolan]] (see the reference below).

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

The idea is probably easier to apprehend through examples rather than through a formal definition, but for the record:

If X is a type of structure that can be defined in a [[category]], [[higher category]], or category with some sort of [[stuff, structure, property|structure]], then the \textbf{walking X} is an informal term for the \emph{free category (resp. higher category, category with suitable structure) containing an X}.

More precisely, if $StructCat$ denotes some (higher) category of categories with an appropriate type of structure, then the \textbf{walking X} is an object $[X] \in StructCat$ together with a [[natural transformation|natural]] [[equivalence]]

\begin{displaymath}
StructCat([X],C) \simeq \{Xs \; in \; C\}
\end{displaymath}
between the hom-set/category/space from $[X]$ to $C$, for any $C\in StructCat$, and the set/category/space of all Xs in $C$.

\begin{remark}
\label{}\hypertarget{}{}
In other words, the structured category $[X]$ equipped with its canonical type $X$ is initial among such structured categories that come equipped with such types $X$. A fancier expression is that $[X]$ `coclassifies' such types: this is analogous to how a [[classifying space]] $B G$ for a [[topological group]] $G$ classifies $G$-[[bundles]], in that every $G$-bundle $p: E \to X$ over a suitable space $X$ has a classifying map $\chi_p: X \to B G$ (unique up to homotopy) such that pulling back the canonical $G$-bundle type $\pi: E G \to B G$ along $\chi_p$ reproduces the type $p$. Only here we say `coclassifies' (as for example in this \href{http://nforum.mathforge.org/discussion/1529/walking-structures/#Item_5}{comment}), since here we instead ``push forward'' the canonical type $X$ of $[X]$ along a structured-category morphism $[X] \to C$ to obtain a given type of $C$.

\end{remark}
Pronunciation is just as in `John is a walking almanac' or `Eugene Levy is a walking pair of eyebrows'.

\hypertarget{examples}{}\subsection*{{Examples}}\label{examples}

\begin{itemize}%
\item The [[interval category]] is the \emph{walking arrow}.


\item The augmented/algebraist's [[simplex category]] is ``the \emph{walking [[monoid]]}'' (in a [[monoidal category]]). That is to say: the simplex category is initial (in a 2-categorical sense) among monoidal categories equipped with a monoid object. Intuitively, it is [[the]] monoidal category that results if all one need be told about it is that it has a monoid object -- all the morphisms of the category are obtainable from the monoid structure by applying the operations of a monoidal category, and they are subject to no further relations beyond those implied by the monoid axioms.


\item Similarly, the [[Lawvere theory]] of groups can be described as ``the \emph{walking [[group object|group]]}'' (qua [[cartesian monoidal categories]]). This gives a good intuitive description: this Lawvere theory can be understood as the category (with finite products) that results if all one need be told about it is that it has a [[group object]]; the rest of the structure of this category can be deduced from this one fact.



\end{itemize}
The last two examples indicate the need for a little care: the [[doctrine]] or type of structured category in which the `$X$' of ``the walking $X$'' lives should either be specified or clear from context. For example, if one simply says ``the walking monoid'', this means the simplex category if the surrounding context is the doctrine of monoidal categories -- but means something else (the Lawvere theory of monoids) if the ambient context is the doctrine of categories with finite products, and it means the category opposite to that of finitely presentable monoids if we are in the doctrine of [[finitely complete categories]].

If the doctrine is not specified, then a reasonable default is a `minimal' doctrine in which the concept makes sense; for example, to make sense of monoids, one doesn't need more than monoidal categories. See also [[microcosm principle]].

Thus, more generally,

\begin{itemize}%
\item The [[syntactic category]] of a [[theory]] $T$ in some [[doctrine]] $D$ is the ``walking $T$-model'' (in a $D$-category). In particular, the [[classifying topos]] of a [[geometric theory]] $T$ is ``the \emph{walking $T$-model}'' \emph{qua} [[Grothendieck toposes]] (where the morphisms are the left-adjoint parts of [[geometric morphisms]]).

\end{itemize}
\hypertarget{relation_to_initial_objects}{}\subsection*{{Relation to initial objects}}\label{relation_to_initial_objects}

The walking X is, of course, not the same as the [[initial object|initial]] X.

Consider for example the case when X is a pointed monoid (a monoid equipped with an element). The initial pointed monoid (in $Set$) is the [[natural numbers]] equipped with $1\in \mathbb{N}$. Whereas the walking pointed monoid (qua category with finite products, say) is a category $C_M$ with finite products containing a [[monoid object]] $M\in C_M$ and an ``[[generalized element|element]]'' $e:1\to M$. They have different types and different universal properties: $\mathbb{N}$ has a universal property mapping into other pointed monoids in $Set$, while $C_M$ has a universal property mapping into other categories with products equipped with pointed monoids.

Nevertheless, the first sits inside the second! Specifically, for any category $C$ with products, the ``underlying set'' functor $C(1,-):C\to Set$ is product-preserving and hence carries monoid objects to monoid objects, and in the case of the walking pointed monoid we have $C_M(1,M) \cong \mathbb{N}$.

This is true rather generally: \emph{the initial X is the underlying X of the walking X}. One general theorem of this sort is the following:

\begin{utheorem}
Let $K$ be a [[2-category]] containing an object $S$, and suppose that:

\begin{enumerate}%
\item The domain projection $K\sslash S \to K$ from the [[lax slice 2-category]] has a section. Explicitly, for every object $X$ we have a map $s_X : X\to S$ and for every morphism $f:X\to Y$ we have a 2-cell $\sigma_f : s_X \to s_Y f$, such that for every 2-cell $\alpha :f\to g$ we have $\sigma_g . s_Y\alpha = \sigma_f$, and these vary functorially.
\item We have $s_S \cong 1_S$, and for any $X$ the composite $s_X \xrightarrow{\sigma_{s_X}} s_S s_X \cong s_X$ is the identity.

\end{enumerate}
Then for any $X$, the morphism $s_X:X\to S$ is the initial object of the hom-category $K(X,S)$.

\end{utheorem}
\begin{proof}
We will use the characterization of initial objects via \href{/nlab/show/initial+object#ConesOverTheIdentity}{cones over the identity}. Thus, we must construct a natural transformation from the constant functor $\Delta_{s_X} : K(X,S) \to K(X,S)$ to the identity, which is the identity at $s_X$. However, given any $f:X\to S$, we have the 2-cell $s_X \xrightarrow{\sigma_f} s_S f \cong f$, and the assumption $\sigma_g . s_Y\alpha = \sigma_f$ makes this a natural transformation; and the final assumption says exactly that this is the identity at $s_X$.

\end{proof}
To see how this theorem implies that the initial X is the underlying X of the walking X, consider again the case of pointed monoids. Let $K$ be the 2-category of categories with products and product-preserving functors, let $S=Set$, and let $s_C : C \to Set$ be $C(1,-)$. The hypotheses are easy to verify; thus the theorem tells us that $C(1,-)$ is the initial functor $C\to Set$ for any $C$.

Now take $C$ to be the walking pointed monoid $C_M$ above. Then its universal property tells us that functors $F:C_M\to Set$ are equivalent to pointed monoids $F(M)$ in $Set$; so we see that $C(1,M)$ is the initial pointed monoid in $Set$, i.e. $\mathbb{N}$.

A similar argument applies whenever we have a ``$Set$-like'' object of a 2-category with ``underlying set'' morphisms to it. For instance, in place of categories with finite products we could consider categories with finite limits. However, in other cases, such as monoidal categories, there is a disconnect: the natural ``underlying set'' functor for a monoidal category $C$ is $C(I,-)$, where $I$ is the unit object; but in general this is only \emph{lax} monoidal, whereas the universal property of a ``walking X qua monoidal category'' is relative to \emph{strong} monoidal functors.

It does often happen that this disconnect can be bridged. For instance, suppose X is something that can be defined in any [[multicategory]] (like a pointed monoid). Then we can apply the above argument to the 2-category of multicategories, as the walking X qua multicategory has a universal property relative to functors of multicategories, even though such functors correspond to \emph{lax} functors between monoidal categories. It follows that the underlying set functor $C_M(;-) : C_M\to Set$ of the walking X qua multicategory corresponds to the initial X in $Set$.

Moreover, we can deduce from this that the underlying pointed monoid of the walking X qua monoidal category is also the initial X in $Set$. This is because the walking X qua monoidal category is the monoidal category freely generated by the walking X qua multicategory, and a multicategory embeds fully-faithfully in the monoidal category that it freely generates. In terms of the [[type theory]] that generates walking Xs, the latter fact can be seen as a sort of [[canonicity]] for the tensor-product constructor.

Similar arguments apply in other cases. For instance, in the 2-category of [[double categories]] we can take $S$ to be the double category [[Span]]; this has the same problem as that of monoidal categories, but we can solve it similarly by considering [[virtual double categories]] instead.

On the other hand, there are also cases where this argument does not apply. For instance, X could be something that can be defined in a monoidal category but \emph{not} in a multicategory, such as a [[Frobenius monoid]]. In this case the claim doesn't even make sense: the functor $C(I,-)$, being only lax monoidal in general, need not preserve Frobenius monoids. It seems that in most cases where an ``underlying set'' functor $C(I,-)$ preserves Xs, there is a kind of [[generalized multicategory]] in which Xs can be defined and this argument carried through, but I do not know of a general theory suggesting this.

\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item A \href{http://golem.ph.utexas.edu/category/2010/01/f_and_the_shibboleth.html}{Caf\'e{} post} essentially about walking objects (among other things), including a \href{http://golem.ph.utexas.edu/category/2010/01/f_and_the_shibboleth.html#c031066}{comment} that explains the terminology.

\end{itemize}
[[!redirects walking]] [[!redirects walking structure]] [[!redirects walking structures]] [[!redirects walking object]] [[!redirects walking objects]]



\end{document}