Skip to main content

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:15-12:05

Location: 206 Upson Hall

Instructor: Ross Tate
Office: 434 Gates Hall
Office Hours: Friday 1:30-2:30

Grading There will be a small homework assignment almost every week (no midterms or final):
Assignments: 100%

Piazza: http://piazza.com/cornell/spring2018/cs6117

Related Reading

Schedule

DateTopicReadingAssignments
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,4c-4f), 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.10-12, 3.13(1-2,4,6), 3.14-15
Isomorphisms
Feb 2 Functors, Part 1 3.17-18, 3.20(1-4,6-8,10,13)
Functors
Week 3
Feb 5 No Lecture
Feb 7 No Lecture
Feb 9 Functors, Part 2 3.21,3.22(2),3.23-24,3.25(1),3.26(1-3)
3.27(2-3),3.29(1-2,4),3.30(1),3.31-32
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,C10-C12) Due: Assignment 4
Feb 28 Reflective Subcategories, Part 2 4.19-23
Reflections
Available: Assignment 5
Mar 2 Coreflective Subcategories 4.25, 4.26(A1,B4), 4.27
Week 7
Mar 5 Duality
Contravariant Functors
3.5-6
3.20(4,5,8-9)
Due: Assignment 5
Mar 7 Concrete Categories 5.1, 5.2(1-2,4,7), 5.3, 5.4(1-3), 5.5(1-4), 5.7(1-2), 5.8
5.9, 5.10(1-3), 5.11(1-4), 5.12, 5.14, 5.18-19
5.21-22, 5.23(1,6), 5.26
5.28, 5.30(2), 5.31
Available: Assignment 6
Mar 9 Functor-Induced Categories 5.37, 5.38(1,4), 5.39
5.40-42, 5.44
Coalgebras
Week 8
Mar 12 Natural Transformations, Part 1 6.1, 6.2(1-2,5,6), 6.5, 6.6(1,4-5), 6.7 Due: Assignment 6
Mar 14 Natural Transformations, Part 2 6.3-4, 6.13-14, 6A Available: Assignment 7
Mar 16 2-Categories 2-Categories
Week 9
Mar 19 Initial, Terminal, and Zero Objects
Discrete and Indiscrete Objects
Separators and Coseparators
Sections and Retracts
7.1, 7.2(1-4,8-9), 7.3-9
8.1, 8.2(1-4,7), 8.3-4, 8.5(1-5)
7.10, 7.11(1-2,4-5), 7.12, 7.16-17, 7.18(1,3,8)
7.19, 7.20(1,6), 7.21-24, 7.25(1), 7.26-31
Due: Assignment 7
Mar 21 Monomorphisms and Epimorphisms
Subobjects and Quotient Objects
Equalizers and Coequalizers
Regular Monomorphisms and Epimorphisms
7.32, 7.33(1,3-4,7), 7.34-36, 7.37(2), 7.39, 7.40(1-3,5-6), 7.41-45
7.77-78, 7.84-85, 7.86(1-2,4)
7.51, 7.52(1), 7.53-55, 7.68, 7.69(1-3), 7.70
7.56-59, 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.1-4, 10.62
10.5-6, 10.7(2), 10.9-10, 10.64, 10.11-16, 10.65
10.19, 10.20(1-2,5-8), 10.21-30, 10.31(1-2,4), 10.34-37, 10.67(1-3,8)
10.41-43, 10.45-46, 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(2-4,6), 8.18, 8.19(1), 8.40(1), 17.1
21.1, 21.7, 21.8(1-3), 21.9-11
8.22, 8.23(1,3,5,8,16), 8.24-28, 8.40(2), 8.41(1,2a-2b)
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.1-3
Monads and Comonads
Due: Assignment 9
Available: Assignment 10
Apr 11 Monad Algebras 20.4, 20.5(1-3), 20.7-11, 20.12(1-3,5-8,10)
Monad Algebras
Apr 13 Effects 20B(a-c)
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,3-4,6), 15.4-18
Factorization Structures
Available: Assignment 13
May 4 Implicational Subcategories (16.11), 16.12-13, 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: Make-Up 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 long-term 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 write-up. 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.