-
Notifications
You must be signed in to change notification settings - Fork 7
/
P1-Polynomials.tex
9122 lines (8061 loc) · 542 KB
/
P1-Polynomials.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
% !TeX root = P1-Polynomials.tex
\documentclass[Book-Poly]{subfiles}
\begin{document}
\setcounter{chapter}{0}%Just finished 0.
%---------------- Part ----------------%
\part{The category of polynomial functors}\label{part.poly}
\Opensolutionfile{solutions}[solution-file1]
%------------ Chapter ------------%
\chapter{Representable functors from the~category of sets} \label{ch.poly.rep-sets}
In this chapter, we lay the categorical groundwork needed to define our category of interest, the category of polynomial functors.
We begin by examining a special kind of polynomial functor that you may already be familiar with---representable functors from the category $\smset$ of sets and functions.%
\index{functor!representable|(}
\index{functor!polynomial|see{polynomial functor}}
\index{polynomial functor}
\index{functor!set-valued}
We highlight the role these representable functors play in what is arguably the fundamental theorem of category theory, the Yoneda lemma.
We will also discuss sums and products of sets and of set-valued functors, which we will need to construct our polynomial functors.
%-------- Section --------%
\section{Representable functors and the Yoneda lemma} \label{sec.poly.rep-sets.yon}
\index{Yoneda lemma}
Representable functors---special functors to the category of sets---provide the foundation for the category $\poly$.
While much of the following theory applies to representable functors from any category, we need only focus on representable functors $\smset\to\smset$.
\begin{definition}[Representable functor] \label{def.representable}
For a set $S$, we denote by $\yon^S\colon\smset\to\smset$ the functor that sends each set $X$ to the set $X^S=\smset(S,X)$ and each function $h\colon X\to Y$ to the function $h^S\colon X^S\to Y^S$ that sends $g\colon S\to X$ to $g\then h\colon S\to Y$.\footnote{Throughout this text, given morphisms $f \colon A \to B$ and $g \colon B \to C$ in a category, we will denote their composite morphism $A \to C$ interchangeably as $f \then g$ or $g \circ f$ (or even $gf$), whichever is more convenient.}
We call a functor (isomorphic to one) of this form a \emph{representable functor}, or a \emph{representable}.
In particular, we call $\yon^S$ the functor \emph{represented by} $S$, and we call $S$ the \emph{representing set of $\yon^S$}.
As $\yon^S$ denotes raising a variable to the power of $S$, we will also refer to representables as \emph{pure powers}.%
\index{pure power|see{functor, representable}}
\end{definition}
The symbol $\yon$ stands for Yoneda, for reasons we will explain in \cref{lemma.yoneda} and \cref{exc.finish_proof_yoneda} \cref{exc.finish_proof_yoneda.embed}.
Throughout this book, we will use the notation $\0\coloneqq\{\}=\varnothing,$ $\1\coloneqq\{1\},$ $\2\coloneqq\{1,2\},$ $\3\coloneqq\{1,2,3\}$, and so on, with $\ord{n}\coloneqq\{1,\ldots,n\}$
\begin{example}
The functor that sends each set $X$ to $X\times X$ and each function $h\colon X\to Y$ to $(h\times h)\colon (X\times X)\to(Y\times Y)$ is representable.
After all, $X\times X \iso X^\2$, so this functor is the pure power $\yon^\2$.
\end{example}
\begin{exercise}\label{exc.representable_fun}\index{functor!representable}\index{representable polynomial|seealso{functor!representable}}
For each of the following functors $\smset\to\smset$, say if it is representable or not; if it is, give the set that represents it.
\begin{enumerate}
\item The identity functor $X\mapsto X$, which sends each function to itself.
\item The constant functor $X\mapsto\2$, which sends every function to the identity on $\2$.
\item The constant functor $X\mapsto\1$, which sends every function to the identity on $\1$.
\item The constant functor $X\mapsto\0$, which sends every function to the identity on $\0$.
\item A functor $X\mapsto X^\nn$.
If it could be representable, where should it send each function?
\item A functor $X\mapsto \2^X$.
If it could be representable, where should it send each function? \qedhere
\end{enumerate}
\index{functor!identity}\index{functor!constant}
\begin{solution}
\begin{enumerate}
\item The identity functor $X\mapsto X$ is represented by the set $\1$: a function $\1 \to X$ can be identified with an element of $X$, so $\smset(\1,X)\iso X$.
Alternatively, note that $X^\1 \iso X$.
\item \label{sol.representable_fun.2} The constant functor $X\mapsto\2$ is not representable: it sends $\1$ to $\2$, but $\1^S \iso \1 \not\iso \2$ for any set $S$.
\item The constant functor $X\mapsto\1$ is represented by $S=\0$: there is exactly one function $\0 \to X$, so $\smset(\0,X) \iso \1$.
Alternatively, note that $X^0 \iso \1$.
\item The constant functor $X\mapsto\0$ is not representable for the same reason as in \cref{sol.representable_fun.2}.
\item The functor $\yon^\nn$ that sends $X\mapsto X^\nn$ is represented by $\nn$, by definition.
It should send each function $h \colon X \to Y$ to the function $h^\nn \colon X^\nn \to Y^\nn$ that sends each $g \colon \nn \to X$ to $g \then h \colon \nn \to Y$.
\item No $\smset \to \smset$ functor $X\mapsto \2^X$ is representable, for the same reason as in \cref{sol.representable_fun.2}.
(There \emph{is}, however, a functor $\smset\op \to \smset$ sending $X \mapsto 2^X$ that is understood to be representable in a more general sense.)
\end{enumerate}
\end{solution}
\end{exercise}
Now that we have introduced representable functors, we study the maps between them.
As representables are functors, the maps between them are natural transformations.
\index{natural transformation!between representables}
\begin{proposition}\label{prop.representable_nt}
For any function $f\colon R\to S$, there is an induced natural transformation $\yon^f\colon\yon^S\to \yon^R$; on any set $X$ its $X$-component $X^f\colon X^S\to X^R$ is given by sending $g\colon S\to X$ to $f\then g\colon R\to X$.
\end{proposition}
\begin{proof}
See \cref{exc.representable_nt}.
\end{proof}
\begin{exercise} \label{exc.representable_nt}
To prove \cref{prop.representable_nt}, show that for any function $f\colon R\to S$, the given construction $\yon^f\colon\yon^S\to\yon^R$ really is a natural transformation.
That is, for any function $h\colon X\to Y$, show that the following naturality square commutes:
\begin{equation} \label{diag.yon_embed_nat}
\begin{tikzcd}%[bottom base]
X^S\ar[r, "h^S"]\ar[d, "X^f"']&
Y^S\ar[d, "Y^f"]\\
X^R\ar[r, "h^R"']&
Y^R\ar[ul, phantom, "?"]
\end{tikzcd}
\end{equation}
\qedhere
\begin{solution}
To show that \eqref{diag.yon_embed_nat} commutes, we note that by the construction of the components of $\yon^f$ in the statement of \cref{prop.representable_nt}, both vertical maps in the diagram compose functions from $S$ with $f \colon R \to S$ on the left; and by \cref{def.representable}, both horizontal maps compose functions to $X$ with $h \colon X \to Y$ on the right.
So by the associativity of composition, the diagram commutes: $(f\then g)\then h=f\then(g\then h)$ for all $g\colon S\to X$.
\end{solution}
\end{exercise}\index{associativity}
\begin{exercise} \label{exc.representable_nt_components}
Let $X$ be an arbitrary set. For each of the following sets $R,S$ and functions $f\colon R\to S$, describe the $X$-component $X^f\colon X^S\to X^R$ of the natural transformation $\yon^f\colon\yon^S\to\yon^R$.
\begin{enumerate}
\item \label{exc.representable_nt_components.id} $R=\5$, $S=\5$, $f=\id_\5$. (You should describe the function $X^{\id_\5}\colon X^\5\to X^\5$.)
\item $R=\2$, $S=\1$, $f$ is the unique function.
\item $R=\1$, $S=\2$, $f(1)=1$.
\item $R=\1$, $S=\2$, $f(1)=2$.
\item $R=\0$, $S=\5$, $f$ is the unique function.
\item $R=\nn$, $S=\nn$, $f(n)=n+1$.
\qedhere
\end{enumerate}
\begin{solution}
In each case, given $f \colon R \to S$, we can find the $X$-component $X^f \colon X^S \to X^R$ of the natural transformation $\yon^f\colon\yon^S\to\yon^R$ by applying \cref{prop.representable_nt}, which says that $X^f$ sends each $g \colon S \to X$ to $f \then g \colon R \to X$.
\begin{enumerate}
\item Here $X^{\id_5}\colon X^\5\to X^\5$ is the identity function.
\item If $f\colon\2\to\1$ is the unique function, then $X^f\colon X^\1\to X^\2$ sends each $g \in X$ (i.e.\ function $g \colon \1 \to X$) to the function that maps both elements of $\2$ to $g$.
We can think of $X^f$ as the diagonal $X \to X \times X$.
\item If $f\colon\1\to\2$ sends $1\mapsto1$, then $X^f\colon X^\2\to X^\1$ sends each $g \colon \2 \to X$ to $g(1)$, viewed as a function $\1 \to X$.
We can think of $X^f$ as the left projection $X \times X \to X$.
\item If $f\colon\1\to\2$ sends $1\mapsto2$, then $X^f\colon X^\2\to X^\1$ sends each $g \colon \2 \to X$ to $g(2)$, viewed as a function $\1 \to X$.
We can think of $X^f$ as the right projection $X \times X \to X$.
\item Here $X^f\colon X^\5\to X^\0\iso\1$ is the unique function.
\item If $f\colon\nn\to\nn$ sends $n\mapsto n+1$, then $X^f\colon X^\nn\to X^\nn$ sends each $g \colon \nn \to X$ to the function $h \colon \nn \to X$ defined by $h(n)\coloneqq g(n+1)$ for all $n \in \nn$.
We can think of $X^f$ as removing the first term of an infinite sequence of elements $(g(0),g(1),g(2),\ldots)$ of $X$ to obtain a new sequence $(g(1),g(2),g(3),\ldots)$.
\end{enumerate}
\end{solution}
\end{exercise}
These representable functors and natural transformations live in the larger category $\smset^\smset$, whose objects are functors $\smset\to\smset$ and whose morphisms are the natural transformations between them.
\begin{exercise} \label{exc.representable_nt_functorial}
Show that the construction $f\mapsto\yon^f$ from \cref{prop.representable_nt} defines a functor
\begin{equation} \label{eqn.yoneda_embedding}
\yon^-\colon\smset\op\to\smset^\smset
\end{equation}
by verifying functoriality, as follows.
\begin{enumerate}
\item Show that for any set $S$, the natural transformation $\yon^{\id_S}\colon\yon^S\to\yon^S$ is the identity.
\item Show that for functions $f\colon R\to S$ and $g\colon S\to T$, we have $\yon^g\then\yon^f=\yon^{f\then g}$. \qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item The fact that $\yon^{\id_S}\colon\yon^S\to\yon^S$ is the identity is just a generalization of \cref{exc.representable_nt_components} \cref{exc.representable_nt_components.id}.
For any set $X$, the $X$-component $X^{\id_S} \colon X^S \to X^S$ of $\yon^{\id_S}$ sends each $h \colon S \to X$ to $\id_S \then h = h$, so $X^{\id_S}$ is the identity natural transformation on $X^S$.
Hence $\yon^{\id_S}$ is the identity on $\yon^S$.
\item Fix $f \colon R \to S$ and $g \colon S \to T$; we wish to show that $\yon^g \then \yon^f = \yon^{f \then g}$.
It suffices to show componentwise that $X^g \then X^f = X^{f \then g}$ for every set $X$.
Indeed, $X^g$ sends each $h \colon T \to X$ to $g \then h$; then $X^f$ sends $g \then h$ to $f \then g \then h = X^{f \then g}(h)$.
\end{enumerate}
\end{solution}
\end{exercise}
We now have all the ingredients we need to state and prove the Yoneda lemma on the category of sets.
\index{Yoneda lemma}
\begin{lemma}[Yoneda lemma]\label{lemma.yoneda}
Given a functor $F\colon\smset\to\smset$ and a set $S$, there is an isomorphism
\begin{equation}\label{eqn.yoneda}
F(S)\iso\smset^\smset(\yon^S,F)
\end{equation}
where the right hand side is the set of natural transformations $\yon^S\to F$.
Moreover, \eqref{eqn.yoneda} is natural in both $S$ and $F$.
\end{lemma}
\begin{proof}[Proof]
Given a natural transformation $m\colon\yon^S\to F$, consider its $S$-component $m_S\colon S^S\to F(S)$.
Applying this function to $\id_S\in S^S$ yields an element $m_S(\id_S)\in F(S)$.
Conversely, given an element $a\in F(S)$, there is a natural transformation we denote by $m^a\colon\yon^S\to F$ whose $X$-component is the function $X^S\to F(X)$ that sends $g\colon S\to X$ to $F(g)(a)$.
In \cref{exc.finish_proof_yoneda} we ask you to show that this is indeed natural in $X$; that these two constructions, $m\mapsto m_S(\id_S)$ and $a\mapsto m^a$, are mutually inverse; and that the resulting isomorphism is natural.
\end{proof}
\index{natural transformation!and Yoneda embedding}
\begin{exercise}\label{exc.finish_proof_yoneda}
In this exercise, we fill in the details of the preceding proof.
\begin{enumerate}
\item Show that for any $a\in F(S)$, the maps $X^S\to F(X)$ defined in the proof of \cref{lemma.yoneda} are natural in $X$.
\item Show that the two mappings given in the proof of \cref{lemma.yoneda} are mutually inverse, thus defining the isomorphism \eqref{eqn.yoneda}.
\item Show that \eqref{eqn.yoneda} as defined is natural in $F$.
\item Show that \eqref{eqn.yoneda} as defined is natural in $S$.
\item \label{exc.finish_proof_yoneda.embed} As a corollary of \cref{lemma.yoneda}, show that the functor $\yon^-\colon\smset\op\to\smset^\smset$ from \eqref{eqn.yoneda_embedding} is fully faithful---in particular, there is an isomorphism $S^T\iso \smset^\smset(\yon^S,\yon^T)$ for sets $S,T$.
For this reason, we call $\yon^-$ the \emph{Yoneda embedding}.
\qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item To check that $X^S \to F(X)$ is natural in $X$, we verify that the naturality square
\[
\begin{tikzcd}[ampersand replacement=\&]
X^S\ar[r, "h^S"]\ar[d, "F(-)(a)"']\&
Y^S\ar[d, "F(-)(a)"]\\
F(X)\ar[r, "F(h)"']\&
F(Y)
\end{tikzcd}
\]
commutes for all $h \colon X \to Y$.
The top map $h^S$ sends any $g \colon S \to X$ to $g \then h$ (\cref{def.representable}), which is then sent to $F(g \then h)(a)$ by the right map.
Meanwhile, the left map sends $g$ to $F(g)(a)$, which is then sent to $F(h)(F(g)(a))$ by the bottom map.
So by the functoriality of $F$, the square commutes.
\item We show that the maps $m\mapsto m_S(\id_S)$ and $a\mapsto m^a$ defined in the proof of \cref{lemma.yoneda} are mutually inverse.
First, we show that for any natural transformation $m \colon \yon^S \to F$, we have $m^{m_S(\id_S)} = m$.
Given a set $X$, the $X$-component of $m^{m_S(\id_S)}$ sends each $g \colon S \to X$ to $F(g)(m_S(\id_S))$; it suffices to show that this is also where the $X$-component of $m$ sends $g$.
Indeed, by the naturality of $m$, the square
\[
\begin{tikzcd}[ampersand replacement=\&]
S^S\ar[r, "g^S"]\ar[d, "m_S"']\&
X^S\ar[d, "m_X"]\\
F(S)\ar[r, "F(g)"']\&
F(X)
\end{tikzcd}
\]
commutes, so in particular, following $\id_S\in S^S$ around this diagram, we have
\begin{equation} \label{eqn.finish_proof_yoneda}
F(g)(m_S(\id_S)) = m_X(g^S(\id_S)) = m_X(\id_S \then g) = m_X(g).
\end{equation}
In the other direction, we show that for any $a \in F(S)$, we have $m^a_S(\id_S) = a$: by construction, $m^a_S \colon S^S \to F(S)$ sends $\id_S$ to $F(\id_S)(a) = a$.
\item It suffices to show that given functors $F, G\colon\smset\to\smset$ and a natural transformation $\alpha \colon F \to G$, the naturality square
\[
\begin{tikzcd}[ampersand replacement=\&]
\smset^\smset(\yon^S,F)\ar[d, "- \then \alpha"']\ar[r, "\sim"]\&
F(S)\ar[d, "\alpha_S"]\\
\smset^\smset(\yon^S,G)\ar[r, "\sim"]\&
G(S)
\end{tikzcd}
\]
commutes.
The top map sends any $m \colon \yon^S \to F$ to $m_S(\id_S)$, which in turn is sent by the right map to $\alpha_S(m_S(\id_S)) = (m \then \alpha)_S(\id_S)$.
This is also where the bottom map sends $m \then \alpha$, so the square commutes.
\item It suffices to show that given a function $g \colon S \to X$, the naturality square
\[
\begin{tikzcd}[ampersand replacement=\&]
\smset^\smset(\yon^S,F)\ar[d, "\yon^g \then -"']\ar[r, "\sim"]\&
F(S)\ar[d, "F(g)"]\\
\smset^\smset(\yon^X,F)\ar[r, "\sim"]\&
F(X)
\end{tikzcd}
\]
commutes.
The left map sends any $m \colon \yon^S \to F$ to $\yon^g \then m$, which is sent by the bottom map to $(\yon^g \then m)_X(\id_X) = m_X(X^g(\id_X)) = m_X(g \then \id_X) = m_X(g)$.
Meanwhile, the top map sends $m$ to $m_S(\id_S)$, which is sent by the right map to $F(g)(m_S(\id_S))$.
So the square commutes by \eqref{eqn.finish_proof_yoneda}.
\item To show that $\smset^\smset(\yon^S, \yon^T) \iso S^T$, just take $F\coloneqq\yon^T$ in \cref{lemma.yoneda} so that $F(S)\iso S^T$.
\end{enumerate}
\end{solution}
\end{exercise}
\index{functor!representable|)}
How will we go from these representable functors to polynomial ones?%
\index{polynomial functor}
Recall that, in algebra, a polynomial is just a sum of pure powers.
So we will define a \emph{polynomial functor} $\smset\to\smset$ to be a sum of pure power functors---that is, the representable functors $\yon^A$ for each set $A$ we just introduced.%
\footnote{This analogy isn't perfect: in algebra, polynomials are generally finite sums of pure powers, whereas our polynomial functors may be infinite sums of representables.
However, we are not the first to use the term ``polynomial'' this way, and the name stuck.}
All of our polynomials will be in one variable, $\yon$.
Every other letter or number that shows up in our notation for a polynomial will denote a set.
For example, in the polynomial
\begin{equation} \label{eqn.biz_poly}
\rr\yon^\zz+\3\yon^{\3}+\yon^A+\sum_{i\in I}\yon^{R_i+Q_i^\2},
\end{equation}
$\rr$ denotes the set of real numbers, $\zz$ denotes the set of integers, $\2$ and $\3$ respectively denote the sets $\{1,2\}$ and $\{1,2,3\}$, and $A$, $I$, $Q_i$, and $R_i$ denote arbitrary sets.
To make sense of these polynomials, we need to define functor addition,%
\index{functor!sum of functors}
\index{functor!product of functors}
\index{polynomial functor!sum of polynomials}
\index{polynomial functor!product of polynomials}\index{product|seealso{polynomial functor, product of polynomials}}
both in the binary case (i.e.\ what is $\yon^A+\yon^B$?) and more generally over arbitrary sets (i.e.\ what is $\sum_{i\in I}\yon^{A_i}$?).
This will allow us to interpret polynomials like \eqref{eqn.biz_poly}.
In particular, just as $3y^3=y^3+y^3+y^3$ in algebra, the summand $\3\yon^\3$ of \eqref{eqn.biz_poly} denotes the sum of representables $\yon^\3+\yon^\3+\yon^\3$, while the summand $\rr\yon^\zz$ denotes the sum over $\rr$ of copies of $\yon^\zz$.
While polynomial functors will be defined as sums, products of polynomials will turn out to be polynomials as well, again mimicking polynomials in algebra.
To make sense of these products, we will also define functor multiplication.
The construction of sums and products of functors $\smset\to\smset$ will rely on the construction of sets and products of sets themselves.
%-------- Section --------%
\section{Sums and products of sets} \label{sec.poly.rep-sets.sum-prod-set}
\index{set!sum of sets}
\index{set!product of sets}
\index{set!indexing}\index{category!discrete}\index{indexed set}
Let $I$ be a set, and let $X_i$ be a set for each $i\in I$.
Classically, we may denote this \emph{$I$-indexed family of sets} by $(X_i)_{i\in I}$.
Categorically, we may view this data as a specific kind of functor: if we identify the set $I$ with the \emph{discrete category} on $I$, whose objects are the elements of $I$ and whose morphisms are all identities, then $(X_i)_{i\in I}$ can be identified with a functor $X\colon I\to\smset$ with $X(i)\coloneqq X_i$.
\index{indexed family of objects}
To compromise, we will denote an indexed family of sets by $X\colon I\to\smset$ for a set $I$ viewed as a discrete category (although we will occasionally use the classical notation when convenient), but denote the set obtained by evaluating $X$ at each $i\in I$ by $X_i$ rather than $X(i)$.
To pick out an element of one of the sets in the indexed family $X\colon I\to\smset$, we need to specify both an index $i\in I$ and an element $x\in X_i$.
We call the set of such pairs $(i,x)$ the \emph{sum} of this indexed family, as below.
\begin{definition}[Sum of sets] \label{def.sum_sets}
Let $I$ be a set and $X\colon I\to\smset$ be an $I$-indexed family of sets.
The \emph{sum $\sum_{i\in I}X_i$ of the indexed family $X$} is the set
\[
\sum_{i\in I}X_i\coloneqq\{(i,x)\mid i\in I\text{ and }x\in X_i\}.
\]
When $I\coloneqq\{i_1,\ldots,i_n\}$ is finite, we may alternatively denote this sum as
\[
X_{i_1}+\cdots+X_{i_n}.
\]
\end{definition}
\index{element!of a sum of sets}
\index{element!of a product of sets}
\index{dependent function}\index{indexed set}
Say instead we pick an element from \emph{every} set in the indexed family: that is, we construct an assignment $i\mapsto x_i$, where each $x_i\in X_i$.
If every $X_i$ were the same set $X$, then this would just be a function $I\to X$.
More generally, this assignment is what we call a \emph{dependent function}: its codomain $X_i$ \emph{depends} on its input $i$.
\index{dependent function}
We write the signature of such a dependent function as
\[
f \colon (i \in I) \to X_i.
\]
Note that the indexed family of sets $X\colon I\to\smset$ completely determines this signature.
The set of all dependent functions whose signature is determined by a given indexed family of sets is the \emph{product} of that indexed family, as below.
\begin{definition}[Product of sets] \label{def.prod_sets}
Let $I$ be a set and $X\colon I\to\smset$ be an $I$-indexed family of sets.
The \emph{product $\prod_{i\in I}X_i$ of the indexed family $X$} is the set of dependent functions
\[
\prod_{i\in I}X_i\coloneqq\{f \colon (i \in I) \to X_i\}.
\]
When $I\coloneqq\{i_1,\ldots,i_n\}$ is finite, we may alternatively denote this product as
\[
X_{i_1}\times\cdots\times X_{i_n} \qqor X_{i_1}\cdots X_{i_n}.
\]
\end{definition}\index{dependent function}
For a dependent function $f\colon(i\in I)\to X_i$, we may denote the element of $X_i$ that $f$ assigns to $i\in I$ by $f(i), fi,$ or $f_i$.
When $I\coloneqq\{i_1,\ldots,i_n\}$ is finite, we may identify $f$ with the $n$-tuple $(f(i_1),\ldots,f(i_n))$; similarly, when $I\coloneqq\nn$, we may identify $f$ with the infinite sequence $(f_0,f_1,f_2,\ldots)$.
\index{set!cardinality of}
\begin{example}\label{ex.two_sums_and_prods}
If $I\coloneqq\2=\{1,2\}$, then an $I$-indexed family $X\colon I\to \smset$ consists of two sets---say $X_1\coloneqq\{a,b,c\}$ and $X_2\coloneqq\{c,d\}$.
Their sum is then the disjoint union
\[
\sum_{i\in \2}X_i=X_1+X_2=\{(1,a),(1,b),(1,c),(2,c),(2,d)\}.
\]
The cardinality\footnote{The \emph{cardinality} of a set is the number of elements it contains, at least when the set is finite; with care the notion can be extended to infinite sets as well.} of $X_1+X_2$ will always be the sum of the cardinalities of $X_1$ and $X_2$, justifying the use of the word ``sum.''
Meanwhile, their product is the usual cartesian product
\index{cartesian product|see{product}}\index{product}
\[\prod_{i\in \2}X_i \cong X_1\times X_2=\{(a,c),(a,d),(b,c),(b,d),(c,c),(c,d)\}.\]
The cardinality of $X_1\times X_2$ will always be the product of the cardinalities of $X_1$ and $X_2$, justifying the use of the word ``product.''
\end{example}
\begin{exercise}\label{exc.on_sums_prods_sets}\index{indexed set}
Let $I$ be a set.
\begin{enumerate}
\item \label{exc.on_sums_prods_sets.sum} Show that there is an isomorphism of sets $I\iso\sum_{i\in I}\1$.
\item \label{exc.on_sums_prods_sets.prod} Show that there is an isomorphism of sets $\1\iso\prod_{i\in I}\1$.
\end{enumerate}
As a special case, suppose that $I\coloneqq\0=\varnothing$ and that $X\colon \varnothing\to\smset$ is the unique empty indexed family of sets.
\begin{enumerate}[resume]
\item Is it true that $X_i=\1$ for each $i\in I$?
\item Justify the statement ``the empty sum is $\0$'' by showing that there is an isomorphism of sets $\sum_{i\in\varnothing}X_i\iso\0$.
\item Justify the statement ``the empty product is $\1$'' by showing that there is an isomorphism of sets $\prod_{i\in\varnothing}X_i\iso\1$.
\qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item \label{sol.on_sums_prods_sets.sum}
To show that $I\iso\sum_{i \in I}\1$, observe that $x \in \1 = \{1\}$ if and only if $x = 1$, so $\sum_{i \in I} \1 = \{(i, 1) \mid i \in I\}$.
Then the function $I \to \sum_{i \in I} \1$ that sends each $i \in I$ to $(i, 1)$ is clearly an isomorphism.
\item \label{sol.on_sums_prods_sets.prod}
To show that $\1 \iso \prod_{i \in I} \1$, it suffices to show that there is a unique dependent function $f \colon (i \in I) \to \1$.
As $\1 = \{1\}$, such a function $f$ must always send $i \in I$ to $1$.
This uniquely characterizes $f$, so there is indeed only one such dependent function.
\item \label{sol.on_sums_prods_sets.vac} Yes: since $I$ is empty, there are no $i \in I$.
So it is true that $X_i = 1$ holds whenever $i \in I$ holds, because $i \in I$ never holds.
We say that this sort of statement is \emph{vacuously true}.
\item As $I = \0 = \varnothing$, we have $\sum_{i\in\varnothing}X_i = \sum_{i\in I}\1 \iso I = \0$, where the equation on the left follows from \cref{sol.on_sums_prods_sets.vac} and the isomorphism in the middle follows from \cref{sol.on_sums_prods_sets.sum}.
\item As $I = \varnothing$, we have $\prod_{i\in\varnothing}X_i = \prod_{i\in I}\1 \iso \1$, where the equation on the left follows from \cref{sol.on_sums_prods_sets.vac} and the isomorphism on the right follows from \cref{sol.on_sums_prods_sets.prod}.
\end{enumerate}
\end{solution}
\end{exercise}
The following standard fact describes the constructions from \cref{def.sum_sets,def.prod_sets} categorically and further justifies why we call them sums and products.
\index{product}
\index{coproduct}
\index{diagram}
\begin{proposition} \label{prop.set_prod_coprod}\index{functor!set-valued}
Let $I$ be a set and $X\colon I\to\smset$ be an $I$-indexed family of sets. Then the sum $\sum_{i\in I}X_i$ is the categorical coproduct of these sets in $\smset$ (i.e.\ the colimit of the functor $X\colon I\to\smset$, viewed as a diagram), and the product $\prod_{i\in I}X_i$ is the categorical product of these sets in $\smset$ (i.e.\ the limit of the functor $X\colon I\to\smset$, viewed as a diagram).
\end{proposition}
\index{coproduct!inclusion map into}
\index{coproduct!universal property of}
\index{product!projection map out of}
\index{product!universal property of}\index{colimit}
\begin{proof}
The sum $\sum_{i\in I}X_i$ comes equipped with an inclusion $\iota_j\colon X_j\to\sum_{i\in I}X_i$ for each $j\in I$ given by $x\mapsto(j,x)$.
The product $\prod_{i\in I}X_i$ comes equipped with a projection $\pi_j\colon\prod_{i\in I}X_i\to X_j$ for each $j\in I$ sending each $f\colon(i\in I)\to X_i$ to $f(j)$.
These satisfy the universal properties for categorical coproducts and products, respectively; see \cref{exc.set_prod_coprod}.
\end{proof}
\begin{exercise} \label{exc.set_prod_coprod}
\begin{enumerate}
\item Show that $\sum_{i\in I}X_i$ along with the inclusions $\iota_j\colon X_j\to\sum_{i\in I}X_i$ described in the proof of \cref{prop.set_prod_coprod} satisfy the universal property of a categorical coproduct: for any set $Y$ with functions $g_j\colon X_j\to Y$ for each $j\in I$, there exists a unique function $h\colon\sum_{i\in I}X_i\to Y$ for which $\iota_j\then h=g_j$ for all $j\in I$.
\item Show that $\prod_{i\in I}X_i$ along with the projections $\pi_j\colon\prod_{i\in I}X_i\to X_j$ described in the proof of \cref{prop.set_prod_coprod} satisfy the universal property of a categorical product: for any set $Y$ with functions $g_j\colon Y\to X_j$ for each $j\in I$, there exists a unique function $h\colon Y\to\prod_{i\in I}X_i$ for which $h\then\pi_j=g_j$ for all $j\in I$. \qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item Any function $h\colon\sum_{i\in I}X_i\to Y$ for which $\iota_j\then h=g_j$ for all $j\in I$ must satisfy $h(j,x)=h(\iota_j(x))=g_j(x)$ for all $j\in I$ and $x\in X_j$.
This uniquely characterizes $h$, so if we define $h(j,x)\coloneqq g_j(x)$ we are done.
\item Any function $h\colon Y\to\prod_{i\in I}X_i$ for which $h\then\pi_j=g_j$ for all $j\in I$ must satisfy $h(y)_j=\pi_j(h(y))=g_j(y)$ for all $y\in Y$ and $j\in I$.
This uniquely characterizes $h(y)$ and thus $h$, so if we define $h(y)\colon(i\in I)\to X_i$ to be the dependent function given by $i\mapsto g_i(y)$ we are done.
\end{enumerate}
\end{solution}
\end{exercise}
Though we proved above explicitly that $\smset$ has all small products and coproducts, from here on out, we will assume the standard categorical fact that $\smset$ is complete (has all small limits) and cocomplete (has all small colimits). % TODO: add ref for this??
\index{limit}
\index{colimit}
We have constructed categorical sums and products of sets, but we can also construct categorical sums and products of the maps between them: functions.
\index{coproduct!of functions}
\index{product!of functions}
\begin{definition}[Categorical sum and product of functions] \label{def.sum-prod-func}
Let $I$ be a set and $X,Y\colon I\to\smset$ be $I$-indexed families of sets.
Given a natural transformation $f\colon X\to Y$, i.e.\ an $I$-indexed family of functions $(f_i\colon X_i\to Y_i)_{i\in I}$, its \emph{categorical sum} (or \emph{coproduct}) is the function
\[
\sum_{i\in I}f_i\colon\sum_{i\in I}X_i\to\sum_{i\in I}Y_i
\]
that, given $i\in I$ and $x\in X_i$, sends $(i,x)\mapsto(i,f_i(x))$; while its \emph{categorical product} is the function
\[
\prod_{i\in I}f_i\colon\prod_{i\in I}X_i\to\prod_{i\in I}Y_i
\]
that sends each $g\colon(i\in I)\to X_i$ to the \emph{composite dependent function} $(i\in I)\to Y_i$, denoted $g\then f$ or $f\circ g$, which sends $i\in I$ to $f_i(g(i))$.
When $I\coloneqq\{i_1,\ldots,i_n\}$ is finite, we may alternatively denote this categorical sum and product of functions respectively as\footnote{We will take care to highlight when this notation may clash with a sum (resp.\ product) of functions with common domain and codomain whose codomain has an additive (resp.\ multiplicative) structure.}
\[
f_{i_1}+\cdots+f_{i_n} \qqand f_{i_1}\times\cdots\times f_{i_n}.
\]
\end{definition}
\begin{exercise} \label{exc.sum-prod-func}
\begin{enumerate}
\item Show that the categorical sum of functions is the one induced by the universal property of the categorical sum of sets.
That is, given a set $I$, two $I$-indexed families of sets $X,Y\colon I\to\smset$, and a natural transformation $f\colon X\to Y$, the function $\sum_{i\in I}f_i\colon\sum_{i\in I}X_i\to\sum_{i\in I}Y_i$ that we called the categorical sum is induced by the following composite maps for $j\in I$:
\[
X_j\To{f_j}Y_j\To{\iota'_j}\sum_{i\in I}Y_i,
\]
where $\iota'_j$ is the inclusion.
It then follows by a standard categorical argument that the sum is functorial, i.e.\ that the sum of identities is an identity and that the sum of composites is the composite of sums.
\item Similarly, show that the categorical product of functions is the one induced by the universal property of the categorical product of sets.
That is, given the same setup as the previous part, the function $\prod_{i\in I}f_i\colon\prod_{i\in I}X_i\to\prod_{i\in I}Y_i$ that we called the categorical product is induced by the following composite maps for $j\in J$:
\[
\prod_{i\in I}X_i\To{\pi_j}X_j\To{f_j}Y_j.
\]
Again, this implies that the product is functorial. \qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item It suffices to show that the following square, where the vertical maps are the inclusions, commutes for all $j\in I$:
\[
\begin{tikzcd}[column sep=large]
X_j \ar[d, "\iota_j"] \ar[r, "f_j"] & Y_j \ar[d, "\iota'_j"] \\
\sum_{i\in I}X_i \ar[r, "\sum_{i\in I}f_i"] & \sum_{i\in I}Y_i
\end{tikzcd}
\]
Given $x\in X_j$, the left inclusion map sends $x$ to $(j,x)$, which the bottom sum of maps sends to $(j,f_j(x))$.
Meanwhile, the top map sends $x$ to $f_j(x)$, which the right inclusion map again sends to $(j,f_j(x))$.
\item It suffices to show that the following square, where the vertical maps are the projections, commutes for all $j\in I$:
\[
\begin{tikzcd}[column sep=large]
\prod_{i\in I}X_i \ar[d, "\pi_j"] \ar[r, "\prod_{i\in I}f_i"] & \prod_{i\in I}Y_i \ar[d, "\pi'_j"] \\
X_j \ar[r, "f_j"] & Y_j
\end{tikzcd}
\]
Given $g\colon(i\in I)\to X_i$ in $\prod_{i\in I}X_i$, the top product of maps sends $g$ to $f\circ g$, which the right projection map sends to $f_j(g(j))$.
Meanwhile, the left projection map sends $g$ to $g(j)$, which the bottom map again sends to $f_j(g(j))$.
\end{enumerate}
\end{solution}
\end{exercise}
We now highlight some tools and techniques to help us work with sum and product sets.
\begin{exercise}\label{exc.product_as_sections}
Let $I$ be a set and $X \colon I \to \smset$ be an indexed family.
There is a
projection function
$\pi_1 \colon \sum_{i \in I} X_i \to I$
defined by $\pi_1(i, x) \coloneqq i$.
\begin{enumerate}
\item What is the signature of the second projection $\pi_2(i, x) \coloneqq x$?
(Hint: it's a dependent function.)
\item A \emph{section} of a function $r \colon A \to B$ is a function $s \colon B \to A$ such that $s \then r = \id_B$.
Show that the product of the indexed family is isomorphic to the set of sections of $\pi_1$:
\[\prod_{i \in I} X_i \cong \left\{s \colon I \to \sum_{i \in I} X_i \,\middle|\, s \then \pi_1 = \id_I\right\}.\]
\qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item The second projection $\pi_2(i, x) = x$ sends each pair $p \coloneqq (i, x) \in \sum_{i \in I} X_i$ to $x$, an element of $X_i$.
Note that we can write $i$ in terms of $p$ as $\pi_1(p)$.
This allows us to write the signature of $\pi_2$ as $\pi_2 \colon (p \in \sum_{i \in I} X_i) \to X_{\pi_1(p)}$.
\item Let $S := \{s \colon I \to \sum_{i \in I} X_i \mid s \then \pi_1 = \id_I\}$ be the set of sections of $\pi_1$. To show that $\prod_{i \in I} X_i \cong S$, we will exhibit maps in either direction and show that they are mutually inverse.
For each $f \colon (i \in I) \to X_i$ in $\prod_{i \in I} X_i$, we have $f(i) \in X_i$ for $i \in I$, so we can define a function $s_f \colon I \to \sum_{i \in I} X_i$ that sends $i\mapsto(i, f(i))$.
Then $\pi_1(s_f(i)) = \pi_1(i, f(i)) = i$, so $s_f$ is a section of $\pi_1$.
Hence $f \mapsto s_f$ is a map $\prod_{i \in I} X_i \to S$.
In the other direction, for each section $s \colon I \to \sum_{i \in I} X_i$ we have $\pi_1(s(i)) = i$ for $i \in I$, so we can write $s(i)$ as an ordered pair $(i, \pi_2(s(i)))$ with $\pi_2(s(i)) \in X_i$.
Hence we can define a dependent function $f_s \colon (i \in I) \to X_i$ sending $i\mapsto\pi_2(s(i))$.
Then $s \mapsto f_s$ is a map $S \to \prod_{i \in I} X_i$.
By construction $s_{f_s}(i) = (i, f_s(i)) = (\pi_1(s(i)), \pi_2(s(i))) = s(i)$ and $f_{s_f}(i) = \pi_2(s_f(i)) = \pi_2(i, f(i)) = f(i)$, so these maps are mutually inverse.
\end{enumerate}
\end{solution}
\end{exercise}\index{dependent function}
A helpful way to think about sum or product sets is to consider what choices must be made to specify an element of such a set.
In the following examples, say that we have a set $I$ and an $I$-indexed family $X \colon I \to \smset$.
Below, we give the instructions for choosing an element of $\sum_{i \in I} X_i$.
\begin{quote}
To choose an element of $\sum_{i \in I} X_i$:
\begin{enumerate}
\item choose an element $i \in I$;
\item choose an element of $X_i$.
\end{enumerate}
\end{quote}
\index{element!of a dependent sum}
Then the projection $\pi_1$ from \cref{exc.product_as_sections} sends each element of $\sum_{i \in I} X_i$ to the element of $i \in I$ chosen in step 1, while the projection $\pi_2$ sends each element of $\sum_{i \in I} X_i$ to the element of $X_i$ chosen in step 2.
Next, we give the instructions for choosing an element of $\prod_{i \in I} X_i$.
\begin{quote}
To choose an element of $\prod_{i \in I} X_i$:
\begin{enumerate}
\item for each element $i \in I$:
\begin{enumerate}[label*=\arabic*.]
\item choose an element of $X_i$.
\end{enumerate}
\end{enumerate}
\end{quote}
\index{element!of a dependent product}
\index{element!of a nested dependent set}
Armed with these interpretations, we can tackle more complicated expressions, including those with nested $\sum$'s and $\prod$'s such as
\begin{equation}\label{eqn.sum_prod_sum}
A \coloneqq \sum_{i\in I}\prod_{j\in J(i)}\sum_{k\in K(i,j)}X(i,j,k).
\end{equation}
The instructions for choosing an element of $A$ form a nested list, as follows.
\begin{quote}
To choose an element of $A$:
\begin{enumerate}
\item choose an element $i \in I$;
\item for each element $j \in J(i)$:
\begin{enumerate}[label*=\arabic*.]
\item choose an element $k \in K(i,j)$;
\item choose an element of $X(i,j,k)$.
\end{enumerate}
\end{enumerate}
\end{quote}
Here the choice of $k\in K(i,j)$ may depend on $i$ and $j$: different values of $i$ and $j$ may lead to different sets $K(i,j)$.
By describing $A$ like this, we see that each $a \in A$ can be projected to an element $i\coloneqq\pi_1(a) \in I$, chosen in step 1, and a dependent function $\pi_2(a)$, chosen in step 2.
This dependent function in turn sends each $j \in J(i)$ to a pair that can be projected to an element $k\coloneqq\pi_1(\pi_2(a)(j)) \in K(i, j)$ chosen in step 2.1 and an element $\pi_2(\pi_2(a)(j)) \in X(i,j,k)$ chosen in step 2.2.
\begin{example}%[Notation for $\sum\prod$ stuff]
\label{ex.notation_sum_prod}
% Here we give notation for the elements of a set involving $\sum$'s and $\prod$'s such as that in \eqref{eqn.sum_prod_sum}.
Let $I\coloneqq\{1,2\}$; let $J(1)\coloneqq\{j\}$ and $J(2)\coloneqq\{j,j'\}$; let $K(1,j)\coloneqq\{k_1,k_2\}$, $K(2,j)\coloneqq\{k_1\}$, and $K(2,j')\coloneqq\{k'\}$; and let $X(i,j,k)\coloneqq\{x,y\}$ for all $i,j,k$. Now the formula
\[\sum_{i\in I}\prod_{j\in J(i)}\sum_{k\in K(i,j)}X(i,j,k)\]
from \eqref{eqn.sum_prod_sum} specifies a fixed set. Here is a list of all eight of its elements:
\[
\left\{
\begin{gathered}
\big(1, j\mapsto(k_1,x)\big),\qquad
\big(1, j\mapsto(k_1,y)\big),\qquad
\big(1, j\mapsto(k_2,x)\big),\qquad
\big(1, j\mapsto(k_2,y)\big),\\
\big(2, j\mapsto(k_1,x), j'\mapsto(k',x)\big),\qquad
\big(2, j\mapsto(k_1,x), j'\mapsto(k',y)\big),\\
\big(2, j\mapsto(k_1,y), j'\mapsto(k',x)\big),\qquad
\big(2, j\mapsto(k_1,y), j'\mapsto(k',y)\big)
\end{gathered}
\right\}
\]
In each case, we first chose an element $i\in I$, either 1 or 2. Then for each $j\in J(i)$ we chose an element $k\in K(i,j)$ and an element of $X(i,j,k)$.
\end{example}
\begin{exercise}
Consider the set
\begin{equation}\label{eqn.prod_sum_prod}B \coloneqq \prod_{i\in I}\sum_{j\in J(i)}\prod_{k\in K(i,j)}X(i,j,k).\end{equation}
\begin{enumerate}
\item Give the instructions for choosing an element of $B$ as a nested list, like we did for $A$ just below \eqref{eqn.sum_prod_sum}.
\item With $I$, $J$, $K$, and $X$ as in \cref{ex.notation_sum_prod}, how many elements are in $B$?
\item Write out three of these elements in the style of \cref{ex.notation_sum_prod}.
\qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item Here are the instructions for choosing an element of $B$ as a nested list.
\begin{quote}
To choose an element of $B$:
\begin{enumerate}[label=\arabic*.]
\item for each element $i \in I$:
\begin{enumerate}[label*=\arabic*.]
\item choose an element $j \in J(i)$;
\item for each element $k \in K(i, j)$:
\begin{enumerate}[label*=\arabic*.]
\item choose an element of $X(i,j,k)$.
\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{quote}
\item Given $I\coloneqq\{1,2\}$, $J(1)\coloneqq\{j\}$, $J(2)\coloneqq\{j,j'\}$, $K(1,j)\coloneqq\{k_1,k_2\}$, $K(2,j)\coloneqq\{k_1\}$, $K(2,j')\coloneqq\{k'\}$, and $X(i,j,k)\coloneqq\{x,y\}$ for all $i,j,k$, our goal is to count the number of elements in $B$.
To compute the cardinality of $B$, we can use the fact that the cardinality of a sum (resp.\ product) is the sum (resp.\ product) of the cardinalities of the summands (resp.\ factors).
So
\begin{align*}
|B| &= \prod_{i\in I}\sum_{j\in J(i)}\prod_{k\in K(i,j)}|X(i,j,k)| \\
&= \prod_{i\in \{1,2\}}\sum_{j\in J(i)}\prod_{k\in K(i,j)}2 \\
&= \left(\sum_{j\in J(1)} 2^{|K(1,j)|}\right)\left(\sum_{j\in J(2)} 2^{|K(2,j)|}\right) \\
&= \left(2^2\right)\left(2^1 + 2^1\right) = 16.
\end{align*}
\item Here are three of the elements of $B$ (you may have written down others):
\begin{itemize}
\item $(1 \mapsto (j, k_1 \mapsto x, k_2 \mapsto y), 2 \mapsto (j', k' \mapsto x))$
\item $(1 \mapsto (j, k_1 \mapsto y, k_2 \mapsto y), 2 \mapsto (j, k_1 \mapsto y))$
\item $(1 \mapsto (j, k_1 \mapsto y, k_2 \mapsto x), 2 \mapsto (j', k' \mapsto y))$
\end{itemize}
\qedhere
\end{enumerate}
\end{solution}
\end{exercise}
%Henceforth, we will omit the full sequence of nested instructions corresponding to every sum or product of sets; we will assume you can read them for yourself.
%-------- Subsection --------%
\section{Expanding products of sums} \label{sec.poly.rep-sets.expand}
\index{type theoretic axiom of choice}
\index{distributive law}
We will often encounter sums of sets nested within products, as in \eqref{eqn.sum_prod_sum} and \eqref{eqn.prod_sum_prod}.
The following proposition helps us work with these; it is sometimes called the \emph{type-theoretic axiom of choice}, but it is perhaps more familiar as a set-theoretic analogue of the \emph{distributive property} of multiplication over addition.
While the identity may look foreign, it captures for sets the same process that you would use to multiply multi-digit numbers from grade school arithmetic or polynomials from high school algebra.
\begin{proposition}[Pushing $\prod$ past $\sum$]\label{prop.push_prod_sum_set}
For any sets $I,(J(i))_{i\in I},$ and $(X(i,j))_{i\in I, j\in J(i)}$, we have a natural isomorphism\index{isomorphism!natural}
\begin{equation}\label{eqn.set_completely_distributive}
\prod_{i\in I}\sum_{j\in J(i)}X(i,j)
\iso
\sum_{\bar{j}\in \prod_{i\in I}J(i)}\;\prod_{i\in I}X(i,\bar{j}(i)).\footnote{We draw a bar over $j$ in $\bar{j}$ to remind ourselves that $\bar{j}$ is no longer just an index but a (dependent) function.}
\end{equation}
\end{proposition}
\begin{proof}
First, we construct a map from the left hand set to the right. An element of the set on the left is a dependent function $f \colon (i \in I) \to \sum_{j \in J(i)} X(i, j)$, which we can compose with projections from its codomain to yield $\pi_1(f(i)) \in J(i)$ and $\pi_2(f(i)) \in X(i, \pi_1(f(i)))$ for every $i \in I$.
We can then form the following pair:\footnote{We omit parentheses for function application here and throughout the text for compactness whenever the meaning is clear.}
\[
(i \mapsto \pi_1 fi, i \mapsto \pi_2 fi).
\]
This is an element of the right hand set, because $i \mapsto \pi_1 fi$ is a dependent function in $\prod_{i\in I}J(i)$ and $i \mapsto \pi_2 fi$ is a dependent function in $\prod_{i\in I}X(i,\pi_1 fi)$.
Now we go from right to left.
An element of the right hand set is a pair of dependent functions, $\bar{j} \colon (i \in I) \to J(i)$ and $g \colon
(i \in I) \to X(i, \bar{j}i)$.
We map this pair to the following element of the left hand set, a dependent function $(i\in I)\to\sum_{j\in J(i)}X(i,j)$:
\[
i \mapsto (\bar{j}i, gi).
\]
Finally, we verify that the maps are mutually inverse.
An element $(\bar{j}, g)$ of the right hand set is sent by one map and then the other to the pair
\[
(i \mapsto \pi_1(\bar{j}i, gi), i \mapsto \pi_2(\bar{j}i, gi))=(i \mapsto \bar{j}i, i \mapsto gi)=(\bar{j},g)
\]
Meanwhile, an element $f$ of the left hand set is sent by one map and then the other to the dependent function
\[
i \mapsto (\pi_1 fi, \pi_2 fi).
\]
As $fi$ is a pair whose components are $\pi_1 fi$ and $\pi_2 fi$, the dependent function above is precisely $f$.
\end{proof}
When $J(i)=J$ does not depend on $i\in I$, we can simplify the formula in \eqref{eqn.set_completely_distributive}.
\begin{corollary} \label{cor.push_prod_sum_set_indep}
For any sets $I, J,$ and $(X(i, j))_{i \in I, j \in J}$, we have a natural isomorphism\index{isomorphism!natural}
\begin{equation} \label{eqn.push_prod_sum_set_indep}
\prod_{i\in I}\sum_{j\in J}X(i,j)\cong\sum_{\bar{j}\colon I\to J}\prod_{i\in I}X(i,\bar{j}i),
\end{equation}
where $\bar{j}$ ranges over all (standard, non-dependent) functions $I\to J$.
\end{corollary}
\begin{proof}
Take $J(i)\coloneqq J$ for all $i \in I$ in \eqref{eqn.set_completely_distributive}.
Then the set $\prod_{i\in I}J(i)$ becomes $\prod_{i\in I}J$ (which we may denote in exponential form by $J^I$); its elements, dependent functions $\bar{j}\colon(i\in I)\to J(i)=J$, become standard functions $\bar{j}\colon I\to J$.
\end{proof}
It turns out that being able to push $\prod$ past $\sum$ as in \eqref{eqn.set_completely_distributive} is not a property that is unique to sets.
In general, we refer to a category having this property as follows.
\begin{definition}[Completely distributive category]\index{coproduct}\index{product}
A category $\Cat{C}$ with all small products and coproducts is \emph{completely distributive}\footnote{While our terminology generalizes that of a completely distributive lattice, which has the additional requirement that the category be a poset, it is unfortunately not standard: a completely distributive category refers to a different concept in some categorical literature. We will not use this other concept, so there is no ambiguity.} if products distribute over coproducts as in \eqref{eqn.set_completely_distributive}; that is, for any set $I$, sets $(J(i))_{i\in I}$, and objects $(X(i,j))_{i\in I,j\in J(i)}$ from $\Cat{C}$, we have a natural isomorphism\index{isomorphism!natural}
\begin{equation}\label{eqn.cat_completely_distributive}
\prod_{i\in I}\sum_{j\in J(i)}X(i,j)
\iso
\sum_{\bar{j}\in \prod_{i\in I}J(i)}\;\prod_{i\in I}X(i,\bar{j}i).
\end{equation}
\end{definition}
The term ``completely distributive'' comes from lattice theory. As such it is consistent with two different extensions to categories that may not be posets. We use it to mean that the category has all sums and products and that products distribute over sums. Other authors use it to mean that the category has all colimits and limits and a sort of distributivity between them.
\index{completely distributive category}
So \cref{prop.push_prod_sum_set} states that $\smset$ is completely distributive.
Once we define the category of polynomial functors, we will see that it, too, is completely distributive.
\index{completely distributive category!$\poly$ as}
\index{completely distributive category!$\smset$ as}
\cref{cor.push_prod_sum_set_indep} generalizes to all completely distributive categories as well; we state this formally below.
\begin{corollary} \label{cor.push_prod_sum_obj_indep}
Let $\Cat{C}$ be a completely distributive category.
For any sets $I$ and $J$ and objects $(X(i, j))_{i \in I, j \in J}$ in $\Cat{C}$, we have a natural isomorphism\index{isomorphism!natural}
\begin{equation} \label{eqn.push_prod_sum_obj_indep}
\prod_{i\in I}\sum_{j\in J}X(i,j)\iso\sum_{\bar{j}\colon I\to J}\prod_{i\in I}X(i,\bar{j}i).
\end{equation}
\end{corollary}
\begin{proof}
Again, take $J(i)\coloneqq J$ for all $i \in I$ in \eqref{eqn.cat_completely_distributive}.
\end{proof}
\index{completely distributive category!distributive law in|see{distributive law}}
\index{distributive law}
\begin{exercise}
Let $\Cat{C}$ be a completely distributive category.
How is the usual distributive law
\[
X\times(Y+Z)\iso X\times Y+X\times Z
\]
for $X,Y,Z\in\cat{C}$ a special case of \eqref{eqn.cat_completely_distributive}?
\begin{solution}
We wish to show that $X\times (Y+Z)\iso X\times Y+X\times Z$ using \eqref{eqn.cat_completely_distributive}.
On the left hand side, we are taking a $2$-fold product: a single object times a $2$-fold sum.
So we should let $I\coloneqq\2$ and let $J(1)\coloneqq\1$, with $X(1,1)\coloneqq X$; and $J(2)\coloneqq\2$, with $X(2,1)\coloneqq Y$ and $X(2,2)\coloneqq Z$.
Then
\[
X\times(Y+Z)\iso \prod_{i\in\2}\sum_{j\in J(i)}X(i,j) \iso \sum_{\bar{j}\in\prod_{i\in\2}J(i)}\;\prod_{i\in \2}X(i,\bar{j}(i)) \iso \sum_{\bar{j}\in\prod_{i\in\2}J(i)}X(1,\bar{j}(1))\times X(2,\bar{j}(2)),
\]
where the middle isomorphism follows from \eqref{eqn.cat_completely_distributive}.
The set $\prod_{i\in\2}J(i)$ contains two functions: $(1\mapsto1,2\mapsto1)$ and $(1\mapsto1,2\mapsto2)$.
So we can rewrite the right hand side as
\[
X(1,1)\times X(2,1)+X(1,1)\times X(2,2)\iso X\times Y+X\times Z.
\]
\end{solution}
\end{exercise}
Throughout this book, such as in the exercise below, you will see expressions consisting of alternating products and sums.
Using \eqref{eqn.cat_completely_distributive}, you can always rewrite such an expression as a sum of products, in which every $\sum$ appears before every $\prod$.\footnote{When an expression is written so that every $\sum$ appears before every $\prod$, it is said to be in \emph{disjunctive normal form}.}
This is analogous to how products of sums in high school algebra can always be expanded into sums of products via the distributive property.
\index{disjunctive normal form}
\begin{exercise} \label{exc.push_prod_sum_set}
Let $I, (J(i))_{i\in I},$ and $(K(i,j))_{(i,j)\in IJ}$ be sets, and for each $(i,j,k)\in IJK$, let $X(i,j,k)$ be an object in a completely distributive category.
\begin{enumerate}
\item Rewrite
\[
\sum_{i\in I}\prod_{j\in J(i)}\sum_{k\in K(i,j)}X(i,j,k)
\]
so that every $\sum$ appears before every $\prod$.
\item Rewrite
\[
\prod_{i\in I}\sum_{j\in J(i)}\prod_{k\in K(i,j)}X(i,j,k)
\]
so that every $\sum$ appears before every $\prod$.
\item Rewrite
\[
\prod_{i\in I}\prod_{j\in J(i)}\sum_{k\in K(i,j)}X(i,j,k)
\]
so that every $\sum$ appears before every $\prod$.\qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item By applying \eqref{eqn.cat_completely_distributive}, we can rewrite
\[
\sum_{i\in I}\prod_{j\in J(i)}\sum_{k\in K(i,j)}X(i,j,k)
\]
as
\[
\sum_{i\in I}\sum_{\bar{k}\in \prod_{j\in J}K(i,j)}\prod_{j\in J(i)}X(i,j,\bar{k}j).
\]
\item By applying \eqref{eqn.cat_completely_distributive}, we can rewrite
\[
\prod_{i\in I}\sum_{j\in J(i)}\prod_{k\in K(i,j)}X(i,j,k)
\]
as
\[
\sum_{\bar{j}\in \prod_{i\in I}J(i)}\;\prod_{i\in I}X(i,\bar{j}i)\prod_{k\in K(i,\bar{j}i)}X(i,\bar{j}i,k).
\]
\item By applying \eqref{eqn.cat_completely_distributive}, we can rewrite
\[
\prod_{i\in I}\prod_{j\in J(i)}\sum_{k\in K(i,j)}X(i,j,k)
\]
once as
\[
\prod_{i\in I}\sum_{\bar{k}\in\prod_{j\in J}K(i,j)}\prod_{j\in J(i)}X(i,j,\bar{k}j)
\]
and then again as
\[
\sum_{\bar{\bar{k}}\in\prod_{i\in I}\prod_{j\in J}K(i,j)}\prod_{i\in I}\prod_{j\in J(i)}X(i,j,\bar{\bar{k}}(i,j)).
\]
\end{enumerate}
\end{solution}
\end{exercise}
Now that we understand sums and products of sets, we are ready to explore sums and products of set-valued functors.\index{functor!set-valued}
%-------- Subsection --------%
\section{Sums and products of functors $\smset\to\smset$} \label{sec.poly.rep-sets.sum-prod-func}
Recall that our goal is to define polynomial functors such as $\yon^\2+\2\yon+\1$ and the maps between them.
We have defined representable functors such as $\yon^\2$, $\yon$, and $\1$; we just need to interpret sums of functors $\smset\to\smset$.
But we might as well introduce products of functors at the same time, because they will very much come in handy.
Both these concepts generalize to limits and colimits in $\smset^\smset$.
\begin{proposition} \label{prop.presheaf_lim_ptwise}\index{functor!limit of functors}\index{functor!colimit of functors}\index{limit!of functors}\index{colimit!of functors}
The category $\smset^\smset$ has all small limits and colimits, and they are computed pointwise.
In particular, on objects, given a small category $\cat{J}$ and a functor $F\colon \cat{J}\to\smset^\smset$, for all $X\in\smset$, the limit and colimit of $F$ satisfy isomorphisms
\[
\left(\lim_{j\in\cat{J}} F(j)\right)(X) \iso \lim_{j\in\cat{J}} \left(F(j)(X)\right) \qqand \left(\colim_{j\in\cat{J}} F(j)\right)(X) \iso \colim_{j\in\cat{J}} \left(F(j)(X)\right)
\]
natural in $X$.
\end{proposition}
\begin{proof}
This is a special case of a more general fact when $\smset^\smset$ is replaced by an arbitrary functor category $\Cat{D}^\Cat{C}$, where $\Cat{D}$ is a category that (like $\smset$) has all small limits and colimits; see \cite[pages 22--23, displays (24) and (25)]{macLane1992sheaves}.
\end{proof}
\index{functor!category of functors}\index{limit!of functors $\smset\to\smset$}\index{colimit!of functors $\smset\to\smset$}
Focusing on the case of coproducts and products, the following corollary is immediate.
\index{coproduct}
\begin{corollary}[Sums and products of functors $\smset\to\smset$] \label{cor.sum_prod_set_endofuncs}
Given functors $F,G\colon\smset\to\smset$, their categorical coproduct or sum in $\smset^\smset$, denoted $F+G$, is the functor $\smset\to\smset$ defined for $X,Y\in\smset$ and $f\colon X\to Y$ by
\[
(F+G)(X)\coloneqq F(X)+G(X) \qqand (F+G)(f)\coloneqq F(f)+G(f);
\]
while their categorical product in $\smset^\smset$, denoted $F\times G$ or $FG$, is the functor $\smset\to\smset$ defined for $X,Y\in\smset$ and $f\colon X\to Y$ by
\[
(F\times G)(X)\coloneqq F(X)\times G(X) \qqand (F\times G)(f)\coloneqq F(f)\times G(f).
\]
More generally, given functors $(F_i)_{i\in I}$ indexed over a set $I$, their categorical coproduct or sum and categorical product in $\smset^\smset$, respectively denoted
\[
\sum_{i\in I}F_i\colon\smset\to\smset
\qqand
\prod_{i\in I}F_i\colon\smset\to\smset,
\]
are respectively defined for $X\in\smset$ by
\[
\left(\sum_{i\in I}F_i\right)(X)\coloneqq\sum_{i\in I} F_i(X)
\qqand
\left(\prod_{i\in I}F_i\right)(X)\coloneqq\prod_{i\in I} F_i(X).
\]
and for functions $f\colon X\to Y$ by
\[
\left(\sum_{i\in I}F_i\right)(f)\coloneqq\sum_{i\in I} F_i(f)
\qqand
\left(\prod_{i\in I}F_i\right)(f)\coloneqq\prod_{i\in I} F_i(f).
\]
\end{corollary}
% TODO: sum and products of nat trans & functoriality?
We also note the special case of initial and terminal objects.
Given a set $I\in\smset$, we will also use $I$ to denote the constant functor $\smset\to\smset$ that sends every set to $I$.
\index{functor!constant}
\begin{corollary}[Initial and terminal functors $\smset\to\smset$]
The constant functor $\0\colon\smset\to\smset$ is initial in $\smset^\smset$, while the constant functor $\1\colon\smset\to\smset$ is terminal in $\smset^\smset$.
\end{corollary}
\begin{proof}
As the set $\0$ is initial in $\smset$ (for every set $X$ there is a unique map $\0\to X$), \cref{prop.presheaf_lim_ptwise} implies that the constant functor $\0$ is initial in $\smset^\smset$.
Similarly, as the set $\1$ is terminal in $\smset$ (for every set $X$ there is a unique map $X\to\1$), \cref{prop.presheaf_lim_ptwise} implies that the constant functor $\1$ is terminal in $\smset^\smset$.
\end{proof}
\index{functor!initial}\index{functor!terminal}
Finally, we note that $\smset^\smset$ inherits the distributivity of $\smset$.
\begin{proposition}\label{prop.set_endofunc_distrib}\index{completely distributive category!$\smset^\smset$ as}
The category $\smset^\smset$ is completely distributive.
\end{proposition}
\begin{proof}
This follows directly from the fact that $\smset$ itself is completely distributive (\cref{prop.push_prod_sum_set}) and the fact that sums and products in $\smset^\smset$ are computed pointwise (\cref{cor.sum_prod_set_endofuncs}).
\end{proof}
The following exercises justify some notational shortcuts we will use when denoting polynomial functors.
First, for any set $A$ and functor $F\colon\smset\to\smset$, we may write an $A$-indexed sum of copies of $F$ as $AF$, the product of $F$ and the constant functor $A$; for instance, $\yon+\yon\iso\2\yon$.
\begin{exercise} \label{exc.repeated_sum_is_product}
Show that for a set $A\in\smset$ and a functor $F\colon\smset\to\smset$, an $A$-indexed sum of copies of $F$ is isomorphic to the product of the constant functor $A$ and $F$:
\[
\sum_{a \in A}F\iso AF.
\]
(This is analogous to the fact that adding up $n$ copies of number is equal to multiplying that same number by $n$.)
\begin{solution}
It suffices to show that for all $X\in\smset$, there is an isomorphism
\[
\sum_{a\in A}F(X)\iso(AF)(X)
\]
natural in $X$.
The left hand side is the set $\{(a,s)\mid a\in A\text{ and }s\in F(X)\} \iso A \times F(X)$, while the right hand side is also naturally isomorphic to the set $A(X)\times F(X)\iso A\times F(X)$.
Alternatively, since $\smset^\smset$ is completely distributive by \cref{prop.set_endofunc_distrib}, the result also follows from \eqref{eqn.cat_completely_distributive}, with $I\coloneqq\2, J(1)\coloneqq A, J(2)\coloneqq\1, X(1,a)\coloneqq\1$ (the constant functor) for $a\in A$, and $X(2,1)\coloneqq F$:
\[
AF \iso
\left(\sum_{a\in A}\1\right)F \iso
\prod_{i\in\2}\sum_{j\in J(i)}X(i,j)
\iso
\sum_{\ol{j}\in\prod_{i\in\2}J(i)}\prod_{i\in\2}X(i,\ol{j}(i))
\iso
\sum_{a\in A}\1\times F
\iso
\sum_{a\in A}F.
\]
Here we used the fact that $A\iso\sum_{a\in A}\1$ from \cref{exc.on_sums_prods_sets} \cref{exc.on_sums_prods_sets.sum} (there we proved the statement for sets, but the same statement for the corresponding constant set-valued functors follows immediately).
\end{solution}
\end{exercise}\index{completely distributive category}
Similarly, we may wish to write an $A$-indexed product of copies of $F$ in exponential form as $F^A$.
But since we have already introduced exponential notation for representable functors, this yields two possible interpretations for the functor $\smset\to\smset$ denoted by $\yon^A$: as the functor represented by $A$, or as the $A$-indexed product of copies of the identity functor $\yon\colon\smset\to\smset$.
In fact, the following exercise shows that there is no ambiguity, as the two interpretations are isomorphic.
\begin{exercise}
\begin{enumerate}
\item Show that for a set $I\in\smset$, an $I$-indexed product of copies of the identity functor $\yon\colon\smset\to\smset$ is isomorphic to the functor $\yon^I\colon\smset\to\smset$ represented by $I$:
\[
\prod_{i\in I}\yon\iso\yon^I.
\]
(This is analogous to the fact that multiplying $n$ copies of a number together is equal to raising that same number to the power of $n$.)
\item Show that the $I$-indexed product of copies of a representable functor $\yon^A\colon\smset\to\smset$ for some $A\in\smset$ is isomorphic to the functor $\yon^{IA}\colon\smset\to\smset$ represented by the product set $IA$:
\[
\prod_{i\in I}\yon^A\iso\yon^{IA}.
\]
(Hint: You may use the fact that following natural isomorphism holds between sets of functions:\index{isomorphism!natural}
\[
\{ f \colon I\times A\to X \} \iso \{ g \colon I\to X^A \}.
\]
The process of converting a function $f$ in the left hand set to the corresponding function $i\mapsto(a\mapsto f(i,a))$ in the right is known as \emph{currying}.) \qedhere
\end{enumerate}
\begin{solution}
\begin{enumerate}
\item It suffices to show that for all $X\in\smset$, there is an isomorphism
\[
\prod_{i\in I} \yon(X) \iso \yon^I(X).
\]
natural in $X$.
We have that $\yon(X)\iso X$ and that $\yon^I(X)\iso X^I$.
So both sides are naturally isomorphic to the set of functions $I\to X$.
\item It suffices to show that for all $X\in\smset$, there is an isomorphism
\[
\prod_{i\in I} \yon^A(X) \iso \yon^{IA}(X).
\]
natural in $X$.
We have that $\yon^A(X)\iso X^A$, so $\prod_{i\in I}\yon^A(X)\iso(X^A)^I$, and that $\yon^{IA}(X)\iso X^{IA}$.