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 5417 (not the usual 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/89472980386?pwd=Z3g3Q3h3V1dQUmg2ZlVGU1RwSEhMZz09
Meeting ID: 894 7298 0386
Passcode: NYCCTS

Seminar web page.
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 2022




  • Speaker:     Sergei Burkin, University of Tokyo.

  • Date and Time:     Wednesday September 7, 2022, 7:00 - 8:30 PM.

  • Title:     Segal conditions and twisted arrow categories of operads.

  • Abstract: Several categories, including the simplex category Delta and Moerdijk-Weiss dendroidal category Omega, allow to encode structures (in this case categories and operads reprectively) as Segal presheaves. There are other examples of such categories, which were defined intuitively, by analogy with Delta. We will describe a general construction of categories from operads that produces categories that admit Segal presheaves. This construction explains why these categories appear in homotopy theory, why these allow to encode homotopy coherent structures as simplicial presheaves that satisfy weak Segal condition. Further generalization of this construction to clones shows that these categories are not as canonical as one might have hoped.


  • Speaker:     Prakash Panangaden, McGill University.

  • Date and Time:     Wednesday September 14, 2022, 7:00 - 8:30 PM.

  • Title:     Quantitative Equational Logic.

  • Abstract:


  • Speaker:     James Torre CANCELLED!!!

  • Date and Time:     Wednesday September 28, 2022, 7:00 - 8:30 PM.

  • Title:     Diagonalization, and the Limits of Limitative Theorems.

  • Abstract:


  • Speaker:     David Ellerman, University of Ljubljana.

  • Date and Time:     Wednesday October 19, 2022, 7:00 - 8:30 PM.

  • Title:     To Interpret Quantum Mechanics:``Follow the Math'': The math of QM as the linearization of the math of partitions.

  • Abstract: Set partitions are dual to subsets, so there is a logic of partitions dual to the Boolean logic of subsets. Partitions are the mathematical tool to describe definiteness and indefiniteness, distinctions and distinctions, as well as distinguishability and indistinguishability. There is a semi-algorithmic process or ``Yoga'' of linearization to transform the concepts of partition math into the corresponding vector space concepts. Then it is seen that those vector space concepts, particularly in Hilbert spaces, are the mathematical framework of quantum mechanics. (QM). This shows that those concepts, e.g., distinguishability versus indistinguishability, are the central organizing concepts in QM to describe an underlying reality of objective indefiniteness--as opposed to the classical physics and common sense view of reality as ``definite all the way down'' This approach thus supports what Abner Shimony called the ``Literal Interpretation'' of QM which interprets the formalism literally as describing objective indefiniteness and objective probabilities--as well as being complete in contrast to the other realistic interpretations such as the Bohmian, spontaneous localization, and many world interpretations which embody other variables, other equations, or other worldly ideas.

    The underlying paper is forthcoming in the Foundations of Physics, and the preprint is in the ArXiv here.


  • Speaker:     Ross Street, Macquarie University.

  • Date and Time:     Wednesday October 26, 2022, 7:00 - 8:30 PM.

  • Title:     The core groupoid can suffice.

  • Abstract: Let V be the monoidal category of modules over a commuative ring R. I am interested in categories A for which there is a groupoid G such that the functor categories [A,V] and [G,V] are equivalent. In particular, G could be the core groupoid of A; that is, the subcategory with the same objects and with only the invertible morphisms. Every category A can be regarded as a V-category (that is, an R-linear category), denoted RA, with the same objects and with hom R-module RA(a,b) free on the homset A(a,b). Indeed, RA is the free V-category on A so that the V-functor category [RA,V] is the ordinary functor category [A,V] with the pointwise R-linear structure. In these terms, we are interested in when RA and RG are Morita equivalent V-categories. In my joint work with Steve Lack on Dold-Kan-type equivalences, we had many examples of this phenomenon. However, the example of Nick Kuhn, where A is the category of finite vector spaces over a fixed finite field F with all F-linear functions and G is the general linear groupoid over F, does not fit our theory. Yet the ``kernel'' of the equivalence is of the same type. The present work shows that the category theory behind the Kuhn result also covers our Dold-Kan-type setting. I plan to start with a baby example which highlights the ideas.

    I am grateful to Nick Kuhn and Ben Steinberg for their patient email correspondence with me on this topic.

    Slides.


  • Speaker:     Astra Kolomatskaia, Stony Brook.

  • Date and Time:     Wednesday November 2, 2022, 7:00 - 8:30 PM. IN PERSON TALK.

  • Title:     The Objective Metatheory of Simply Typed Lambda Calculus.

  • Abstract: Lambda calculus is the language of functions. One reduces the application of a function to an argument by substituting the argument for the function's formal parameter inside of the function's body. The result of such a reduction may have further instances of function application. We can write down expressions, such as ((λ f. f f) (λ f. f f)), in which this process does not terminate. In the presence of types, however, one has a normalisation theorem, which effectively states that "programs can be run". One proof of this theorem, which only works for the most elementary of type theories, is to assign some monotone well-founded invariant to a given reduction algorithm. A much more surprising proof proceeds by constructing the normal form of a term by structural recursion on the term's syntactic representation, without ever performing reduction. Such normalisation algorithms fall under the class of Normalisation by Evaluation. Since the accidental discovery of the first such algorithm, it was clear that NbE had some underlying categorical content, and, in 1995, Altenkirch, Hofmann, and Streicher published the first categorical normalisation proof. Discovering this content requires first asking the question “What is STLC?”, perhaps preceded by the question “What is a type theory?”. In this talk we will lay out the details of Altenkirch's seminal paper and explore conceptual refinements discovered in the process of its formalisation in Cubical Agda.

    Slides.


  • Speaker:     Andrei Rodin, University of Lorraine (Nancy, France).

  • Date and Time:     Wednesday November 9, 2022, 7:00 - 8:30 PM.

  • Title:     Kolmogorov's Calculus of Problems and Homotopy Type theory.

  • Abstract: A. N. Kolmogorov in 1932 proposed an original version of mathematical intuitionism where the concept of problem plays a central role, and which differs in its content from the versions of intuitionism developed by A. Heyting and other followers of L. Brouwer. The popular BHK-semantics of Intuitionistic logic follows Heyting's line and conceals the original features of Kolmogorov's logical ideas. Homotopy Type theory (HoTT) implies a formal distinction between sentences and higher-order constructions and thus provides a mathematical argument in favour of Kolmogorov's approach and against Heyting's approach. At the same time HoTT does not support the constructive notion of negation applicable to general problems, which is informally discussed by Kolmogorov in the same context. Formalisation of Kolmogorov-style constructive negation remains an interesting open problem.


  • Speaker:     Saeed Salehi, University of Tabriz.

  • Date and Time:     Wednesday November 23, 2022, Zoom Talk SPECIAL TIME 9:30AM-11:00AM.

  • Title:     Self-Reference and Diagonalization: their difference and a short history.

  • Abstract: What is now called the Diagonal (or the Self-Reference) Lemma, is the statement that for every formula F(x), with the only free variable x, there exists a sentence σ such that σ is equivalent to the F of the Gödel code of σ, i.e., σ ≡ F(#σ); and this equivalence is provable in certain weak arithmetics. This lemma is credited to Gödel (1931), in the special case when F is the unprovability predicate, and to Carnap (1934) in the more general case.

    In this talk, we will argue that Gödel-Carnap's original Diagonal Lemma is not the modern formulation and was more similar to, but not exactly identical with, the Strong Diagonal (or Direct Self-Reference) Lemma. This lemma, so-called recently, says that for every formula F(x), in a sufficiently expressive language, there exists a sentence σ such that σ is equal to the F of the Gödel code of σ, i.e., σ = F(#σ); and this equality is provable in sufficiently strong theories. We will attempt at tracking down the first appearance of the modern formulation of the Diagonal Lemma in the equivalent form, also in the strong direct form of equality.


  • Speaker:    

  • Date and Time:     Wednesday November 30, 2022, 7:00 - 8:30 PM.

  • Title:     TBA.

  • Abstract:


  • Speaker:     Robert Pare, Dalhousie University.

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

  • Title:     The horizontal/vertical synergy of double categories.

  • Abstract: A double category is a category with two types of arrows, horizontal and vertical, related by double cells. Think of sets with functions and relations as arrows and implications as double cells. The theory is 2-dimensional just like for 2-categories. In fact 2-categories were originally defined as double categories in which all vertical arrows were identities. Most of the theory of 2-categories extends to double categories resulting in a deeper understanding. This is one aspect of double categories: they’re “new and improved” 2-categories.

    From a purely formal point of view, a double category is a category object in CAT. Once a familiarity with double categories has developed, it is amusing and instructive to see how the various constructs of formal category theory play out in this setting.

    But these two aspects of double categories, fancy 2-categories or internal categories, are only part of the picture. Perhaps the most important thing is the interplay between the horizontal and the vertical.

    I will start with some examples of double categories to give a feeling for the objects I will be discussing, and then look at several concepts indicative of the rich interplay between the horizontal and the vertical.


  • Speaker:     Gemma De las Cuevas, University of Innsbruck.

  • Date and Time:     Postponed till the Spring.

  • Title:     A framework for universality across disciplines.

  • Abstract: What is the scope of universality across disciplines? And what is its relation to undecidability? To address these questions, we build a categorical framework for universality. Its instances include Turing machines, spin models, and others. We introduce a hierarchy of universality and argue that it distinguishes universal Turing machines as a non-trivial form of universality. We also outline the relation to undecidability by drawing a connection to Lawvere’s Fixed Point Theorem. Joint work with Sebastian Stengele, Tobias Reinhart and Tomas Gonda.

    Spring 2023





  • Speaker:     Igor Baković, University of Osijek, Croatia.

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

  • Title:     Enhanced 2-adjunctions.

  • Abstract: Whenever one has a class of objects possessing certain structure and a hierarchy of morphisms that preserve structure more or less tightly, we are in an enhanced context. Enhanced 2-categories were introduced by Lack and Shulman in 2012 with a paradigmatic example of an enhanced 2-category T-alg of strict algebras for a 2-monad and whose tight and loose 1-cells are pseudo- and lax morphisms of algebras, respectively. They can be defined in two equivalent ways: either as 2-functors, which are the identity on objects, faithful, and locally fully faithful, or as categories enriched over the cartesian closed category F, whose objects are functors that are fully faithful and injective on objects. Lack and Shulman called objects of F full embeddings, but we will call them "enhanced categories" because they are nothing else but categories with a distinguished class of objects, which we call tight.The 2-category F has a much richer structure besides being cartesian closed; there are additional closed (but not monoidal) structures, and we show how 2-categories with a right ideal of 1-cells as in 2-categories with Yoneda structure on them can be presented as categories enriched in F in the sense of Eilenberg and Kelly. Since Lack and Shulman were mainly motivated by limits in enhanced 2-categories, they didn't further develop the theory of enhanced (co)lax functors and their enhanced lax adjunctions. The purpose of this talk is to lay the foundations of the theory of enhanced 2-adjunctions and give their examples throughout mathematics and theoretical computer science.

    Slides.



  • Special Topic:    TQFT and Computation, First Lecture.



  • Speaker:     Mikhail Khovanov, Columbia University.

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

  • Title:     Universal construction and its applications.

  • Abstract: Universal construction starts with an evaluation of closed n-manifolds and builds a topological theory (a lax TQFT) for n-cobordisms. A version of it has been used for years as an intermediate step in constructing link homology theories, by evaluating foams embedded in 3-space. More recently, universal construction in low dimensions has been used to find interesting structures related to Deligne categories, formal languages and automata. In the talk we will describe the universal construction and review these developments.



  • Special Topic:    TQFT and Computation, Second Lecture.



  • Speaker:     Mee Seong Im, United States Naval Academy, Annapolis.

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

  • Title:     Automata and topological theories.

  • Abstract: Theory of regular languages and finite state automata is part of the foundations of computer science. Topological quantum field theories (TQFT) are a key structure in modern mathematical physics. We will interpret a nondeterministic automaton as a Boolean-valued one-dimensional TQFT with defects labelled by letters of the alphabet for the automaton. We will also describe how a pair of a regular language and a circular regular language gives rise to a lax one-dimensional TQFT.

    Slides.



  • Special Topic:    TQFT and Computation, Third Lecture.



  • Speaker:     Joshua Sussan, CUNY.

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

  • Title:     Non-semisimple Hermitian TQFTs.

  • Abstract: Topological quantum field theories coming from semisimple categories build upon interesting structures in representation theory and have important applications in low dimensional topology and physics. The construction of non-semisimple TQFTs is more recent and they shed new light on questions that seem to be inaccessible using their semisimple relatives. In order to have potential applications to physics, these non-semisimple categories and TQFTs should possess Hermitian structures. We will define these structures and give some applications.



  • Speaker:     Jens Hemelaer, University of Antwerp.

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

  • Title:     EILC toposes.

  • Abstract: In topos theory, local connectedness of a geometric morphism is a very geometric property, in the sense that it is stable under base change, can be checked locally, and so on. In some situations however, the weaker property of being essential is easier to verify. In this talk, we will discuss EILC toposes: toposes E such that any essential geometric morphism with codomain E is automatically locally connected. It turns out that many toposes of interest are EILC, including toposes of sheaves on Hausdorff spaces and classifying toposes of compact groups.



  • Speaker:     Jim Otto.

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

  • Title:     P Time, A Bounded Numeric Arrow Category, and Entailments.

  • Abstract:We revisit the characterization of the P Time functions from our McGill thesis.

    1. We build on work of L. Roman (89) on primitive recursion and of A. Cobham (65) and Bellantoni-Cook(92) on P Time.

    2. We use base 2 numbers with the digits 1 & 2. Let N be the set of these numbers. We split the tapes of a multi-tape Turing machine each into 2 stacks of digits 1 & 2. These are (modulo allowing an odd numberof stacks) the multi-stack machines we use to study P Time.

    3. Let Num be the category with objects the finite products of N and arrows the functions between these. From its arrow category Num^2 we abstract the doctrine (here a category of small categories with chosen structure) PTime of categories with with finite products, base 2 numbers, 2-comprehensions, flat recursion, & safe recursion. Since PTime is a locally finitely presentable category, it has an initial category I. Our characterization is that the bottom of the image of I in Num^2 consists of the P Time functions.

    4. We can use I (thinking of its arrows as programs) to run multi-stack machines long enough to get P Time.This is the completeness of the characterization.

    5. We cut down the numeric arrow category Num^2, using Bellantoni-Cook growth & time bounds on the functions, to get a bounded numeric arrow category B. B is in the doctrine PTime. This yields the soundness of the characterization.

    6. For example, the doctrine of toposes with base 1 numbers, choice, & precisely 2 truth values (which captures much of ZC set theory) likely lacks an initial category, much as there is an initial ring, but no initial field.

    7. On the other hand, the L. Roman doctrine PR of categories with finite products, base 1 numbers, & recursion (that is, product stable natural numbers objects) does have an initial category as it consists of the strong models of a finite set of entailments. And is thus locally finitely presentable. We sketch the signature graph for these entailments. And some of these entailments. Similarly (but with more complexity) there are entaiments for the doctrine PTime.

    Slides.



  • Speaker:     Walter Tholen, York University.

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

  • Title:     What does “smallness” mean in categories of topological spaces?

  • Abstract: Quillen’s notion of small object and the Gabriel-Ulmer notion of finitely presentable or generated object are fundamental in homotopy theory and categorical algebra. Do these notions always lead to rather uninteresting classes of objects in categories of topological spaces, such as the class of finite discrete spaces, or just the empty space , as the examples and remarks in the existing literature may suggest?

    In this talk we will demonstrate that the establishment of full characterizations of these notions (and some natural variations thereof) in many familiar categories of spaces, such as those of T_i-spaces (i= 0, 1, 2), can be quite challenging and may lead to unexpected surprises. In fact, we will show that there are significant differences in this regard even amongst the categories defined by the standard separation conditions, with the T1-separation condition standing out. The findings about these specific categories lead us to insights also when considering rather arbitrary full reflective subcategories of Top.

    (Based on joint work with J. Adamek, M. Husek, and J. Rosicky.)




  • Speaker:     Dusko Pavlovic, University of Hawai‘i at Mānoa.

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

  • Title:     Program-closed categories.

  • Abstract: > Let CC be a symmetric monoidal category with a comonoid on every object. Let CC* be the cartesian subcategory with the same objects and just the comonoid homomorphisms. A *programming language* is a well-ordered object P with a *program closure*: a family of X-natural surjections

    CC(XA,B) <<--run_X-- CC*(X,P)

    one for every pair A,B. In this talk, I will sketch a proof that program closure is a property: Any two programming languages are isomorphic along run-preserving morphisms. The result counters Kleene's interpretation of the Church-Turing Thesis, which has been formalized categorically as the suggestion that computability is a structure, like a group presentation, and not a property, like completeness. We prove that it is like completeness. The draft of a book on categorical computability is available from the web site dusko.org.



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

  • Date and Time:     Wednesday May 3, 2023, 7:00 - 8:30 PM. ZOOM TALK POSTPONED TILL THE FALL.

  • Title:     A framework for universality across disciplines.

  • Abstract: What is the scope of universality across disciplines? And what is its relation to undecidability? To address these questions, we build a categorical framework for universality. Its instances include Turing machines, spin models, and others. We introduce a hierarchy of universality and argue that it distinguishes universal Turing machines as a non-trivial form of universality. We also outline the relation to undecidability by drawing a connection to Lawvere’s Fixed Point Theorem. Joint work with Sebastian Stengele, Tobias Reinhart and Tomas Gonda.



  • Speaker:     Arthur Parzygnat, Nagoya University.

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

  • Title:     Inferring the past and using category theory to define retrodiction.

  • Abstract: Classical retrodiction is the act of inferring the past based on knowledge of the present. The primary example is given by Bayes' rule P(y|x) P(x) = P(x|y) P(y), where we use prior information, conditional probabilities, and new evidence to update our belief of the state of some system. The question of how to extend this idea to quantum systems has been debated for many years. In this talk, I will lay down precise axioms for (classical and quantum) retrodiction using category theory. Among a variety of proposals for quantum retrodiction used in settings such as thermodynamics and the black hole information paradox, only one satisfies these categorical axioms. Towards the end of my talk, I will state what I believe is the main open question for retrodiction, formalized precisely for the first time. This work is based on the preprint https://arxiv.org/abs/2210.13531 and is joint work with Francesco Buscemi.