\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*{computad} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{higher_category_theory}{}\paragraph*{{Higher category theory}}\label{higher_category_theory} [[!include higher category theory - contents]] \hypertarget{higher_algebra}{}\paragraph*{{Higher algebra}}\label{higher_algebra} [[!include higher algebra - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{definition}{Definition}\dotfill \pageref*{definition} \linebreak \noindent\hyperlink{globular_computads}{Globular computads}\dotfill \pageref*{globular_computads} \linebreak \noindent\hyperlink{examples}{Examples}\dotfill \pageref*{examples} \linebreak \noindent\hyperlink{on_inverse_diagrams}{On inverse diagrams}\dotfill \pageref*{on_inverse_diagrams} \linebreak \noindent\hyperlink{computads_presheaves_and_opetopes}{Computads, presheaves and opetopes}\dotfill \pageref*{computads_presheaves_and_opetopes} \linebreak \noindent\hyperlink{monadicity}{Monadicity}\dotfill \pageref*{monadicity} \linebreak \noindent\hyperlink{computads_as_cofibrant_resolutions}{Computads as cofibrant resolutions}\dotfill \pageref*{computads_as_cofibrant_resolutions} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} A \emph{computad} is a formal device (due to [[Ross Street]], 1976) for describing ``generators'' of [[higher category theory|higher categories]], and in particular for $n$-[[n-category|categories]]. They generalize [[quivers]] ([[directed graphs]]), which describe generators of ordinary (1-)[[categories]]. In a sense, $n$-computads are the ``most general'' structure from which one can generate a free $n$-category; they allow the free adjoining of $k$-cells whose [[source]] and [[target]] are arbitrary [[composites]] of previously adjoined $(k-1)$-cells. Originally the $n$-categories under consideration were [[strict n-category|strict]], but more recently the concept of $n$-computad has been expanded to take into account weak $n$-categories and other higher-categorical structures. The notion is tied to [[algebraic definition of higher category|algebraic]] senses of higher categories, but computads can also be used as the input for [[geometric definition of higher category|geometric]] senses as well, and may aid in a comparison between the two approaches. Computads are also called [[polygraphs]], following [[Burroni]]; this term is especially used in parts of the literature related to [[rewriting]] theory. \hypertarget{definition}{}\subsection*{{Definition}}\label{definition} Each type of higher-categorical structure comes with its own notion of computad. Thus there are computads for strict $n$-categories, computads for weak $n$-categories, computads for [[double categories]], and so on. \hypertarget{globular_computads}{}\subsubsection*{{Globular computads}}\label{globular_computads} First we will define computads relative to an arbitrary [[globular operad]] $P$. This reproduces the original strict situation when $P$ is the terminal globular operad, whose algebras are [[strict ∞-categories]], but it also applies to operads $P$ whose algebras are [[Batanin weak ∞-categories]]. The generalization to the weak case is originally due to Batanin; the following simpler reformulation of it is due to Richard Garner. Let $P$ be a [[globular operad]] and let $P Alg$ denote the category of $P$-algebras and strict morphisms. Thus if $P$ is terminal, then $P Alg = Str \omega Cat$. We denote by $U_P$ the forgetful functor $P Alg \to GSet$ and by $F_P$ its left adjoint, where $GSet$ denotes the category of [[globular sets]]. Let $2_n$ denote the $n$-[[globe]] and $\partial_n$ its boundary (which is the pushout of two $(n-1)$-globes along their boundaries). These are globular sets and thus they generate free $P$-algebras $F_P 2_n$ and $F_P \partial_n$. We now define, recursively in $n$, the category $n Cptd_P$ of \textbf{$n$-computads} relative to $P$, together with an adjunction \begin{displaymath} n Cptd_P \underoverset{U_n}{F_n}{\rightleftarrows} P Alg . \end{displaymath} \begin{itemize}% \item When $n=0$, the category $(-1) Cptd_P$ is [[Set]], $U_0\colon P Alg \to Set$ picks out the set of objects, and $F_0$ is its left adjoint, which constructs the free $P$-algebra on a set (considered as a globular set concentrated in degree 0). \item If $n\gt 0$, an \textbf{n-computad} consists of an $(n-1)$-computad $C$, a set $X$, and a function \begin{displaymath} x\colon X\to P Alg(F_P \partial_n, F_{n-1} C) = GSet(\partial_n, U_P F_{n-1} C). \end{displaymath} We call $X$ the set of \textbf{n-cells}. Note that $x$ simply equips each $n$-cell with a pair of parallel $(n-1)$-cells in $F_{n-1} C$. In fancy language, the category $n Cptd_P$ is the [[comma category]] $Set / B_n$, where $B_n = P Alg(F_P \partial_n, F_{n-1} -)$. \item The functor $U_n\colon P Alg \to n Cptd_P$ sends a $P$-algebra $A$ to the $n$-computad defined by the $(n-1)$-computad $U_{n-1} A$ together with $X$ and $x$ defined by the following pullback square in [[Set]]: \begin{displaymath} \itexarray{X & \overset{}{\to} & P Alg(F_P 2_n, A)\\ ^x \downarrow && \downarrow\\ P Alg(F_P \partial_n, F_{n-1} U_{n-1} A) & \underset{}{\to} & P Alg(F_P \partial_n, A)} \end{displaymath} Here the bottom map is induced by the counit of the adjunction $F_{n-1}\dashv U_{n-1}$, while the right-hand map is induced by the inclusion $\partial_n \hookrightarrow 2_n$. \item The left adjoint $F_n$ of $U_n$ is defined by taking an $n$-computad $D = (C,X,x)$ to the following pushout in $P Alg$: \begin{displaymath} \itexarray{X\cdot F_P \partial_n & \overset{\overline{x}}{\to} & F_{n-1} C\\ \downarrow && \downarrow\\ X \cdot F_P 2_n & \underset{}{\to} & F_n D} \end{displaymath} Here $\cdot$ denotes a [[copower]] by a set, the top map $\overline{x}$ is the [[adjunct]] of $x$, and the left-hand map is again induced by the inclusion $\partial_n \hookrightarrow 2_n$. Adjointness is easy to verify using the universal properties of pullbacks and pushouts. \end{itemize} Finally, the category $\omega Cptd_P$ of $\omega$-computads is the [[limit]] of the diagram \begin{displaymath} \dots \to 2 Cptd_P \to 1 Cptd_P \to 0 Cptd_P \to (-1) Cptd_P \end{displaymath} consisting of the functors $n Cptd_P \to (n-1)Cptd_P$ taking $(C,X,x)$ to $C$. The functors $U_n$ form a [[cone]] over this diagram and thus induce a functor $U_\omega\colon P Alg \to \omega Cptd_P$, which is easily seen to have a left adjoint which takes an object $(C_n)$ of $\omega Cptd_P$ to the [[colimit]] \begin{displaymath} F_{-1} C_{-1} \to F_0 C_0 \to F_1 C_1 \to F_2 C_2 \to \dots. \end{displaymath} \hypertarget{examples}{}\paragraph*{{Examples}}\label{examples} For simplicity, let $P$ be the terminal globular operad, such that $P$-algebras are [[strict ∞-categories]]. \begin{itemize}% \item As in the definition, a 0-computad is just a set, and the free [[0-category]] on a 0-computad is just itself, considered as a discrete $\omega$-category. \item A 1-computad consists of 0-computad $C$ (i.e. a set) together with another set $X$ and a function $X\to GSet(\partial_1, U_P F_0 C)$. Now $\partial_1$ is just a pair of objects, so this means that each element of $X$ is equipped with a pair of elements of $C$, which we call its [[source]] and [[target]]. Thus a 1-computad is just a [[quiver]]. \item The free 1-category on a 1-computad is the usual free category on a quiver. That is, its objects are the vertices of the graph and its morphisms are finite composable strings of edges in the quiver. \item A 2-computad is given by a quiver together with a set $C_2$ of 2-cells, each equipped with a source and a target which are composable strings of edges in the graph. For example, if the given quiver is a square \begin{displaymath} \itexarray{\bullet & \overset{f}{\to} & \bullet \\ ^h\downarrow && \downarrow^k\\ \bullet& \underset{g}{\to} & \bullet} \end{displaymath} then the free category it generates is the free noncommutative square, having two diagonals $k f$ and $g h$. We can then make a 2-computad by adding one 2-cell $\alpha$ with source $k f$ and target $g h$. The free 2-category on this 2-computad can then be drawn pictorially as \begin{displaymath} \itexarray{\bullet & \overset{f}{\to} & \bullet\\ ^h\downarrow & \swarrow_\alpha & \downarrow^k\\ \bullet & \underset{g}{\to} & \bullet} \end{displaymath} \item Any $n$-[[globular set]] can be considered as an $n$-computad where for each $n$, the functions $s, t: C_n \rightrightarrows F_{n-1}(\mathcal{C})_{n-1}$ land inside $C_{n-1}$. The free $n$-category on this $n$-computad will then agree with the free $n$-category on the $n$-globular set we started with. \item Every [[oriental]] can be presented by a computad, as can every [[opetope]], [[cube]], as can most other [[geometric shapes for higher structures]]. \end{itemize} \hypertarget{on_inverse_diagrams}{}\subsubsection*{{On inverse diagrams}}\label{on_inverse_diagrams} The above definition can easily be generalized by replacing the [[globe category]] by any [[direct category]], i.e. the [[opposite]] of an [[inverse category]]. In more detail, let $\mathcal{I}$ be any inverse category, and consider the [[diagram category]] $\Set^{\mathcal{I}}$. Then any object $n\in \mathcal{I}$ has a [[representable functor]] $Y_n\in \Set^{\mathcal{I}}$ defined by $Y_n(x) = \mathcal{I}(n,x)$, which has a ``boundary'' subfunctor $\partial_n \subset Y_n$ consisting of all nonidentity morphisms $n\to x$ (as $x$ varies). These play the role of $2_n$ and $\partial_n$ above. Let $P$ be a monad on $\Set^{\mathcal{I}}$ with induced adjunction $F_P : \Set^{\mathcal{I}} \rightleftarrows P Alg : U_P$. Since (by definition of ``inverse category'') the objects of $\mathcal{I}$ have a [[well-founded relation]] given by the existence of nonidentity arrows, we will define by well-founded recursion on $n\in \mathcal{I}$ the category $n Cptd_P$ and an adjunction $n Cptd_P \underoverset{U_n}{F_n}{\rightleftarrows} P Alg$. Assume, therefore, that this adjunction has been defined for all $k$ for which there is any nonidentity morphism $n\to k$. Let $(\lt n) Cptd_P$ be the limit of the $k Cptd_P$ for all such $k$, with an induced adjunction $F_{\lt n} \dashv U_{\lt n}$ to $P Alg$ (see below). Now define an $n$-computad to consist of a $(\lt n)$-computad $C$, a set $X$, and a function \begin{displaymath} x\colon X\to P Alg(F_P \partial_n, F_{\lt n} C) = Set^{\mathcal{I}}(\partial_n, U_P F_{\lt n} C). \end{displaymath} The functor $U_n\colon P Alg \to n Cptd_P$ is defined as before: it sends a $P$-algebra $A$ to the $n$-computad defined by the $(\lt n)$-computad $U_{\lt n} A$ together with $X$ and $x$ defined by the following pullback square in [[Set]]: \begin{displaymath} \itexarray{X & \overset{}{\to} & P Alg(F_P Y_n, A)\\ ^x \downarrow && \downarrow\\ P Alg(F_P \partial_n, F_{\lt n} U_{\lt n} A) & \underset{}{\to} & P Alg(F_P \partial_n, A)} \end{displaymath} Similarly, its left adjoint $F_n$ takes an $n$-computad $D = (C,X,x)$ to the following pushout in $P Alg$: \begin{displaymath} \itexarray{X\cdot F_P \partial_n & \overset{\overline{x}}{\to} & F_{\lt n} C\\ \downarrow && \downarrow\\ X \cdot F_P Y_n & \underset{}{\to} & F_n D} \end{displaymath} This definition is not quite correct as written, because it assumes in the definition of $(\lt n)$-computads not just that the categories $k Cptd_P$ are defined with adjunctions to $P Alg$, but that they are related by suitable functors as $k$ varies that commute with these adjunctions. Thus, formally speaking it has to be phrased as a definition of a [[functor]], rather than a function, by well-founded recursion, as explained \href{http://www.staff.science.uu.nl/~ooste110/realizability/wellffunctors.pdf}{here}. We leave the details to the reader. For example, if $\mathcal{I} = \mathcal{P}\times \mathcal{P}$, where $\mathcal{P} = (1 \rightrightarrows 0)$, then there is a monad on $\mathcal{I}$ whose algebras are double categories, and in this way we can obtain a notion of ``double computad''. \hypertarget{computads_presheaves_and_opetopes}{}\subsection*{{Computads, presheaves and opetopes}}\label{computads_presheaves_and_opetopes} The category of computads relative to a globular operad $P$ is sometimes a [[presheaf category]], and when it isn't, it ``almost is.'' At first glance, it may look as though it should always be a presheaf category, say $Set^{Ctp^{op}}$ where $Ctp$ is the category of ``computopes.'' A ``computope'' is, intuitively, one possible ``[[geometric shapes for higher structures|shape]]'' for an $n$-cell in an $n$-category (i.e. a $P$-algebra). For example, every ``[[globe]]'' is a computope, as is every [[simplex]]/[[oriental]], every [[cube]], and so on. It may feel at first as though a computad should be specified by giving a set of cells of each ``shape'' (i.e. for each computope) related by ``face maps,'' generalizing [[globular set]]s, [[simplicial set]]s, [[cubical set]]s, and so on. However, when $P$ is the terminal globular operad whose algebras are \emph{strict} $\omega$-categories, the presence of identities in the notion of free $n$-category prevents this from quite working, for sort of the same reason that [[strict n-categories]] are insufficient for $n\gt 2$. For instance, there is a 2-computad with one 0-cell $x$, \emph{no} 1-cells, and two 2-cells $\alpha$ and $\beta$. The source and target of $\alpha$ and $\beta$ must then both be the identity 1-cell $id_x$ of $x$. Now in the free 2-category generated by this 2-computad, we have $\beta\alpha = \alpha\beta$, by the [[Eckmann-Hilton argument]]. If we define a 3-computad on top of this 2-computad with a 3-cell $\mu$ whose source (say) is $\beta\alpha = \alpha\beta$, then there can be no ``face'' maps from the computope-shape of $\mu$ to the computope-shape of $\beta$ and $\alpha$, since there is no way to distinguish $\alpha$ from $\beta$ (i.e. neither one is the ``first'' or the ``second''). This argument only kicks in for $n\ge 3$, so the categories of 0-computads, 1-computads, and 2-computads are presheaf categories. Moreover, the problem can also be avoided if $P$ is ``suitably weak.'' To define what this means, one considers the ``slices'' of the operad $P$. By truncation, any such $P$ induces a monad $P_k$ on the category of $k$-globular sets. Now the full subcategory of $P_n Alg$ on the objects whose underlying globular set is $(n-1)$-terminal (i.e. terminal in degrees $\lt n$) is [[monadic functor|monadic]] over the category of sets; the resulting monad on [[Set]] is called the \textbf{$k$-slice} of $P$. In Theorem 5.2 of \href{http://arxiv.org/abs/math.CA/0209035}{Computads and slices of operads}, Batanin shows that the category of $n$-computads of a Batanin-operad $P$ is a presheaf category if the $k$-slices of $P$ are [[strongly regular theory|strongly regular theories]] for all $0\leq k \leq n-1$. This applies in particular to the case where $P$ is an operad for Batanin weak $\omega$-categories. On the other hand, even in the strict case we can obtain presheaf categories of suitably restricted computads. For instance, if we consider only ``many-to-one'' computads in which the target of each $n$-cell consists of exactly one $(n-1)$-cell (rather than a free composite of such), we obtain a presheaf category, which is in fact equivalent to the category of [[opetopic set]]s. We also obtain a presheaf category if we restrict both source and target to not be identity arrows; see \hyperlink{Henry17}{Henry 2017}. \hypertarget{monadicity}{}\subsection*{{Monadicity}}\label{monadicity} The monadicity of $\omega Cptd$ over $\omega Cat$ was first claimed by Batanin in his `98 paper. The proof however made use of the fact that $\omega Cptd$ was a category of presheaves, which was later found to be false. M\'e{}tayer provided a corrected proof in \begin{itemize}% \item [[François Métayer]], \href{https://arxiv.org/abs/1606.00139}{Strict $\omega$-categories are monadic over polygraphs}. \end{itemize} \hypertarget{computads_as_cofibrant_resolutions}{}\subsection*{{Computads as cofibrant resolutions}}\label{computads_as_cofibrant_resolutions} Quite generally, computads can be used to describe [[cofibrant object|cofibrant replacements]]. Specifically, the $\omega$-categories freely generated by computads are precisely the cofibrant objects in the [[canonical model structure]] on [[strict ∞-categories]]. This is discussed in \begin{itemize}% \item F. M\'e{}tayer, \emph{Cofibrant complexes are free} (\href{http://arxiv.org/abs/math.CT/0701746}{arXiv}) \item F. M\'e{}tayer, \emph{Resolutions by polygraphs} (\href{http://www.tac.mta.ca/tac/volumes/11/7/11-07.pdf}{tac}) \end{itemize} The cofibrant resolution $(-)_{cof} \to Id : \omega Cat \to \omega Cat$ given by M\'e{}tayer in these articles is the one counit of the [[adjunction]] $\omega Cptd \to \omega Cat$. In particular, this implies that \emph{every} [[strict ∞-category]] is equivalent as an $\omega$-category to one that is freely generated by a computad. (Notice that these articles say ``polygraph'' for ``computad'', following Burroni). It is to be expected that similar results are true for Batanin weak $\omega$-categories, defined as algebras for some other ``contractible'' globular operad $P$. Moreover, for any globular operad $P$, one can show that the ``cofibrant replacement'' obtained as above from the adjunction $\omega Cptd_P \rightleftarrows P Alg$ is the same as the ``canonical'' cofibrant replacement [[comonad]] obtained from the [[algebraic weak factorization system]] on $P Alg$ generated by the boundary inclusions $F_P \partial_n \to F_P 2_n$. This is proven in \begin{itemize}% \item [[Richard Garner]], \href{http://arxiv.org/abs/0810.4450}{Homomorphisms of higher categories}. \end{itemize} In particular, the [[Kleisli category]] of this comonad is a good candidate for the category of \emph{weak functors} between Batanin weak $\omega$-categories. \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[syzygy]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} 2-computads were originally defined by Ross Street in the paper \begin{itemize}% \item [[Ross Street]], \emph{Limits indexed by category-valued 2-functors}. \end{itemize} The goal there was to describe which 2-categories are ``finitely presented'' (the presentation being given by a 2-computad) in order to describe the correct notion of ``finite [[2-limit]]''. I don't know the first use of ``$n$-computads,'' but [[Michael Makkai]] has studied them as a way to define [[opetopic sets]], and shown that they are ``almost'' but not quite a presheaf category: \begin{itemize}% \item Makkai, Harnik, and Zawadowski, \emph{Multitopic sets are the same as many-to-one computads}, \href{http://www.math.mcgill.ca/makkai/m_1_comp/}{link}. \item Makkai, \emph{The word problem for computads}, \href{http://www.math.mcgill.ca/makkai/computad.zip}{link}. \end{itemize} Computads were studied by [[Burroni]] under the name ``polygraph'' in the framework of [[rewriting]]: \begin{itemize}% \item [[Albert Burroni]], \emph{Higher dimensional word problems with applications to equational logic} (\href{https://www.irif.fr/_media/users/burroni/high_word_pb.pdf}{pdf}) \end{itemize} The following more recent papers are referred to above: \begin{itemize}% \item [[Michael Batanin]], \href{http://arxiv.org/abs/math.CA/0209035}{Computads and slices of operads} \item [[Richard Garner]], \href{http://arxiv.org/abs/0810.4450}{Homomorphisms of higher categories}. \item [[Simon Henry]], \href{https://arxiv.org/abs/1711.00744}{Non-unital polygraphs form a presheaf categories}, 2017 \end{itemize} One should beware that there are some erroneous claims in some of Batanin's papers; in particular the claim that computads relative to a globular operad are \emph{always} a presheaf category. This was explicitly shown to be false in \begin{itemize}% \item Michael Makkai and Marek Zawadowski, \emph{The category of 3-computads is not cartesian closed}, \href{http://www.ams.org/mathscinet-getitem?mr=2440266}{MR}. \item Eugenia Cheng, \href{http://arxiv.org/abs/1209.0414}{A direct proof that the category of 3-computads is not cartesian closed} \end{itemize} Finally, we had some blog discussion about this at \begin{itemize}% \item \href{http://golem.ph.utexas.edu/category/2008/10/freely_generated_categories.html}{Freely generated $\omega$-categories}. \end{itemize} [[!redirects computads]] [[!redirects n-computad]] [[!redirects n-computads]] [[!redirects ∞-computad]] [[!redirects ∞-computads]] [[!redirects 2-computad]] [[!redirects 2-computads]] [[!redirects polygraph]] [[!redirects polygraphs]] \end{document}