CS 6117 (Spring 2018)  Category Theory for Computer Scientists
Overview
CS6117  Category Theory for Computer Scientists is an introduction to category theory, with a focus on material with established applications to computer science. The course will emphasize developing comfort with abstraction and instantiation while not assuming students have a strong background in mathematics.
Class Times: MWF 11:1512:05
Location: 206 Upson Hall
Instructor:
Ross Tate
Office: 434 Gates Hall
Office Hours: Friday 1:302:30
Grading There will be a small homework assignment almost every week (no midterms or final):
Assignments: 100%
 There will be 14 assignments.
 Each assignment is worth 8.5%.
 The two worst assignments will be ignored.
 Assignmets are due at the beginning of class on Monday.
 No late assignments.
Piazza: http://piazza.com/cornell/spring2018/cs6117
Related Reading
 Abstract and Concrete Categories  The Joy of Cats by Jiri Adamek, Horst Herrlich, and George E. Strecker (2004)
 Higher Operads, Higher Categories by Tom Leinster (2003)
 Categories for the Working Mathematician by Saunders Mac Lane (1971)
Schedule
Date  Topic  Reading  Assignments 

Week 1  
Jan 24  Categories, Part 1  Reference (updated throughout the semester) Preface 3.1(ignore c), 3.2, 3.3(2b,2d,2f,4a,4c4f), 3.4 Categories 
Available: Assignment 1 
Jan 26  Categories, Part 2  
Week 2  
Jan 29  Categories, Part 3  Due: Assignment 1 Available: Assignment 2 

Jan 31  Isomorphisms  3.8, 3.1012, 3.13(12,4,6), 3.1415 Isomorphisms 

Feb 2  Functors, Part 1  3.1718, 3.20(14,68,10,13) Functors 

Week 3  
Feb 5  No Lecture  
Feb 7  No Lecture  
Feb 9  Functors, Part 2  3.21,3.22(2),3.2324,3.25(1),3.26(13) 3.27(23),3.29(12,4),3.30(1),3.3132 3.50 

Week 4  
Feb 12  Metric Spaces and Topologies, Part 1  Metric Spaces and Topologies  Due: Assignment 2 
Feb 14  Metric Spaces and Topologies, Part 2 Comma Categories, Part 1 
Comma Categories  Available: Assignment 3 
Feb 16  Comma Categories, Part 2  Available: Assignment 4  
Week 5  
Feb 19  February Break  
Feb 21  Subcategories, Part 1  4.1, 4.2(1,2), 4.3(1), 4.9, 4.12, 4.13(1) Subcategories 
Due: Assignment 3 
Feb 23  Subcategories, Part 2  
Week 6  
Feb 26  Reflective Subcategories, Part 1  4.16, 4.17(A1,B3,B7,C10C12)  Due: Assignment 4 
Feb 28  Reflective Subcategories, Part 2  4.1923 Reflections 
Available: Assignment 5 
Mar 2  Coreflective Subcategories  4.25, 4.26(A1,B4), 4.27  
Week 7  
Mar 5  Duality Contravariant Functors 
3.56 3.20(4,5,89) 
Due: Assignment 5 
Mar 7  Concrete Categories  5.1, 5.2(12,4,7), 5.3, 5.4(13), 5.5(14), 5.7(12), 5.8 5.9, 5.10(13), 5.11(14), 5.12, 5.14, 5.1819 5.2122, 5.23(1,6), 5.26 5.28, 5.30(2), 5.31 
Available: Assignment 6 
Mar 9  FunctorInduced Categories  5.37, 5.38(1,4), 5.39 5.4042, 5.44 Coalgebras 

Week 8  
Mar 12  Natural Transformations, Part 1  6.1, 6.2(12,5,6), 6.5, 6.6(1,45), 6.7  Due: Assignment 6 
Mar 14  Natural Transformations, Part 2  6.34, 6.1314, 6A  Available: Assignment 7 
Mar 16  2Categories  2Categories  
Week 9  
Mar 19  Initial, Terminal, and Zero Objects Discrete and Indiscrete Objects Separators and Coseparators Sections and Retracts 
7.1, 7.2(14,89), 7.39 8.1, 8.2(14,7), 8.34, 8.5(15) 7.10, 7.11(12,45), 7.12, 7.1617, 7.18(1,3,8) 7.19, 7.20(1,6), 7.2124, 7.25(1), 7.2631 
Due: Assignment 7 
Mar 21  Monomorphisms and Epimorphisms Subobjects and Quotient Objects Equalizers and Coequalizers Regular Monomorphisms and Epimorphisms 
7.32, 7.33(1,34,7), 7.3436, 7.37(2), 7.39, 7.40(13,56), 7.4145 7.7778, 7.8485, 7.86(12,4) 7.51, 7.52(1), 7.5355, 7.68, 7.69(13), 7.70 7.5659, 7.71, 7.72(1,4), 7.73, 7.75(1), 7.76 

Mar 23  Sources and Sinks (Extremal) Monosources and Episinks Products, Coproducts, and Biproducts Initial Sources and Final Sinks 
10.14, 10.62 10.56, 10.7(2), 10.910, 10.64, 10.1116, 10.65 10.19, 10.20(12,58), 10.2130, 10.31(12,4), 10.3437, 10.67(13,8) 10.4143, 10.4546, 10.68 
Available: Assignment 8 
Week 10  
Mar 26  Structured Arrows/Sources and Costructured Arrows/Sinks Initial and Final Liftings Free and Cofree Objects 
8.15, 8.17(24,6), 8.18, 8.19(1), 8.40(1), 17.1 21.1, 21.7, 21.8(13), 21.911 8.22, 8.23(1,3,5,8,16), 8.2428, 8.40(2), 8.41(1,2a2b) 
Due: Assignment 8 
Mar 28  Transpositions, Adjunctions, and Equivalences  Transpositions and Adjunctions  Available: Assignment 9 
Mar 30  Limits and Colimits  All of Section 11 Kan Extensions Weighted Limits and Colimits 

Week 11  Spring Break  
Apr 2  Spring Break  
Apr 4  Spring Break  
Apr 6  Spring Break  
Week 12  
Apr 9  Monads and Comonads  20.13 Monads and Comonads 
Due: Assignment 9 Available: Assignment 10 
Apr 11  Monad Algebras  20.4, 20.5(13), 20.711, 20.12(13,58,10) Monad Algebras 

Apr 13  Effects  20B(ac) Kleisli Categories 

Week 13  
Apr 16  Multicategories  Multicategories  Due: Assignment 10 
Apr 18  Tensors and Exponentials  Tensors and Exponentials  Available: Assignment 11 
Apr 20  Monoidal Categories  Monoidal For Fun: Physics, Topology, Logic and Computation: A Rosetta Stone 

Week 14  
Apr 23  Encriched Categories, Part 1  Enriched Categories  Due: Assignment 11 
Apr 25  Encriched Categories, Part 2  Available: Assignment 12  
Apr 27  (Op)Indexed Categories  (Op)Indexed Categories  
Week 15  
Apr 30  Universal and Existential Quantification  Universal and Existential Quantification  Due: Assignment 12 
May 2  Factorization Structures  15.1, 15.3(1,2a,34,6), 15.418 Factorization Structures 
Available: Assignment 13 
May 4  Implicational Subcategories  (16.11), 16.1213, 16.1, 16.14  
Week 16  
May 7  Inferring Existential Types, Part 1  Due: Assignment 13  
May 9  Inferring Existential Types, Part 2  Determined Relations  Available: MakeUp Assignment (Due Sat, May 19 by 5pm) 
May 11  No more class! 
Homework Policies
Cornell University has a Code of Academic Integrity, with which you should be familiar. Violations of this code are treated very seriously by Cornell and can have longterm repercussions. In this course, you are encouraged to discuss the content of the course with other students, and you may also discuss homework problems with other students. However, you must do your own work, write up assignments yourself, and if you discuss a problem with another student, you are expected to document this fact in your writeup. It is a violation of the code to copy work, including programs, from other students; it is also a violation to use solutions to homework problems from previous iterations of the same course. Note that Cornell holds responsible for the code violation both the recipient and the donor of improper information.