omegacat.tex 126 KB
Newer Older
Leonard Guetta's avatar
Leonard Guetta committed
1
\chapter{Yoga of \texorpdfstring{$\oo$}{\textomega}-categories}
Leonard Guetta's avatar
Leonard Guetta committed
2
\section{\texorpdfstring{$\oo$}{ω}-graphs, \texorpdfstring{$\oo$}{ω}-magmas and \texorpdfstring{$\oo$}{ω}-categories}
3
\begin{paragr}\label{paragr:defoograph}
Leonard Guetta's avatar
Leonard Guetta committed
4
  An \emph{$\oo$-graph} $X$ consists of an infinite sequence of sets $(X_n)_{n \in \mathbb{N}}$  together with maps 
5
 \[ \begin{tikzcd}
Leonard Guetta's avatar
Leonard Guetta committed
6
    X_{n} &\ar[l,"\src",shift left] \ar[l,"\trgt"',shift right] X_{n+1}
7
8
  \end{tikzcd}
  \]
Leonard Guetta's avatar
Leonard Guetta committed
9
  for every $n \in \mathbb{N}$, subject to the \emph{globular identities}:
10
11
12
  \begin{equation*}
  \left\{
  \begin{aligned}
13
14
    \src \circ \src &= \src \circ \trgt, \\
    \trgt \circ \trgt &= \trgt \circ \src.
15
16
17
  \end{aligned}
  \right.
  \end{equation*}
Leonard Guetta's avatar
Leonard Guetta committed
18
  Elements of $X_n$ are called \emph{$n$\nbd{}cells} or \emph{$n$\nbd{}arrows} or \emph{cells of dimension $n$}. For $n=0$, elements of $X_0$ are also called \emph{objects}. For $x$ an $n$\nbd{}cell with $n>0$, $\src(x)$ is the \emph{source} of $x$ and $\trgt(x)$ is the \emph{target} of $x$. We use the notation \[x : a \to b\] to say that $a$ is the source of $x$ and $b$ is the target of $x$.
19
20

  More generally, for $0\leq k <n$, we define maps $\src_k : X_n \to X_k$ and $\trgt_k : X_n \to X_k$ as
21
  \[
Leonard Guetta's avatar
Leonard Guetta committed
22
  \src_k = \underbrace{\src\circ \dots \circ \src}_{n-k \text{ times}}
23
24
  \]
  and
Leonard Guetta's avatar
Leonard Guetta committed
25
  \[
Leonard Guetta's avatar
Leonard Guetta committed
26
  \trgt_k = \underbrace{\trgt\circ \dots \circ \trgt}_{n-k \text{ times}}.
Leonard Guetta's avatar
Leonard Guetta committed
27
  \]
Leonard Guetta's avatar
Leonard Guetta committed
28
  For an $n$\nbd{}cell $x$, the $k$\nbd{}cells $\src_k(x)$ and $\trgt_k(x)$ are respectively the \emph{$k$\nbd{}source} and the \emph{$k$\nbd{}target} of $x$.
Leonard Guetta's avatar
Leonard Guetta committed
29

Leonard Guetta's avatar
Leonard Guetta committed
30
  Two $n$\nbd{}cells $x$ and $y$ are \emph{parallel} if
Leonard Guetta's avatar
Leonard Guetta committed
31
32
33
34
35
36
37
38
  \[
  n=0
  \]
  or
  \[
  n>0 \text{ and }\src(x)=\src(y) \text{ and } \trgt(x)=\trgt(y).
  \]

Leonard Guetta's avatar
Leonard Guetta committed
39
  Let $0 \leq k <n$. Two $n$\nbd{}cells $x$ and $y$ are \emph{$k$\nbd{}composable} if
Leonard Guetta's avatar
Leonard Guetta committed
40
41
42
  \[
  \src_k(x)=\trgt_k(y).
  \]
43
  Note that the expression \og $x$ and $y$ are $k$\nbd{}composable\fg{} is \emph{not} symmetric in $x$ and $y$ and we \emph{should} rather speak of a ``$k$\nbd{}composable pair $(x,y)$'', although we won't always do it. The set of pairs of $k$\nbd{}composable $n$\nbd{}cells is denoted by $X_n\underset{X_k}{\times}X_n$, and is characterized as the following fibred product
Leonard Guetta's avatar
Leonard Guetta committed
44
45
      \[
    \begin{tikzcd}
46
47
      X_n\underset{X_k}{\times}X_n \ar[r] \ar[dr,phantom,"\lrcorner", very near start] \ar[d] &X_n \ar[d,"\trgt_k"]\\
      X_n \ar[r,"\src_k"] & X_k.
Leonard Guetta's avatar
Leonard Guetta committed
48
49
      \end{tikzcd}
    \]
Leonard Guetta's avatar
Leonard Guetta committed
50
    A \emph{morphism of $\oo$-graphs} $f : X \to Y$ is a sequence $(f_n : X_n \to Y_n)_{n \in \mathbb{N}}$ of maps that is compatible with source and target, i.e.\ for every $n$\nbd{}cell $x$ of $X$ with $n >0$, we have
51
52
53
    \[
    f_{n-1}(\src(x))=\src(f_n(x)) \text{ and } f_{n-1}(\trgt(x))=\trgt(f_n(x)).
    \]
Leonard Guetta's avatar
Leonard Guetta committed
54
    For an $n$\nbd{}cell $x$ of $X$, we often write $f(x)$ instead of $f_n(x)$.
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

    The category of $\oo$-graphs and morphisms of $\oo$-graphs is denoted by $\oo\Grph$.
\end{paragr}
\begin{paragr}\label{paragr:defoomagma}
  An \emph{$\oo$-magma} consists of an $\oo$-graph $X$ together with maps
\begin{align*}
     1_{(\shortminus)}: X_n &\to X_{n+1}\\
    x &\mapsto 1_x
  \end{align*}
  for every $n\geq 0$, and maps
  \begin{align*}
   (\shortminus)\comp_k(\shortminus): X_n \underset{X_k}{\times}X_n &\to X_n\\
    (x,y)&\mapsto x\comp_k y
  \end{align*}
  for all $0 \leq k <n$, subject to the following axioms:
\begin{enumerate}[label=(\alph*)]
Leonard Guetta's avatar
Leonard Guetta committed
71
    \item For every $n\geq 0$ and every $n$\nbd{}cell $x$,
72
73
74
    \[
    \src(1_x)=\src(1_x)=x.
    \]
Leonard Guetta's avatar
Leonard Guetta committed
75
  \item For all  $0 \leq k< n$ and all $k$\nbd{}composable $n$\nbd{}cells $x$ and $y$,
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
    \[
    \src(x\comp_k y) =
    \begin{cases}
      \src(y) &\text{ when }k=n-1,\\
      \src(x)\comp_k \src(y) &\text{ otherwise,}
      \end{cases}
    \]
    and
        \[
    \trgt(x\comp_k y) =
    \begin{cases}
      \trgt(x) & \text{ when }k=n-1,\\
      \trgt(x)\comp_k \trgt(y) &\text{ otherwise.}
      \end{cases}
    \]

  \end{enumerate}
Leonard Guetta's avatar
Leonard Guetta committed
93
We will use the same letter to denote an $\oo$\nbd{}magma and its underlying $\oo$\nbd{}graph.
94

Leonard Guetta's avatar
dodo    
Leonard Guetta committed
95
For an $n$\nbd{}cell $x$, the $(n+1)$\nbd{}cell $1_{x}$ is referred to as the \emph{unit on $x$}. More generally, for all $0 \leq k < n$, we define maps $\1^n_{(\shortminus)} : C_k \to C_n$ as
96
97
98
\[
\1^{n}_{(\shortminus)} := \underbrace{1_{(\shortminus)} \circ \dots \circ 1_{(\shortminus)}}_{n-k \text{ times }} : C_k \to C_n.
\]
Leonard Guetta's avatar
Leonard Guetta committed
99
100
101
102
103
For a $k$\nbd{}cell $x$ and $n>k$, the $n$\nbd{}cell $\1^n_x$ is referred to as
the \emph{$n$\nbd{}dimensional unit on $x$}. For consistency, we also set
\[\1^k_x:=x\]
for every $k$\nbd{}cell $x$. An $n$\nbd{}cell that is a unit on a strictly
lower dimensional cell is sometimes referred to as a \emph{trivial $n$\nbd{}cell}.
104

Leonard Guetta's avatar
Leonard Guetta committed
105
For two $k$\nbd{}composable $n$\nbd{}cells $x$ and $y$, the $n$\nbd{}cell $x \comp_k y$ is referred to as the \emph{$k$\nbd{}composition} of $x$ and $y$.
106

Leonard Guetta's avatar
Leonard Guetta committed
107
More generally, we extend the notion of $k$\nbd{}composition for cells of different dimension in the following way. Let $x$ be an $n$\nbd{}cell, $y$ be an $m$-cell with $m \neq n$ and $k~<~\min\{m,n\}$. The cells $x$ and $y$ are \emph{$k$\nbd{}composable} if $\src_k(x)=\trgt_k(y)$, in which case we define the cell $x\comp_k y$ of dimension $\max\{m,n\}$ as
108
109
110
111
112
113
114
115
116
117
118
119
120
\[
x\comp_k y :=
\begin{cases}
  1^n_x \comp_k y &\text{ if } m<n\\
  x \comp_k 1^m_y  &\text{ if } m>n\\
  \end{cases}
\]
We also follow the convention that if $n<m$, then $\comp_n$ has priority over $\comp_m$. This means that 
\[
x\comp_n y \comp_m z = (x \comp_n y) \comp_m z \text{ and } x \comp_m y \comp_n z = x \comp_m (y \comp_n z)
\]
whenever these equations make sense.

Leonard Guetta's avatar
Leonard Guetta committed
121
A \emph{morphism of $\oo$\nbd{}magmas} $f : X \to Y$ is a morphism of underlying $\oo$\nbd{}graphs that is compatible with units and compositions, i.e.\ for every $n$\nbd{}cell $x$, we have 
122
123
124
    \[
    f(1_x)=1_{f(x)},
    \]
Leonard Guetta's avatar
Leonard Guetta committed
125
    and for every $k$\nbd{}composable $n$\nbd{}cells $x$ and $y$, we have
126
127
128
    \[
    f(x\comp_k y)= f(x) \comp_k f(y).
    \]
Leonard Guetta's avatar
Leonard Guetta committed
129
    We write $\oo\Mag$ for the category of $\oo$\nbd{}magmas and morphisms of $\oo$\nbd{}magmas.
130
131
132
133
\end{paragr}
\begin{paragr}\label{paragr:defoocat}
  An \emph{$\oo$-category} is an $\oo$-magma $X$ that satisfies the following axioms:
  \begin{description}
Leonard Guetta's avatar
Leonard Guetta committed
134
      \item[Units:] for all $k<n$, for every $n$\nbd{}cell $x$, we have
135
136
137
    \[
    \1^n_{\trgt_k(x)}\comp_k x =x= x \comp_k\1^n_{\src_k(x)},
    \]
Leonard Guetta's avatar
Leonard Guetta committed
138
    \item[Functoriality of units:] for all $k<n$ and for all $k$\nbd{}composable $n$\nbd{}cells $x$ and $y$, we have 
139
140
141
142
    \[
    1_{x\comp_k y}=1_{x}\comp_k 1_{y},
    \]

Leonard Guetta's avatar
Leonard Guetta committed
143
  \item[Associativity:] for all  $k<n$, for all $n$\nbd{}cells $x, y$ and $z$ such that $x$ and $y$ are $k$\nbd{}composable, and $y$ and $z$ are $k$\nbd{}composable, we have
144
145
146
    \[
    (x\comp_{k}y)\comp_{k}z=x\comp_k(y\comp_kz),
    \]
Leonard Guetta's avatar
Leonard Guetta committed
147
    \item[Exchange rule:] for all $k,l,n \in \mathbb{N}$ with $k<l<n$, for all $n$\nbd{}cells $x,x',y$ and $y'$  such that
148
149
    \begin{itemize}
    \item[-] $x$ and $y$ are $l$-composable, $x'$ and $y'$ are $l$-composable,
Leonard Guetta's avatar
Leonard Guetta committed
150
    \item[-] $x$ and $x'$ are $k$\nbd{}composable, $y$ and $y'$ are $k$\nbd{}composable,
151
152
153
    \end{itemize}
    we have
    \[
Leonard Guetta's avatar
Leonard Guetta committed
154
    (x \comp_k x')\comp_l (y \comp_k y')=(x \comp_l y)\comp_k (x' \comp_l y').
155
156
    \]
  \end{description}
Leonard Guetta's avatar
Leonard Guetta committed
157
  We will use the same letter to denote an $\oo$\nbd{}category and its underlying $\oo$\nbd{}magma. A \emph{morphism of $\oo$\nbd{}categories} (or \emph{$\oo$\nbd{}functor}) $f : X \to Y$ is simply a morphism of the underlying $\oo$\nbd{}magmas. We denote by $\oo\Cat$ the category of $\oo$\nbd{}categories and morphisms of $\oo$\nbd{}categories. This category is locally presentable.
Leonard Guetta's avatar
Leonard Guetta committed
158
\end{paragr}
159
\begin{paragr}\label{paragr:defncat}
Leonard Guetta's avatar
Leonard Guetta committed
160
161
162
163
164
165
  For $n \in \mathbb{N}$, the notions of \emph{$n$\nbd{}graph}, \emph{$n$\nbd{}magma} and
  \emph{$n$\nbd{}category} are defined as truncated version of $\oo$\nbd{}graph,
  $\oo$\nbd{}magma and $\oo$\nbd{}category in an obvious way. For example, a
  $0$-category is a set and a $1$-category is nothing but a usual (small)
  category. The category of $n$\nbd{}categories and morphisms of $n$\nbd{}categories (or
  $n$\nbd{}functors) is denoted by $n\Cat$. When $n=0$ and $n=1$, we almost always use the notation $\Set$ and $\Cat$ instead of $0\Cat$ and $1\Cat$.
166
167
168
169
170
171
172

  For every $n\geq 0$, there is a canonical functor
  \[
  \tau_{\leq n}^s : \oo\Cat \to n\Cat
  \]
  that simply discards all the cells of dimension strictly higher than $n$. This functor has a left adjoint
  \[
173
  \iota_n : n\Cat \to \oo\Cat,
174
  \]
Leonard Guetta's avatar
Leonard Guetta committed
175
  where for an $n$\nbd{}category $C$, the $\oo$\nbd{}category $\iota_n(C)$ has the same $k$\nbd{}cells as $C$ for $k\leq n$ and only unit cells in dimension strictly higher than $n$. This functor itself has a left adjoint
176
177
178
  \[
  \tau_{\leq n }^i : \oo\Cat \to n\Cat,
  \]
Leonard Guetta's avatar
Leonard Guetta committed
179
  where for an $\oo$\nbd{}category $C$, the $n$\nbd{}category $\tau_{\leq n}^i(C)$ has the same $k$\nbd{}cells as $C$ for $k < n$ and whose set of $n$\nbd{}cells is the quotient of $C_n$ under the equivalence relation $\sim$ generated by
180
181
182
183
184
  \[
  x \sim y \text{ if there exists } z \in C_{n+1} \text{ of the form } z : x \to y.
  \]
  The functor $\tau_{\leq n}^s$ also have a right adjoint
  \[
185
  \kappa_n : n\Cat \to \oo\Cat,
186
  \]
Leonard Guetta's avatar
Leonard Guetta committed
187
188
189
190
  where for an $n$\nbd{}category $C$, the $\oo$\nbd{}category $\kappa_n(C)$ has
  the same $k$\nbd{}cells as $C$ for $k \leq n$ and has exactly one
  $k$\nbd{}cell $x \to y$ for every pair of parallel $(k-1)$\nbd{}cells $(x,y)$
  for $k>n$.
191
192
193
  
  The sequence of adjunctions
  \[
Leonard Guetta's avatar
tpoto    
Leonard Guetta committed
194
   \tau^{i}_{\leq n} \dashv \iota_n \dashv \tau^s_{\leq n} \dashv \kappa_n
195
  \]
Leonard Guetta's avatar
Leonard Guetta committed
196
197
  is maximal in that $\kappa_n$ doesn't have a right adjoint and $\tau^{i}_{\leq
    n}$ doesn't have a left adjoint.
198
199
200

  The functors $\tau^{s}_{\leq n}$ and $\tau^{i}_{\leq n}$ are respectively referred to as the \emph{stupid truncation functor} and the \emph{intelligent truncation functor}.

Leonard Guetta's avatar
Leonard Guetta committed
201
202
203
  The functor $\iota_n$ is fully faithful and preserves both limits and
  colimits; in regards to these properties, we often identify $n\Cat$ with the
  essential image of $\iota_n$, which is the full subcategory of $\oo\Cat$
Leonard Guetta's avatar
Leonard Guetta committed
204
  spanned by the $\oo$\nbd{}categories whose $k$\nbd{}cells for $k >n$ are all units.
205
206
\end{paragr}
\begin{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
207
  For $n \geq 0$, we define the $n$\nbd{}skeleton functor $\sk_n : \oo\Cat \to \oo\Cat$ as
208
  \[
209
  \sk_n := \iota_n \circ \tau^{s}_{\leq n}.
210
  \]
Leonard Guetta's avatar
Leonard Guetta committed
211
212
  This functor preserves both limits and colimits. For an $\oo$\nbd{}category
  $C$, $\sk_n(C)$ is the sub-$\oo$\nbd{}category of $C$ generated by the
Leonard Guetta's avatar
Leonard Guetta committed
213
214
  $k$\nbd{}cells of $C$ with $k\leq n$ in an obvious sense. It is also
  convenient to define $\sk_{-1}(C)$ to be the empty $\oo$\nbd{}category
215
  \[
Leonard Guetta's avatar
Leonard Guetta committed
216
    \sk_{-1}(C)=\emptyset
217
  \]
Leonard Guetta's avatar
Leonard Guetta committed
218
219
  for every $\oo$\nbd{}category $C$. Note that the functor $\sk_{-1} : \oo\Cat
  \to \oo\Cat$ preserves colimits but does not preserve limits.
Leonard Guetta's avatar
Leonard Guetta committed
220
221
222
223
224
  The inclusion induces a canonical filtration
  \[
  \emptyset=\sk_{-1}(C) \hookrightarrow \sk_{0}(C) \hookrightarrow \sk_{1}(C) \hookrightarrow \cdots \hookrightarrow\sk_{n}(C) \hookrightarrow\cdots,
  \]
  and we leave the proof of the following lemma as an easy exercise for the reader.
225
226
\end{paragr}
\begin{lemma}\label{lemma:filtration}
Leonard Guetta's avatar
Leonard Guetta committed
227
  Let $C$ be an $\oo$\nbd{}category. The colimit of the canonical filtration
228
    \[
Leonard Guetta's avatar
Leonard Guetta committed
229
  \sk_{-1}(C) \hookrightarrow \sk_{0}(C) \hookrightarrow \sk_{1}(C) \hookrightarrow \cdots \hookrightarrow\sk_{n}(C) \hookrightarrow\cdots
230
  \]
Leonard Guetta's avatar
Leonard Guetta committed
231
  is $C$ and for $n \geq 0$ the universal arrow $\sk_{n}(C) \to C$ is given by the co-unit of the adjunction $\tau^{s}_{\leq n} \dashv \iota_n$.
232
\end{lemma}
Leonard Guetta's avatar
Leonard Guetta committed
233
\begin{paragr}\label{paragr:defglobe}
Leonard Guetta's avatar
Leonard Guetta committed
234
  For $n \in \mathbb{N}$, the \emph{$n$\nbd{}globe} $\sD_n$ is the $n$\nbd{}category that has:
Leonard Guetta's avatar
Leonard Guetta committed
235
  \begin{itemize}[label=-]
Leonard Guetta's avatar
Leonard Guetta committed
236
  \item exactly one non-trivial $n$\nbd{}cell, which we refer to as the \emph{principal $n$\nbd{}cell} of $\sD_n$, and which we denote by $e_n$,
Leonard Guetta's avatar
Leonard Guetta committed
237
  \item exactly two non-trivial $k$\nbd{}cells for every $k<n$; these $k$\nbd{}cells being parallel and given by the $k$\nbd{}source and the $k$\nbd{}target of $e_n$.
238
  \end{itemize}
Leonard Guetta's avatar
Leonard Guetta committed
239
  This completely describes the $n$\nbd{}category $\sD_n$ as no non-trivial composition can occur. Here are pictures in low dimension:
240
      \[
Leonard Guetta's avatar
Leonard Guetta committed
241
  \sD_0= \begin{tikzcd}\bullet,\end{tikzcd}
242
243
  \]
  \[
Leonard Guetta's avatar
Leonard Guetta committed
244
  \sD_1 = \begin{tikzcd} \bullet \ar[r] &\bullet, \end{tikzcd}
245
246
247
  \]
  \[
  \sD_2 = \begin{tikzcd}
Leonard Guetta's avatar
Leonard Guetta committed
248
249
    \bullet \ar[r,bend left=50,""{name = U,below}] \ar[r,bend right=50,""{name=D}]&\bullet, \ar[Rightarrow, from=U,to=D]
  \end{tikzcd}
250
251
252
  \]
    \[
    \sD_3 = \begin{tikzcd}
Leonard Guetta's avatar
Leonard Guetta committed
253
         \bullet \ar[r,bend left=50,""{name = U,below,near start},""{name = V,below,near end}] \ar[r,bend right=50,""{name=D,near start},""{name = E,near end}]&\bullet. \ar[Rightarrow, from=U,to=D, bend right,""{name= L,above}]\ar[Rightarrow, from=V,to=E, bend left,""{name= R,above}]
254
    \arrow[phantom,"\Rrightarrow",from=L,to=R]
Leonard Guetta's avatar
Leonard Guetta committed
255
  \end{tikzcd}
256
    \]
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
257
    For every $\oo$\nbd{}category $C$, the map
258
259
260
261
    \begin{align*}
      \Hom_{\oo\Cat}(\sD_n,C) &\to C_n \\
      F &\mapsto F(e_n)
    \end{align*}
Leonard Guetta's avatar
Leonard Guetta committed
262
    is a bijection natural in $C$. In other words, the $n$\nbd{}globe represents the functor
263
264
265
266
    \begin{align*}
      \oo\Cat &\to \Set\\
      C &\mapsto C_n.
    \end{align*}
Leonard Guetta's avatar
Leonard Guetta committed
267
    For an $n$\nbd{}cell $x$ of $C$, we denote by
268
269
270
    \[
    \langle x \rangle : \sD_n \to C
    \]
Leonard Guetta's avatar
Leonard Guetta committed
271
    the canonically associated $\oo$\nbd{}functor.
272
\end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
273
\begin{paragr}\label{paragr:inclusionsphereglobe}
Leonard Guetta's avatar
Leonard Guetta committed
274
  For $n \in \mathbb{N}$, the $n$\nbd{}sphere $\sS_n$ is the $n$\nbd{}category that has
Leonard Guetta's avatar
Leonard Guetta committed
275
  exactly two parallel non-trivial $k$\nbd{}cells for every $k\leq n$. In other words, we have
276
  \[
277
  \sS_{n}=\sk_n(\sD_{n+1}),
278
279
280
  \]
  and in particular, we have a canonical inclusion functor
  \[
281
  i_{n+1} : \sS_{n} \to \sD_{n+1}.
282
  \]
Leonard Guetta's avatar
Leonard Guetta committed
283
  It is also customary to define $\sS_{-1}$ to be the empty $\oo$\nbd{}category and $i_{-1}$ to be the unique $\oo$\nbd{}functor
284
285
286
  \[
  \emptyset \to \sD_0.
  \]
287
  Notice that for every $n\geq 0$, the following commutative square
288
289
  \[
  \begin{tikzcd}
290
291
292
    \sS_{n-1} \ar[r,"i_n"] \ar[d,"i_n"] & \sD_n \ar[d,"j_n^+"]\\
    \sD_n \ar[r,"j_n^-"'] & \sS_{n},
%    \ar[from=1-1,to=2-2,phantom,very near end,"\ulcorner"]
293
294
  \end{tikzcd}
  \]
295
  where we wrote $j_n^+$ (resp.\ $j_n^-$) for the morphism $\langle \trgt(e_{n+1}) \rangle : \sD_n \to \sS_n$ (resp.\ $\langle \src(e_{n+1}) \rangle : \sD_n \to \sS_n$), is cocartesian.
Leonard Guetta's avatar
Leonard Guetta committed
296
% The two anonymous arrows of the previous square are representing each one of the two parallel $n$\nbd{}cells of $\sS_n$.
297

Leonard Guetta's avatar
Leonard Guetta committed
298
  Here are some pictures of the $n$\nbd{}spheres in low dimension:
299
         \[
Leonard Guetta's avatar
Leonard Guetta committed
300
  \sS_0= \begin{tikzcd}\bullet & \bullet, \end{tikzcd}
301
302
  \]
  \[
Leonard Guetta's avatar
Leonard Guetta committed
303
  \sS_1 = \begin{tikzcd}     \bullet \ar[r,bend left=50,""{name = U,below}] \ar[r,bend right=50,""{name=D}]&\bullet,  \end{tikzcd}
304
305
306
  \]
  \[
  \sS_2 = \begin{tikzcd}
Leonard Guetta's avatar
Leonard Guetta committed
307
308
         \bullet \ar[r,bend left=50,""{name = U,below,near start},""{name = V,below,near end}] \ar[r,bend right=50,""{name=D,near start},""{name = E,near end}]&\bullet. \ar[Rightarrow, from=U,to=D, bend right,""{name= L,above}]\ar[Rightarrow, from=V,to=E, bend left,""{name= R,above}]
    \end{tikzcd}
309
310
  \]
  
Leonard Guetta's avatar
Leonard Guetta committed
311
  For an $\oo$\nbd{}category $C$ and $n\geq 0$, an $\oo$\nbd{}functor
312
313
314
  \[
  \sS_n \to C
  \]
Leonard Guetta's avatar
Leonard Guetta committed
315
  amounts to the data of two parallel $n$\nbd{}cells of $C$. In other words, $\sS_{n}$ represents the functor $\oo\Cat \to \Set$ that sends an $\oo$\nbd{}category to the set of its parallel $n$\nbd{}cells. For $(x,y)$ a pair of parallel $n$\nbd{}cells of $C$, we denote by
316
317
318
  \[
  \langle x,y \rangle : \sS_{n} \to C
  \]
Leonard Guetta's avatar
Leonard Guetta committed
319
  the canonically associated $\oo$\nbd{}functor. For example, the $\oo$\nbd{}functor $i_n$ is nothing but
320
  \[
321
  \langle \src(e_{n+1}),\trgt(e_{n+1}) \rangle : \sS_{n} \to \sD_{n+1}.
322
323
  \]
  \end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
324
\section{Free \texorpdfstring{$\oo$}{ω}-categories}
325
\begin{definition}\label{def:nbasis}
Leonard Guetta's avatar
Leonard Guetta committed
326
  Let $C$ be an $\oo$\nbd{}category and $n \geq 0$. A subset $E \subseteq C_n$ of the $n$\nbd{}cells of $C$ is an \emph{$n$\nbd{}basis of $C$} if the commutative square
327
328
  \[
  \begin{tikzcd}[column sep=huge, row sep=huge]
329
   \displaystyle \coprod_{ x \in E}\ar[d,"\displaystyle\coprod_{x \in E} i_n"'] \sS_{n-1} \ar[r,"{\langle \src(x),\trgt(x)\rangle_{x \in E}}"] & \sk_{n-1}(C) \ar[d,hook] \\
330
331
332
333
334
   \displaystyle \coprod_{x \in E} \sD_n \ar[r,"\langle x \rangle_{x \in E}"] & \sk_{n}(C) 
  \end{tikzcd}
  \]
  is cocartesian.
\end{definition}
Leonard Guetta's avatar
Leonard Guetta committed
335
336
\begin{remark}\label{remark:nbasisncat}
  Note that since for all $n<m$, we have $\sk_n \circ \sk_m = \sk_n$, an $\oo$\nbd{}category $C$ has an $n$\nbd{}basis if and only if $\sk_n(C)$ has an $n$\nbd{}basis. 
Leonard Guetta's avatar
Leonard Guetta committed
337
\end{remark}
338
\begin{paragr}\label{paragr:defnbasisdetailed}
Leonard Guetta's avatar
Leonard Guetta committed
339
340
341
  Let us unfold Definition \ref{def:nbasis}. For $n=0$, $E$ is an $0$\nbd{}basis
  of $C$ if $E=C_0$. For $n>0$,
  $E$ is $n$\nbd{}basis of $C$ if for every $n$\nbd{}category $D$, for every $(n-1)$-functor
342
  \[
343
  F : \tau_{\leq n-1}^{s}(C) \to \tau_{\leq n-1}^{s}(D),
344
  \]
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
345
  and for every map
346
347
348
349
350
351
352
  \[
  f : E \to D_n
  \]
  such that for every $x \in E$,
  \[
  \src(f(x))=F(\src(x)) \text{ and } \trgt(f(x))=F(\trgt(x)),
  \]
Leonard Guetta's avatar
Leonard Guetta committed
353
 there exists a \emph{unique} $n$\nbd{}functor
354
355
356
357
358
  \[
  \tilde{F} : \tau^{s}_{\leq n}(C) \to D
  \]
  such that $\tilde{F}_k = F_k$ for every $k<n$ and $\tilde{F}_n(x) = f(x)$ for every $x \in E$.

Leonard Guetta's avatar
Leonard Guetta committed
359
  Intuitively speaking, this means that $\sk_{n}(C)$ has been obtained from $\sk_{n-1}(C)$ by freely adjoining the cells in $E$.
360
\end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
361

Leonard Guetta's avatar
Leonard Guetta committed
362
363
364
% \begin{example}\label{zerobase}
%   Every $\oo$\nbd{}category $C$ has a $0$-basis which is $C_0$ itself. This is the unique $0$-base possible. 
%   \end{example}
365
\begin{example}\label{dummyexample}
Leonard Guetta's avatar
Leonard Guetta committed
366
  An $n$\nbd{}category (seen as an $\oo$\nbd{}category) always has a $k$\nbd{}basis for every $k>n$, namely the empty set.
367
\end{example}
Leonard Guetta's avatar
Leonard Guetta committed
368
 Less trivial examples will come along soon.
369
\begin{definition}\label{def:freeoocat}
Leonard Guetta's avatar
Leonard Guetta committed
370
  An $\oo$\nbd{}category is \emph{free}\footnote{Other common terminology for ``free $\oo$\nbd{}category'' is ``$\oo$\nbd{}category free on a polygraph'' \cite{burroni1993higher} or ``$\oo$\nbd{}category free on a computad'' \cite{street1976limits,makkai2005word}.} if it has $n$\nbd{}basis for every $n \geq 0$.
371
372
\end{definition}
\begin{paragr}\label{paragr:freencat}
Leonard Guetta's avatar
Leonard Guetta committed
373
  By considering $n\Cat$ as a subcategory of $\oo\Cat$, the previous definition also works for $n$\nbd{}categories. It follows from Example \ref{dummyexample} that an $n$\nbd{}category is free if and only if it has a $k$\nbd{}basis for every $0 \leq k \leq n$.
374
\end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
375
376
We now wish to recall an important result due to Makkai concerning the
uniqueness of the $n$\nbd{}basis for a free $\oo$\nbd{}category. First we need the following definition.
Leonard Guetta's avatar
Leonard Guetta committed
377
\begin{definition}\label{def:indecomposable}
Leonard Guetta's avatar
Leonard Guetta committed
378
  Let $C$ be an $\oo$\nbd{}category. For $n>0$, an $n$\nbd{}cell $x$ of $C$ is \emph{indecomposable} if both following conditions are satisfied:
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
  \begin{enumerate}[label=(\alph*)]
  \item $x$ is not a unit on a lower dimensional cell,
  \item if $x$ is of the form
    \[
    x=a\comp_k b
    \]
    with $k<n$, then either
    \[
    a=\1^n_{\trgt_k(x)},
    \]
    or
    \[
    b=\1^n_{\src_k(x)}.
    \]
  \end{enumerate}
  For $n=0$, all $0$-cells are, by convention, indecomposable.
\end{definition}
We can now state the promised result, whose proof can be found in \cite[Section 4, Proposition 8.3]{makkai2005word}.
\begin{proposition}[Makkai]\label{prop:uniquebasis}
Leonard Guetta's avatar
Leonard Guetta committed
398
  Let $C$ be a free $\oo$\nbd{}category. For every $n \in \mathbb{N}$, $C$ has a \emph{unique} $n$\nbd{}basis. The cells of this $n$\nbd{}basis are exactly the indecomposable $n$\nbd{}cells of $C$.
399
400
\end{proposition}
\begin{remark}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
401
  Note that there is a subtlety in the previous proposition. It is not true in general that if an $\oo$\nbd{}category $C$ has an $n$\nbd{}basis then it is unique. The point is that we need the existence of the $k$\nbd{}bases for $k<n$ in order to prove the uniqueness the $n$\nbd{}basis. (See the paper of Makkai cited previously for details.)
402
403
\end{remark}
\begin{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
404
  Proposition \ref{prop:uniquebasis} allows us to speak of \emph{the} $k$\nbd{}basis of a free $\oo$\nbd{}category $C$ and more generally of the \emph{basis} of $C$ for the sequence
405
406
407
  \[
  (\Sigma_k)_{k \in \mathbb{N}}
  \]
Leonard Guetta's avatar
Leonard Guetta committed
408
  where each $\Sigma_k$ is the $k$\nbd{}basis of $C$. In the case that $C$ is a free $n$\nbd{}category with $n$ finite and in light of Example \ref{dummyexample}, we will also speak of \emph{the basis of $C$} as the finite sequence
409
  \[
410
  (\Sigma_k)_{0 \leq k \leq n}.
411
  \]
412
  
Leonard Guetta's avatar
Leonard Guetta committed
413
  We often refer to the elements of the $n$\nbd{}basis of a free $\oo$\nbd{}category as the \emph{generating $n$\nbd{}cells}. This sometimes leads to use the alternative terminology \emph{set of generating $n$\nbd{}cells} instead of \emph{$n$\nbd{}basis}.      
414
\end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
415
\begin{definition}\label{def:rigidmorphism}
Leonard Guetta's avatar
Leonard Guetta committed
416
  Let $X$ and $Y$ be two free $\oo$\nbd{}categories. An $\oo$\nbd{}functor $f : X \to Y$ is \emph{rigid} if for every $n\geq 0$ and every generating $n$\nbd{}cell $x$ of $X$, $f(x)$ is a generating $n$\nbd{}cell of $Y$.
Leonard Guetta's avatar
Leonard Guetta committed
417
\end{definition}
Leonard Guetta's avatar
Leonard Guetta committed
418
419
420
So far, we have not yet seen examples of free $\oo$\nbd{}categories. In order to
do so, we will explain in a further section a recursive way of constructing free
$\oo$\nbd{}categories; but let us first take a little detour.
421

422
\section{Suspension of monoids and counting generators}\label{sec:suspmonoids}
423
\begin{paragr}\label{paragr:suspmonoid}
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
424
  Let $M$ be a monoid. For every $n >0$, let $B^{n}M$ be the $n$\nbd{}magma such that:
425
426
  \begin{itemize}[label=-]
  \item it has only one object $\star$,
Leonard Guetta's avatar
Leonard Guetta committed
427
428
    \item it has only one $k$\nbd{}cell for $0 < k <n$, which is $\1^k_{\star}$,
  \item the set of $n$\nbd{}cells is (the underlying set of) $M$,
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
429
  \item for every $k<n$, the $k$\nbd{}composition of $n$\nbd{}cells is given by the composition law of the monoid (which makes sense since all $n$\nbd{}cells are $k$\nbd{}composable) and the only unital $n$\nbd{}cell is given by the neutral element of the monoid.
430
431
432
  \end{itemize}
  It is sometimes useful to extend the above construction to the case $n=0$ by saying that $B^0M$ is the underlying set of the monoid $M$.
  
Leonard Guetta's avatar
Leonard Guetta committed
433
  For $n=1$, $B^1M$ is nothing but the monoid $M$ seen as $1$-category with one object.
434

Leonard Guetta's avatar
Leonard Guetta committed
435
  For $n>1$, while it is clear that all first three axioms of $n$\nbd{}category (units, functoriality of units and associativity) hold, it is not always true that the exchange rule is satisfied. If $\ast$ denotes the composition law of the monoid, this axiom states that for all $a,b,c,d \in M$, we must have
436
437
438
  \[
  (a \ast b) \ast (c \ast d) = (a \ast c ) \ast (b \ast d).
  \]
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
439
  It is straightforward to see that this equation holds if and only if $M$ is commutative. Hence, we have proved the following lemma.
440
441
442
\end{paragr}
\begin{lemma}
  Let $M$ be a monoid and $n \in \mathbb{N}$. Then:
Leonard Guetta's avatar
Leonard Guetta committed
443
  \begin{itemize}[label=-]
444
  \item if $n=1$, $B^1M$ is a $1$-category,
Leonard Guetta's avatar
Leonard Guetta committed
445
  \item if $n>1$, the $n$\nbd{}magma $B^nM$ is an $n$\nbd{}category if and only if $M$ is commutative.
446
447
    \end{itemize}
\end{lemma}
Leonard Guetta's avatar
Leonard Guetta committed
448
\iffalse\begin{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
449
  For $n=1$, the correspondence $M \mapsto B^nM$ obviously defines a functor
Leonard Guetta's avatar
Leonard Guetta committed
450
451
452
453
454
455
456
457
458
459
  \[
  B^n : \Mon \to n\Cat,
  \]
  where $\Mon$ is the category of monoids, sand for $n>1$, a functor
  \[
  B^n : \CMon \to n\Cat,
  \]
  where $\CMon$ is the category of commutative monoids. This functor is fully faithful and 
\end{paragr}
\begin{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
460
  For an integer $n\geq 1$ and a monoid $M$ (commutative if $n>1$), the $n$\nbd{}category $B^nM$ has the particular property of having exactly one $k$\nbd{}cell for each $k<n$ (which all are the iterated units on the only object of $B^nM$). As it happens, this property is sufficient enough to characterize $n$\nbd{}categories isomorphic to a $B^nM$ for some monoid $M$. This result will be a consequence of the famous ``Eckmann-Hilton argument''.
Leonard Guetta's avatar
Leonard Guetta committed
461
462
463
464
465
466
467
468
469
\end{paragr}
\begin{lemma}[Eckmann-Hilton argument]
  Let $(M,\times,1)$ and $(M,\ast,1)$ two monoid structures on the same set $M$ and with the same unit. Suppose that for every $a,b,c,d \in M$, the exchange rule holds:
  \[
  (a \times b) \ast (b \times c) = (a \ast c) \times (b \ast d).
  \]
  Then, the two operations $\ast$ and $\times$ are equal, and furthermore they are commutative.
\end{lemma}
\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
470
  This follows immediately from the sequence of equalities:
Leonard Guetta's avatar
Leonard Guetta committed
471
472
473
474
475
476
477
478
479
480
481
482
483
  \begin{align*}
    a\times b &= (a\ast 1) \times (1 \ast b)\\
    &= (a \times 1) \ast ( 1 \times b)\\
    &= a \ast b \\
    &= (1 \times a ) \ast (b \times 1)\\
    &=(1 \ast b) \times (a \ast 1)\\
    &= b \times a.\qedhere
    \end{align*}
\end{proof}
\begin{remark}
  It is not necessary to suppose in the previous lemma that the two units of the two monoid structures coincide, as it can be shown to be also a consequence of the exchange rule. The version we gave is nevertheless sufficient for our purpose.
\end{remark}
\begin{proposition}
Leonard Guetta's avatar
Leonard Guetta committed
484
  Let $n \geq 0$ and $C$ be an $n$\nbd{}category that has exactly one $k$\nbd{}cell for each $0 \leq k < n$. Then, there exists a monoid $M$ such that $C \simeq B^nM$. This monoid is unique up to a (non necessarily unique) isomorphism.  
Leonard Guetta's avatar
Leonard Guetta committed
485
486
\end{proposition}
\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
487
  For $n=1$, the existence is obvious since the data of $C$ itself is exactly that of a monoid. For $n>1$, this follows from the Eckmann-Hilton argument. The uniqueness comes from the fact that the functor 
Leonard Guetta's avatar
Leonard Guetta committed
488
489
\end{proof}
\fi
490
491
This construction will turn out to be of great use many times in this dissertation and we now explore a few of its properties.
\begin{lemma}\label{lemma:nfunctortomonoid}
Leonard Guetta's avatar
Leonard Guetta committed
492
  Let $C$ be an $n$\nbd{}category with $n\geq 1$ and let $M=(M,\ast,1)$ be a monoid (commutative if $n>1$). The map
493
494
495
496
497
498
  \begin{align*}
    \Hom_{n\Cat}(C,B^nM) &\to \Hom_{\Set}(C_n,M)\\
    F &\mapsto F_n
  \end{align*}
  is injective and its image consists exactly of those functions $f : C_n \to M$ such that:
  \begin{itemize}[label=-]
Leonard Guetta's avatar
Leonard Guetta committed
499
  \item for every $0 \leq k <n$ and every pair $(x,y)$ of $k$\nbd{}composable $n$\nbd{}cells of $C$, we have
500
501
502
503
504
505
506
507
508
509
    \[
    f(x\comp_ky)=f(x)\ast f(y),
    \]
  \item for every $x \in C_{n-1}$, we have
    \[
    f(1_x)=1.
    \]
    \end{itemize}
\end{lemma}
\begin{proof}
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
510
  The injectivity part follows from the fact that $(B^nM)_k$ is a singleton set for every $k<n$ and hence, an $n$\nbd{}functor $F : C \to B^nM$ is entirely determined by its restriction to the $n$\nbd{}cells $F_n : C_n \to M$.
511

Leonard Guetta's avatar
dodo    
Leonard Guetta committed
512
  The characterization of the image is immediate once noted that the requirements are only the reformulation of the axioms of $n$\nbd{}functors in this particular case.
513
514
\end{proof}
\begin{lemma}\label{lemma:freencattomonoid}
Leonard Guetta's avatar
Leonard Guetta committed
515
  Let $C$ be an $n$\nbd{}category with $n \geq 1$ and $M$ a monoid (commutative if $n>1$). If $C$ has $n$\nbd{}basis $E$, then the map
516
517
518
519
520
521
522
  \begin{align*}
    \Hom_{n\Cat}(C,B^nM) &\to \Hom_{\Set}(E,M)\\
    F &\mapsto F_n\vert_{E}
  \end{align*}
  is bijective.
\end{lemma}
\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
523
This is an immediate consequence of the universal property of an $n$\nbd{}basis (as explained in Paragraph \ref{paragr:defnbasisdetailed})
524
525
\end{proof}
We can now prove the important proposition below.
Leonard Guetta's avatar
Leonard Guetta committed
526
\begin{proposition}\label{prop:countingfunction}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
527
  Let $C$ be an $\oo$\nbd{}category and suppose that $C$ has an $n$\nbd{}basis $E$ with $n\geq 0$. For every $\alpha \in E$, there exists a unique function
528
529
530
  \[
  w_{\alpha} : C_n \to \mathbb{N}
  \]
Leonard Guetta's avatar
Leonard Guetta committed
531
  such that:
532
533
534
  \begin{enumerate}[label=(\alph*)]
  \item $w_{\alpha}(\alpha)=1$,
  \item $w_{\alpha}(\beta)=0$ for every $\beta \in E$ such that $\beta \neq \alpha$,
Leonard Guetta's avatar
Leonard Guetta committed
535
  \item for every $0 \leq k<n$ and every pair $(x,y)$ of $k$\nbd{}composable $n$\nbd{}cells of $C$, we have
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
    \[
    w_{\alpha}(x\comp_k y)=w_{\alpha}(x)+w_{\alpha}(y).
    \]
  \end{enumerate}
  \iffalse
Furthermore, this function satisfies the condition
  \begin{enumerate}[label=(\alph*),resume]
  \item If $n>0$, for every $x \in C_{n-1}$, we have
    \[
    w_{\alpha}(1_x)=0.
    \]
  \end{enumerate}
  \fi
\end{proposition}
\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
551
552
  Notice first that $C$ has an $n$\nbd{}basis if and only if $\sk_n(C)$ has an
  $n$\nbd{}basis (Remark \ref{remark:nbasisncat}). Hence we can suppose that $C$ is an $n$\nbd{}category.
553

Leonard Guetta's avatar
Leonard Guetta committed
554
  For $n=0$, conditions (c) is vacuous and the assertion is trivial.
555
556
557

  Now let $n>0$ and consider the monoid  $\mathbb{N}=(\mathbb{N},+,0)$. The existence of a function $C_n \to \mathbb{N}$ satisfying conditions (a) and (b) follows from Lemma \ref{lemma:freencattomonoid} and the fact that it satisfies (c) follows Lemma \ref{lemma:nfunctortomonoid}.

Leonard Guetta's avatar
Leonard Guetta committed
558
  For the uniqueness, notice that for every $x \in C_{n-1}$ we have $1_x =1_x\comp_{n-1} 1_x$ and thus condition (c) implies that  
559
560
561
  \[
  w_{\alpha}(1_x)=0.
  \]
Leonard Guetta's avatar
Leonard Guetta committed
562
  Hence, we can apply Lemma \ref{lemma:nfunctortomonoid} which shows that $w_{\alpha}$ necessarily comes from an $n$\nbd{}functor $C \to B^n\mathbb{N}$. Then, the uniqueness follows from conditions (a) and (b) and Lemma \ref{lemma:freencattomonoid}.
563
\end{proof}
Leonard Guetta's avatar
Leonard Guetta committed
564
\begin{paragr}\label{paragr:weight}
Leonard Guetta's avatar
Leonard Guetta committed
565
  Let $C$ be an $n$\nbd{}category with an $n$\nbd{}basis $E$. For an $n$\nbd{}cell $x$ of $C$,
Leonard Guetta's avatar
Leonard Guetta committed
566
  we refer to the integer $w_{\alpha}(x)$ as the \emph{weight of $\alpha$ in
Leonard Guetta's avatar
Leonard Guetta committed
567
568
    $x$}. The reason for such a name will become clearer after Remark
  \ref{remark:weightexplicitly} where we give an
Leonard Guetta's avatar
Leonard Guetta committed
569
  explicit construction of $w_{\alpha}$ as a function that ``counts the number
Leonard Guetta's avatar
Leonard Guetta committed
570
  of occurrences of $\alpha$ in an $n$\nbd{}cell''.
Leonard Guetta's avatar
Leonard Guetta committed
571
572
573
574
575
576

  
  For later reference, let us also highlight the fact that in the proof of the previous proposition, we have shown the important property that if $n>0$, then for $y \in C_{n-1}$, we have
  \[
  w_{\alpha}(1_y)=0.
  \]
Leonard Guetta's avatar
Leonard Guetta committed
577
  This implies that for $n>1$, there might be $n$\nbd{}cells $x$ such that
Leonard Guetta's avatar
Leonard Guetta committed
578
579
580
  \[
  x \neq \alpha \text{ and }w_{\alpha}(x)=1.
  \]
Leonard Guetta's avatar
Leonard Guetta committed
581
 Indeed, suppose that there exists a $k$\nbd{}cell $z$ with $0<k<n-1$ which is not a unit on a lower dimensional cell and such that $\trgt_{k-1}(z)=\src_{k-1}(\alpha)$, then we have
Leonard Guetta's avatar
Leonard Guetta committed
582
583
584
585
586
587
  \[
  w_{\alpha}(\alpha\comp_{k-1}\1^n_z)=w_{\alpha}(\alpha)+w_{\alpha}(\1^n_z)=1.
  \]
\end{paragr}


Leonard Guetta's avatar
Leonard Guetta committed
588
\section{Recursive construction of free \texorpdfstring{$\oo$}{ω}-categories}\label{section:freeoocataspolygraph}
Leonard Guetta's avatar
Leonard Guetta committed
589
\begin{definition}\label{def:cellularextension}
Leonard Guetta's avatar
Leonard Guetta committed
590
  Let $n \in \mathbb{N}$. A \emph{$n$\nbd{}cellular extension} consists of a quadruplet $\E=(C,\Sigma,\sigma,\tau)$ where:
Leonard Guetta's avatar
Leonard Guetta committed
591
  \begin{itemize}[label=-]
Leonard Guetta's avatar
Leonard Guetta committed
592
  \item $C$ is an $n$\nbd{}category,
Leonard Guetta's avatar
Leonard Guetta committed
593
  \item $\Sigma$ is a set, whose elements are referred to as the \emph{indeterminates} of $\E$,
Leonard Guetta's avatar
Leonard Guetta committed
594
    \item $\sigma$ and $\tau$ are maps $\Sigma \to C_n$ such that for every element $x \in \Sigma$, the $n$\nbd{}cells $\sigma(x)$ and $\tau(x)$ are parallel.
Leonard Guetta's avatar
Leonard Guetta committed
595
596
597
  \end{itemize}
\end{definition}
\begin{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
598
  If we are given an $n$\nbd{}category $C$, then we also say that an $n$\nbd{}cellular extension $\E$ is a \emph{cellular extension of $C$} if it is of the form $\E=(C,\Sigma,\sigma,\tau)$.
Leonard Guetta's avatar
break    
Leonard Guetta committed
599
  
Leonard Guetta's avatar
Leonard Guetta committed
600
  Intuitively speaking, the indeterminates are formal extra $(n+1)$\nbd{}cells attached to $C$ via $\sigma$ and $\tau$. For every $x \in \Sigma$, the $n$\nbd{}cells $\sigma(x)$ and $\tau(x)$ are understood respectively the source and target of $x$ (which makes sense since these two $n$\nbd{}cells are parallel). Consequently, we often adopt the notation
Leonard Guetta's avatar
Leonard Guetta committed
601
602
603
  \[
  x : a \to b
  \]
Leonard Guetta's avatar
Leonard Guetta committed
604
  for an indeterminate such that $\sigma(x)=a$ and $\tau(x)=b$.
Leonard Guetta's avatar
Leonard Guetta committed
605
606
  \end{paragr}
\begin{definition}
Leonard Guetta's avatar
Leonard Guetta committed
607
  Let $\E=(C,\Sigma,\sigma,\tau)$ and $\E'=(C',\Sigma',\sigma',\tau')$ be two $n$\nbd{}cellular extensions. A morphism of $n$\nbd{}cellular extensions $\E \to \E'$ consists of a pair $(F,\varphi)$ where:
Leonard Guetta's avatar
Leonard Guetta committed
608
  \begin{itemize}[label=-]
Leonard Guetta's avatar
Leonard Guetta committed
609
  \item F is an $n$\nbd{}functor $C \to C'$,
Leonard Guetta's avatar
Leonard Guetta committed
610
611
612
613
614
615
    \item $\varphi$ is a map $\Sigma \to \Sigma'$,
  \end{itemize}
  such that for every $x \in \Sigma$, we have
  \[
  \sigma'(\varphi(x))=F(\sigma(x)) \text{ and } \tau'(\varphi(x))=F(\tau(x)).
  \]
Leonard Guetta's avatar
Leonard Guetta committed
616
  \end{definition}
Leonard Guetta's avatar
Leonard Guetta committed
617
\begin{paragr}\label{paragr:freecext}
Leonard Guetta's avatar
Leonard Guetta committed
618
   For $n\geq 0$, we denote by $n\Cat^{+}$ the category of $n$\nbd{}cellular extensions and morphisms of $n$\nbd{}cellular extensions. Every $(n+1)$\nbd{}category $C$ canonically defines an $n$\nbd{}cellular extension $(\tau^s_{\leq n }(C),C_{n+1},\src,\trgt)$ where $\src,\trgt : C_{n+1} \to C_n$ are the source and target maps of $C$. This defines a functor
Leonard Guetta's avatar
Leonard Guetta committed
619
620
  \begin{align*}
    U_n : (n+1)\Cat &\to n\Cat^+\\
Leonard Guetta's avatar
break    
Leonard Guetta committed
621
    C &\mapsto (\tau^s_{\leq n }(C),C_{n+1},\src,\trgt).
Leonard Guetta's avatar
Leonard Guetta committed
622
  \end{align*}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
623
  On the other hand, every $n$\nbd{}cellular extension $\E=(D,\Sigma,\sigma,\tau)$ yields an $(n+1)$\nbd{}category $\E^*$ defined as the following amalgamated sum:
Leonard Guetta's avatar
Leonard Guetta committed
624
   \begin{equation}\label{squarefreecext}
Leonard Guetta's avatar
Leonard Guetta committed
625
  \begin{tikzcd}[column sep=huge, row sep=huge]
626
    \displaystyle\coprod_{x \in \Sigma}\sS_n \ar[d,"\displaystyle\coprod_{x \in \Sigma}i_{n+1}"']\ar[r,"{\langle \sigma(x),\tau(x)\rangle_{x \in \Sigma}}"] & D \ar[d] \\
Leonard Guetta's avatar
Leonard Guetta committed
627
    \displaystyle\coprod_{x \in \Sigma}\sD_{n+1}\ar[r]&\E^*.
Leonard Guetta's avatar
Leonard Guetta committed
628
    \ar[from=1-1,to=2-2,very near end,phantom,"\ulcorner"]
Leonard Guetta's avatar
Leonard Guetta committed
629
  \end{tikzcd}
Leonard Guetta's avatar
Leonard Guetta committed
630
  \end{equation}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
631
  This defines a functor
Leonard Guetta's avatar
Leonard Guetta committed
632
633
634
635
636
637
  \begin{align*}
    n\Cat^+ &\to (n+1)\Cat \\
    \E &\mapsto \E^*,
  \end{align*}
  which is easily checked to be left adjoint to $U_n$.

Leonard Guetta's avatar
dodo    
Leonard Guetta committed
638
   Now let $\phi : \coprod_{x \in \Sigma} \sD_{n} \to \E^*$ be the bottom map of square \eqref{squarefreecext}. It induces a canonical map
Leonard Guetta's avatar
Leonard Guetta committed
639
640
641
642
  \begin{align*}
    j: \Sigma &\to (\E^*)_{n+1}\\
    x &\mapsto \phi_x(e_{n+1}),
  \end{align*}
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
643
  where $e_{n+1}$ is the principal $(n+1)$\nbd{}cell of $\sD_{n+1}$ (\ref{paragr:defglobe}). Notice that this map is natural in that,  for every morphism of $n$\nbd{}cellular extensions
Leonard Guetta's avatar
Leonard Guetta committed
644
  \[G=(F,\varphi) : \E \to \E',\] the square
Leonard Guetta's avatar
Leonard Guetta committed
645
646
  \[
  \begin{tikzcd}
Leonard Guetta's avatar
Leonard Guetta committed
647
    \Sigma \ar[d,"j"] \ar[r,"\varphi"] & \Sigma' \ar[d,"j'"] \\
Leonard Guetta's avatar
Leonard Guetta committed
648
649
650
    (\E^*)_{n+1} \ar[r,"(G^*)_{n+1}"]&(\E'^*)_{n+1}
  \end{tikzcd}
  \]
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
651
  is commutative. Notice also that $j$ is compatible with source and target in the sense that for every $x \in \Sigma$, we have
Leonard Guetta's avatar
Leonard Guetta committed
652
653
654
655
656
  \[
  \src(j(x))=\sigma(x) \text{ and } \trgt(j(x))=\tau(x).
  \]
\end{paragr}
\begin{lemma}\label{lemma:basisfreecext}
Leonard Guetta's avatar
Leonard Guetta committed
657
  Let $\E=(C,\Sigma,\sigma,\tau)$ be an $n$\nbd{}cellular extension. The canonical map
Leonard Guetta's avatar
Leonard Guetta committed
658
659
660
661
662
  \[
   j: \Sigma \to (\E^*)_{n+1}
   \]
   is injective.
\end{lemma}
Leonard Guetta's avatar
Leonard Guetta committed
663
\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
664
   A thorough reading of the techniques used in the proofs of Lemma \ref{lemma:nfunctortomonoid}, Lemma \ref{lemma:freencattomonoid} and Proposition \ref{prop:countingfunction} shows that the universal property defining $\E^*$ as the amalgamated sum \eqref{squarefreecext} is sufficient enough to prove the existence, for each $x \in \Sigma$, of a function
Leonard Guetta's avatar
Leonard Guetta committed
665
666
667
  \[
  w_{x} : (\E^*)_{n+1} \to \mathbb{N}
  \]
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
668
  such that $w_{x}(j(x))=1$ and $w_{x}(j(y))=0$ for every $y \in \Sigma$ with $y\neq x$. In particular, this implies that $j$ is injective.
Leonard Guetta's avatar
Leonard Guetta committed
669
\end{proof}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
670
\begin{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
671
  In consequence of the previous lemma, we will often identify $\Sigma$ to a subset of $(\E^*)_{n+1}$. When we do so, it will \emph{always} be via the map $j$. This identification is compatible with source and target in the sense that the source (resp. target) of $x \in \Sigma$, seen as an $(n+1)$\nbd{}cell of $\E^*$, is exactly $\sigma(x)$ (resp. $\tau(x)$).
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
672
673
\end{paragr}
\iffalse
Leonard Guetta's avatar
Leonard Guetta committed
674
\begin{paragr}
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
675
  In particular, the previous lemma tells us that for every $n$\nbd{}cellular extension $\E=(C,\Sigma,\sigma,\tau)$, the set of indeterminates $\Sigma$ canonically defines a subset of the $(n+1)$\nbd{}cells of $\E^*$. As of now, we will consider $\Sigma$ as a subset of $(\E^{*})_{n+1}$ and $j$ as the canonical inclusion. 
Leonard Guetta's avatar
Leonard Guetta committed
676
\end{paragr}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
677
\fi
Leonard Guetta's avatar
Leonard Guetta committed
678
679
We can now prove the following proposition, which is the key result of this section. It is slightly less trivial than it appears.
\begin{proposition}\label{prop:fromcexttocat}
Leonard Guetta's avatar
OUF    
Leonard Guetta committed
680
  For  every $n$\nbd{}cellular extension $\E=(C,\Sigma,\sigma,\tau)$, the subset $\Sigma \subseteq (\E^{*})_{n+1}$ is an $(n+1)$\nbd{}basis of $\E^*$.
Leonard Guetta's avatar
Leonard Guetta committed
681
682
683
  \end{proposition}

\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
684
685
686
687
  Notice first that since the map $i_{n+1} : \sS_n \to \sD_{n+1}$ is nothing but
  the canonical inclusion $\sk_{n}(\sD_{n+1}) \to
  \sk_{n+1}(\sD_{n+1})=\sD_{n+1}$, it follows easily from square
  \eqref{squarefreecext} and the fact that the skeleton functors preserve colimits, that $C$ is canonically isomorphic to $\sk_n(\E^*)$ and that the map $C \to \E^*$ can be identified with the canonical inclusion $\sk_n(\E^*) \to \sk_{n+1}(\E^*)=\E^*$. Hence, cocartesian square \eqref{squarefreecext} can be identified with
Leonard Guetta's avatar
Leonard Guetta committed
688
689
    \[
  \begin{tikzcd}[column sep=huge, row sep=huge]
690
    \displaystyle\coprod_{x \in \Sigma}\sS_n \ar[d,"\displaystyle\coprod_{x \in \Sigma}i_{n+1}"']\ar[r,"{\langle \src(x),\trgt(x)\rangle_{x \in \Sigma}}"] & \sk_{n}(\E^*) \ar[d,hook] \\
Leonard Guetta's avatar
Leonard Guetta committed
691
    \displaystyle\coprod_{x \in \Sigma}\sD_{n+1}\ar[r]&\sk_{n+1}(\E^*).
Leonard Guetta's avatar
Leonard Guetta committed
692
693
694
    \ar[from=1-1,to=2-2,very near end,phantom,"\ulcorner"]
  \end{tikzcd}
  \]
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
695
  Since we have identified $\Sigma$ to a subset of the $n$\nbd{}cells of $\E^*$ via $j$, the above cocartesian square means exactly that $\Sigma$ is an $(n+1)$\nbd{}basis of $\E^*$. 
Leonard Guetta's avatar
Leonard Guetta committed
696
\end{proof}
697
\begin{paragr}\label{paragr:cextfromsubset}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
698
  Let $C$ be an $(n+1)$\nbd{}category and $E$ be a subset $E \subseteq C_{n+1}$. This defines an $n$\nbd{}cellular extension
Leonard Guetta's avatar
Leonard Guetta committed
699
700
701
  \[
  \E_E =(\tau_{\leq n}^s(C),E,\src,\trgt),
  \]
Leonard Guetta's avatar
Leonard Guetta committed
702
  where $\src$ and $\trgt$ are simply the restriction to $E$ of the source and target maps $C_{n+1} \to C_n$. The canonical inclusion $E \hookrightarrow C_{n+1}$ induces a morphism of $n$\nbd{}cellular extensions
Leonard Guetta's avatar
Leonard Guetta committed
703
704
705
  \[
  \E_E \to U_n(C),
  \]
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
706
  and then, by adjunction, an $(n+1)$\nbd{}functor
Leonard Guetta's avatar
Leonard Guetta committed
707
708
709
710
  \[
  \E_E^* \to C.
  \]
\end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
711
\begin{proposition}\label{prop:criterionnbasis}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
712
  Let $C$ be an $(n+1)$\nbd{}category. A subset $E \subseteq C_{n+1}$ is an $(n+1)$\nbd{}basis of $C$ if and only if the canonical $(n+1)$\nbd{}functor
Leonard Guetta's avatar
Leonard Guetta committed
713
714
715
716
  \[
  \E_E^* \to C
  \]
  is an isomorphism. 
Leonard Guetta's avatar
break    
Leonard Guetta committed
717
718
\end{proposition}
\begin{proof}
Leonard Guetta's avatar
dodo    
Leonard Guetta committed
719
  It is clear that the canonical $(n+1)$\nbd{}functor $\E^*_E \to C$ sends $E$, seen as a subset of $(\E^*_E)_{n+1}$, to $E$, seen as a subset of $C_{n+1}$. Hence, it follows from Proposition \ref{prop:fromcexttocat} that if this $(n+1)$\nbd{}functor is an isomorphism, then $E$ is an $(n+1)$\nbd{}base of $C$.
Leonard Guetta's avatar
break    
Leonard Guetta committed
720

Leonard Guetta's avatar
Leonard Guetta committed
721
  Conversely, if $E$ is an $(n+1)$\nbd{}base of $C$, then we can define an $(n+1)$\nbd{}functor $C \to \E_E^*$ that sends $E$, seen as a subset of $C_{n+1}$, to $E$, seen as a subset of $(\E^*_E)_{n+1}$ (and which is obviously the identity on cells of dimension strictly lower than $n+1$). The fact that $C$ and $\E^*$ have $E$ as an $(n+1)$\nbd{}base implies that this $(n+1)$\nbd{}functor $C \to \E^*$ is the inverse of the canonical one $\E^* \to C$.
Leonard Guetta's avatar
break    
Leonard Guetta committed
722
\end{proof}
Leonard Guetta's avatar
Leonard Guetta committed
723
724
725
\begin{paragr}
  We extend the definitions and results from \ref{def:cellularextension} to \ref{prop:criterionnbasis} to the case $n=-1$ by saying that a $(-1)$-cellular extension is simply a set $\Sigma$ (which is the set the indeterminates) and $(-1)\Cat^+$ is the category of sets. Since a $0\Cat$ is also the category of sets, it makes sense to define the functors
  \[
Leonard Guetta's avatar
Leonard Guetta committed
726
  U_{-1} : 0\Cat \to (-1)\Cat^+
Leonard Guetta's avatar
Leonard Guetta committed
727
728
729
730
731
  \]
  and
  \[
  (-)^* : (-1)\Cat^+ \to 0\Cat
  \]
Leonard Guetta's avatar
Leonard Guetta committed
732
  to be both the identity functor on $\Set$. 
Leonard Guetta's avatar
Leonard Guetta committed
733
\end{paragr}
Leonard Guetta's avatar
Leonard Guetta committed
734
735
\begin{proposition}\label{prop:freeonpolygraph}
  Let $(\E^{(n)})_{n \geq -1}$ be a sequence where:
Leonard Guetta's avatar
Leonard Guetta committed
736
  \begin{itemize}[label=-]
Leonard Guetta's avatar
Leonard Guetta committed
737
  \item $\E^{(-1)}$ is a $(-1)$-cellular extension,
Leonard Guetta's avatar
Leonard Guetta committed
738
    \item for every $n\geq 0$, $\E^{(n)}$ is a cellular extension of the $n$\nbd{}category $(\E^{(n-1)})^*$.
Leonard Guetta's avatar
break    
Leonard Guetta committed
739
  \end{itemize}
Leonard Guetta's avatar
Leonard Guetta committed
740
  Then, the $\oo$\nbd{}category defined as the colimit of the canonical diagram
Leonard Guetta's avatar
Leonard Guetta committed
741
742
743
  \[
  (\E^{(-1)})^* \to (\E^{(0)})^* \to \cdots \to (\E^{(n)})^* \to \cdots
  \]
Leonard Guetta's avatar
Leonard Guetta committed
744
  is free and for every $n \in \mathbb{N}$, its $n$\nbd{}basis is (canonically isomorphic to) the set of indeterminates of $\E^{(n+1)}$.
Leonard Guetta's avatar
Leonard Guetta committed
745

Leonard Guetta's avatar
Leonard Guetta committed
746
  Moreover, suppose we are given another sequence $(\E'^{(n)})_{n\geq -1}$ as above and a sequence 
Leonard Guetta's avatar
Leonard Guetta committed
747
748
749
  \[
  (G^{(n)}=(F^{(n)},\varphi^{(n)}) : \E^{(n)} \to \E'^{(n)})_{n \geq -1}
  \]
Leonard Guetta's avatar
Leonard Guetta committed
750
  where each $G^{(n)}$ is a morphism of $n$\nbd{}cellular extensions such that for every $n \geq 0$
Leonard Guetta's avatar
break    
Leonard Guetta committed
751
  \[
Leonard Guetta's avatar
Leonard Guetta committed
752
  F^{(n)}=(G^{(n-1)})^*.
Leonard Guetta's avatar
break    
Leonard Guetta committed
753
  \]
Leonard Guetta's avatar
Leonard Guetta committed
754
  Then, the $\oo$\nbd{}functor
Leonard Guetta's avatar
Leonard Guetta committed
755
756
757
758
759
  \[
  \colim_{n\geq -1 }(\E^{(n)})^* \to \colim_{n\geq -1 }(\E'^{(n)})^*
  \]
  induced by colimit is rigid.
  
Leonard Guetta's avatar
Leonard Guetta committed
760
  Conversely, every free $\oo$\nbd{}category and every rigid $\oo$\nbd{}functor arise this way.
Leonard Guetta's avatar
break    
Leonard Guetta committed
761
\end{proposition}
Leonard Guetta's avatar
Leonard Guetta committed
762
\begin{proof}
Leonard Guetta's avatar
Leonard Guetta committed
763
764
765
766
767
  From the first part Proposition \ref{prop:fromcexttocat} we know that every
  $(\E^{(n)})^*$ has an $(n+1)$\nbd{}basis, which is canonically isomorphic to
  the set of indeterminates of $\E^{(n)}$. Besides, since for every $n\geq 0$,
  $\E^{(n)}$ is a cellular extension of $(\E^{(n-1)})^*$, we have
  $\sk_{n-1}((\E^{(n)})^*)=(\E^{(n-1)})^*$ by definition. Hence, by a straightforward induction, each $\E^{(n)}$ is a free $(n+1)$\nbd{}category and its $k$\nbd{}basis for $0 \leq k \leq n+1$ is (canonically isomorphic to) the set of indeterminates of $\E^{(k-1)}$.
Leonard Guetta's avatar
Leonard Guetta committed
768
769
770
771
  Now let $C :=\colim_{n \geq -1}(\E^{(n)})^*$. Since for every $k\geq 0$, $\sk_k$ preserves colimits and since $\sk_k((\E^{(n)})^*)=(\E^{(k-1)})^*$ for all $0\leq k <n$, we have that
  \[
  \sk_k(C)=(\E^{(k-1)})^*
  \]
Leonard Guetta's avatar
Leonard Guetta committed
772
  for every $k \geq 0$. Altogether, this proves that $C$ is free and its $k$\nbd{}basis is the set of indeterminates of $\E^{(k-1)}$ for every $k \geq 0$.
Leonard Guetta's avatar
Leonard Guetta committed
773

Leonard Guetta's avatar
Leonard Guetta committed
774
  The fact that a sequence of morphisms of cellular extensions that satisfy the hypothesis given in the statement of the proposition induces a rigid $\oo$\nbd{}functor is proven in a similar fashion.
Leonard Guetta's avatar
Leonard Guetta committed
775
  
Leonard Guetta's avatar
Leonard Guetta committed
776
  For the converse part, notice that a free $\oo$\nbd{}category $C$, whose basis is denoted by $(\Sigma_k)_{k \in \mathbb{N}}$, induces a sequence of cellular extensions:
Leonard Guetta's avatar
Leonard Guetta committed
777
778
779
780
781
782
783
  \[
  \E_C^{(-1)}:=\Sigma_0
  \]
  and
  \[
  \E_C^{(n)}:=(\sk_n(C),\Sigma_{n+1},\src,\trgt) \text{ for } n\geq 0.
  \]
Leonard Guetta's avatar
Leonard Guetta committed
784
  It follows from Proposition \ref{prop:criterionnbasis} that $\sk_n(C)\simeq (\E_C^{(n-1)})^*$ and, then, from Lemma \ref{lemma:filtration} that $C \simeq \colim_{n \geq -1}\E_C^{(n)}$.
Leonard Guetta's avatar
Leonard Guetta committed
785

Leonard Guetta's avatar
OUF    
Leonard Guetta committed
786
  Finally, notice that the construction $C \mapsto (\E_C^{(n)})_{n \geq -1}$ described above is obviously functorial with respect to rigid $\oo$\nbd{}functors and the isomorphism $\sk_n(C)\simeq (\E_C^{(n)})^*$ is natural with respect to rigid $\oo$\nbd{}functors. Since the statement of Lemma \ref{lemma:filtration} is also natural in $C$, this easily implies that every rigid $\oo$\nbd{}functor arises as the colimit of sequence of morphisms of cellular extensions as described in the statement of the proposition.
Leonard Guetta's avatar
Leonard Guetta committed
787
\end{proof}
Leonard Guetta's avatar
Leonard Guetta committed
788
\begin{remark}
Leonard Guetta's avatar