The New York City

Category Theory Seminar

Department of Computer Science
Department of Mathematics
The Graduate Center of The City University of New York

THIS SEMESTER, SOME TALKS WILL BE IN-PERSON AND SOME WILL BE ON ZOOM.
Time: Wednesdays 07:00 PM Eastern Time (US and Canada)

IN-PERSON INFORMATION:
365 Fifth Avenue (at 34th Street) map
(Diagonally across from the Empire State Building)
New York, NY 10016-4309
Room 6417
The videos of the lectures will be put up on YouTube a few hours after the lecture.


ZOOM INFORMATION:
https://brooklyn-cuny-edu.zoom.us/j/83479113097?pwd=Wis5OG80WUdScFQwcXdFRlVQdjZoZz09
Meeting ID: 834 7911 3097
Passcode: NYCCTS

Seminar web page.
YouTube videoed talks.
Previous semesters.
researchseminars.org page.

Contact N. Yanofsky to schedule a speaker
or to add a name to the seminar mailing list.

Fall 2023



  • Speaker:     Tomáš Gonda, University of Innsbruck.

  • Date and Time:     Wednesday September 27, 2023, 5:00 - 6:00 PM. ZOOM TALK. NOTE SPECIAL TIME!

  • Title:     A Framework for Universality in Physics, Computer Science, and Beyond.

  • Abstract: Turing machines and spin models share a notion of universality according to which some simulate all others. We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and others. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.


  • Speaker:     Thiago Alexandre, University of São Paulo (Brazil).

  • Date and Time:     Wednesday October 11, 2023, 7:00 - 8:30 PM. IN PERSON TALK.

  • Title:     Internal homotopy theories.

  • Abstract: The idea of 'Homotopy theories' was introduced by Heller in his seminal paper from 1988. Two years later, Grothendieck discovered the theory of derivators (1990), exposed in his late manuscript Les Dérivateurs, and developed further by several authors. Essentially, there are no significant differences between Heller's homotopy theories and Grothendieck's derivators. They are tautologically the same 2-categorical yoga. However, they come from distinct motivations. For Heller, derivators should be a definitive answer to the question "What is a homotopy theory?", while for Grothendieck, who was strongly inspired by topos cohomology, the first main motivation for derivators was to surpass some technical deficiencies that appeared in the theory of triangulated categories. Indeed, Grothendieck designed the axioms of derivators in light of a certain 2-functorial construction, which associates the corresponding (abelian) derived category to each topos, and more importantly, inverse and direct cohomological images to each geometric morphism. It was from this 2-functorial construction, from where topos cohomology arises, that Grothendieck discovered the axioms of derivators, which are surprisingly the same as Heller's homotopy theories. Nowadays, it is commonly accepted that a homotopy theory is a quasi-category, and they can all be presented by a localizer (M,W), i.e., a couple composed by a category M and a class of arrows in W. This point of view is not so far from Heller, since pre-derivators, quasi-categories, and localizers, are essentially equivalent as an answer to the question "What is a homotopy theory?". In my talk, I will expose these subjects in more detail, and I am also going to explore how to internalize a homotopy theory in an arbitrary (Grothendieck) topos, a problem which strongly relates formal logic and homotopical algebra.


  • Speaker:     Michael Shulman, University of San Diego.

  • Date and Time:     Wednesday October 18, 2023, 7:00 - 8:30 PM. ZOOM TALK.

  • Title:     The derivator of setoids.

  • Abstract: The question of "what is a homotopy theory" or "what is a higher category" is already interesting in classical mathematics, but in constructive mathematics (such as the internal logic of a topos) it becomes even more subtle. In particular, existing constructive attempts to formulate a homotopy theory of spaces (infinity-groupoids) have the curious property that their "0-truncated objects" are more general than ordinary sets, being instead some kind of "free exact completion" of the category of sets (a.k.a. "setoids"). It is at present unclear whether this is a necessary feature of a constructive homotopy theory or whether it can be avoided somehow. One way to find some evidence about this question is to use the "derivators" of Heller, Franke, and Grothendieck, as they give us access to higher homotopical structure without depending on a preconcieved notion of what such a thing should be. It turns out that constructively, the free exact completion of the category of sets naturally forms a derivator that has a universal property analogous to the classical category of sets and to the classical homotopy theory of spaces: it is the "free cocompletion of a point" in a certain universe. This suggests that either setoids are an unavoidable aspect of constructive homotopy theory, or more radical modifications to the notion of homotopy theory are needed.


  • Speaker:     Emilio Minichiello, CUNY Graduate Center.

  • Date and Time:     Wednesday October 25, 2023, 7:00 - 8:30 PM. IN PERSON TALK.

  • Title:     A Mathematical Model of Package Management Systems.

  • Abstract: In this talk, I will review some recent joint work with Gershom Bazerman and Raymond Puzio. The motivation is simple: provide a mathematical model of package management systems, such as the Hackage package respository for Haskell, or Homebrew for Mac users. We introduce Dependency Structures with Choice (DSC) which are sets equipped with a collection of possible dependency sets for every element and satisfying some simple conditions motivated from real life use cases. We define a notion of morphism of DSCs, and prove that the resulting category of DSCs is equivalent to the category of antimatroids, which are mathematical structures found in combinatorics and computer science. We analyze this category, proving that it is finitely complete, has coproducts and an initial object, but does not have all coequalizers. Further, we construct a functor from a category of DSCs equipped with a certain subclass of morphisms to the opposite of the category of finite distributive lattices, making use of a simple finite characterization of the Bruns-Lakser completion.


  • Speaker:     Larry Moss, Indiana University, Bloomington .

  • Date and Time:     Wednesday November 8, 2023, 7:00 - 8:30 PM. ZOOM TALK

  • Title:     On Kripke, Vietoris, and Hausdorff Polynomial Functors.

  • Abstract: The Vietoris space of compact subsets of a given Hausdorff space yields an endofunctor V on the category of Hausdorff spaces. Vietoris polynomial endofunctors on that category are built from V, the identity and constant functors by forming products, coproducts and compositions. These functors are known to have terminal coalgebras and we deduce that they also have initial algebras. We present an analogous class of endofunctors on the category of extended metric spaces, using in lieu of V the Hausdorff functor H. We prove that the ensuing Hausdorff polynomial functors have terminal coalgebras and initial algebras. Whereas the canonical constructions of terminal coalgebras for Vietoris polynomial functors takes omega steps, one needs \omega + \omega steps in general for Hausdorff ones. We also give a new proof that the closed set functor on metric spaces has no fixed points. This is joint work with Jiri Adamek and Stefan Milius.


  • Speaker:     Pedro Sota , CANCELLED.

  • Date and Time:     Wednesday November 22, 2023, 7:00 - 8:30 PM. ZOOM TALK.

  • Title:     TBA.

  • Abstract:


  • Speaker:     Charlotte Aten, University of Denver.

  • Date and Time:     Wednesday November 29, 2023, 7:00 - 8:30 PM. ZOOM TALK.

  • Title:     A categorical semantics for neural networks.

  • Abstract:: In recent work on discrete neural networks, I considered such networks whose activation functions are polymorphisms of finite, discrete relational structures. The general framework I provided was not entirely categorical in nature but did provide a stepping stone to a categorical treatment of neural nets which are definitionally incapable of overfitting. In this talk I will outline how to view neural nets as categories of functors from certain multicategories to a target multicategory. Moreover, I will show that the results of my PhD thesis allow one to systematically define polymorphic learning algorithms for such neural nets in a manner applicable to any reasonable (read: functorial) finite data structure.


  • Speaker:     TBA, TBA.

  • Date and Time:     Wednesday December 6, 2023, 7:00 - 8:30 PM.

  • Title:     TBA.

  • Abstract:

    Spring 2024





  • Speaker:     Saeed Salehi, Univeristy of Tabriz.

  • Date and Time:     Wednesday February 7, 2024, 11:00AM - 12:00 NOON. NOTICE SPECIAL TIME!!! ZOOM TALK!!!

  • Title:     On Chaitin's two HP's: (1) Heuristic Principle and (2) Halting Probability.

  • Abstract: Two important achievements of Chaitin will be investigated: the Omega number, which is claimed to be the halting probability of input-free programs, and the heuristic principle, which is claimed to hold for program-size complexity. Chaitin's heuristic principle says that the theories cannot prove the heavier sentences; the sentences and the theories were supposedly weighed by various computational complexities, which all turned out to be wrong or incomplete. In this talk, we will introduce a weighting that is not based on any computational complexity but on the provability power of the theories, for which Chaitin's heuristic principle holds true. Also, we will show that the Omega number is not equal to the halting probability of the input-free programs and will suggest some methods for calculating this probability, if any.



  • Speaker:     Astra Kolomatskaia, Stony Brook.

  • Date and Time:     Wednesday February 28, 2024, 7:00 - 8:30 PM. IN PERSON TALK!

  • Title:     Displayed Type Theory and Semi-Simplicial Types.

  • Abstract: One way to think about the language of Homotopy Type Theory [HoTT], is that it enforces that anything you can say is "up to homotopy". In particular, equality proofs are not strict, but rather carry the data of a particular [class of] deformation. In HoTT, all types have the structure of an infinity groupoid, and thus the language allows for conveniently working with certain infinitary structures synthetically. However, one of the most important and long standing open problems in the field is to analytically define infinitary structures such as semi-simplicial types [i.e. semi-simplicial sets "valued in" homotopy types]. The primary difficulty with this has been that as soon as you use the equality symbol in an attempted definition of such a structure, you fall into a pit of higher coherence issues such that infinitely many layers of higher coherences, with each depending on the proofs of all of the prior ones and growing exponentially in complexity, become required. In HoTT, therefore, one comes directly face-to-face with the core problems of homotopy coherent mathematics.

    In this talk, we will construct semi-simplicial types in Displayed Type Theory [dTT], a fully semantically general homotopy type theory. Many of our main results are independent of type theory and will say something new and surprising about the homotopy theoretic notion of a classifier for semi-simplicial objects.

    This talk is based on joint work with Michael Shulman. Reference: https://arxiv.org/abs/2311.18781



  • Speaker:     Jean-Pierre Marquis, Universite de Montreal.

  • Date and Time:     Wednesday March 6, 2024, 7:00 - 8:30 PM. IN PERSON TALK!

  • Title:     Hom sweet Hom: a sketch of the history of duality in category theory.

  • Abstract: Duality, in its various forms and roles, played a surprisingly important part in the development of category theory. In this talk, I will concentrate on the development of these forms and roles that lead to the categorical formulation of Stone-type dualities in the 1970s. I will emphasize the epistemological gain and loss along the way.



  • Speaker:     Sina Hazratpour, Johns Hopkins University.

  • Date and Time:     Wednesday March 20, 2024, 4:00 - 5:30 PM. NOTE SPECIAL TIME. ZOOM TALK!!!

  • Title:     Fibred Categories in Lean.

  • Abstract: Fibred categories are one of the most important and useful concepts in category theory and its application in categorical logic. In this talk I present my recent formalization of fired categories in the interactive theorem prover Lean 4. I begin by highlighting certain technical challenges associated with handling the equality of objects and functors within the extensional dependent type system of Lean, and how they can be overcome. In this direction, I will demonstrate how we can take advantage of dependent coercion, instance synthesis, and automation tactics from of the Lean toolbox. Finally I will discuss a formalization of Homotopy Type Theory in Lean 4 using a fired categorical framework.

    Lean formalization repository.



  • Speaker:     Ellis D. Cooper.

  • Date and Time:     Wednesday April 10, 2024, 7:00 - 8:30 PM. IN-PERSON

  • Title:     Pulse Diagrams and Category Theory.

  • Abstract: ``Pulse diagrams'' are motivated by the ubiquity of pulsation in biology, from action potentials, to heartbeat, to respiration, and at longer time-scales to circadian rhythms and even to human behavior. The syntax of the diagrams is simple, and the semantics are easy to define and simulate with Python code. They express behaviors of parts and wholes as in categorical mereology, but are missing a compositional framework, like string diagrams. Examples to discuss include cellular automata, leaky-integrate-and-fire neurons, harmonic frequency generation, Gillespie algorithm for the chemical master equation, piecewise-linear genetic regulatory networks, Lotka-Volterra systems, and if time permits, aspects of the adaptive immune system. The talk is more about questions than about answers.



  • Speaker:     Juan Orendain, Case Western Univeristy.

  • Date and Time:     Wednesday May 8, 2024, 7:00 - 8:30 PM. ZOOM TALK.

  • Title:     Canonical squares in fully faithful and absolutely dense equipments.

  • Abstract: Equipments are categorical structures of dimension 2 having two separate types of 1-arrows -vertical and horizontal- and supporting restriction and extension of horizontal arrows along vertical ones. Equipments were defined by Wood in [W] as 2-functors satisfying certain conditions, but can also be understood as double categories satisfying a fibrancy condition as in [Sh]. In the zoo of 2-dimensional categorical structures, equipments nicely fit in between 2-categories and double categories, and are generally considered as the 2-dimensional categorical structures where synthetic category theory is done, and in some cases, where monoidal bicategories are more naturally defined.

    In a previous talk in the seminar, I discussed the problem of lifting a 2-category into a double category along a given category of vertical arrows, and how this problem allows us to define a notion of length on double categories. The length of a double category is a number that roughly measures the amount of work one needs to do to reconstruct the double category from a bicategory along its set of vertical arrows.

    In this talk I will review the length of double categories, and I will discuss two recent developments in the theory: In the paper [OM] a method for constructing different double categories from a given bicategory is presented. I will explain how this construction works. One of the main ingredients of the construction are so-called canonical squares. In the preprint [O] it is proven that in certain classes of equipments -fully faithful and absolutely dense- every square that can be canonical is indeed canonical. I will explain how from this, it can be concluded that fully faithful and absolutely dense equipments are of length 1, and so they can be 'easily' reconstructed from their horizontal bicategories.

    References:
    [O] Length of fully faithful framed bicategories. arXiv:2402.16296.
    [OM] J. Orendain, R. Maldonado-Herrera, Internalizations of decorated bicategories via π-indexings. To appear in Applied Categorical Structures. arXiv:2310.18673.
    [W] R. K. Wood, Abstract Proarrows I, Cahiers de topologie et géométrie différentielle 23 3 (1982) 279-290.
    [Sh] M. Shulman, Framed bicategories and monoidal fibrations. Theory and Applications of Categories, Vol. 20, No. 18, 2008, pp. 650–738.




  • Speaker:     Raymond Puzio.

  • Date and Time:     Wednesday May 15, 2024, 7:00 - 8:30 PM. IN-PERSON!

  • Title:     Uniqueness of Classical Retrodiction.

  • Abstract: In previous talks at this Category seminar and at the Topology, Geometry and Physics seminar, Arthur Parzygnat showed how Bayesian inversion and its generalization to quantum mechanics may be interpreted as a functor on a suitable category of states which satisfies certain axioms. Such a functor is called a retrodiction and Parzygnat and collaborators conjectured that retrodiction is unique. In this talk, I will present a proof of this conjecture for the special case of classical probability theory on finite state spaces.

    In this special case, the category in question has non-degenerate probability distributions on finite sets as its objects and stochastic matrices as its morphisms. After preliminary definitions and lemmas, the proof proceeds in three main steps.

    In the first step, we focus on certain groups of automorphisms of certain objects. As a consequence of the axioms, it follows that these groups are preserved under any retrodiction functor and that the restriction of the functor to such a group is a certain kind of group automorphism. Since this group is isomorphic to a Lie group, it is easy to prove that the restriction of a retrodiction to such a group must equal Bayesian inversion if we assume continuity. If we do not make that assumption, we need to work harder and derive continuity "from scratch" starting from the positivity condition in the definition of stochastic matrix.

    In the second step, we broaden our attention to the full automorphism groups of objects of our category corresponding to uniform distributions. We show that these groups are generated by the union of the subgroup consisting of permutation matrices and the subgroup considered in the first step. From this fact, it follows that the restriction of a retrodiction to this larger group must equal Bayesian inversion.

    In the third step, we finally consider all the objects and morphisms of our category. As a consequence of what we have shown in the first two steps and some preliminary lemmas, it follows that retrodiction is given by matrix conjugation. Furthermore, Bayesian inversion is the special case where the conjugating matrices are diagonal matrices. Because the hom sets of our category are convex polytopes and a retrodiction functor is a continuous bijection of such sets, a retodiction must map polytope faces to faces. By an algebraic argument, this fact implies that the conjugating matrices are diagonal, answering the conjecture in the affirmative.

    Paper.



  • Speaker:     Emilio Minichiello , The CUNY Graduate Center.

  • Date and Time:     Wednesday May 22, 2024, 7:00 - 8:30 PM. IN PERSON TALK!

  • Title:     Presenting Profunctors.

  • Abstract: In categorical database theory, profunctors are ubiquitous. For example, they are used to define schemas in the algebraic data model. However, they can also be used to query and migrate data. In this talk, we will discuss an interesting phenomenon that arises when trying to model profunctors in a computer. We will introduce two notions of profunctor presentations: the UnCurried and Curried presentations. They are modeled on thinking of profunctors as functors P: C^op x D -> Set and as functors P: C^op -> Set^D, respectively. Semantically of course, these are equivalent, but their syntactic properties are quite different. The UnCurried presentations are more intuitive and easier to work with, but they carry a fatal flaw: there does not exist a semantics-preserving composition operation of UnCurried presentations that also preserves finiteness. Therefore we introduce the Curried presentations and show that they remedy this flaw. In the process, we characterize which UnCurried Presentations can be made Curried, and discuss some applications. This talk will be based off of this recent preprint which is joint work with Gabriel Goren Roig and Joshua Meyers.



  • Speaker:     Samuel Mimram, École Polytechnique.

  • Date and Time:     Wednesday May 29, 2024, 2:00PM NOTICE SPECIAL TIME. ZOOM TALK.

  • Title:     Coherence in cartesian theories using rewriting.

  • Abstract: The celebrated Squier theorem allows to prove coherence properties of algebraic structures, such as MacLane's coherence theorem for monoidal categories, based on rewriting techniques. We are interested here in extending the theory and associated tools simultaneously in two directions. Firstly, we want to take in account situations where coherence is partial, in the sense that it only applies for a subset of structural morphisms (for instance, in the case of the coherence theorem for symmetric monoidal categories, we do not want to strictify the symmetry). Secondly, we are interested in structures where variables can be duplicated or erased. We develop theorems and rewriting techniques in order to achieve this, first in the setting of abstract rewriting systems, and then extend them to term rewriting systems, suitably generalized in order to take coherence in account. As an illustration of our results, we explain how to recover the coherence theorems for monoidal and symmetric monoidal categories.