3.5: Bonus- An introduction to limits and colimits - Mathematics

What do products of sets, the results of Π -operations on database instances, and meets ! in a preorder all have in common? The answer, as we shall see, is that they are all examples of limits. Recall that Π! takes a database instance I: C → Set and turns it into a set Π!(I).

More generally, a limit turns a functor F : C → D into an object of D.

Terminal objects and products

Terminal objects and products are each a sort of limit. Let’s discuss them in turn.

Terminal objects. The most basic limit is a terminal object.

Definition: 3.79.

Let C be a category. Then an object Z in C is a terminal object if, for each object C of C, there exists a unique morphism !: C Z.

Since this unique morphism exists for all objects in C, we say that terminal objects have a universal property.

Example 3.80.

In Set, any set with exactly one element is a terminal object. Why? Consider some such set {•}. Then for any other set C we need to check that there is exactly one function !: C → {•}. This unique function is the one that does the only thing that can be done: it maps each element c (in) C to the element • (in) {•}.

Exercise 3.81.

Let (P, ≤) be a preorder, let z (in) P be an element, and let P be the corresponding category (see Section 3.2.3). Show that z is a terminal object in P if and only if it is a top element in P: that is, if and only if for all c (in) P we have c z.

Exercise 3.82.

Name a terminal object in the category Cat. (Hint: recall Exercise 3.76.) ♦

Exercise (PageIndex{1})

Not every category has a terminal object. Find one that doesn’t. ♦

Proposition 3.84.

All terminal objects in a category C are isomorphic.

Proof. This is a simple, but powerful standard argument. Suppose Z and Z′ are both terminal objects in some category C. Then there exist (unique) maps a : Z Z′ and b : Z′ → Z. Composing these, we get a map a ; b : Z Z. Now since Z is terminal, this map Z Z must be unique. But (id_{Z}) is also such a map. So we must have a ; b = (id_{Z}). Similarly, we find that b ; a = (id_{Z'}). Thus a is an isomorphism, with inverse b. □

Remark 3.85 (“The limit” vs. “a limit”). Not only are all terminal objects isomorphic, there is a unique isomorphism between any two. We hence say “terminal objects are unique up to unique isomorphism.” To a category theorist, this is very nearly the same thing as saying “all terminal objects are equal.” Thus we often abuse terminology and talk of ‘the’ terminal object, rather than “a” terminal object. We will do the same for any sort of limit or colimit, e.g. speak of “the product” of two sets, rather than “a product.” We saw a similar phenomenon in Definition 1.81.

Products. Products are slightly more complicated to formalize than terminal objects, but they are familiar in practice.

Definition: 3.86.

Let C be a category, and let X, Y be objects in C. A product of X and Y is an object, denoted X × Y, together with morphisms (p_{X}) : X × Y → X and (p_{Y}) : X × Y Y such that for all objects C together with morphisms f : C X and g : C Y, there exists a unique morphism C X × Y, denoted ⟨f , g⟩, for which the following diagram commutes:

We will try to bring this down to earth in Example 3.87. Before we do, note that X × Y is an object equipped with morphisms to X and Y. Roughly speaking, it is like “the best object-equipped with morphisms to X and Y” in all of C, in the sense that any other object-equipped with morphisms to X and Y maps to it uniquely. This is called a universal property. It’s customary to use a dotted line to indicate the unique morphism that exists because of some universal property.

Example 3.87.

In Set, a product of two sets X and Y is their usual cartesian product

X × Y := {(x, y) | x (in) X, y (in) Y},

which comes with two projections pX : X × Y X and pY : X × Y Y, given by (_{pX})(x, y) := x and (_{pY})(x, y) := y.

Given any set C with functions f : C X and g :C Y, the unique map from C to X × Y such that the required diagram commutes is given by

f ,g⟩(c) := (f (c), g(c)).

Here is a picture of the product (underline{6}) × (underline{4}) of sets (underline{6}) and (underline{4}).

Exercise 3.88.

Let (P, ≤) be a preorder, let x, y (in) P be elements, and let P be the corresponding category. Show that the product x × y in P agrees with their meet x (wedge) y in P. ♦

Example 3.89.

Given two categories C and D, their product C × D may be given as follows. The objects of this category are pairs (c, d), where c is an object of C and d is an object of D. Similarly, morphisms (c, d) → (c′, d′) are pairs (f , g) where f : c c′ is a morphism in C and g : d d′ is a morphism in D. Composition of morphisms is simply given by composing each entry in the pair separately, so (f,g) ; (f′,g′) = (f ; f′,g' ; g′).

Exercise 3.90.

  1. What are the identity morphisms in a product category C × D?
  2. Why is composition in a product category associative?
  3. What is the product category 1 × 2?
  4. What is the product category P × Q when P and Q are preorders and P and Q are the corresponding categories? ♦

These two constructions, terminal objects and products, are subsumed by the notion of limit.


We’ll get a little abstract. Consider the definition of product. This says that given any pair of maps (X leftarrow C stackrel{g}{ ightarrow} Y), there exists a unique map C X × Y such that certain diagrams commute. This has the flavor of being terminal—there is a unique map to X × Y—but it seems a bit more complicated. How are the two ideas related?

It turns out that products are terminal objects, but of a different category, which we’ll call Cone(X, Y), the category of cones over X and Y in C. We will see in Exercise 3.91 that (X stackrel{p_{X}}{longleftarrow} X imes Y stackrel{p_{Y}}{longrightarrow} Y) is a terminal object in Cone(X, Y). An object of Cone(X, Y) is simply a pair of maps (X stackrel{f}{longleftarrow} X imes Y stackrel{g}{longrightarrow} Y). A morphism from (X stackrel{f}{longleftarrow} X imes Y stackrel{g}{longrightarrow} Y) to (X stackrel{f'}{longleftarrow} X imes Y stackrel{g'}{longrightarrow} Y) in Cone(X,Y)isamorphisma:CC inCsuchthat the following diagram commutes:

Exercise 3.91.

Check that a product (X stackrel{p_{X}}{longleftarrow} X imes Y stackrel{p_{Y}}{longrightarrow} Y) is exaclty the same as a terminal object in Cone(X,Y). ♦

We’re now ready for the abstract definition. Don’t worry if the details are unclear; the main point is that it is possible to unify terminal objects, maximal elements, and meets, products of sets, preorders, and categories, and many other familiar friends under the scope of a single definition. In fact, they’re all just terminal objects in different categories. Recall from Definition 3.51 that formally speaking, a diagram in C is just a functor D : J → C. Here J is called the indexing category of the diagram D.

Definition: 3.92.

Let D : J → C be a diagram. A cone (C, c∗) over D consists of

(i) an object C (in) C;

(ii) for each object j (in) J, a morphism (c_{j}) : C D(j).

To be a cone, these must satisfy the following property:

(a) for each f : j k in J, we have (c_{k}) = (c_{j}); D(f).

A morphism of cones (C, c∗) → (C′, c∗′) is a morphism a : C C′ in C such that for all j (in) J we have (c_{j}) = a ; (c'_{j}). Cones over D, and their morphisms, form a category Cone(D). The limit of D, denoted lim(D), is the terminal object in the category Cone(D). Say it is the cone lim(D) = (C, c∗); we refer to C as the limit object and the map (c_{j}) for any j (in) J as the (j^{th}) projection map.

For visualization purposes, if J is the free category on the graph

with five objects and five non-identity morphisms, then we may draw a diagram D : J → C inside C as on the left below, and a cone on it as on the right:

Here, any two parallel paths that start at C are considered the same. Note that both these diagrams depict a collection of objects and morphisms inside the category C.

Example 3.93.

Terminal objects are limits where the indexing category is empty, J = Ø.

Example (PageIndex{1})

Products are limits where the indexing category consists of two objects v,w and no arrows,

Finite limits in Set

Recall that this discussion was inspired by wanting to understand Π-operations, and in particular Π!. We can now see that a database instance I : C → Set is a diagram in Set. The functor Π! takes the limit of this diagram. In this subsection we give a formula describing the result. This captures all finite limits in Set.

In database theory, we work with categories C that are presented by a finite graph plus equations. We won’t explain the details, but it’s in fact enough just to work with the graph part: as far as limits are concerned, the equations in C don’t matter. For consistency with the rest of this section, let’s denote the database schema by J instead of C.

Theorm 3.95.

Let J be a category presented by the finite graph (V, A , s, t) together with some equations, and let D: J → Set be a set-valued functor. Write V = {v1,...,vn}. The set

(egin{aligned} &lim _{g} D:=left{left(d_{1}, ldots, d_{n} ight) mid d_{i} in Dleft(v_{i} ight) ext { for all } 1 leq i leq n ight. ext { and }
& ext { for all } a: v_{i} ightarrow v_{j} in A, ext { we have } left.D(a)left(d_{i} ight)=d_{j} ight}

together with the projection maps (p_{i}) : ((lim_{J}) D) → D(vi) given by (p_{i})(d1, . , dn) := di, is a limit of D.

Example 3.96.

If J is the empty graph (square), then n = 0: there are no vertices. There is ex- actly one empty tuple ( ), which vacuously satisfies the properties, so we’ve constructed the limit as the singleton set {( )} consisting of just the empty tuple. Thus the limit of the empty diagram, i.e. the terminal object in Set is the singleton set. See Remark 3.85.

Exercise 3.97.

Show that the limit formula in Theorem 3.95 works for products. See Example 3.94. ♦

Exercise 3.98.

If D: 1 → Set is a functor, what is the limit of D? Compute it using Theorem 3.95, and check your answer against Definition 3.92. ♦

Pullbacks. In particular, the condition that the limit of D : J → Set selects tuples (d1,...,dn) such that D(a)((d_{i})) = dj for each morphism a: i j in J allows us to use limits to select data that satisfies certain equations or constraints. This is what allows us to express queries in terms of limits. Here is an example.

Example 3.99.

If J is presented by the cospan graph (stackrel{x}{ullet} stackrel{f}{longrightarrow} stackrel{a}{ullet} stackrel{g}{longleftarrow} y), then its limit is known as a pullback. Given the diagram (X stackrel{f}{ ightarrow} A stackrel{g}{leftarrow} Y), the pull back is the cone shown on the left below:

The fact that the diagram commutes means that the diagonal arrow ca is in some sense superfluous, so one generally denotes pullbacks by dropping the diagonal arrow, naming the cone point X ×(_{A}) Y, and adding the ( ext { I }) symbol, as shown to the right above. Here is a picture to help us unpack the definition in Set. We take X = (underline{6}), Y = (underline{4}), and A to be the set of colors {red, blue, black}.

The functions f : (underline{6}) → A and g : (underline{4}) → A are expressed in the coloring of the dots: for example, g(2) = g(4) = red, while f (5) = black. The pullback selects pairs (i, j) (in) (underline{6}) × (underline{4}) such that f (i) and g(j) have the same color.

Remark 3.100. As mentioned following Definition 3.68, this definition of pullback is not to be confused with the pullback of a set-valued functor along a functor; they are for now best thought of as different concepts which accidentally have the same name. Due to the power of the primordial ooze, however, the pullback along a functor is a special case of pullback as the limit of a cospan: it can be understood as the pullback of a certain cospan in Cat. To unpack this, however, requires the notions of category of elements and discrete opfibration; ask your friendly neighborhood category theorist.

Brief note on colimits

Just like upper bounds have a dual concept—namely that of lower bounds—so limits have a dual concept: colimits. To expose the reader to this concept, we provide a succinct definition of these using opposite categories and opposite functors. The point, however, is just exposure; we will return to explore colimits in detail in Chapter 6.

Exercise 3.101.

Recall from Example 3.27 that every category C has an opposite Cop. Let F : C → D be a functor. How should we define its opposite, F (^{op}) : C(^{op}) → D(^{op})? That is, how should F (^{op}) act on objects, and how should it act on morphisms? ♦

Definition: 3.102.

Given a category C we say that a cocone in C is a cone in C(^{op}). Given a diagram D: J → C, we may take the limit of the functor D(^{op}): J(^{op}) → C(^{op}).

This is a cone in C(^{op}), and so by definition a cocone in C. The colimit of D is this cocone.

Definition 3.102 is like a compressed file: useful for transmitting quickly, but com- pletely useless for working with, unless you can successfully unpack it. We will unpack it later in Chapter 6 when we discuss electric circuits.

Explicitly using limits and colimits

induced using the universal property of colim K colim_K and lim I lim_I by the family of composites

of the limit projection for i ∈ I iin I and the colimit injection for k ∈ K kin K . Recall that I I -limits are said to commute with K K -colimits if and only if f f is an isomorphism for any D D .

I don’t know whether distributivity over uniform colimits is actually any weaker, but if it is, then the non-uniform version seems more correct.

For Kan extensions

This is because any pullback of a fibration is an exact square. This isomorphism has a mate

The formulation in terms of Kan extensions generalizes naturally to derivators, and can also be internalized to internal categories and fibrations in any locally cartesian closed category.

For sound doctrines

See Appendix A in AR for a comparison of this definition to the above explicit definition in the special case of distributivity of filtered colimits over small limits in locally finitely presentable categories and distributivity of sifted colimits over small limits in varieties of algebras.

3.5: Bonus- An introduction to limits and colimits - Mathematics

(ii) Categories.
Examples of categories and functors. Natural transformations. Products and coproducts. Free objects in a category.

(iii) More module theory.
Free modules and the Invariant Basis Property. Exact sequences of modules. Left exactness of Hom. Projective and injective modules. Chain conditions and composition series. Hilbert's Basis Theorem. The Nullstellensatz.

(iv) Semisimple rings.
Semisimple rings and modules. Group rings and Maschke's Theorem. Wedderburn'Theorem on semisimple artinian rings. Application to group representations.

(v) Tensor products and multilinear algebra.
Tensor products of modules. Mapping property of tensor products. Right exactness of tensor products. Flat modules. Exterior and symmetric products.

(vi) Introduction to homological algebra.
Complexes and resolutions. Definitions of Ext and Tor. Long exact sequences for Ext and Tor, (as time allows).

5. Exams and Homework

6. Final Exam

7. Grades

Grades will be computed according to the following scheme:
2 hourly exams 26%
5 sets of homework 39%
Final 35%
Total 100%

8. Office Hours

9. Bulletin Board

1/25/12. Homework 1 will be available for download on Thursday 1/26 pm. It will be due on 2/3/12.

1/25/12. The general policy on graded homework and take-home exams is that you are expected to work independently. This is a comp exam course, so grading has to be taken seriously. We will be watching for signs of collaboration!

1/26/12. Homework 1 is now available: it is due on 2/3/12.

2/1/12. There are extra office hours today 2-3.

2/10/12. Solutions to HW1 can be downloaded. Note that there is an error in the solution to Problem 3, (a) implies (b). An additional condition on the ring is needed. Everyone got full points for this part of the problem.

2/10/12. Exam 1 will be on Tuesday, February 21. This will be a take-home exam with limited time. The exam can be taken 9-12am or 1-4pm. A sign up sheet is available during class hour. Unless you have made alternative arrangements, you will pick up your exam from 339 IH at either 9am or 1pm and return it to the same place by 12 or 4 respectively. There will be envelopes hung on the door.

2/13/12. Exam 1 will cover everything we've had up to the end of last Friday's lecture.

2/21/12. Homework 2 is now available. It is due on 2/29/12.

2/24/12. Solutions to Exam 1 are now available.

3/2/12. Exam 2 will be an in-class midterm exam. It will be on Wednesday 3/28, in the week after the Break.

3/2/12. Solutions to Exam 1 have now been posted.

3/2/12. Homework 3 will be available on Monday, 3/5/12. It is due on 3/14/12.

3/8/12. Solutions to Homework 2 have now been posted.

3/12/12. Exam 2. This will be held in class on Wednesday 3/28. This is basically a question and answer exam designed to test general knowledge of the course material. It will cover everything from free modules to Maschke's Theorem. There are four questions: (i) definitions, (ii) statements of results, (iii) examples, (iv) you will be asked for the proof of a result on projective modules that we've had in class.

3/12/12. Arrangements for week March 26-30. I will be in Europe that week. On Monday 3/26 the class will be taken by Professor S. Ullom. Exam 2 on Wednesday 3/28 will be proctored by my TA, Jinhyung To. There will be no class on Friday 3/30. Normal classes resume on April 2. This means that my last office hours before Exam 2 are this week on Thursday 3/15/12. After that I expect to be in email contact.

3/21/12. Solutions to Homework 3 are now available.

3/21/12. Enjoy the Break, but remember Exam 2 on Wednesday, 3/28.

3/22/12. On 3/26 Professor Ullom will start tensor products. On 4/2 I will finish the material on representations of finite groups.

4/4/12. Today I will finish representations of finite groups and continue with tensor products.

4/4/12. The final exam. The final exam will be as scheduled on Friday, May 11, 7-10pm in 243 AH. It will cover the whole material of the course. The rules for the exam are open notes and class material such as homework or exam solutions. But no books or material copied from books will be allowed.

4/5/12. Solutions to Exam 1 have now been posted.

4/9/12. Homework 4 has now been posted it is due on 4/18/12.

4/19/12. Homework 5 is now available: it is due on 4/30/12.

4/19/12. You should take note of the changed grade distribution detailed above. This was necessary because we now have just two in-class exams and five sets of graded homework.

4/23/12. Notice to the Class. Last night I tripped over a box at home and badly bruised a knee. Today I am not mobile, so unfortunately I have to cancel class. I'm hoping to be able to give class on Wednesday, but stay tuned for further news. I'm sorry about this (DR).

4/24/12. There will be class tomorrow (Wednesday). I shall quickly finish symmetric algebras and discuss briefly exterior algebras. Then I'll start on our introduction to homological algebra.

4/30/12. The final exam. This will cover all topics in the course except for homological algebra. The exam is open notes and other class material. But please do not bring any books or other outside material into the exam. The exam date is May 11, 7-10pm in 243 AH. There will be office hours next week at times to be posted.

5/2/12. Homework 5 can be picked up at 339 IH in an envelope on the door. Solutions have been posted.

Math 8253: Class Outlines, Fall 2017

12/13/17: Application of our description of morphisms from a scheme to an affine scheme: every scheme has a unique morphism to Spec &Zopf. Relative projective n-spaces &Popf n S. [Class notes. Vakil: Sections 4.4.9-10]

12/11/17: Homework 5 is due. Morphisms from a scheme to an affine scheme are determined by homomorphisms of rings of global sections. The spectrum of a quasi-coherent algebra, relative affine n-spaces &Aopf n S. [Class notes. Hartshorne: Exercises II.2.4 and II.5.17(c)]

12/06/17: Examples: an affine line with a doubled point and the projective line. The proof of the theorem on scheme gluing. Gluing morphisms of schemes. [Class notes. Vakil: Sections 4.4.6-8. Hartshorne: Example II.2.3.6, Exercise II.2.12, Step 3 in the proof of Theorem II.3.3]

12/04/17: The proof of the theorem on the coherence of direct image. Construction of schemes by gluing: generalities. Example: an affine line with a doubled point. [Class notes. Vakil: Sections 4.4.4-5. Hartshorne: Exercise II.1.22, Sections II.2.3.5-6, Exercise II.2.12]

12/1/17: Irregular class meeting. The canceled class is made up at regular time on Friday in regular classroom. Direct and inverse images of quasi-coherent sheaves. [Class notes. Vakil: Sections 16.1-3. Hartshorne: Sections II.5.2 and II.5.8, Exercise II.5.3]

11/29/17: Class canceled: the instructor is sick.

11/27/17: Direct and inverse images of OX-modules. Exactness properties of direct and inverse image. [Class notes. Vakil: Section 16.3.4-5. Hartshorne: The beginning of Section II.5 (pp. 109-110)]

11/22/17: Class canceled for Wednesday evening before Thanksgiving. Happy holiday!

11/20/17: A remark on locally finitely presentable sheaves on a general scheme. Direct and inverse images of sheaves. [Class notes. Vakil: Sections 2.2.H, 2.6, 2.7. Hartshorne: P. 65, Exercise II.1.18]

11/15/17: Homework 4 is due. Quasi-coherent sheaves on a general scheme. [Class notes. Vakil: Section 13.4. Hartshorne: Section II.5 from 5.6 through 5.7]

11/13/17: Quasi-coherent and coherent sheaves on a general scheme, continued. [Class notes. Vakil: Sections 13.1-3, 13.6, skipping 13.3.4. Hartshorne: Section II.5 through 5.5, skipping direct and inverse images f* and f*]

11/8/17: Quasi-coherent and coherent sheaves on a general scheme. [Class notes. Vakil: Sections 2.5, 13.2-3. Hartshorne: pp. 63-64, Section II.5 through 5.6, skipping direct and inverse images f* and f*]

11/6/17: Abelian properties of sheaves: kernels, cokernels, exact sequences. Being associated with a module is a local property of a sheaf on an affine scheme. [Class notes. Vakil: Sections 2.5, 13.2-3. Hartshorne: pp. 63-64, Section II.5 through 5.6, skipping quasi-coherent sheaves on nonaffine schemes and direct and inverse images f* and f*]

11/1/17: Other forms of Hilbert's Nullstellensatz. Quasi-coherent sheaves. [Class notes. Vakil: Sections 3.2.3-I, 4.1.D-4. Hartshorne: Section II.5 through 5.1, skipping direct and inverse images f* and f*, and II.5.5]

10/30/17: The homework is due. The affine n-space and another form of Hilbert's Nullstellensatz. [Class notes. Vakil: Sections 3.2.3-I]

10/25/17: Affine schemes, general schemes and their morphisms. [Class notes. Vakil: Sections 4.3, 6.3 through 6.3.D. Hartshorne: Section II.2 before graded rings and Proj]

10/23/17: Ringed spaces, their morphisms. Locally ringed spaces. [Class notes. Vakil: Sections 2.3.A, 2.2.13, 6.2-3 before 6.3.2. Hartshorne: pp. 71-72, Section II.2 through p. 73]

10/18/17: Proving that the extension of the sheaf OX from basic open sets in X = Spec A to all opens sets is a sheaf: the case of a general covering. Sheaves associated to A-modules. The stalk. The étalé space of a presheaf. Sheafification. [Class notes. Vakil: Sections 2.7, 2.2.3-6, 2.2.11, 2.4. Hartshorne: Section II.5, skipping morphisms, graded rings and Proj]

10/16/17: The homework is due. Discussion of homework. Extending the sheaf OX from basic open sets in X = Spec A to all opens sets. Proving it is a sheaf (the case of a covering of an open set by basic open sests). [Class notes. Vakil: Section 2.7. Hartshorne: pp. 70-72]

10/11/17: Inductive and projective limits, a.k.a. colimits and limits. [Class notes. Vakil: Section 1.4]

10/9/17: Constructing the structure sheaf on the spectrum of a ring: sheaf Axiom 2 (gluing) of the functor D(f) &mapsto Af on the basic open sets. Construction of the structure sheaf on Spec A. [Class notes. Hartshorne: Section II.2 (pp. 70-72). Vakil: Section 4.1 after Exercise 4.1.B]

10/4/17: Constructing the structure sheaf on the spectrum of a ring: sheaf Axiom 1 (locality) of the functor D(f) &mapsto Af on the basic open sets. [Class notes. Hartshorne: Section II.2 (pp. 70-72). Vakil: Section 4.1 through Exercise 4.1.B]

10/2/17: Maps of spectra, continued. Sheaves. [Class notes. Hartshorne: Section II.1. Vakil: Sections 2.1, 2.2, 3.2.9-10]

9/27/17: The first homework is due. Discussion of homework. Maps of spectra. [Class notes. Hartshorne: Section II.2 before graded rings, ignoring sheaves. Vakil: Sections 3.2.9-10]

9/25/17: Zariski topology: compactness. Irreducibility. Maps of spectra under quotients. The generic point of an irreducible set. [Class notes. Hartshorne: Section II.2 before graded rings, ignoring morphisms and sheaves for the time being. Vakil: Sections 3.3, 3.6]

9/20/17: More on spectra and their topology. The ideal-closed set correspondence. Kolmogorov separation. [Class notes. Hartshorne: Section II.2 before graded rings, ignoring morphisms and sheaves for the time being. Vakil: Sections 3.2 skipping 3.2.9-10, 3.7]

9/18/17: The spectrum of a ring: basic closed and open sets, the Zariski topology and its properties. [Class notes. Hartshorne: Section II.2 before graded rings, ignoring morphisms and sheaves for the time being. Vakil: Sections 3.1, 3.2 through 3.2.8, 3.4, 3.5]

9/15/17: Reminder: no class meetings on Fridays anymore.

9/13/17: Coordinate interpretation of morphisms of solution functors. Gluing solution functors. The idea of a scheme. [Class notes. Hartshorne: pp. 58-59. Vakil: Intro to Section 3.1.]

9/11/17: Maps between solution sets of different polynomial systems. Yoneda's Lemma. The equivalence of the category of solution functors of polynomial systems to the opposite of the category of finitely presentable k-algebras. [Class notes. Vakil: Sections 1.3.10-11. Compare our theorems to Proposition 3.5 and its corollaries in Hartshorne's Chapter I.]

9/8/17: Class meeting canceled and replaced by a talk by Professor Yuri Tschinkel on Rationality Problems (regular classroom, regular time). [Preprint]

9/6/17: Introduction. Syllabus handed out. Motivation (a modern twist on Classical Algebraic Geometry): solution sets of a polynomial system V over a ring k as a functor of points on the category of k-algebras k'. (To brush up on categories and functors, read Section 1.2 of Vakil's Rising Sea.) The equivalence of this functor to the functor Homk(O(V), &ndash) of k-algebra homomorphisms O(V) &rarr k'. [Syllabus. Class notes. Vakil: Section 1.2. Hartshorne: Pages 1-2 before the definition of an algebraic set.]

Cross-Listed Courses

Computer Science

COMS S3251 Computational Linear Algebra. 3 points.

Not offered during 2021-22 academic year.

Prerequisites: two terms of calculus.

Computational linear algebra, solution of linear systems, sparse linear systems, least squares, eigenvalue problems, and numerical solution of other multivariate problems as time permits.

COMS W4203 Graph Theory. 3 points.

Prerequisites: ( COMS W3203 )

General introduction to graph theory. Isomorphism testing, algebraic specification, symmetries, spanning trees, traversability, planarity, drawings on higher-order surfaces, colorings, extremal graphs, random graphs, graphical measurement, directed graphs, Burnside-Polya counting, voltage graph theory.


Prerequisites: Any introductory course in computer programming.
Prerequisites: Any introductory course in computer programming. Logic and formal proofs, sequences and summation, mathematical induction, binomial coefficients, elements of finite probability, recurrence relations, equivalence relations and partial orderings, and topics in graph theory (including isomorphism, traversability, planarity, and colorings)

Industrial Engineering and Operations Research

CSOR E4010 Graph Theory: A Combinatorial View. 3 points.

Lect: 3.Not offered during 2021-22 academic year.

Prerequisites: Linear Algebra, or instructor's permission.

Graph Theory is an important part of the theoretical basis of operations research. A good understanding of the basic fundamentals of graph theory is necessary in order to apply the theory successfully in the future. This is an introductory course in graph theory with emphasis on its combinatorial aspects. It covers basic definitions, and some fundamental concepts in graph theory and its applications. Topics include trees and forests graph coloring, connectivity, matching theory and others. This course will provide a solid foundation for students in the IEOR department, on which further courses may build.

Milnor exact sequences

For homotopy groups


(Milnor exact sequence for homotopy groups)

the failure of the limit over the homotopy groups of the stages of the tower to equal the homotopy groups of the limit of the tower is at most in the kernel of the canonical comparison map


With respect to the classical model structure on simplicial sets or the classical model structure on topological spaces, a tower of fibrations as stated is a fibrant object in the injective model structure on functors [ ( ℕ , ≥ ) , sSet ] inj [(mathbb,geq), sSet]_ ( [ ( ℕ , ≥ ) , Top ] inj [(mathbb,geq), Top]_ ) (prop). Hence the plain limit over this diagram represents the homotopy limit. By the discussion there, up to weak equivalence that homotopy limit is also the pullback in

where on the right we have the product over all the canonical fibrations out of the path space objects. Hence also the left vertical morphism is a fibration, and so by taking its fiber over a basepoint, the pasting law gives a homotopy fiber sequence

Chopping that off by forming kernel and cokernel yields the claim for positive q q . For q = 0 q = 0 it follows by inspection.

For chain homology


be a tower of chain complexes (of abelian groups) such that it satisfies degree-wise the Mittag-Leffler condition, def. , and write

For generalized cohomology groups

Of spaces


(Milnor exact sequence for generalized cohomology)

Then the canonical morphisms make a short exact sequence

the failure of the canonical comparison map E ˜ • ( X ) → lim ⟵ E ˜ • ( X n ) ilde E^ullet(X) o underset ilde E^ullet(X_n) to the limit of the cohomology groups on the finite stages to be an isomorphism is at most in a non-vanishing kernel


for the disjoint unions of the cylinders over all the stages in even and all those in odd degree, respectively.

These come with canonical inclusion maps into the mapping telescope Tel ( X • ) Tel(X_ullet) (def.), which we denote by

The first two are obvious, the third is this proposition.

hence that the bottom sequence is also a long exact sequence.

This is the morphism from def. for the sequence

Hence truncating the above long exact sequence by forming kernel and cokernel of ∂ partial , the result follows via remark and definition .

Office: 1097 Evans Hall
Office Hours (Spring 2018): W 12:30-3:30
Email: qchu[at]math[dot]berkeley[dot]edu

I am a sixth-year graduate student at the University of California, Berkeley. (Note that there is another graduate student of the same name here.) My advisor is David Nadler.



Spring 2018: Math 110 Linear Algebra (Frenkel). Course website.

Fall 2017: Math 55 Discrete Mathematics (Holtz). Section website (last updated 8/27/17).

Spring 2016: Math 54 Linear Algebra and Differential Equations (Yuan). Course website, section website (last updated 2/19/16).

Fall 2015: Math 54 Linear Algebra and Differential Equations (Nadler). Course website, section website (last updated 11/11/15)

Spring 2014: Math 1B Calculus (Reshetikhin). Course website, section website (last updated 4/23/14)

Fall 2013: Math 1A Calculus (Steel). Course website, section website (last updated 12/10/13)


  • Commitment semantics for sequential decision making under reward uncertainty, CHAI Seminar, UC Berkeley, 7/4/2017.
  • Wick's lemma, Factorization Algebras Seminar, UC Berkeley, 2/25/2016.
  • Higher linear algebra, GRASP Seminar, UC Berkeley, 11/6/2015.
  • Derived stacks, Student Algebraic Geometry Seminar, UC Berkeley, 9/21/2015.
  • Structure theory of real semisimple Lie groups, Branes and Representations Seminar, UC Berkeley, 3/6/2015.
  • Clifford algebras and K-theory, xkcd Seminar, Stanford, 10/29/2014.
  • Concrete interpretations of higher cohomology, GRASP Seminar, UC Berkeley, 10/10/2014.
  • The index theorem for the Dirac operator (after Witten), Symplectic and Quantum Geometry Seminar, UC Berkeley, 10/8/2014.
  • Examples of 3-manifolds, Low-Dimensional Topology and Differential Geometry Seminar, UC Berkeley, 9/12/2014.
  • Introduction to groupoids, Student Geometry and Topology Seminar, UC Berkeley, 3/10/2014.
  • Quantum field theory on finite graphs, GRASP Seminar, UC Berkeley, 2/14/2014.
  • What is a groupoid?, Nadler Seminar, UC Berkeley, 2/13/2014.
  • Prefactorization algebras, Seminar on Factorization Algebras in Quantum Field Theory, UC Berkeley, 2/5/2014.
  • Koszul algebras and Koszul duality, Koszul Duality Seminar, UC Berkeley, 9/26/13.
  • Homotopy limits and colimits, Pre-MSRI Semester Seminar, UC Berkeley, 9/24/13.
  • Poisson algebras and deformation quantization, GRASP Seminar, UC Berkeley, 9/13/13.
  • The Euler characteristic for dummies, Many Cheerful Facts Seminar, UC Berkeley, 4/2/13.
  • Diagrammatic algebra and the representation theory of SU(2), GRASP Seminar, UC Berkeley, 10/5/12.

Classes, Seminars, and Conferences

Notes are unedited. Any errors introduced are mine.

  • Math 276 An Invitation to Factorization Algebras (Teichner, Mazel-Gee). Notes (last updated 4/18/16).
    (Hess, Sinha). (Nadler).
  • Math 290 Branes and Representations (Teleman).
    . Notes (last updated 12/13/14)
  • Math 290 Symplectic and Quantum Geometry (Teleman).
  • West Coast Algebraic Topology Summer School: Topological Field Theories (Ayala, Blumberg, Francis, Freed, Gwilliam, Poirier, Schommer-Pries, Adem, Cohen, Sinha). Syllabus, notes and problem sets
  • Math 290 Factorization Algebras in Quantum Field Theory (Gwilliam, Teichner).
  • Math 276 Functorial Field Theories and Ring Spectra (Teichner).
  • Math 261B Lie Groups (Serganova). Notes (last updated 12/4/13, slightly incomplete)
  • Math 274 Microlocal Geometry (Nadler). Notes (last updated 12/5/13)
  • Math 208 C*-algebras (Rieffel). Notes (last updated 5/3/13)
  • Math 239 Discrete Mathematics for the Life Sciences (Pachter). Notes (last updated 4/25/13, incomplete)
  • Math 256B Algebraic Geometry (Nadler). Notes (last updated 4/25/13, incomplete)
  • Math 253 Homological Algebra (Wodzicki). Notes (last updated 11/18/12)
  • Math 274 The Geometry and Algebra of Curves on Surfaces (Thurston). Notes (last updated 1/14/13)
  • Math 275 Quantum Field Theory (Reshetikhin). Notes (last updated 11/18/12)


On December 6th, 2013, I passed my qualifying exam. Here is my syllabus and transcript.

In the summer of 2013 I was an instructor at the Summer Program for Applied Rationality and Cognition.

In the summer of 2012 I was a counselor at the Program in Mathematics for Young Scientists (PROMYS), where I had previously been a student in the summer of 2006.

Angeleri Hügel, L.: On the abundance of silting modules. In: Surveys in Representation Theory of Algebras, Contemp. Math., vol. 716, pp. 1–23. American Mathematical Society, Providence (2018)

Angeleri Hügel, L., Coelho, F.U.: Infinitely generated tilting modules of finite projective dimension. Forum Math. 13(2), 239–250 (2001)

Angeleri Hügel, L., Marks, F., Vitória, J.: Torsion pairs in silting theory. Pac. J. Math. 291(2), 257–278 (2017)

Bazzoni, S.: The $t$-structure induced by an $n$-tilting module. Trans. Am. Math. Soc. 371(9), 6309–6340 (2019)

Beĭlinson, A.A., Bernstein, J., Deligne, P.: Faisceaux pervers. Analysis and topology on singular spaces. I (Luminy, 1981), Astérisque, vol. 100, pp. 5–171. Soc. Math. France, Paris (1982)

Beligiannis, A.: Relative homological algebra and purity in triangulated categories. J. Algebra 227(1), 268–361 (2000)

Bondarko, M.V.: On torsion pairs, (well generated) weight structures, adjacent t-structures, and related (co)homological functors. arXiv:1611.00754 (2016)

Chang, C.C., Keisler, H.J.: Model Theory, Studies in Logic and the Foundations of Mathematics, vol. 73, 3rd edn. North-Holland, Amsterdam (1990)

Colpi, R., Mantese, F., Tonolo, A.: Cotorsion pairs, torsion pairs, and $Sigma $-pure-injective cotilting modules. J. Pure Appl. Algebra 214(5), 519–525 (2010)

Crawley-Boevey, W.: Infinite-dimensional modules in the representation theory of finite-dimensional algebras. In: Algebras and Modules, I (Trondheim, 1996), CMS Conf. Proc., vol. 23, pp. 29–54. American Mathematical Society, Providence (1998)

Garkusha, G., Prest, M.: Triangulated categories and the Ziegler spectrum. Algebr. Represent. Theory 8(4), 499–523 (2005)

Groth, M.: Derivators, pointed derivators and stable derivators. Algebr. Geom. Topol. 13(1), 313–374 (2013)

Groth, M.: Revisiting the canonicity of canonical triangulations. Theory Appl. Categ. 33, 350–389, Paper No. 14 (2018)

Happel, D., Reiten, I., Smalø, S.O.: Tilting in abelian categories and quasitilted algebras. Mem. Am. Math. Soc. 120(575), viii+ 88 (1996)

Harada, M.: Perfect categories. V. Osaka J. Math. 10, 585–596 (1973)

Herzog, I.: The Ziegler spectrum of a locally coherent Grothendieck category. Proc. Lond. Math. Soc. (3) 74(3), 503–558 (1997)

Keller, B.: Deriving DG categories. Ann. Sci. École Norm. Sup. (4) 27(1), 63–102 (1994)

Keller, B., Vossieck, D.: Aisles in derived categories. Bull. Soc. Math. Belg. Sér. A 40(2), 239–253 (1988). Deuxième Contact Franco-Belge en Algèbre (Faulx-les-Tombes, 1987)

Krause, H.: The spectrum of a locally coherent category. J. Pure Appl. Algebra 114(3), 259–271 (1997)

Krause, H.: Exactly definable categories. J. Algebra 201(2), 456–492 (1998)

Krause, H.: Smashing subcategories and the telescope conjecture–an algebraic approach. Invent. Math. 139(1), 99–133 (2000)

Krause, H.: Coherent functors in stable homotopy theory. Fundam. Math. 173(1), 33–56 (2002)

Krause, H.: The stable derived category of a Noetherian scheme. Compos. Math. 141(5), 1128–1162 (2005)

Marks, F., Vitória, J.: Silting and cosilting classes in derived categories. J. Algebra 501(2), 526–544 (2018)

Nicolás, P., Saorín, M., Zvonareva, A.: Silting theory in triangulated categories with coproducts. J. Pure Appl. Algebra 223(6), 2273–2319 (2019)

Parra, C.E., Saorín, M.: Direct limits in the heart of a t-structure: the case of a torsion pair. J. Pure Appl. Algebra 219(9), 4117–4143 (2015)

Parra, C.E., Saorín, M.: Addendum to “Direct limits in the heart of a t-structure: the case of a torsion pair” [J. Pure Appl. Algebra 219 (9) (2015) 4117–4143] [MR3336001]. J. Pure Appl. Algebra 220(6), 2467–2469 (2016)

Prest, M.: Model Theory and Modules, London Mathematical Society Lecture Note Series, vol. 130. Cambridge University Press, Cambridge (1988)

Prest, M.: Purity, Spectra and Localisation, Encyclopedia of Mathematics and its Applications, vol. 121. Cambridge University Press, Cambridge (2009)

Prest, M.: Definable additive categories: purity and model theory. Mem. Am. Math. Soc. 210(987), vi+109 (2011)

Psaroudakis, C., Vitória, J.: Realisation functors in tilting theory. Math. Z. 288(3), 965–1028 (2018)

Saorín, M.: On locally coherent hearts. Pac. J. Math. 287(1), 199–221 (2017)

Saorín, M., Št’ovíek, J., Virili, S.: t-structures on stable derivators and Grothendieck hearts. arXiv:1708.07540 (2018)

Stenström, B.: Coherent rings and $F, P$-injective modules. J. Lond. Math. Soc. 2(2), 323–329 (1970)

Šťovíček, J.: Derived equivalences induced by big cotilting modules. Adv. Math. 263, 45–87 (2014)

Math/Stat 431 Introduction to the Theory of Probability

Math 431 is an introduction to the theory of probability, the part of mathematics that studies random phenomena. We model simple random experiments mathematically and learn techniques for studying these models. Topics covered include axioms of probability, random variables, the most important discrete and continuous probability distributions, expectations, moment generating functions, conditional probability and conditional expectations, multivariate distributions, Markov's and Chebyshev's inequalities, laws of large numbers, and the central limit theorem.

Math 431 is not a course in statistics. Statistics is a discipline mainly concerned with analyzing and representing data. Probability theory forms the mathematical foundation of statistics, but the two disciplines are separate.

From a broad intellectual perspective, probability is one of the core areas of mathematics with its own distinct style of reasoning. Among the other core areas are analysis, algebra, geometry/topology, logic and computation.

To go beyond 431 in probability you should take next Math 521 - Analysis, and after that one or both of these: Math 632 - Introduction to Stochastic Processes and Math 635 - Introduction to Brownian Motion and Stochastic Calculus. Those who would like a proof based introduction to probability could consider taking Math 531 - Probability Theory (531 requires a proof based course as a prerequisite).

Where is probability used?

Probability theory is ubiquitous in natural science, social science and engineering, so this course can be valuable in conjunction with many different majors. Aside from being a beautiful subject in and of itself, is used throughout the sciences and industry. For example, in biology many models of cellular phenomena are now modeled probabilistically as opposed to deterministically. As for industry, many models used by insurance and financial companies are probabilistic in nature. Thus, those wishing to go into actuarial science or finance need to have a solid understanding of probability. Probabilistic models show up in the study of networks, making probability theory useful for those interested in computer science and information technology.


To be technically prepared for Math 431 one needs to be comfortable with the language of sets and calculus, including multivariable calculus, and be ready for abstract reasoning. Basic techniques of counting is also useful, but we will review these along the way. Probability theory can seem very hard in the beginning, even after success in past math courses.

[email protected]

We will use the [email protected] website of the course to post homework assignments and solutions. The lecture notes will also be posted there.


  • A first course in Probability, by Sheldon Ross
  • Probability, by Jim Pitman.
  • Probability, statistics, and stochastic processes, by Peter Olofsson.
  • Probability and random processes, by Geoffrey Grimmett and David Stirzaker.
  • Midterm exam 1: Thursday, October 13 , 7:15-8:45 PM, 1310 Sterling
  • Midterm exam 2: Wednesday, November 30, 7:15-8:45 PM, 1310 Sterling
  • Final exam: Tuesday, December 20, 12:25PM - 2:25PM, Room TBA


  • 1st quiz: September 13, Tuesday, end of class.
  • 2nd quiz: September 20, Tuesday, end of class.
  • 3rd quiz: September 27, Tuesday, end of the class
  • 4th quiz: October 4, Tuesday, end of the class

There will be no more quizzes in the semester.


Homework assignments will be posted on the [email protected] site of the course. Weekly homework assignments are usually due on Thursday at the beginning of the class. You can also submit your solution in an electronic form via [email protected], but it has to arrive by 9:30AM on the due date. Note that there is a (short) homework assignment due on the first Thursday (September 8).
Some homework assignments will contain bonus problems for those who would like extra challenge. The points from the bonus problems will be converted into extra credit at the end of the semester.

Instructions for homework

  • Observe rules of academic integrity. Handing in plagiarized work, whether copied from a fellow student or off the web, is not acceptable. Plagiarism cases will lead to sanctions.
  • Homework is collected at the beginning of the class period on the due date. No late assignments will be accepted. You can bring the homework earlier to the instructor's office.
  • Working in groups on homework assignments is strongly encouraged however, every student must write their own assignments.
  • Organize your work neatly. Use proper English. Write in complete English or mathematical sentences. Answers should be simplified as much as possible. If the answer is a simple fraction or expression, a decimal answers from a calculator is not necessary. For some exercises you will need a calculator to get the final answer.
  • Answers to some exercises are in the back of the book, so answers alone carry no credit. It's all in the reasoning you write down.
  • Put problems in the correct order and staple your pages together.
  • Do not use paper torn out of a binder.
  • Be neat. There should not be text crossed out.
  • Recopy your problems. Do not hand in your rough draft or first attempt.
  • Papers that are messy, disorganized or unreadable cannot be graded.
  • I strongly encourage you to type up your solutions (perhaps using Latex).

Weekly schedule

Here is a tentative weekly schedule, to be adjusted as we go. The numbers refer to sections in lecture notes that can be found at the [email protected] website.

The Math Club provides interesting lectures and other math-related events. Everybody is welcome. Summer Reading Suggestions

--> Notice: Prof. Kurtz will teach our class on Tuesday Oct. 29. We will not meet on Thursday Oct. 31. We can use this extra time later if we need it. -->

Gradient Tree Boosting Markdown Syntax for Jupyter

But instead of writing all of that yourself, you may prefer to…

Here is the Markdown syntax in plain text:

WOW! That was a lot of stuff you went through! Claps claps claps …

BONUS 4: Quick and Criminally Short Explanation of Gradient Tree Boosting Algorithm

Gradient Tree Boosting Algorithm combines Decision Trees in an additive and sequential manner to incrementally make better predictions on training data.

It starts with an initial constant value of prediction for all data points (which is mean value in case of regression).

In every subsequent iteration, it fits a tree to negative of gradient of loss with respect to predictions of model learned so far (which in regression case turns out to be error i.e. actual-predicted value).

This new tree is then combined with the previous trees to get updated predictions for each data point.

You stop the algorithm at a preset number of iterations.

PS: This is a very very generic explanation diluting a lot of important details.

BONUS 5: Variance Covariance Matrix in Markdown

The goal of this seminar is to understand the work of Barwick, Glasman, and Haine on stratified étale homotopy theory, following their paper/book Exodromy [Exo]. This is a generalisation of monodromy representations of ℓ-adic local systems to constructible sheaves.

We will start with the version for stratified topological spaces, where MacPherson defined the exit path category, an analogue of the fundamental groupoid for stratified spaces. Next, we will discuss higher categorical versions due to Treumann and Lurie. We then spend some time reviewing classical étale homotopy theory, and proceed to the stratified étale homotopy type.

The ultimate goal is to get to the exodromy theorem for ℓ-adic constructible sheaves. As in the monodromy case, there is a topology that interacts with the ℓ-adic topology. To make sense of this in a higher categorical context, we need to talk about pyknotic objects, which some of you may know under the different guise of condensed mathematics.

Watch the video: Εισαγωγή στα Όρια Συναρτήσεων part 1 Μαθηματικά και Στοιχεία Στατιστικής Γ Λυκείου (November 2021).