-
Notifications
You must be signed in to change notification settings - Fork 356
/
hits.tex
2192 lines (1930 loc) · 131 KB
/
hits.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\chapter{Higher inductive types}
\label{cha:hits}
\index{type!higher inductive|(}%
\indexsee{inductive!type!higher}{type, higher inductive}%
\indexsee{higher inductive type}{type, higher inductive}%
\section{Introduction}
\label{sec:intro-hits}
\index{generation!of a type, inductive|(}
Like the general inductive types we discussed in \cref{cha:induction}, \emph{higher inductive types} are a general schema for defining new types generated by some constructors.
But unlike ordinary inductive types, in defining a higher inductive type we may have ``constructors'' which generate not only \emph{points} of that type, but also \emph{paths} and higher paths in that type.
\index{type!circle}%
\indexsee{circle type}{type,circle}%
For instance, we can consider the higher inductive type $\Sn^1$ generated by
\begin{itemize}
\item A point $\base:\Sn^1$, and
\item A path $\lloop : {\id[\Sn^1]\base\base}$.
\end{itemize}
This should be regarded as entirely analogous to the definition of, for instance, $\bool$, as being generated by
\begin{itemize}
\item A point $\bfalse:\bool$ and
\item A point $\btrue:\bool$,
\end{itemize}
or the definition of $\nat$ as generated by
\begin{itemize}
\item A point $0:\nat$ and
\item A function $\suc:\nat\to\nat$.
\end{itemize}
When we think of types as higher groupoids, the more general notion of ``generation'' is very natural:
since a higher groupoid is a ``multi-sorted object'' with paths and higher paths as well as points, we should allow ``generators'' in all dimensions.
We will refer to the ordinary sort of constructors (such as $\base$) as \define{point constructors}
\indexdef{constructor!point}%
\indexdef{point!constructor}%
or \emph{ordinary constructors}, and to the others (such as $\lloop$) as \define{path constructors}
\indexdef{constructor!path}%
\indexdef{path!constructor}%
or \emph{higher constructors}.
Each path constructor must specify the starting and ending point of the path, which we call its \define{source}
\indexdef{source!of a path constructor}%
and \define{target};
\indexdef{target!of a path constructor}%
for $\lloop$, both source and target are $\base$.
Note that a path constructor such as $\lloop$ generates a \emph{new} inhabitant of an identity type, which is not (at least, not \emph{a priori}) equal to any previously existing such inhabitant.
In particular, $\lloop$ is not \emph{a priori} equal to $\refl{\base}$ (although proving that they are definitely unequal takes a little thought; see \cref{thm:loop-nontrivial}).
This is what distinguishes $\Sn^1$ from the ordinary inductive type \unit.
There are some important points to be made regarding this generalization.
\index{free!generation of an inductive type}%
First of all, the word ``generation'' should be taken seriously, in the same sense that a group can be freely generated by some set.
In particular, because a higher groupoid comes with \emph{operations} on paths and higher paths, when such an object is ``generated'' by certain constructors, the operations create more paths that do not come directly from the constructors themselves.
For instance, in the higher inductive type $\Sn^1$, the constructor $\lloop$ is not the only nontrivial path from $\base$ to $\base$; we have also ``$\lloop\ct\lloop$'' and ``$\lloop\ct\lloop\ct\lloop$'' and so on, as well as $\opp{\lloop}$, etc., all of which are different.
This may seem so obvious as to be not worth mentioning, but it is a departure from the behavior of ``ordinary'' inductive types, where one can expect to see nothing in the inductive type except what was ``put in'' directly by the constructors.
Secondly, this generation is really \emph{free} generation: higher inductive types do not technically allow us to impose ``axioms'', such as forcing ``$\lloop\ct\lloop$'' to equal $\refl{\base}$.
However, in the world of $\infty$-groupoids,%
\index{.infinity-groupoid@$\infty$-groupoid}
there is little difference between ``free generation'' and ``presentation'',
\index{presentation!of an infinity-groupoid@of an $\infty$-groupoid}%
\index{generation!of an infinity-groupoid@of an $\infty$-groupoid}%
since we can make two paths equal \emph{up to homotopy} by adding a new 2-di\-men\-sion\-al generator relating them (e.g.\ a path $\lloop\ct\lloop = \refl{\base}$ in $\base=\base$).
We do then, of course, have to worry about whether this new generator should satisfy its own ``axioms'', and so on, but in principle any ``presentation'' can be transformed into a ``free'' one by making axioms into constructors.
As we will see, by adding ``truncation constructors'' we can use higher inductive types to express classical notions such as group presentations as well.
Thirdly, even though a higher inductive type contains ``constructors'' which generate \emph{paths in} that type, it is still an inductive definition of a \emph{single} type.
In particular, as we will see, it is the higher inductive type itself which is given a universal property (expressed, as usual, by an induction principle), and \emph{not} its identity types.
The identity type of a higher inductive type retains the usual induction principle of any identity type (i.e.\ path induction), and does not acquire any new induction principle.
Thus, it may be nontrivial to identify the identity types of a higher inductive type in a concrete way, in contrast to how in \cref{cha:basics} we were able to give explicit descriptions of the behavior of identity types under all the traditional type forming operations.
For instance, are there any paths from $\base$ to $\base$ in $\Sn^1$ which are not simply composites of copies of $\lloop$ and its inverse?
Intuitively, it seems that the answer should be no (and it is), but proving this is not trivial.
Indeed, such questions bring us rapidly to problems such as calculating the homotopy groups of spheres, a long-standing problem in algebraic topology for which no simple formula is known.
Homotopy type theory brings a new and powerful viewpoint to bear on such questions, but it also requires type theory to become as complex as the answers to these questions.
\index{dimension!of path constructors}%
Fourthly, the ``dimension'' of the constructors (i.e.\ whether they output points, paths, paths between paths, etc.)\ does not have a direct connection to which dimensions the resulting type has nontrivial homotopy in.
As a simple example, if an inductive type $B$ has a constructor of type $A\to B$, then any paths and higher paths in $A$ result in paths and higher paths in $B$, even though the constructor is not a ``higher'' constructor at all.
The same thing happens with higher constructors too: having a constructor of type $A\to (\id[B]xy)$ means not only that points of $A$ yield paths from $x$ to $y$ in $B$, but that paths in $A$ yield paths between these paths, and so on.
As we will see, this possibility is responsible for much of the power of higher inductive types.
On the other hand, it is even possible for constructors \emph{without} higher types in their inputs to generate ``unexpected'' higher paths.
For instance, in the 2-dimensional sphere $\Sn^2$ generated by
\symlabel{s2a}
\index{type!2-sphere}%
\begin{itemize}
\item A point $\base:\Sn^2$, and
\item A 2-dimensional path $\surf:\refl{\base} = \refl{\base}$ in ${\base=\base}$,
\end{itemize}
there is a nontrivial \emph{3-dimensional path} from $\refl{\refl{\base}}$ to itself.
Topologists will recognize this path as an incarnation of the \emph{Hopf fibration}.
From a category-theoretic point of view, this is the same sort of phenomenon as the fact mentioned above that $\Sn^1$ contains not only $\lloop$ but also $\lloop\ct\lloop$ and so on: it's just that in a \emph{higher} groupoid, there are \emph{operations} which raise dimension.
Indeed, we saw many of these operations back in \cref{sec:equality}: the associativity and unit laws are not just properties, but operations, whose inputs are 1-paths and whose outputs are 2-paths.
\index{generation!of a type, inductive|)}%
% In US Trade format it wants a page break here but then it stretches the above itemize,
% so we give it some stretchable space to use if it wants to.
\vspace*{0pt plus 20ex}
\section{Induction principles and dependent paths}
\label{sec:dependent-paths}
When we describe a higher inductive type such as the circle as being generated by certain constructors, we have to explain what this means by giving rules analogous to those for the basic type constructors from \cref{cha:typetheory}.
The constructors themselves give the \emph{introduction} rules, but it requires a bit more thought to explain the \emph{elimination} rules, i.e.\ the induction and recursion principles.
In this book we do not attempt to give a general formulation of what constitutes a ``higher inductive definition'' and how to extract the elimination rule from such a definition --- indeed, this is a subtle question and the subject of current research.
Instead we will rely on some general informal discussion and numerous examples.
\index{type!circle}%
\index{recursion principle!for S1@for $\Sn^1$}%
The recursion principle is usually easy to describe: given any type equipped with the same structure with which the constructors equip the higher inductive type in question, there is a function which maps the constructors to that structure.
For instance, in the case of $\Sn^1$, the recursion principle says that given any type $B$ equipped with a point $b:B$ and a path $\ell:b=b$, there is a function $f:\Sn^1\to B$ such that $f(\base)=b$ and $\apfunc f (\lloop) = \ell$.
\index{computation rule!for S1@for $\Sn^1$}%
\index{equality!definitional}%
The latter two equalities are the \emph{computation rules}.
\index{computation rule!for higher inductive types|(}%
\index{computation rule!propositional|(}%
There is, however, a question of whether these computation rules are judgmental\index{judgmental equality} equalities or propositional equalities (paths).
For ordinary inductive types, we had no qualms about making them judgmental, although we saw in \cref{cha:induction} that making them propositional would still yield the same type up to equivalence.
In the ordinary case, one may argue that the computation rules are really \emph{definitional} equalities, in the intuitive sense described in the Introduction.
\index{equality!judgmental}%
For higher inductive types, this is less clear. %, and it is likewise less clear to what extent these equalities can be made judgmental in the known set-theoretic models.
Moreover, since the operation $\apfunc f$ is not really a fundamental part of the type theory, but something that we \emph{defined} using the induction principle of identity types (and which we might have defined in some other, equivalent, way), it seems inappropriate to refer to it explicitly in a \emph{judgmental} equality.
Judgmental equalities are part of the deductive system, which should not depend on particular choices of definitions that we may make \emph{within} that system.
There are also semantic and implementation issues to consider; see the Notes.
It does seem unproblematic to make the computational rules for the \emph{point} constructors of a higher inductive type judgmental.
In the example above, this means we have $f(\base)\jdeq b$, judgmentally.
This choice facilitates a computational view of higher inductive types.
Moreover, it also greatly simplifies our lives, since otherwise the second computation rule $\apfunc f (\lloop) = \ell$ would not even be well-typed as a propositional equality; we would have to compose one side or the other with the specified identification of $f(\base)$ with $b$.
(Such problems do arise eventually, of course, when we come to talk about paths of higher dimension, but that will not be of great concern to us here.
See also \cref{sec:hubs-spokes}.)
Thus, we take the computation rules for point constructors to be judgmental, and those for paths and higher paths to be propositional.%
\footnote{In particular, in the language of \cref{sec:types-vs-sets}, this means that our higher inductive types are a mix of \emph{rules} (specifying how we can introduce such types and their elements, their induction principle, and their computation rules for point constructors) and \emph{axioms} (the computation rules for path constructors, which assert that certain identity types are inhabited by otherwise unspecified terms).
We may hope that eventually, there will be a better type theory in which higher inductive types, like univalence, will be presented using only rules and no axioms.%
\indexfoot{axiom!versus rules}%
\indexfoot{rule!versus axioms}%
}
\begin{rmk}\label{rmk:defid}
Recall that for ordinary inductive types, we regard the computation rules for a recursively defined function as not merely judgmental equalities, but \emph{definitional} ones, and thus we may use the notation $\defeq$ for them.
For instance, the truncated predecessor\index{predecessor!function, truncated} function $p:\nat\to\nat$ is defined by $p(0)\defeq 0$ and $p(\suc(n))\defeq n$.
In the case of higher inductive types, this sort of notation is reasonable for the point constructors (e.g.\ $f(\base)\defeq b$), but for the path constructors it could be misleading, since equalities such as $\ap f \lloop = \ell$ are not judgmental.
Thus, we hybridize the notations, writing instead $\ap f \lloop \defid \ell$ for this sort of ``propositional equality by definition''.
\end{rmk}
\index{computation rule!for higher inductive types|)}%
\index{computation rule!propositional|)}%
\index{type!circle|(}%
\index{induction principle!for S1@for $\Sn^1$}%
Now, what about the induction principle (the dependent eliminator)?
Recall that for an ordinary inductive type $W$, to prove by induction that $\prd{x:W} P(x)$, we must specify, for each constructor of $W$, an operation on $P$ which acts on the ``fibers'' above that constructor in $W$.
For instance, if $W$ is the natural numbers \nat, then to prove by induction that $\prd{x:\nat} P(x)$, we must specify
\begin{itemize}
\item An element $b:P(0)$ in the fiber over the constructor $0:\nat$, and
\item For each $n:\nat$, a function $P(n) \to P(\suc(n))$.
\end{itemize}
The second can be viewed as a function ``$P\to P$'' lying \emph{over} the constructor $\suc:\nat\to\nat$, generalizing how $b:P(0)$ lies over the constructor $0:\nat$.
By analogy, therefore, to prove that $\prd{x:\Sn^1} P(x)$, we should specify
\begin{itemize}
\item An element $b:P(\base)$ in the fiber over the constructor $\base:\Sn^1$, and
\item A path from $b$ to $b$ ``lying over the constructor $\lloop:\base=\base$''.
\end{itemize}
Note that even though $\Sn^1$ contains paths other than $\lloop$ (such as $\refl{\base}$ and $\lloop\ct\lloop$), we only need to specify a path lying over the constructor \emph{itself}.
This expresses the intuition that $\Sn^1$ is ``freely generated'' by its constructors.
The question, however, is what it means to have a path ``lying over'' another path.
It definitely does \emph{not} mean simply a path $b=b$, since that would be a path in the fiber $P(\base)$ (topologically, a path lying over the \emph{constant} path at $\base$).
Actually, however, we have already answered this question in \cref{cha:basics}: in the discussion preceding \cref{lem:mapdep} we concluded that a path from $u:P(x)$ to $v:P(y)$ lying over $p:x=y$ can be represented by a path $\trans p u = v$ in the fiber $P(y)$.
Since we will have a lot of use for such \define{dependent paths}
\index{path!dependent}%
in this chapter, we introduce a special notation for them:
\begin{equation}
(\dpath P p u v) \defeq (\transfib{P} p u = v).\label{eq:dpath}
\end{equation}
\begin{rmk}
There are other possible ways to define dependent paths.
For instance, instead of $\trans p u = v$ we could consider $u = \trans{(\opp p)}{v}$.
We could also obtain it as a special case of a more general ``heterogeneous equality'',
\index{heterogeneous equality}%
\index{equality!heterogeneous}%
or with a direct definition as an inductive type family.
All these definitions result in equivalent types, so in that sense it doesn't much matter which we pick.
However, choosing $\trans p u = v$ as the definition makes it easiest to conclude other things about dependent paths, such as the fact that $\apdfunc{f}$ produces them, or that we can compute them in particular type families using the transport lemmas in \cref{sec:computational}.
\end{rmk}
With the notion of dependent paths in hand, we can now state more precisely the induction principle for $\Sn^1$: given $P:\Sn^1\to\type$ and
\begin{itemize}
\item an element $b:P(\base)$, and
\item a path $\ell : \dpath P \lloop b b$,
\end{itemize}
there is a function $f:\prd{x:\Sn^1} P(x)$ such that $f(\base)\jdeq b$ and $\apd f \lloop = \ell$.
As in the non-dependent case, we speak of defining $f$ by $f(\base)\defeq b$ and $\apd f \lloop \defid \ell$.
\begin{rmk}\label{rmk:varies-along}
When describing an application of this induction principle informally, we regard it as a splitting of the goal ``$P(x)$ for all $x:\Sn^1$'' into two cases, which we will sometimes introduce with phrases such as ``when $x$ is $\base$'' and ``when $x$ varies along $\lloop$'', respectively.
\index{vary along a path constructor}%
There is no specific mathematical meaning assigned to ``varying along a path'': it is just a convenient way to indicate the beginning of the corresponding section of a proof; see \cref{thm:S1-autohtpy} for an example.
\end{rmk}
Topologically, the induction principle for $\Sn^1$ can be visualized as shown in \cref{fig:topS1ind}.
Given a fibration over the circle (which in the picture is a torus), to define a section of this fibration is the same as to give a point $b$ in the fiber over $\base$ along with a path from $b$ to $b$ lying over $\lloop$.
The way we interpret this type-theoretically, using our definition of dependent paths, is shown in \cref{fig:ttS1ind}: the path from $b$ to $b$ over $\lloop$ is represented by a path from $\trans \lloop b$ to $b$ in the fiber over $\base$.
\begin{figure}
\centering
\begin{tikzpicture}
\draw (0,0) ellipse (3 and .5);
\draw (0,3) ellipse (3.5 and 1.5);
\begin{scope}[yshift=4]
\clip (-3,3) -- (-1.8,3) -- (-1.8,3.7) -- (1.8,3.7) -- (1.8,3) -- (3,3) -- (3,0) -- (-3,0) -- cycle;
\draw[clip] (0,3.5) ellipse (2.25 and 1);
\draw (0,2.5) ellipse (1.7 and .7);
\end{scope}
\node (P) at (4.5,3) {$P$};
\node (S1) at (4.5,0) {$\Sn^1$};
\draw[->>,thick] (P) -- (S1);
\node[fill,circle,inner sep=1pt,label={below right:$\base$}] at (0,-.5) {};
\node at (-2.6,.6) {$\lloop$};
\node[fill,circle,\OPTblue,inner sep=1pt] (b) at (0,2.3) {};
\node[\OPTblue] at (-.2,2.1) {$b$};
\begin{scope}
\draw[\OPTblue] (b) to[out=180,in=-150] (-2.7,3.5) to[out=30,in=180] (0,3.35);
\draw[\OPTblue,dotted] (0,3.35) to[out=0,in=175] (1.4,4.35);
\draw[\OPTblue] (1.4,4.35) to[out=-5,in=90] (2.5,3) to[out=-90,in=0,looseness=.8] (b);
\end{scope}
\node[\OPTblue] at (-2.2, 3.3) {$\ell$};
\end{tikzpicture}
\caption{The topological induction principle for $\Sn^1$}
\label{fig:topS1ind}
\end{figure}
\begin{figure}
\centering
\begin{tikzpicture}
\draw (0,0) ellipse (3 and .5);
\draw (0,3) ellipse (3.5 and 1.5);
\begin{scope}[yshift=4]
\clip (-3,3) -- (-1.8,3) -- (-1.8,3.7) -- (1.8,3.7) -- (1.8,3) -- (3,3) -- (3,0) -- (-3,0) -- cycle;
\draw[clip] (0,3.5) ellipse (2.25 and 1);
\draw (0,2.5) ellipse (1.7 and .7);
\end{scope}
\node (P) at (4.5,3) {$P$};
\node (S1) at (4.5,0) {$\Sn^1$};
\draw[->>,thick] (P) -- (S1);
\node[fill,circle,inner sep=1pt,label={below right:$\base$}] at (0,-.5) {};
\node at (-2.6,.6) {$\lloop$};
\node[fill,circle,\OPTblue,inner sep=1pt] (b) at (0,2.3) {};
\node[\OPTblue] at (-.3,2.3) {$b$};
\node[fill,circle,\OPTpurple,inner sep=1pt] (tb) at (0,1.8) {};
% \draw[\OPTpurple,dashed] (b) to[out=0,in=0,looseness=5] (0,4) to[out=180,in=180] (tb);
\draw[\OPTpurple,dashed] (b) arc (-90:90:2.9 and 0.85) arc (90:270:2.8 and 1.1);
\begin{scope}
\clip (b) -- ++(.1,0) -- (.1,1.8) -- ++(-.2,0) -- ++(0,-1) -- ++(3,2) -- ++(-3,0) -- (-.1,2.3) -- cycle;
\draw[\OPTred,dotted,thick] (.2,2.07) ellipse (.2 and .57);
\begin{scope}
% \draw[clip] (b) -- ++(.1,0) |- (tb) -- ++(-.2,0) -- ++(0,-1) -| ++(3,3) -| (b);
\clip (.2,0) rectangle (-2,3);
\draw[\OPTred,thick] (.2,2.07) ellipse (.2 and .57);
\end{scope}
\end{scope}
\node[\OPTred] at (1,1.2) {$\ell: \trans \lloop b=b$};
\end{tikzpicture}
\caption{The type-theoretic induction principle for $\Sn^1$}
\label{fig:ttS1ind}
\end{figure}
Of course, we expect to be able to prove the recursion principle from the induction principle, by taking $P$ to be a constant type family.
This is in fact the case, although deriving the non-dependent computation rule for $\lloop$ (which refers to $\apfunc f$) from the dependent one (which refers to $\apdfunc f$) is surprisingly a little tricky.
\begin{lem}\label{thm:S1rec}
\index{recursion principle!for S1@for $\Sn^1$}%
\index{computation rule!for S1@for $\Sn^1$}%
If $A$ is a type together with $a:A$ and $p:\id[A]aa$, then there is a
function $f:\Sn^1\to{}A$ with
\begin{align*}
f(\base)&\defeq a \\
\apfunc f(\lloop)&\defid p.
\end{align*}
\end{lem}
\begin{proof}
We would like to apply the induction principle of $\Sn^1$ to the constant type family, $(\lam{x} A): \Sn^1\to \UU$.
The required hypotheses for this are a point of $(\lam{x} A)(\base) \jdeq A$, which we have (namely $a:A$), and a dependent path in $\dpath {x \mapsto A}{\lloop} a a$, or equivalently $\transfib{x \mapsto A}{\lloop} a = a$.
This latter type is not the same as the type $\id[A]aa$ where $p$ lives, but it is equivalent to it, because by \cref{thm:trans-trivial} we have $\transconst{A}{\lloop}{a} : \transfib{x \mapsto A}{\lloop} a= a$.
Thus, given $a:A$ and $p:a=a$, we can consider the composite
\[\transconst{A}{\lloop}{a} \ct p:(\dpath {x \mapsto A}\lloop aa).\]
Applying the induction principle, we obtain $f:\Sn^1\to A$ such that
\begin{align}
f(\base) &\jdeq a \qquad\text{and}\label{eq:S1recindbase}\\
\apdfunc f(\lloop) &= \transconst{A}{\lloop}{a} \ct p.\label{eq:S1recindloop}
\end{align}
It remains to derive the equality $\apfunc f(\lloop)=p$.
However, by \cref{thm:apd-const}, we have
\[\apdfunc f(\lloop) = \transconst{A}{\lloop}{f(\base)} \ct \apfunc f(\lloop).\]
Combining this with~\eqref{eq:S1recindloop} and canceling the occurrences of $\transconstf$ (which are the same by~\eqref{eq:S1recindbase}), we obtain $\apfunc f(\lloop)=p$.
\end{proof}
% Similarly, in this case we speak of defining $f$ by $f(\base)\defeq a$ and $\ap f \lloop \defid p$.
We also have a corresponding uniqueness principle.
\begin{lem}\label{thm:uniqueness-for-functions-on-S1}
\index{uniqueness!principle, propositional!for functions on the circle}%
If $A$ is a type and $f,g:\Sn^1\to{}A$ are two maps together with two
equalities $p,q$:
\begin{align*}
p:f(\base)&=_Ag(\base),\\
q:\map{f}\lloop&=^{\lam{x} x=_Ax}_p\map{g}\lloop.
\end{align*}
Then for all $x:\Sn^1$ we have $f(x)=g(x)$.
\end{lem}
\begin{proof}
We apply the induction principle of $\Sn^1$ at the type family $P(x)\defeq(f(x)=g(x))$.
When $x$ is $\base$, $p$ is exactly what we need.
And when $x$ varies along $\lloop$, we need
\(p=^{\lam{x} f(x)=g(x)}_{\lloop} p,\)
which by \cref{thm:transport-path,thm:dpath-path} can be reduced to $q$.
\end{proof}
\index{universal!property!of S1@of $\Sn^1$}%
These two lemmas imply the expected universal property of the circle:
\begin{lem}\label{thm:S1ump}
For any type $A$ we have a natural equivalence
\[ (\Sn^1 \to A) \;\eqvsym\;
\sm{x:A} (x=x).
\]
\end{lem}
\begin{proof}
We have a canonical function $f:(\Sn^1 \to A) \to \sm{x:A} (x=x)$ defined by $f(g) \defeq (g(\base),\ap g \lloop)$.
In the other direction, we have $g:\sm{x:A} (x=x) \to (\Sn^1 \to A)$ defined by taking a pair $(b,\ell)$ to the function $\Sn^1 \to A$ given by the recursion principle of the circle.
Now, by the computation rule of the recursion principle, $f \circ g \htpy \idfunc$.
Whereas $g \circ f \htpy \idfunc$ by the uniqueness principle,
since \((g \circ f)(\lloop) =^{\lam{x} x=_Ax}_{\refl{\base}} \lloop\), again, by the computation rule of the recursion principle of the circle.
Thus, f has a quasi-inverse, and is therefore an equivalence.
\end{proof}
\index{type!circle|)}%
As in \cref{sec:htpy-inductive}, we can show that the conclusion of \cref{thm:S1ump} is equivalent to having an induction principle with propositional computation rules.
Other higher inductive types also satisfy lemmas analogous to \cref{thm:S1rec,thm:S1ump}; we will generally leave their proofs to the reader.
We now proceed to consider many examples.
\section{The interval}
\label{sec:interval}
\index{type!interval|(defstyle}%
\indexsee{interval!type}{type, interval}%
The \define{interval}, which we denote $\interval$, is perhaps an even simpler higher inductive type than the circle.
It is generated by:
\begin{itemize}
\item a point $\izero:\interval$,
\item a point $\ione:\interval$, and
\item a path $\seg : \id[\interval]\izero\ione$.
\end{itemize}
\index{recursion principle!for interval type}%
The recursion principle for the interval says that given a type $B$ along with
\begin{itemize}
\item a point $b_0:B$,
\item a point $b_1:B$, and
\item a path $s:b_0=b_1$,
\end{itemize}
there is a function $f:\interval\to B$ such that $f(\izero)\jdeq b_0$, $f(\ione)\jdeq b_1$, and $\ap f \seg = s$.
\index{induction principle!for interval type}%
The induction principle says that given $P:\interval\to\type$ along with
\begin{itemize}
\item a point $b_0:P(\izero)$,
\item a point $b_1:P(\ione)$, and
\item a path $s:\dpath{P}{\seg}{b_0}{b_1}$,
\end{itemize}
there is a function $f:\prd{x:\interval} P(x)$ such that $f(\izero)\jdeq b_0$, $f(\ione)\jdeq b_1$, and $\apd f \seg = s$.
Regarded purely up to homotopy, the interval is not really interesting:
\begin{lem}\label{thm:contr-interval}
The type $\interval$ is contractible.
\end{lem}
\begin{proof}
We prove that for all $x:\interval$ we have $x=_\interval\ione$. In other words we want a
function $f$ of type $\prd{x:\interval}(x=_\interval\ione)$. We begin to define $f$ in the following way:
\begin{alignat*}{2}
f(\izero)&\defeq \seg &:\izero&=_\interval\ione,\\
f(\ione)&\defeq \refl\ione &:\ione &=_\interval\ione.
\end{alignat*}
It remains to define $\apd{f}\seg$, which must have type $\seg =_\seg^{\lam{x} x=_\interval\ione}\refl \ione$.
By definition this type is $\trans\seg\seg=_{\ione=_\interval\ione}\refl\ione$, which in turn is equivalent to $\rev\seg\ct\seg=\refl\ione$.
But there is a canonical element of that type, namely the proof that path inverses are in fact inverses.
\end{proof}
However, type-theoretically the interval does still have some interesting features, just like the topological interval in classical homotopy theory.
For instance, it enables us to give an easy proof of function extensionality.
(Of course, as in \cref{sec:univalence-implies-funext}, for the duration of the following proof we suspend our overall assumption of the function extensionality axiom.)
\begin{lem}\label{thm:interval-funext}
\index{function extensionality!proof from interval type}%
If $f,g:A\to{}B$ are two functions such that $f(x)=g(x)$ for every $x:A$, then
$f=g$ in the type $A\to{}B$.
\end{lem}
\begin{proof}
Let's call the proof we have $p:\prd{x:A}(f(x)=g(x))$. For all $x:A$ we define
a function $\widetilde{p}_x:\interval\to{}B$ by
\begin{align*}
\widetilde{p}_x(\izero) &\defeq f(x), \\
\widetilde{p}_x(\ione) &\defeq g(x), \\
\map{\widetilde{p}_x}\seg &\defid p(x).
\end{align*}
We now define $q:\interval\to(A\to{}B)$ by
\[q(i)\defeq(\lam{x} \widetilde{p}_x(i))\]
Then $q(\izero)$ is the function $\lam{x} \widetilde{p}_x(\izero)$, which is equal to $f$ because $\widetilde{p}_x(\izero)$ is defined by $f(x)$.
Similarly, we have $q(\ione)=g$, and hence
\[\map{q}\seg:f=_{(A\to{}B)}g \qedhere\]
\end{proof}
In \cref{ex:funext-from-interval} we ask the reader to complete the proof of the full function extensionality axiom from \cref{thm:interval-funext}.
\index{type!interval|)}%
\section{Circles and spheres}
\label{sec:circle}
\index{type!circle|(}%
We have already discussed the circle $\Sn^1$ as the higher inductive type generated by
\begin{itemize}
\item A point $\base:\Sn^1$, and
\item A path $\lloop : {\id[\Sn^1]\base\base}$.
\end{itemize}
\index{induction principle!for S1@for $\Sn^1$}%
Its induction principle says that given $P:\Sn^1\to\type$ along with $b:P(\base)$ and $\ell :\dpath P \lloop b b$, we have $f:\prd{x:\Sn^1} P(x)$ with $f(\base)\jdeq b$ and $\apd f \lloop = \ell$.
Its non-dependent recursion principle says that given $B$ with $b:B$ and $\ell:b=b$, we have $f:\Sn^1\to B$ with $f(\base)\jdeq b$ and $\ap f \lloop = \ell$.
We observe that the circle is nontrivial.
\begin{lem}\label{thm:loop-nontrivial}
$\lloop\neq\refl{\base}$.
\end{lem}
\begin{proof}
Suppose that $\lloop=\refl{\base}$.
Then since for any type $A$ with $x:A$ and $p:x=x$, there is a function $f:\Sn^1\to A$ defined by $f(\base)\defeq x$ and $\ap f \lloop \defid p$, we have
\[p = f(\lloop) = f(\refl{\base}) = \refl{x}.\]
But this implies that every type is a set, which as we have seen is not the case (see \cref{thm:type-is-not-a-set}).
\end{proof}
The circle also has the following interesting property, which is useful as a source of counterexamples.
\begin{lem}\label{thm:S1-autohtpy}
There exists an element of $\prd{x:\Sn^1} (x=x)$ which is not equal to $x\mapsto \refl{x}$.
\end{lem}
\begin{proof}
We define $f:\prd{x:\Sn^1} (x=x)$ by $\Sn^1$-induction.
When $x$ is $\base$, we let $f(\base)\defeq \lloop$.
Now when $x$ varies along $\lloop$ (see \cref{rmk:varies-along}), we must show that $\transfib{x\mapsto x=x}{\lloop}{\lloop} = \lloop$.
However, in \cref{sec:compute-paths} we observed that $\transfib{x\mapsto x=x}{p}{q} = \opp{p} \ct q \ct p$, so what we have to show is that $\opp{\lloop} \ct \lloop \ct \lloop = \lloop$.
But this is clear by canceling an inverse.
To show that $f\neq (x\mapsto \refl{x})$, it suffices to show that $f(\base) \neq \refl{\base}$.
But $f(\base)=\lloop$, so this is just the previous lemma.
\end{proof}
For instance, this enables us to extend \cref{thm:type-is-not-a-set} by showing that any universe which contains the circle cannot be a 1-type.
\begin{cor}
If the type $\Sn^1$ belongs to some universe \type, then \type is not a 1-type.
\end{cor}
\begin{proof}
The type $\Sn^1=\Sn^1$ in \type is, by univalence, equivalent to the type $\eqv{\Sn^1}{\Sn^1}$ of auto\-equivalences of $\Sn^1$, so it suffices to show that $\eqv{\Sn^1}{\Sn^1}$ is not a set.
\index{automorphism!of S1@of $\Sn^1$}%
For this, it suffices to show that its equality type $\id[(\eqv{\Sn^1}{\Sn^1})]{\idfunc[\Sn^1]}{\idfunc[\Sn^1]}$ is not a mere proposition.
Since being an equivalence is a mere proposition, this type is equivalent to $\id[(\Sn^1\to\Sn^1)]{\idfunc[\Sn^1]}{\idfunc[\Sn^1]}$.
But by function extensionality, this is equivalent to $\prd{x:\Sn^1} (x=x)$, which as we have seen in \cref{thm:S1-autohtpy} contains two unequal elements.
\end{proof}
\index{type!circle|)}%
\index{type!2-sphere|(}%
\indexsee{sphere type}{type, sphere}%
We have also mentioned that the 2-sphere $\Sn^2$ should be the higher inductive type generated by
\symlabel{s2b}
\begin{itemize}
\item A point $\base:\Sn^2$, and
\item A 2-dimensional path $\surf:\refl{\base} = \refl{\base}$ in ${\base=\base}$.
\end{itemize}
\index{recursion principle!for S2@for $\Sn^2$}%
The recursion principle for $\Sn^2$ is not hard: it says that given $B$ with $b:B$ and $s:\refl b = \refl b$, we have $f:\Sn^2\to B$ with $f(\base)\jdeq b$ and $\aptwo f \surf = s$.
Here by ``$\aptwo f \surf$'' we mean an extension of the functorial action of $f$ to two-dimensional paths, which can be stated precisely as follows.
\begin{lem}\label{thm:ap2}
Given $f:A\to B$ and $x,y:A$ and $p,q:x=y$, and $r:p=q$, we have a path $\aptwo f r : \ap f p = \ap f q$.
\end{lem}
\begin{proof}
By path induction, we may assume $p\jdeq q$ and $r$ is reflexivity.
But then we may define $\aptwo f {\refl p} \defeq \refl{\ap f p}$.
\end{proof}
In order to state the general induction principle, we need a version of this lemma for dependent functions, which in turn requires a notion of dependent two-dimensional paths.
As before, there are many ways to define such a thing; one is by way of a two-dimensional version of transport.
\begin{lem}\label{thm:transport2}
Given $P:A\to\type$ and $x,y:A$ and $p,q:x=y$ and $r:p=q$, for any $u:P(x)$ we have $\transtwo r u : \trans p u = \trans q u$.
\end{lem}
\begin{proof}
By path induction.
\end{proof}
Now suppose given $x,y:A$ and $p,q:x=y$ and $r:p=q$ and also points $u:P(x)$ and $v:P(y)$ and dependent paths $h:\dpath P p u v$ and $k:\dpath P q u v$.
By our definition of dependent paths, this means $h:\trans p u = v$ and $k:\trans q u = v$.
Thus, it is reasonable to define the type of dependent 2-paths over $r$ to be
\[ (\dpath P r h k )\defeq (h = \transtwo r u \ct k). \]
We can now state the dependent version of \cref{thm:ap2}.
\begin{lem}\label{thm:apd2}
Given $P:A\to\type$ and $x,y:A$ and $p,q:x=y$ and $r:p=q$ and a function $f:\prd{x:A} P(x)$, we have
$\apdtwo f r : \dpath P r {\apd f p}{\apd f q}$.
\end{lem}
\begin{proof}
Path induction.
\end{proof}
\index{induction principle!for S2@for $\Sn^2$}%
Now we can state the induction principle for $\Sn^2$: suppose we are given $P:\Sn^2\to\type$ with $b:P(\base)$ and $s:\dpath Q \surf {\refl b}{\refl b}$ where $Q\defeq\lam{p} \dpath P p b b$. Then there is a function $f:\prd{x:\Sn^2} P(x)$ such that $f(\base)\jdeq b$ and $\apdtwo f \surf = s$.
\index{type!2-sphere|)}%
Of course, this explicit approach gets more and more complicated as we go up in dimension.
Thus, if we want to define $n$-spheres for all $n$, we need some more systematic idea.
One approach is to work with $n$-dimensional loops\index{loop!n-@$n$-} directly, rather than general $n$-dimensional paths.\index{path!n-@$n$-}
\index{type!pointed}%
Recall from \cref{sec:equality} the definitions of \emph{pointed types} $\type_*$, and the $n$-fold loop space\index{loop space!iterated} $\Omega^n : \type_* \to \type_*$
(\cref{def:pointedtype,def:loopspace}). Now we can define the
$n$-sphere $\Sn^n$ to be the higher inductive type generated by
\index{type!n-sphere@$n$-sphere}%
\begin{itemize}
\item A point $\base:\Sn^n$, and
\item An $n$-loop $\lloop_n : \Omega^n(\Sn^n,\base)$.
\end{itemize}
In order to write down the induction principle for this presentation, we would need to define a notion of ``dependent $n$-loop\indexdef{loop!dependent n-@dependent $n$-}'', along with the action of dependent functions on $n$-loops.
We leave this to the reader (see \cref{ex:nspheres}); in the next section we will discuss a different way to define the spheres that is sometimes more tractable.
\section{Suspensions}
\label{sec:suspension}
\indexsee{type!suspension of}{suspension}%
\index{suspension|(defstyle}%
The \define{suspension} of a type $A$ is the universal way of making the points of $A$ into paths (and hence the paths in $A$ into 2-paths, and so on).
It is a type $\susp A$ defined by the following generators:\footnote{There is an unfortunate clash of notation with dependent pair types, which of course are also written with a $\Sigma$.
However, context usually disambiguates.}
\begin{itemize}
\item a point $\north:\susp A$,
\item a point $\south:\susp A$, and
\item a function $\merid:A \to (\id[\susp A]\north\south)$.
\end{itemize}
The names are intended to suggest a ``globe'' of sorts, with a north pole, a south pole, and an $A$'s worth of meridians
\indexdef{pole}%
\indexdef{meridian}%
from one to the other.
Indeed, as we will see, if $A=\Sn^1$, then its suspension is equivalent to the surface of an ordinary sphere, $\Sn^2$.
\index{recursion principle!for suspension}%
The recursion principle for $\susp A$ says that given a type $B$ together with
\begin{itemize}
\item points $n,s:B$ and
\item a function $m:A \to (n=s)$,
\end{itemize}
we have a function $f:\susp A \to B$ such that $f(\north)\jdeq n$ and $f(\south)\jdeq s$, and for all $a:A$ we have $\ap f {\merid(a)} = m(a)$.
\index{induction principle!for suspension}%
Similarly, the induction principle says that given $P:\susp A \to \type$ together with
\begin{itemize}
\item a point $n:P(\north)$,
\item a point $s:P(\south)$, and
\item for each $a:A$, a path $m(a):\dpath P{\merid(a)}ns$,
\end{itemize}
there exists a function $f:\prd{x:\susp A} P(x)$ such that $f(\north)\jdeq n$ and $f(\south)\jdeq s$ and for each $a:A$ we have $\apd f {\merid(a)} = m(a)$.
Our first observation about suspension is that it gives another way to define the circle.
\begin{lem}\label{thm:suspbool}
\index{type!circle}%
$\eqv{\susp\bool}{\Sn^1}$.
\end{lem}
\begin{proof}
Define $f:\susp\bool\to\Sn^1$ by recursion such that $f(\north)\defeq \base$ and $f(\south)\defeq\base$, while $\ap f{\merid(\bfalse)}\defid\lloop$ but $\ap f{\merid(\btrue)} \defid \refl{\base}$.
Define $g:\Sn^1\to\susp\bool$ by recursion such that $g(\base)\defeq \north$ and $\ap g \lloop \defid \merid(\bfalse) \ct \opp{\merid(\btrue)}$.
We now show that $f$ and $g$ are quasi-inverses.
First we show by induction that $g(f(x))=x$ for all $x:\susp \bool$.
If $x\jdeq\north$, then $g(f(\north)) \jdeq g(\base)\jdeq \north$, so we have $\refl{\north} : g(f(\north))=\north$.
If $x\jdeq\south$, then $g(f(\south)) \jdeq g(\base)\jdeq \north$, and we choose the equality $\merid(\btrue) : g(f(\south)) = \south$.
It remains to show that for any $y:\bool$, these equalities are preserved as $x$ varies along $\merid(y)$, which is to say that when $\refl{\north}$ is transported along $\merid(y)$ it yields $\merid(\btrue)$.
By transport in path spaces and pulled back fibrations, this means we are to show that
\[ \opp{\ap g {\ap f {\merid(y)}}} \ct \refl{\north} \ct \merid(y) = \merid(\btrue). \]
Of course, we may cancel $\refl{\north}$.
Now by \bool-induction, we may assume either $y\jdeq \bfalse$ or $y\jdeq \btrue$.
If $y\jdeq \bfalse$, then we have
\begin{align*}
\opp{\ap g {\ap f {\merid(\bfalse)}}} \ct \merid(\bfalse)
&= \opp{\ap g {\lloop}} \ct \merid(\bfalse)\\
&= \opp{(\merid(\bfalse) \ct \opp{\merid(\btrue)})} \ct \merid(\bfalse)\\
&= \merid(\btrue) \ct \opp{\merid(\bfalse)} \ct \merid(\bfalse)\\
&= \merid(\btrue)
\end{align*}
while if $y\jdeq \btrue$, then we have
\begin{align*}
\opp{\ap g {\ap f {\merid(\btrue)}}} \ct \merid(\btrue)
&= \opp{\ap g {\refl{\base}}} \ct \merid(\btrue)\\
&= \opp{\refl{\north}} \ct \merid(\btrue)\\
&= \merid(\btrue).
\end{align*}
Thus, for all $x:\susp \bool$, we have $g(f(x))=x$.
Now we show by induction that $f(g(x))=x$ for all $x:\Sn^1$.
If $x\jdeq \base$, then $f(g(\base))\jdeq f(\north)\jdeq\base$, so we have $\refl{\base} : f(g(\base))=\base$.
It remains to show that this equality is preserved as $x$ varies along $\lloop$, which is to say that it is transported along $\lloop$ to itself.
Again, by transport in path spaces and pulled back fibrations, this means to show that
\[ \opp{\ap f {\ap g {\lloop}}} \ct \refl{\base} \ct \lloop = \refl{\base}.\]
However, we have
\begin{align*}
\ap f {\ap g {\lloop}} &= \ap f {\merid(\bfalse) \ct \opp{\merid(\btrue)}}\\
&= \ap f {\merid(\bfalse)} \ct \opp{\ap f {\merid(\btrue)}}\\
&= \lloop \ct \refl{\base}
\end{align*}
so this follows easily.
\end{proof}
Topologically, the two-point space \bool is also known as the \emph{0-dimensional sphere}, $\Sn^0$.
(For instance, it is the space of points at distance $1$ from the origin in $\mathbb{R}^1$, just as the topological 1-sphere is the space of points at distance $1$ from the origin in $\mathbb{R}^2$.)
Thus, \cref{thm:suspbool} can be phrased suggestively as $\eqv{\susp\Sn^0}{\Sn^1}$.
\index{type!n-sphere@$n$-sphere|defstyle}%
\indexsee{n-sphere@$n$-sphere}{type, $n$-sphere}%
In fact, this pattern continues: we can define all the spheres inductively by
\begin{equation}\label{eq:Snsusp}
\Sn^0 \defeq \bool
\qquad\text{and}\qquad
\Sn^{n+1} \defeq \susp \Sn^n.
\end{equation}
We can even start one dimension lower by defining $\Sn^{-1}\defeq \emptyt$, and observe that $\eqv{\susp\emptyt}{\bool}$.
To prove carefully that this agrees with the definition of $\Sn^n$ from the previous section would require making the latter more explicit.
However, we can show that the recursive definition has the same universal property that we would expect the other one to have.
If $(A,a_0)$ and $(B,b_0)$ are pointed types (with basepoints often left implicit), let $\Map_*(A,B)$ denote the type of based maps:
\index{based map}
\symlabel{based-maps}
\[ \Map_*(A,B) \defeq \sm{f:A\to B} (f(a_0)=b_0). \]
Note that any type $A$ gives rise to a pointed type $A_+ \defeq A+\unit$ with basepoint $\inr(\ttt)$; this is called \emph{adjoining a disjoint basepoint}.
\indexdef{basepoint!adjoining a disjoint}%
\index{disjoint!basepoint}%
\index{adjoining a disjoint basepoint}%
\begin{lem}
For a type $A$ and a pointed type $(B,b_0)$, we have
\[ \eqv{\Map_*(A_+,B)}{(A\to B)} \]
\end{lem}
Note that on the right we have the ordinary type of \emph{unbased} functions from $A$ to $B$.
\begin{proof}
From left to right, given $f:A_+ \to B$ with $p:f(\inr(\ttt)) = b_0$, we have $f\circ \inl : A \to B$.
And from right to left, given $g:A\to B$ we define $g':A_+ \to B$ by $g'(\inl(a))\defeq g(a)$ and $g'(\inr(u)) \defeq b_0$.
We leave it to the reader to show that these are quasi-inverse operations.
\end{proof}
In particular, note that $\eqv{\bool}{\unit_+}$.
Thus, for any pointed type $B$ we have
\[{\Map_*(\bool,B)} \eqvsym {(\unit \to B)}\eqvsym B.\]
%
Now recall that the loop space\index{loop space} operation $\Omega$ acts on pointed types, with definition $\Omega(A,a_0) \defeq (\id[A]{a_0}{a_0},\refl{a_0})$.
We can also make the suspension $\susp$ act on pointed types, by $\susp(A,a_0)\defeq (\susp A,\north)$.
\begin{lem}\label{lem:susp-loop-adj}
\index{universal!property!of suspension}%
For pointed types $(A,a_0)$ and $(B,b_0)$ we have
\[ \eqv{\Map_*(\susp A, B)}{\Map_*(A,\Omega B)}.\]
\end{lem}
\addtocounter{thm}{1} % Because we removed a numbered equation in commit 8f54d16
\begin{proof}
We first observe the following chain of equivalences:
\begin{align*}
\Map_*(\susp A, B) & \defeq \sm{f:\susp A\to B} (f(\north)=b_0) \\
& \eqvsym \sm{f:\sm{b_n : B}{b_s : B} (A \to (b_n = b_s))} (\fst(f)=b_0) \\
& \eqvsym \sm{b_n : B}{b_s : B} \big(A \to (b_n = b_s)\big) \times (b_n=b_0) \\
& \eqvsym \sm{p : \sm{b_n : B} (b_n=b_0)}{b_s : B} (A \to (\fst(p) = b_s)) \\
& \eqvsym \sm{b_s : B} (A \to (b_0 = b_s))
\end{align*}
The first equivalence is by the universal property of suspensions, which says that
\[ \Parens{\susp A \to B} \eqvsym \Parens{\sm{b_n : B} \sm{b_s : B} (A \to (b_n = b_s)) } \]
with the function from right to left given by the recursor (see \cref{ex:susp-lump}).
The second and third equivalences are by \cref{ex:sigma-assoc}, along with a reordering of components.
Finally, the last equivalence follows from \cref{thm:omit-contr}, since by \cref{thm:contr-paths}, $\sm{b_n : B} (b_n=b_0)$ is contractible with center $(b_0, \refl{b_0})$.
The proof is now completed by the following chain of equivalences:
\begin{align*}
\sm{b_s : B} (A \to (b_0 = b_s))
&\eqvsym \sm{b_s : B}{g:A \to (b_0 = b_s)}{q:b_0 = b_s} (g(a_0) = q)\\
&\eqvsym \sm{r : \sm{b_s : B}(b_0 = b_s)}{g:A \to (b_0 = \proj1(r))} (g(a_0) = \proj2(r))\\
&\eqvsym \sm{g:A \to (b_0 = b_0)} (g(a_0) = \refl{b_0})\\
&\jdeq \Map_*(A,\Omega B).
\end{align*}
Similar to before, the first and last equivalences are by \cref{thm:omit-contr,thm:contr-paths}, and the second is by \cref{ex:sigma-assoc} and reordering of components.
\end{proof}
\index{type!n-sphere@$n$-sphere|defstyle}%
In particular, for the spheres defined as in~\eqref{eq:Snsusp} we have
\index{universal!property!of Sn@of $\Sn^n$}%
\[ \Map_*(\Sn^n,B) \eqvsym \Map_*(\Sn^{n-1}, \Omega B) \eqvsym \cdots \eqvsym \Map_*(\bool,\Omega^n B) \eqvsym \Omega^n B. \]
Thus, these spheres $\Sn^n$ have the universal property that we would expect from the spheres defined directly in terms of $n$-fold loop spaces\index{loop space!iterated} as in \cref{sec:circle}.
\index{suspension|)}%
\section{Cell complexes}
\label{sec:cell-complexes}
\index{cell complex|(defstyle}%
\index{CW complex|(defstyle}%
In classical topology, a \emph{cell complex} is a space obtained by successively attaching discs along their boundaries.
It is called a \emph{CW complex} if the boundary of an $n$-dimensional disc\index{disc} is constrained to lie in the discs of dimension strictly less than $n$ (the $(n-1)$-skeleton).\index{skeleton!of a CW-complex}
Any finite CW complex can be presented as a higher inductive type, by turning $n$-dimensional discs into $n$-dimensional paths and partitioning the image of the attaching\index{attaching map} map into a source\index{source!of a path constructor} and a target\index{target!of a path constructor}, with each written as a composite of lower dimensional paths.
Our explicit definitions of $\Sn^1$ and $\Sn^2$ in \cref{sec:circle} had this form.
\index{torus}%
Another example is the torus $T^2$, which is generated by:
\begin{itemize}
\item a point $b:T^2$,
\item a path $p:b=b$,
\item another path $q:b=b$, and
\item a 2-path $t: p\ct q = q \ct p$.
\end{itemize}
Perhaps the easiest way to see that this is a torus is to start with a rectangle, having four corners $a,b,c,d$, four edges $p,q,r,s$, and an interior which is manifestly a 2-path $t$ from $p\ct q$ to $r\ct s$:
\begin{equation*}
\xymatrix{
a\ar@{=}[r]^p\ar@{=}[d]_r \ar@{}[dr]|{\Downarrow t} &
b\ar@{=}[d]^q\\
c\ar@{=}[r]_s &
d
}
\end{equation*}
Now identify the edge $r$ with $q$ and the edge $s$ with $p$, resulting in also identifying all four corners.
Topologically, this identification can be seen to produce a torus.
\index{induction principle!for torus}%
\index{torus!induction principle for}%
The induction principle for the torus is the trickiest of any we've written out so far.
Given $P:T^2\to\type$, for a section $\prd{x:T^2} P(x)$ we require
\begin{itemize}
\item a point $b':P(b)$,
\item a path $p' : \dpath P p {b'} {b'}$,
\item a path $q' : \dpath P q {b'} {b'}$, and
\item a 2-path $t'$ between the ``composites'' $p'\ct q'$ and $q'\ct p'$, lying over $t$.
\end{itemize}
In order to make sense of this last datum, we need a composition operation for dependent paths, but this is not hard to define.
Then the induction principle gives a function $f:\prd{x:T^2} P(x)$ such that $f(b)\jdeq b'$ and $\apd f {p} = p'$ and $\apd f {q} = q'$ and something like ``$\apdtwo f t = t'$''.
However, this is not well-typed as it stands, firstly because the equalities $\apd f {p} = p'$ and $\apd f {q} = q'$ are not judgmental, and secondly because $\apdfunc f$ only preserves path concatenation up to homotopy.
We leave the details to the reader (see \cref{ex:torus}).
Of course, another definition of the torus is $T^2 \defeq \Sn^1 \times \Sn^1$ (in \cref{ex:torus-s1-times-s1} we ask the reader to verify the equivalence of the two).
\index{Klein bottle}%
\index{projective plane}%
The cell-complex definition, however, generalizes easily to other spaces without such descriptions, such as the Klein bottle, the projective plane, etc.
But it does get increasingly difficult to write down the induction principles, requiring us to define notions of dependent $n$-paths and of $\apdfunc{}$ acting on $n$-paths.
Fortunately, once we have the spheres in hand, there is a way around this.
\section{Hubs and spokes}
\label{sec:hubs-spokes}
\indexsee{spoke}{hub and spoke}%
\index{hub and spoke|(defstyle}%
In topology, one usually speaks of building CW complexes by attaching $n$-dimensional discs along their $(n-1)$-dimensional boundary spheres.
\index{attaching map}%
However, another way to express this is by gluing in the \emph{cone}\index{cone!of a sphere} on an $(n-1)$-dimensional sphere.
That is, we regard a disc\index{disc} as consisting of a cone point (or ``hub''), with meridians
\index{meridian}%
(or ``spokes'') connecting that point to every point on the boundary, continuously, as shown in \cref{fig:hub-and-spokes}.
\begin{figure}
\centering
\begin{tikzpicture}
\draw (0,0) circle (2cm);
\foreach \x in {0,20,...,350}
\draw[\OPTblue] (0,0) -- (\x:2cm);
\node[\OPTblue,circle,fill,inner sep=2pt] (hub) at (0,0) {};
\end{tikzpicture}
\caption{A 2-disc made out of a hub and spokes}
\label{fig:hub-and-spokes}
\end{figure}
We can use this idea to express higher inductive types containing $n$-dimensional path con\-struc\-tors for $n>1$ in terms of ones containing only 1-di\-men\-sion\-al path con\-struc\-tors.
The point is that we can obtain an $n$-dimensional path as a continuous family of 1-dimensional paths parametrized by an $(n-1)$-di\-men\-sion\-al object.
The simplest $(n-1)$-dimensional object to use is the $(n-1)$-sphere, although in some cases a different one may be preferable.
(Recall that we were able to define the spheres in \cref{sec:suspension} inductively using suspensions, which involve only 1-dimensional path constructors.
Indeed, suspension can also be regarded as an instance of this idea, since it involves a family of 1-dimensional paths parametrized by the type being suspended.)
\index{torus}
For instance, the torus $T^2$ from the previous section could be defined instead to be generated by:
\begin{itemize}
\item a point $b:T^2$,
\item a path $p:b=b$,
\item another path $q:b=b$,
\item a point $h:T^2$, and
\item for each $x:\Sn^1$, a path $s(x) : f(x)=h$, where $f:\Sn^1\to T^2$ is defined by $f(\base)\defeq b$ and $\ap f \lloop \defid p \ct q \ct \opp p \ct \opp q$.
\end{itemize}
The induction principle for this version of the torus says that given $P:T^2\to\type$, for a section $\prd{x:T^2} P(x)$ we require
\begin{itemize}
\item a point $b':P(b)$,
\item a path $p' : \dpath P p {b'} {b'}$,
\item a path $q' : \dpath P q {b'} {b'}$,
\item a point $h':P(h)$, and
\item for each $x:\Sn^1$, a path $\dpath {P}{s(x)}{g(x)}{h'}$, where $g:\prd{x:\Sn^1} P(f(x))$ is defined by $g(\base)\defeq b'$ and $\apd g \lloop \defid t(p' \ct q' \ct \opp{(p')} \ct \opp{(q')})$.
In the latter, $\ct$ denotes concatenation of dependent paths, and the definition of $t:\eqv{(\dpath{P}{\ap f \lloop}{b'}{b'})}{(\dpath{P\circ f}{\lloop}{b'}{b'})}$ is left to the reader.
\end{itemize}
Note that there is no need for dependent 2-paths or $\apdtwofunc{}$.
We leave it to the reader to write out the computation rules.
\begin{rmk}\label{rmk:spokes-no-hub}
One might question the need for introducing the hub point $h$; why couldn't we instead simply add paths continuously relating the boundary of the disc to a point \emph{on} that boundary, as shown in \cref{fig:spokes-no-hub}?
However, this does not work without further modification.
For if, given some $f:\Sn^1 \to X$, we give a path constructor connecting each $f(x)$ to $f(\base)$, then what we end up with is more like the picture in \cref{fig:spokes-no-hub-ii} of a cone whose vertex is twisted around and glued to some point on its base.
The problem is that the specified path from $f(\base)$ to itself may not be reflexivity.
We could remedy the problem by adding a 2-dimensional path constructor to ensure this, but using a separate hub avoids the need for any path constructors of dimension above~$1$.
\end{rmk}
\begin{figure}
\centering
\begin{minipage}{2in}
\begin{center}
\begin{tikzpicture}
\draw (0,0) circle (2cm);
\clip (0,0) circle (2cm);
\foreach \x in {0,15,...,165}
\draw[\OPTblue] (0,-2cm) -- (\x:4cm);
\end{tikzpicture}
\end{center}
\caption{Hubless spokes}
\label{fig:spokes-no-hub}
\end{minipage}
\qquad
\begin{minipage}{2in}
\begin{center}
\begin{tikzpicture}[xscale=1.3]
\draw (0,0) arc (-90:90:.7cm and 2cm) ;
\draw[dashed] (0,4cm) arc (90:270:.7cm and 2cm) ;
\draw[\OPTblue] (0,0) to[out=90,in=0] (-1,1) to[out=180,in=180] (0,0);
\draw[\OPTblue] (0,4cm) to[out=180,in=180,looseness=2] (0,0);
\path (0,0) arc (-90:-60:.7cm and 2cm) node (a) {};
\draw[\OPTblue] (a.center) to[out=120,in=10] (-1.2,1.2) to[out=190,in=180] (0,0);
\path (0,0) arc (-90:-30:.7cm and 2cm) node (b) {};
\draw[\OPTblue] (b.center) to[out=150,in=20] (-1.4,1.4) to[out=200,in=180] (0,0);
\path (0,0) arc (-90:0:.7cm and 2cm) node (c) {};
\draw[\OPTblue] (c.center) to[out=180,in=30] (-1.5,1.5) to[out=210,in=180] (0,0);
\path (0,0) arc (-90:30:.7cm and 2cm) node (d) {};
\draw[\OPTblue] (d.center) to[out=190,in=50] (-1.7,1.7) to[out=230,in=180] (0,0);
\path (0,0) arc (-90:60:.7cm and 2cm) node (e) {};
\draw[\OPTblue] (e.center) to[out=200,in=70] (-2,2) to[out=250,in=180] (0,0);
\clip (0,0) to[out=90,in=0] (-1,1) to[out=180,in=180] (0,0);
\draw (0,4cm) arc (90:270:.7cm and 2cm) ;
\end{tikzpicture}
\end{center}
\caption{Hubless spokes, II}
\label{fig:spokes-no-hub-ii}
\end{minipage}
\end{figure}
\begin{rmk}
\index{computation rule!propositional}%
Note also that this ``translation'' of higher paths into 1-paths does not preserve judgmental computation rules for these paths, though it does preserve propositional ones.
\end{rmk}
\index{cell complex|)}%
\index{CW complex|)}%
\index{hub and spoke|)}%
\section{Pushouts}
\label{sec:colimits}
\index{type!limit}%
\index{type!colimit}%
\index{limit!of types}%
\index{colimit!of types}%
From a category-theoretic point of view, one of the important aspects of any foundational system is the ability to construct limits and colimits.
In set-theoretic foundations, these are limits and colimits of sets, whereas in our case they are limits and colimits of \emph{types}.
We have seen in \cref{sec:universal-properties} that cartesian product types have the correct universal property of a categorical product of types, and in \cref{ex:coprod-ump} that coproduct types likewise have their expected universal property.
As remarked in \cref{sec:universal-properties}, more general limits can be constructed using identity types and $\Sigma$-types, e.g.\ the pullback\index{pullback} of $f:A\to C$ and $g:B\to C$ is $\sm{a:A}{b:B} (f(a)=g(b))$ (see \cref{ex:pullback}).
However, more general \emph{colimits} require identifying elements coming from different types, for which higher inductives are well-adapted.
Since all our constructions are homotopy-invariant, all our colimits are necessarily \emph{homotopy colimits}, but we drop the ubiquitous adjective in the interests of concision.
In this section we discuss \emph{pushouts}, as perhaps the simplest and one of the most useful colimits.
Indeed, one expects all finite colimits (for a suitable homotopical definition of ``finite'') to be constructible from pushouts and finite coproducts.
It is also possible to give a direct construction of more general colimits using higher inductive types, but this is somewhat technical, and also not completely satisfactory since we do not yet have a good fully general notion of homotopy coherent diagrams.
\indexsee{type!pushout of}{pushout}%
\index{pushout|(defstyle}%
\index{span}%
Suppose given a span of types and functions:
\[\Ddiag=\;\vcenter{\xymatrix{C \ar^g[r] \ar_f[d] & B \\ A & }}\]
The \define{pushout} of this span is the higher inductive type $A\sqcup^CB$ presented by
\begin{itemize}
\item a function $\inl:A\to A\sqcup^CB$,
\item a function $\inr:B \to A\sqcup^CB$, and
\item for each $c:C$ a path $\glue(c):(\inl(f(c))=\inr(g(c)))$.
\end{itemize}
In other words, $A\sqcup^CB$ is the disjoint union of $A$ and $B$, together with for every $c:C$ a witness that $f(c)$ and $g(c)$ are equal.
The recursion principle says that if $D$ is another type, we can define a map $s:A\sqcup^CB\to{}D$ by defining
\begin{itemize}
\item for each $a:A$, the value of $s(\inl(a)):D$,
\item for each $b:B$, the value of $s(\inr(b)):D$, and
\item for each $c:C$, the value of $\mapfunc{s}(\glue(c)):s(\inl(f(c)))=s(\inr(g(c)))$.
\end{itemize}
We leave it to the reader to formulate the induction principle.
It also implies the uniqueness principle that if $s,s':A\sqcup^CB\to{}D$ are two maps such that
\index{uniqueness!principle, propositional!for functions on a pushout}%
\begin{align*}
s(\inl(a))&=s'(\inl(a))\\
s(\inr(b))&=s'(\inr(b))\\
\mapfunc{s}(\glue(c))&=\mapfunc{s'}(\glue(c))
\qquad\text{(modulo the previous two equalities)}
\end{align*}
for every $a,b,c$, then $s=s'$.
To formulate the universal property of a pushout, we introduce the following.
\begin{defn}\label{defn:cocone}
Given a span $\Ddiag= (A \xleftarrow{f} C \xrightarrow{g} B)$ and a type $D$, a \define{cocone under $\Ddiag$ with vertex $D$}
\indexdef{cocone}%
\index{vertex of a cocone}%
consists of functions $i:A\to{}D$ and $j:B\to{}D$ and a homotopy $h : \prd{c:C} (i(f(c))=j(g(c)))$:
\[\uppercurveobject{{ }}\lowercurveobject{{ }}\twocellhead{{ }}
\xymatrix{C \ar^g[r] \ar_f[d] \drtwocell{^h} & B \ar^j[d] \\ A \ar_i[r] & D
}\]
We denote by $\cocone{\Ddiag}{D}$ the type of all such cocones, i.e.
\[ \cocone{\Ddiag}{D} \defeq
\sm{i:A\to D}{j:B\to D} \prd{c:C} (i(f(c))=j(g(c))).
\]
\end{defn}
Of course, there is a canonical cocone under $\Ddiag$ with vertex $A\sqcup^C B$ consisting of $\inl$, $\inr$, and $\glue$.
\[\uppercurveobject{{ }}\lowercurveobject{{ }}\twocellhead{{ }}
\xymatrix{C \ar^g[r] \ar_f[d] \drtwocell{^\glue\ \ } & B \ar^\inr[d] \\
A \ar_-\inl[r] & A\sqcup^CB }\]
The following lemma says that this is the universal such cocone.
\begin{lem}\label{thm:pushout-ump}
\index{universal!property!of pushout}%
For any type $E$, there is an equivalence
\[ (A\sqcup^C B \to E) \;\eqvsym\; \cocone{\Ddiag}{E}. \]
\end{lem}
\begin{proof}
Let's consider an arbitrary type $E:\type$.
There is a canonical function $c_\sqcup$ defined by
\[\function{(A\sqcup^CB\to{}E)}{\cocone{\Ddiag}{E}}
{t}{(t\circ{}\inl,t\circ{}\inr,\mapfunc{t}\circ{}\glue)}\]
We write informally $t\mapsto\composecocone{t}c_\sqcup$ for this function.
We show that this is an equivalence.
Firstly, given a $c=(i,j,h):\cocone{\mathscr{D}}{E}$, we need to construct a
map $\mathsf{s}(c)$ from $A\sqcup^CB$ to $E$.
\[\uppercurveobject{{ }}\lowercurveobject{{ }}\twocellhead{{ }}
\xymatrix{C \ar^g[r] \ar_f[d] \drtwocell{^h} & B \ar^{j}[d] \\
A \ar_-{i}[r] & E }\]
The map $\mathsf{s}(c)$ is defined in the following way
\begin{align*}
\mathsf{s}(c)(\inl(a))&\defeq i(a),\\
\mathsf{s}(c)(\inr(b))&\defeq j(b),\\
\mapfunc{\mathsf{s}(c)}(\glue(x))&\defid h(x).
\end{align*}
We have defined a map
\[\function{\cocone{\Ddiag}{E}}{(A\sqcup^CB\to{}E)}{c}{\mathsf{s}(c)}\]
and we need to prove that this map is an inverse to
$t\mapsto{}\composecocone{t}c_\sqcup$.
On the one hand, if $c=(i,j,h):\cocone{\Ddiag}{E}$, we have
\begin{align*}
\composecocone{\mathsf{s}(c)}c_\sqcup & =
(\mathsf{s}(c)\circ\inl,\mathsf{s}(c)\circ\inr,
\mapfunc{\mathsf{s}(c)}\circ\glue) \\
& = (\lamu{a:A} \mathsf{s}(c)(\inl(a)),\;
\lamu{b:B} \mathsf{s}(c)(\inr(b)),\;
\lamu{x:C} \mapfunc{\mathsf{s}(c)}(\glue(x))) \\
& = (\lamu{a:A} i(a),\;
\lamu{b:B} j(b),\;
\lamu{x:C} h(x)) \\
& \jdeq (i, j, h) \\
& = c.
\end{align*}
%
On the other hand, if $t:A\sqcup^CB\to{}E$, we want to prove that
$\mathsf{s}(\composecocone{t}c_\sqcup)=t$.
For $a:A$, we have
\[\mathsf{s}(\composecocone{t}c_\sqcup)(\inl(a))=t(\inl(a))\]
because the first component of $\composecocone{t}c_\sqcup$ is $t\circ\inl$. In