-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy path3.html
1161 lines (1033 loc) · 50.5 KB
/
3.html
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
<!doctype html>
<html lang="ja">
<head>
<meta charset="utf-8">
<title>圏論勉強会 第3回 @ ワークスアプリケーションズ</title>
<meta name="description" content="Seminar of category theory">
<meta name="author" content="Koichi Nakamura">
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
<link rel="stylesheet" href="css/reveal.css">
<link rel="stylesheet" href="css/theme/sky.css" id="theme">
<meta http-equiv="X-UA-Compatible" CONTENT="IE=EmulateIE7" />
<!-- For syntax highlighting -->
<link rel="stylesheet" href="plugin/highlight/styles/github.css">
<!-- If the query includes 'print-pdf', use the PDF print sheet -->
<script>
document.write( '<link rel="stylesheet" href="css/print/' + ( window.location.search.match( /print-pdf/gi ) ? 'pdf' : 'paper' ) + '.css" type="text/css" media="print">' );
</script>
<script type="text/javascript" async
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS_HTML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
}
});
</script>
<style type="text/css">
<!--
div.definition {
padding-top: 10px;
padding-bottom: 10px;
padding-left: 10px;
padding-right: 10px;
border: 4px solid #333333;
box-shadow: 0 0 10px rgba(0, 0, 0, 0.15);
}
div.theorem {
padding-top: 10px;
padding-bottom: 10px;
padding-left: 10px;
padding-right: 10px;
border: 4px solid #333333;
box-shadow: 0 0 10px rgba(0, 0, 0, 0.15);
}
div.equation {
margin: 10px;
padding-top: 10px;
padding-bottom: 10px;
padding-left: 10px;
padding-right: 10px;
border: 2px solid #C0C0C0;
}
-->
</style>
<!--[if lt IE 9]>
<script src="lib/js/html5shiv.js"></script>
<![endif]-->
</head>
<body>
<div class="reveal">
<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section>
<h1>圏論勉強会<br>第3回</h1>
<h3>@ワークスアプリケーションズ</h3>
<small> 中村晃一 <br> 2013年5月30日</small>
$$ \newcommand\append{{+\hspace{-.7em}+}} $$
</section>
<section>
<h3>謝辞</h3>
<p>
この勉強会の企画，会場設備の提供をして頂きました<br>
㈱ ワークスアプリケーションズ様<br>
にこの場をお借りして御礼申し上げます。
</p>
</section>
<section>
<h3> この会について </h3>
<ul>
<li> <span style="color:red">圏論(category theory)</span>を題材にいろんなことを学びます。</li>
<li> 分かり易さを重視して初歩的な例を多用します。</li>
<li> 関数型言語の経験がある方がより楽しめると思います。資料中では主にHaskellを使います。 </li>
<li> 中高生も数人見ているらしいのでプログラミングと関係が浅い内容も取り上げます。</li>
<li> この資料は<a href="http://nineties.github.com/category-seminar/">http://nineties.github.com/category-seminar</a>に置いてあります。</li>
</ul>
</section>
<section>
<h2> 第3回: 様々な圏 </h2>
</section>
<section>
<h3> 第3回の内容 </h3>
<p>
今回は様々な圏と見なせる数学的構造を沢山見ていきます。
また,前回モノイド・群で確認した事実の圏論による一般化も行います。
</p>
</section>
<section>
<h3> 定義の復習 </h3>
<p>
初回に紹介した各種概念の復習をします。自然変換はまだよく分からないという人が多いと思いますが,今後徐々に理解を深めて行けば良いです。
</p>
</section>
<section id="category">
<h3> 圏の定義 </h3>
<div class="definition">
<p>
<span style="color:red">圏(category)</span>とは
</p>
<ul>
<li> 対象(object):$A,B,C,\cdots$ </li>
<li> 射(arrow,morphism):$f,g,h,\cdots$ </li>
<li> 射の合成(composition): $\circ$ </li>
</ul>
<p>
からなり,以後の条件を全て満たすものである。
</p>
</div>
</section>
<section>
<div class="definition">
<p>
任意の射$f$には
</p>
<ul>
<li> ドメイン(domain): $\mathrm{dom}(f)$ </li>
<li> コドメイン(codomain): $\mathrm{cod}(f)$ </li>
</ul>
<p>
という２つの対象が備わる。<br>
$\mathrm{dom}(f) = A$,$\mathrm{cod}(f) = B$である事を $ f: A\rightarrow B$ と表す。
</p>
<div align="center"> <img src="fig/category1.png"> </div>
</div>
</section>
<section>
<div class="definition">
<p> 射$f:A\rightarrow B$,$g:B\rightarrow C$が存在するならば, </p>
<ul>
<li> 合成射(composite) $ g\circ f: A \rightarrow C $ </li>
</ul>
<p>
も存在する。
</p>
<div align="center"> <img src="fig/category2.png"> </div>
</div>
</section>
<section>
<div class="definition">
<p> 任意の射$f: A \rightarrow B$, $g: B \rightarrow C$, $h: C \rightarrow D$に対して 結合律(associative law) </p>
<div align="center"> $ (h\circ g)\circ f = h \circ (g\circ f)$ </div>
<p> が成り立つ。すなわち,下図が可換である。</p>
<div align="center"> <img width="55%" src="fig/category4.png"> </div>
</div>
</section>
<section>
<div class="definition">
<p> 任意の対象$A$に対して </p>
<ul>
<li> 恒等射(identity) $ 1_A: A \rightarrow A $ </li>
</ul>
<p> が存在し,任意の$f: A \rightarrow B$に対して単位元律(<span style="font-width:80%">identity law</span>) </p>
<div align="center"> $ f\circ 1_A = 1_B \circ f = f $ </div>
<p> が成り立つ。すなわち,右下図が可換である。</p>
<div align="center"> <img width="55%" src="fig/category3.png"> </div>
</div>
</section>
<section id="isomorphism">
<h3> 同型の定義 </h3>
<div class="definition">
<p>
$f: A\rightarrow B$に対して,$g: B\rightarrow A$が存在し,
</p>
<div align="center"> $ g\circ f = 1_A\qquad f\circ g = 1_B$ </div>
<p>
が成り立つならば$f$を<span style="color:red">同型射(isomorphism)</span>と呼ぶ。<br>
また,圏$\mathbf{C}$において$A$と$B$の間に同型射が存在するならば,$\mathbf{C}$において$A$は$B$と<span style="color:red">同型(isomorphic)</span>であると言い,
$$ A \cong B$$
と表す。
</p>
<div align="center"><img src="fig/inverse.png"> </div>
</div>
</section>
<section id="functor">
<h3> 函手の定義 </h3>
<div class="definition">
<p> 圏$\mathbf{C}$から圏$\mathbf{D}$への函手$F: \mathbf{C}\rightarrow\mathbf{D}$とは
$\mathbf{C}$の各対象$A$に$\mathbf{D}$の対象$F(A)$を対応付け,
$\mathbf{C}$の各射$f: A\rightarrow B$に$\mathbf{D}$の射$ F(f): F(A) \rightarrow F(B) $を
対応付ける2つの関数の組であり,以下の条件を満たすものである。 </p>
<div align="left">
<ul>
<li> 任意の$\mathbf{C}$の射$f: A\rightarrow B$, $g: B\rightarrow C$に対して
$$ F(g\circ f) = F(g) \circ F(f) $$
</li>
<li> 任意の$\mathbf{C}$の対象$A$に対して
$$ F(1_A) = 1_{F(A)} $$
</li>
</ul>
</div>
</div>
</section>
<section id="natural_transformation">
<h3> 自然変換の定義 </h3>
<div class="definition">
<div align="left" style="font-size:90%">
函手$F, G: \mathbf{C}\rightarrow\mathbf{D}$間の<span style="color:red">自然変換(natural transformation)</span>
$$ \vartheta: F \rightarrow G$$
とは,$\mathbf{D}$の射$\vartheta_X: F(X) \rightarrow G(X)$の集合であり,任意の$\mathbf{C}$の射$f: A\rightarrow B$に対して下図が可換であるもの。
</div>
<div align="center"> <img width="50%" src="fig/natural_transformation.png"> </div>
</div>
</section>
<section>
<h2> 主役級の圏 </h2>
</section>
<section>
<h3> 集合の圏:$\mathbf{Sets}$ </h3>
<ul>
<li> 対象: 集合 </li>
<li> 射: 関数 </li>
<li> 射の合成: 関数合成 </li>
</ul>
<p> からなる非常に巨大な圏です。 $\mathbf{Sets}$ではなく$\mathbf{Set}$と書いている本もあります。
</p>
</section>
<section>
<h3> 宇宙 </h3>
<p>
$\mathbf{Sets}$の対象全てからなる集合を$U$と表す事にします。
</p>
<p class="fragment">
すると$U$は集合なので「$U$自体も$\mathbf{Sets}$の対象の一つなのか？」,つまり
$$ U \in U $$
なのかという疑問が生じます。これは,何か気持ち悪い感じがします。
</p>
<p class="fragment">
実際これは「カントールのパラドックス」と呼ばれる有名な逆理を導いてしまいます。
</p>
</section>
<section>
<h3> 宇宙 </h3>
<p>
そこで,数学を行うのに必要なありとあらゆる集合を要素として持つ,ものすごく巨大な領域$U$(宇宙と呼びます)が存在する事を仮定して,
単に「集合」と言った場合には「($U$に属する)集合」という限定詞が付く事にします。
</p>
<div align="center"> <img width="60%" src="fig/universe.png"> </div>
</section>
<section>
<h3> 宇宙 </h3>
<p>
正確には,集合$U$と$U$の要素を区別する為に$U$の要素を「小さい集合」と呼びます。つまり,$\mathbf{Sets}$とは「小さい集合と関数からなる圏」なのです。
</p>
<p class="fragment">
この会の目的はこうした基礎論の学習ではないので「集合」という言葉を気軽に使いますが,このような背景があることは知っておいて下さい。
</p>
</section>
<section>
<h3> モノイドの圏:$\mathbf{Mon}$ </h3>
<ul>
<li> 対象: モノイド </li>
<li> 射: モノイドの準同型 </li>
<li> 射の合成: 準同型の合成 </li>
</ul>
<p>
からなる圏を$\mathbf{Mon}$と言います。
</p>
<p>
モノイド一般について考える場合の舞台となります。
</p>
<div align="center"> <img src="fig/mon.png"> </div>
</section>
<section>
<h3> 群の圏:$\mathbf{Grp}$ </h3>
<ul>
<li> 対象: 群 </li>
<li> 射: 群の準同型 </li>
<li> 射の合成: 準同型の合成 </li>
</ul>
<p>
同様に群とその準同型写像からなる圏も考えられこれを$\mathbf{Grp}$と呼びます。
</p>
</section>
<section>
<h3> 構造と準同型からなる圏 </h3>
<p>
モノイドや群は構造を持つ集合であり,準同型は構造を保つ関数(写像)です。つまり$\mathbf{Mon}$や$\mathbf{Grp}$は<span style="color:red">構造と準同型からなる圏</span>の一例です。
</p>
</section>
<section>
<h3> 構造と準同型からなる圏 </h3>
<p>
このような圏には多種多様なものが存在します。圏を身近に感じてもらう為にいくつか紹介しようと思います。
</p>
<ul>
<li> ベクトル空間と線形写像 </li>
<li> グラフとグラフ準同型 </li>
<li> 実数の集合と連続関数 </li>
<li> 位相空間と連続写像 </li>
<li> 順序集合と単調写像 </li>
</ul>
</section>
<section>
<h3> ベクトル空間の圏 </h3>
<div style="font-size:80%">
<p>
ベクトルとはいくつかの条件を満たす「足し算」と「定数倍」を備えた物でした。この概念を一般化すると<span style="color:red">ベクトル空間(vector space)</span>となります。
</p>
<p>
ベクトル空間の構造(つまり「足し算」と「定数倍」)を保つ写像が<span style="color:red">線形写像(linear mapping)</span>です。
</p>
$$ \begin{aligned}
& F(\vec{x} + \vec{y}) = F(\vec{x}) + F(\vec{y}) \\
& F(k\vec{x}) = kF(\vec{x})
\end{aligned} $$
</div>
<div align="center"> <img size="40%" src="fig/vector_space.png"> </div>
</section>
<section>
<h3> グラフの圏 </h3>
<p>
<span style="color:red">グラフ(graph)</span>とは頂点と辺からなる構造です。この構造を保つ写像が<span style="color:red">グラフ準同型(graph homomorphism)</span>です。つまり,辺$e$が辺$F(e)$に移るなら$e$の両端も$F(e)$の対応する両端に移るような写像です。
</p>
<div align="center"> <img src="fig/graph_homomorphism.png"> </div>
</section>
<section>
<h3> 実数の集合と連続関数の圏 </h3>
<p>
実数の集合には点と点のつながりを表す<span style="color:red">位相</span>という構造が入っています。左下図の様なグラフとして表した時につながっている関数を連続関数(continuous function)と言って,これは位相を保ちます。
</p>
<div align="center"> <img src="fig/continuous_function.png"> </div>
</section>
<section>
<h3> 位相空間の圏$\mathbf{Top}$ </h3>
<p style="font-size:90%">
これを一般化すると<span style="color:red">位相空間(topological space)</span>と<span style="color:red">連続写像(continuous mapping)</span>というものになります。直感的に説明すると位相空間とはつながりという情報を持った図形で,連続写像とは切ったり穴を開けない写像です。
</p>
<div align="left" style="font-size:50%">
注: 実際には開集合系というものを用いて厳密に定義されます。
</div>
<img align="right" src="http://upload.wikimedia.org/wikipedia/commons/2/26/Mug_and_Torus_morph.gif">
<p style="font-size:90%">
右のアニメーション(<a href="http://ja.wikipedia.org/wiki/%E4%BD%8D%E7%9B%B8%E5%90%8C%E5%9E%8B">wikipedia/位相同型</a>)は連続写像の中でも<span style="color:red">位相同型写像(homeomorphism)</span>という「元に戻せる連続写像」を表しています。
位相空間としてはコーヒーカップとドーナツは本質的に同じであるという事です。
</p>
</section>
<section>
<h3> 順序集合と単調写像 </h3>
<p>
整数や実数などには順序($\leqq$)という構造が入っています。このような集合を順序集合(さらに一般化すると半順序集合)と言います。
そして順序を保つ写像を<span style="color:red">単調写像(monotone mapping)</span>と言います。
</p>
<p>
例えば(広義)単調増加な実数列
$$ a_0 \leqq a_1 \leqq a_2 \leqq \cdots $$
とは「$i \leqq j$ならば$a_i \leqq a_j$」を常に満たす数列なので,自然数から実数への単調写像になっています。
</p>
</section>
<section>
<h3> 具体圏 </h3>
<p>
これまでに見てきた圏は構造を持った「集合」と構造を保つ「関数(写像)」からなる圏でしたので,
<span style="color:red">$\mathbf{Sets}$の一部と同一視可能</span>です。<br>
この事の定式化はまだ出来ませんが,このような圏を<span style="color:red">具体圏(concrete category)</span>と言います。
</p>
</section>
<section>
<h3> 型の圏 </h3>
<p> $L$を関数型プログラミング言語とした時, </p>
<ul>
<li> 対象: $L$におけるデータの型 </li>
<li> 射: $L$における関数 </li>
<li> 射の合成: 関数の合成 </li>
</ul>
<p>
という圏を作れます。これを$\mathbf{C}(L)$と表す事にします。
</p>
<p>
また,よく登場するので$\mathrm{Hask} = \mathbf{C}(\text{Haskell})$と略記します。
</p>
</section>
<section>
<h3> プログラムの意味 </h3>
<p> $\mathbf{C}(L)$における「型」と「関数(プログラム)」はただのコード<small>(を適当な同値関係で割ったもの)</small>であって,それ自体は意味を持ちません。
</p>
<p class="fragment">
「型」と「プログラム」にある構造を持ったドメインと呼ばれる集合とその間の関数を割り当てるとプログラムに意味を与える事が出来るのですが,この関係は$\mathbf{C}(L)$からドメインのなす圏$\mathbf{D}$への函手
$$ \mathbf{C}(L) \rightarrow \mathbf{D} $$
となります。
</p>
<p class="fragment">
分かりやすく言えば,コンパイラは函手と見なせるという事です。
</p>
</section>
<section>
<h3> 証明の圏 </h3>
<p>
「今日が$5$月の晴れた日である」という仮定がもし正しいならば「今日が$5$月である」という結論も正しいと考えられます。
</p>
<div class="fragment">
<p>
「かつ」を表す記号を$\wedge$とし
</p>
<ul>
<li> $A$:今日が$5$月である </li>
<li> $B$:今日が晴れた日である</li>
</ul>
<p>
と記号化すると,$A\wedge B$という論理式から$A$という論理式を作り出す操作として形式化出来ます。
</p>
</div>
</section>
<section>
<p> このように論理式から論理式を導く規則を<span style="color:red">推論規則(deduction rule)</span>と言い,</p>
<div align="center"> <img width="70%" src="fig/category_of_proofs1.png"> </div>
<img align="right" width="15%" src="fig/category_of_proofs2.png">
<p> 推論を積み重ねて$\varphi_0$から$\varphi_n$を得る事を仮定$\varphi_0$の下での$\varphi_n$の<span style="color:red">(形式的)証明(proof)</span>と呼びます。</p>
<p class="fragment">
すると論理式を対象とし,証明を射とする圏が出来ます。
</p>
</section>
<section>
<h3> 圏の圏:$\mathbf{Cat}$ </h3>
<ul>
<li> 対象: (小さい)圏 </li>
<li> 射: 函手 </li>
<li> 射の合成: 函手の合成 </li>
</ul>
<p> という圏を考える事が出来ます。これを<span style="color:red">$\mathbf{Cat}$</span>と言います。</p>
<img align="right" src="fig/cat.png">
</section>
<section>
<h2> 脇役的な圏 </h2>
</section>
<section>
<h3> 離散圏 </h3>
<p>
集合を一つ取って,それを圏と見なす事も可能です。
</p>
<ul>
<li> 対象: 集合の要素 </li>
<li> 射: 恒等射のみ </li>
</ul>
<p>
とします。これを<span style="color:red">離散圏(discrete category)</span>と言います。
</p>
<p>
恒等射は常に存在するので、下図の様に省略して描きます。
</p>
<div align="center"> <img width="50%" src="fig/discrete_category.png"> </div>
</section>
<section>
<h3> モノイド・群 </h3>
<p>
モノイドを一つ取ればは「対象が一つの圏」となります。<br>
群は「対象が一つで,全ての射が同型射である圏」です。
</p>
<div align="center"> <img src="fig/a_monoid.png"> </div>
</section>
<section>
<h3> 注 </h3>
<p>
例えば「列と連結」からなるモノイドを思い出して下さい。これを一つの圏として解釈すると
<span style="color:red">射が個々の列</span>であり,<span style="color:red">射の合成が連結</span>であり,対象には特に意味がありません。
</p>
<p class="fragment">
射とは必ずしも関数ではないので注意して下さい。
</p>
<div align="center"> <img src="fig/a_monoid2.png"> </div>
</section>
<section>
<h3> 前順序集合 </h3>
<p> 任意の対象$A$,$B$について$A$から$B$へ向かう射が高々$1$つしかない圏を<span style="color:red">前順序集合(preordered set)</span>と言います。</p>
<div align="center"> <img src="fig/preorder.png"> </div>
</section>
<section>
<p>
$A$から$B$へのただ一つの射を$A \leqq B$と表す事にして,定義を翻訳すると
</p>
<div class="equation">
$$ \begin{aligned}
\text{反射律:}& A\leqq A \\
\text{推移律:}& A\leqq B,B\leqq C\ \text{ならば}\ A\leqq C
\end{aligned} $$
</div>
<p>
が常に成り立つ集合ということになります。
</p>
<p class="fragment">
例えば$\leqq$を「年齢の大小」にすると,人の集合は前順序集合となります。
</p>
<p class="fragment">
一方$\leqq$を「グー・チョキ・パーの強さの比較」とすると推移律を満たさないのでこれは前順序になりません。
</p>
</section>
<section>
<h3> 半順序集合 </h3>
<p> 任意の対象間に,向きを区別せずに数えて射が高々$1$つしかない圏を<span style="color:red">半順序集合(partial ordered set)</span>と言います。
</p>
<p> これも翻訳すると前順序集合であって </p>
<div class="equation">
$$ \text{反対称律:} A\leqq B,B\leqq A\ \text{ならば}\ A = B $$
</div>
<p>
を満たす集合という事になります。
</p>
<p class="fragment">
先ほどの「年齢の大小」の例は年齢が等しくても同じ人とは限らないので半順序集合にはなりません。
</p>
</section>
<section>
<h3> 半順序集合の例 </h3>
<p> $\leqq$を$\subseteq$と解釈すると半順序集合となります。
他の射を合成して得られる射は省略しています。
</p>
<div align="center"> <img width="70%" src="fig/inclusion_relation.png"> </div>
</section>
<section>
<h3> 半順序集合の例 </h3>
<p> $A \leqq B$を「$B$が$A$で割り切れる」と解釈すると半順序集合となります。</p>
<div align="center"> <img src="fig/divisible_relation.png"> </div>
</section>
</section>
<section>
<h3> 半順序集合の例 </h3>
<p> $\leqq$を自然数や実数などの通常の大小関係として解釈しても半順序となります。</p>
<p class="fragment"> これらの様に,全てのペア$A$,$B$間に$A \leqq B$か$B\leqq A$が成り立つ半順序集合を<span style="color:red">全順序集合(totally ordered set)</span>と言います。
</p>
<div align="center"> <img src="fig/product14.png"> </div>
</section>
<section>
<h3> 空圏$\mathbf{0}$ </h3>
<p>
対象も射も全く無い圏を空圏と言い,$\mathbf{0}$と表します。
</p>
<div align="center"> <img width="70%" src="fig/category-0.png"> </div>
</section>
<section>
<h3> $\mathbf{1}$ </h3>
<p> 対象が$1$つ,射が恒等射のみの圏を$\mathbf{1}$と表します。 </p>
<div align="center"> <img width="70%" src="fig/category-1.png"> </div>
</section>
<section>
<h3> $\mathbf{2}$ </h3>
<p> 対象が$2$つで,恒等射以外の射が下図のように$1$つある圏を$\mathbf{2}$と表します。</p>
<div align="center"> <img width="70%" src="fig/category-2.png"> </div>
</section>
<section>
<h3> $\mathbf{3}$ </h3>
<p> 対象が$3$つで,恒等射以外の射が下図のように$3$つある圏を$\mathbf{3}$と表します。</p>
<div align="center"> <img width="70%" src="fig/category-3.png"> </div>
</section>
<section>
<h3> 何の役に立つのか? </h3>
<p>
まず,どれも分り易いので圏論を学習する際の練習用に使えます。
</p>
<p class="fragment">
実用上は函手とセットで考える事が多いです。
</p>
</section>
<section>
<h3> $\mathbf{1},\mathbf{2},\mathbf{3}$からの函手 </h3>
<div align="center"> <img src="fig/functor_from_123.png"> </div>
</section>
<section>
<h3> $\mathbf{1},\mathbf{2},\mathbf{3}$からの函手 </h3>
<p>
$\mathbf{1}$から$\mathbf{C}$への函手は$\mathbf{C}$の対象と一対一に対応します。つまり,$\mathbf{1}$からの<span style="color:red">函手と対象を同一視出来る</span>という事です。
</p>
<div class="fragment">
<p> このように </p>
<ul>
<li> $F:\mathbf{1}\rightarrow \mathbf{C}$は$\mathbf{C}$の対象と同一視可能 </li>
<li> $F:\mathbf{2}\rightarrow \mathbf{C}$は$\mathbf{C}$の射と同一視可能 </li>
<li> $F:\mathbf{3}\rightarrow \mathbf{C}$は$\mathbf{C}$の合成可能な射の対と同一視可能 </li>
</ul>
<p>
という事が言えます。
</p>
<p class="fragment">
対象や射などの「もの」と函手などの「マッピング」が,相互に移り変われるものである事を理解することが大切です。
</p>
</div>
</section>
<section>
<h3> 離散圏からの函手 </h3>
<p> 離散圏$A$からの函手は$\mathbf{C}$の対象から(重複を許して)$A$の要素と同じ数だけ対象を選ぶ事と解釈出来ます。
</p>
<div align="center"> <img width="70%" src="fig/functor_from_disc.png"> </div>
</section>
<section>
<h3> 「型」としての圏 </h3>
<p> このように函手$F: \mathbf{J}\rightarrow \mathbf{C}$は圏$\mathbf{J}$を「型」と見なすとその型に当てはまる$\mathbf{C}$の部分を取り出すものだと考える事が出来ます。</p>
<div align="center"> <img width="70%" src="fig/functor_from_order.png"> </div>
</section>
<section>
<h3> $\mathbf{0}$からの函手 </h3>
<p>
最後に一つ分かりにくい話をしますと,空圏$\mathbf{0}$から任意の圏$\mathbf{C}$へは唯一つだけ函手が存在します。これを$0_{\mathbf{C}}$と書くことにします。
</p>
<div align="center"> <img width="70%" src="fig/zero_functor.png"> </div>
</section>
<section>
<h3> 空関数 </h3>
<p>
知っておいて欲しいのは空集合$\emptyset$から任意の集合への関数が唯一つだけ存在する事を証明出来るという事です。これを<span style="color:red">空関数(empty function)</span>と言います。この事実は今後も登場します。
</p>
<p style="font-size:60%">
【説明】<br>
$A$から$B$への関数とは「任意の$a\in A$について唯一つの$b\in B$を対応させる関係」の事です。これは$(a, b)$の対の集合として表現出来ます。つまり関数$f$とは「任意の$a\in A$について,$(a,b)\in F$となるような$b\in B$が唯一つ存在するような集合$F$」として定義されます。ここで$A = \emptyset$の時に$F = \emptyset$とすると,任意の$B$について$F$は上の条件を満たします。つまり$F = \emptyset$が定める関数が存在します。これが空関数です。$A = \emptyset$なので$F = \emptyset$以外有り得ませんから唯一性も示されます。
</p>
</section>
<section>
<h3> 圏から圏を作る </h3>
</section>
<section>
<h3> 積圏 </h3>
<p> 圏$\mathbf{C}$と$\mathbf{D}$の対象の対,射の対を新たな対象・射として構成した圏を<span style="color:red">積圏(product category)</span>と言い$\mathbf{C}\times\mathbf{D}$と表します。射の合成は対のそれぞれを合成する事によって定義します。
$$ (f_1,f_2)\circ(g_1,g_2) = (f_1\circ g_1, f_2\circ g_2) $$
</p>
<div align="center"> <img width="90%" src="fig/product_category.png"> </div>
</section>
<section>
<h3> 函手圏 </h3>
<p>
圏$\mathbf{C}$と圏$\mathbf{D}$を固定して
</p>
<ul>
<li> 対象: $\mathbf{C}$から$\mathbf{D}$への函手 </li>
<li> 射: 自然変換 </li>
<li> 射の合成: 自然変換の(垂直)合成 </li>
</ul>
<p>
という圏を考える事が出来ます。これを<span style="color:red">函手圏(functor category)</span>と言い$\mathbf{D}^\mathbf{C}$と表します。
</p>
</section>
<section>
<img align="right" width="70%" src="fig/functor_category.png">
<p style="font-size:80%">こんな感じです。ガクガクの矢印が函手で点線の矢印が自然変換です。分り易い例をいくつか見てみましょう。
</p>
</section>
<section>
<h3> $\mathbf{C}^\mathbf{1}$ </h3>
<img align="right" width="50%" src="fig/functor_category2.png">
<p style="font-size:80%">
$\mathbf{C}^\mathbf{1}$の対象は$\mathbf{1}$から$\mathbf{C}$への函手です。これは$\mathbf{C}$の対象と同一視出来るので同じ記号で表す事にします。函手$A$の像(行き先)は対象$A$一つですから,任意の射$f: A\rightarrow B$が一つの自然変換を定めます。逆も然りです。
</p>
<p class="fragment" style="font-size:80%">
つまり
$$ \mathbf{C}^\mathbf{1} \cong \mathbf{C} \quad \text{in $\mathbf{Cat}$}$$
です。
</p>
</section>
<section>
<h3> $\mathbf{C}^\mathbf{0}$ </h3>
<img align="right" width="50%" src="fig/functor_category3.png">
<p style="font-size:80%">
$\mathbf{C}^\mathbf{0}$の対象は空圏$\mathbf{0}$から$\mathbf{C}$への函手つまり,$0_{\mathbf{C}}$一つだけです。すると$0_{\mathbf{C}}$の像は空集合ですので,自然変換は$0_{\mathbf{C}}$をそれ自身に写すもののみです。
</p>
<p class="fragment" style="font-size:80%">
つまり$\mathbf{C}^\mathbf{0}$は対象が一つで恒等射のみなので
$$ \mathbf{C}^\mathbf{0} \cong \mathbf{1} \quad \text{in $\mathbf{Cat}$}$$
です。
</p>
</section>
<section>
<h3> $\mathbf{C}^{\rightarrow}$ </h3>
<img align="right" width="50%" src="fig/functor_category4.png">
<p style="font-size:80%">
$\mathbf{2}$から$\mathbf{C}$への函手のなす圏を考えます。
積圏$\mathbf{C}\times\mathbf{C}$と混同しないように$\mathbf{C}^{\rightarrow}$と表す事にします。
</p>
<p style="font-size:80%">
前に見たようにこの圏の対象は$\mathbf{C}$の射です(右図では$f$と$g$)。
すると右図のような四角い可換図式を作る$2$つの射(右図では$\tau$と$\sigma$)が自然変換です。
</p>
<p class="fragment" style="font-size:80%">
この様な「射」を対象とし「可換図式」を射とする圏を<span style="color:red">射圏(arrow category)</span>と言います。
</p>
</section>
<section>
<p> 他にも圏から圏を構成する方法は沢山ありますが,時間が無さそうなので今後必要になったら随時紹介していく事にします。
</p>
</section>
<section>
<h2> 自由対象 </h2>
</section>
<section>
<h3> 自由モノイド </h3>
<p>
前回<span style="color:red">自由モノイド(free monoid)</span>というモノイドを紹介しました。
</p>
<p>
自由モノイドとは「列と連結」からなるモノイドと思ってよく,任意の他のモノイドへの準同型が「長さ$1$の列のマッピング」のみによって決定されるという良い性質を持っていました。
</p>
<p class="fragment">
今日はこれの一般化を考えたいのですが,具体例を作るのは簡単なのでいくつか見てみます。
</p>
</section>
<section id="semigroup">
<h3> 半群 </h3>
<div class="definition">
<p>
<span style="color:red">半群(semigroup)</span>とは集合$M$，$M$上の二項演算$\cdot$の組$(M, \cdot)$で，以下の条件を満たすものである。<br>
</p>
<ul>
<li>結合律: 任意の$x,y,z \in M$について
$$ (x\cdot y)\cdot z = x\cdot (y \cdot z)$$
</li>
</ul><br>
</div>
<p> つまり,半群に単位元の存在という条件を加えたのがモノイドです。</p>
<p class="fragment">
では<span style="color:red">自由半群</span>を作ってみましょう。
</p>
</section>
<section>
<p> まず種になる集合(生成系)が必要です。仮に$A = \{a,b,c\}$とします。</p>
<p> これらに２項演算を$0$回以上適用して出来上がる項は </p>
$$ a,\,b,\,c,\,ab,\,bc,\,\cdots,\,(ab)c,\,a(bc)\cdots $$
<p> です。見やすさの為に$\cdot$は省略します。</p>
<div class="fragment">
<p>
結合律があるので$(ab)c=a(bc)$などが成り立ちますから括弧を外すと
</p>
$$ a,\,b,\,c,\,ab,\,bc,\,\cdots,\,abc,\,\cdots $$
<p>
となります。他に等式はありませんから,これらを別々の元として持つ構造が$A$上の自由半群となります。
</p>
</div>
<p class="fragment">
つまり自由半群とは「<span style="color:red">長さが$1$以上の列</span>(と連結)」です。
</p>
</section>
<section id="magma">
<h3> マグマ </h3>
<div class="definition">
<p>
<span style="color:red">マグマ(magma)</span>とは集合$M$，$M$上の二項演算$\cdot$の組$(M, \cdot)$をもつものである。
</p>
</div>
<p> マグマに結合律を加えたのが半群です。</p>
<p class="fragment">
では<span style="color:red">自由マグマ</span>を作ってみましょう。
</p>
</section>
<section>
<p> 生成系を$A = \{a,b,c\}$とします。</p>
<p> これらに２項演算を$0$回以上適用して出来上がる項は </p>
$$ a,\,b,\,c,\,ab,\,bc,\,\cdots,\,(ab)c,\,a(bc)\cdots $$
<p> です。</p>
<p class="fragment">
マグマには一切の等式がないので,これらを全て異なる元として持つ構造が自由マグマです。
</p>
<p class="fragment">
つまり自由マグマとは「葉にのみ値を持つ<span style="color:red">二分木</span>(とその連結)」です。
</p>
</section>
<section>
<h3> 自由マグマ </h3>
<div align="center"> <img width="90%" src="fig/free_magma.png"> </div>
</section>
<section>
<h3> 可換モノイド </h3>
<div class="definition">
<p>
<span style="color:red">可換モノイド(commutative monoid)</span>とはモノイド$(M,\cdot)$であって,以下の条件を満たすものである。
</p>
<ul>
<li>可換則: 任意の$x,y \in M$について
$$ x\cdot y = y\cdot x $$
</li>
</ul><br>
</div>
<p class="fragment">
では<span style="color:red">自由可換モノイド</span>とはどんな構造でしょうか？
</p>
</section>
<section>
<h3> 冪等モノイド </h3>
<div class="definition">
<p>
<span style="color:red">冪等モノイド(idempotent monoid)</span>とはモノイド$(M,\cdot)$であって,以下の条件を満たすものである。
</p>
<ul>
<li>冪等則: 任意の$x \in M$について
$$ x\cdot x = x$$
</li>
</ul><br>
</div>
<p>
では<span style="color:red">自由冪等モノイド</span>とはどんな構造でしょうか？
</p>
</section>
<section>
<h3> 冪等可換モノイド </h3>
<div class="definition">
<p>
<span style="color:red">冪等可換モノイド(idempotent commutative monoid)</span>とはモノイド$(M,\cdot)$であって冪等則と可換則を満たすものである。
</p>
</div>
<p>
では<span style="color:red">自由冪等可換モノイド</span>とはどんな構造でしょうか？
</p>
</section>
<section>
<p> 是非、何らかの代数の本を読むことをお薦めしますが、以下を眺めるだけでも楽しいと思います。</p>
<a href="http://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%B0%E3%83%9E_(%E6%95%B0%E5%AD%A6)">wikipedia/マグマ</a><br>
<a href="http://ja.wikipedia.org/wiki/%E5%8D%8A%E7%BE%A4">wikipedia/半群</a><br>
<a href="http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%82%A4%E3%83%89">wikipedia/モノイド</a><br>
<a href="http://ja.wikipedia.org/wiki/%E7%BE%A4_(%E6%95%B0%E5%AD%A6)">wikipedia/群</a><br>
</section>
<section>
<h3> プログラミングと代数 </h3>
<p>
プログラミングで扱う様々なデータ構造は何らかの代数構造であるということに気づく事が大切です。
</p>
<p>
前回,$\mathbf{foldMap},\mathbf{fold[r|l]}$でモノイド準同型を作って様々な計算が行える事を見ましたが,同様の事が出来ることになります。その際,何が出来て何が出来ないかは代数の構造を調べれば良いという事になります。
</p>
</section>
<section>
<h3> 自由対象 </h3>
<ul>
<li> 自由モノイドは$\mathbf{Mon}$の自由対象 </li>
<li> 自由半群は「半群と準同型のなす圏」の自由対象 </li>
<li> 自由マグマは「マグマと準同型のなす圏」の自由対象 </li>
</ul>
<p>
などと言います。ということで圏$\mathbf{C}$の自由対象というものを考えます。
</p>
<p>
これらは全て「生成系(集合)と要素のマッピング(関数)」という下部の構造($\mathbf{Sets}$の中にある)から,上部の構造$\mathbf{C}$における射が一意的に決定されるという性質を持っています。
</p>
</section>
<section>
<h3> こんな感じ </h3>
<div align="center"> <img src="fig/free_object.png"> </div>
</section>
<section>
<h3> 忘却函手 </h3>
<p> $\mathbf{C}$(構造を持つ集合と構造を保つ関数の圏)の「構造」を捨てて$\mathbf{Sets}$(集合と関数の圏)そのまま移す函手
$$ |-| : \mathbf{C}\rightarrow \mathbf{Sets}$$
を<span style="color:red">忘却函手(forgetful functor)</span>と言います。
</p>
<div align="left" style="font-size:50%">
注: 一般には忠実函手というもので一般化しますが,今回は単に集合と関数をそのまま同じものに写す函手を考えます。
</div>
</section>
<section id="free_object">
<h3> 自由対象(狭義) </h3>
<div class="definition" style="font-size:80%">
<p>
$|-|:\mathbf{C}\rightarrow\mathbf{Sets}$を忘却函手とする。<br>
$\mathbf{C}$の対象$F(A)$が集合$A$上の自由対象であるとは,ある関数$i: A\rightarrow |F(A)|$を備えており,任意の$\mathbf{C}$の対象$X$と関数$f: A\rightarrow |X|$について,下図が可換となるような射$\overline{f}: F(A)\rightarrow X$が唯一に定まる事である。
</p>
<div align="center"> <img width="70%" src="fig/free_object2.png"> </div>
</div>
</section>
<section>
<h3> Haskellでの実装例 </h3>
<p> マグマを例に取って実装してみます。コード:<a href="code/Magma.hs">Magma.hs</a>
</p>
<pre><code data-trim class="haskell" contenteditable>
module Magma where
-- モノイドはマグマの一種なのでimportしときます。
import Data.Monoid
import Data.Foldable
-- マグマとは集合A(型aと対応)とA上の二項演算(magappendと対応)を
-- 備えた代数構造です。
class Magma a where
magappend :: a -> a -> a
-- 自由マグマとは二分木です。
-- Nodeが自由マグマの積。
-- Leafが自由対象のスライドにあるiです。
data FreeMagma a = Leaf a | Node (FreeMagma a) (FreeMagma a) deriving (Show, Eq)
-- foldMapMagma fが自由対象のスライドにある「fバー」です。
foldMapMagma :: Magma b => (a -> b) -> FreeMagma a -> b
foldMapMagma f (Leaf x) = f x
foldMapMagma f (Node l r) = foldMapMagma f l `magappend` foldMapMagma f r
-- 実際にはData.Foldableのインスタンスにした方が良いでしょう。
-- foldr, foldl, find, elem, notElem, concat, forM_, ....などなどの便利関数が
-- 使える様になります。
-- 自由マグマはもちろんマグマです。
instance Magma (FreeMagma a) where
magappend = Node
-- モノイドもマグマです。
newtype WrappedMonoid a = WrapMonoid a deriving (Show, Eq)
instance Monoid a => Magma (WrappedMonoid a) where
WrapMonoid x `magappend` WrapMonoid y = WrapMonoid (x `mappend` y)
-- モノイドでないマグマ演算の例として