Statement on Black Lives Matter
Title: The pebbling comonad in finite model theory (an exposition)
Abstract: In this talk, I will exposit some of the main ideas and results of the seminal 2017 paper “The pebbling comonad in finite model theory” by Samson Abramsky, Anuj Dawar, and Pengming Wang. In this paper, the authors demonstrate that pebble games, which are a powerful combinatorial tool in the study of finite model theory, constraint satisfaction, and database theory, admit a natural formulation in terms of comonads, which leads to comonadic characterizations of many central concepts in finite model theory. Specifically, given a relational signature S and S-structures A and B, the authors establish that winning strategies for the Duplicator in existential pebble games from A to B are equivalently given by morphisms from A to B in the coKleisli categories of certain comonads on the category of S-structures. The paper thereby provides a connection between two broad topics in logic and computer science that have previously been largely disjoint: the interaction of logic with computational complexity, and the study of the semantics of programs and processes. Time permitting, I will also discuss some extensions of their results that I have recently proved.
Title: Grandad of all Computation
Abstract: Moses Schönfinkel invented “combinatory logic”—aka combinatory algebra (CA )—in 1920. It consisted of a binary operation and two constants $S$ and $K$ (called combinators by Haskell Curry who further investigated CAs in the 1950s) which satisfy just two identities. That such a simple gadget can generate all computable functions is—well—amazing.
However, that was not the end of the story.
In 1975 Solomon Feferman introduced the notion of a partial combinatory algebra (PCA) and showed that it too could generate all computable functions … but furthermore had as a prime example the usual notion of computability which the average CS student meets in theory courses via Turing machines. Again, this is an amazingly simple structure which can express all computation: it consists of a partial binary operation and combinators $S$ and $K$ which satisfy just four identities.
In 2008 Pieter Hofstra and I introduced Turing Categories: we argued that this notion subsumed all the previous notions of computability. Furthermore, it turned out that the initial Turing category was generated by a generic PCA … and, thus, this gadget was, therefore, the grandad of all computation.
Now CAs are well known to have a confluent rewriting system, which this is very important as it is the rewriting system which generates computation. By analogy to a CA, this generic PCA should have a nice rewriting system. However, it is still has not been proven that PCAs do have a confluent rewriting system!
The talk is aimed to introduce Turing categories, PCAs, and a suggestion for what the rewriting system should be.
Title: Enriched algebraic theories, monads, and varieties
Abstract: In this talk, I will summarize the research on enriched algebraic theories, monads, and varieties that I produced with Rory Lucyshyn-Wright during my previous postdoctoral fellowship at Brandon University. I will start by providing a historical overview of the subject, which originated with Birkhoff, Lawvere, and Linton in the 1930s and 1960s. Birkhoff initiated the study of universal algebra by defining the notion of an (equational) variety of algebras, which is a class of algebraic structures axiomatized by certain equations. Lawvere and Linton then established purely categorical formulations of Birkhoff’s varieties, in terms of Lawvere theories and finitary monads on Set. I will then describe the ways in which, over the next 50 years, various researchers generalized Lawvere theories and finitary monads to certain enriched settings, by developing enriched notions of Lawvere theory and monad. None of these frameworks developed an enriched notion of variety, and moreover they were largely formulated for locally presentable bases of enrichment, which exclude many important categories of a topological flavour. Moreover, there was no overarching framework that encompassed all of these works. To address these issues, Rory and I developed notions of enriched Lawvere theory, enriched monad, and enriched variety that encompassed all of these prior works and also extended their applicability to many new mathematical settings (especially in topology and analysis). I will conclude by mentioning some of my current and planned research on this topic, which I will talk about at future seminars.
Title: CoCalculus from Monads
Abstract: This is a report from team Functor Calculus at the 4th Women in Topology conference. In earlier work, K. Hess and B. Johnson invented a way of producing what they call “calculus towers” from comonads. These calculus towers generalize functor calculus, and recover other important examples of towers in topology such as certain towers of localizations. In joint work with R. Brooks, K. Hess, B. Johnson, J. Rasmusen and B. Schreiner we produced a dualization of the Hess-Johnson machinery. The resulting “cocalculus towers” recover dual functor calculus, an important co-tower approximating homotopy functors to spectra. Both types of functor calculus are used to approximate important functors in homotopy theory in a manner similair to the Taylor series approximations of functions, but an important distinction for functors is that it is not always possible to recover the entire series from it’s homogeneous parts. Using dual calculus, R. McCarthy and several of his students (including me) produced a variety of results which indicated when one can recover the series from the homogeneous pieces. In this talk, I will explain the generalization of dual calculus to “cocalculus” and explain what kind of results we hope this may lead to in the future.
Title: Counterfactual Logics via Comparative Possibility
Abstract:
In 1973, C. I. Lewis published a landmark text developing a theory of counterfactual logics. The primary goal of the text was in providing a logical framework where one could reason about sentences of the form: “if P were true, then Q would be true”. Such sentences were handled with a new connective and the majority of his text explores the semantics and behavior of this new connective. More general semantics and other connectives were introduced as well and briefly discussed, including a comparative possibility relation. It isn’t until the last chapter of his book that Lewis actually described the syntax for the logics, a reformulation of the semantics, soundness and completeness theorems, and a list of axioms, among other things. This final chapter is unusual for many reasons, the logic and semantics rely on the comparative possibility relation instead of the counterfactual relation and all of the proofs and definitions are written in extremely terse prose. Moreover, this chapter discusses a large family of logics as well as their related modal logics.
In this talk we’ll first go over the sort of counterfactual logic and semantics that Lewis is primarily interested in. Then we’ll discuss the semantics and logic in terms of the comparative possibility relation. Finally, we’ll give an overview of how the soundness and completeness proofs work and where the difficulties lie.
Title: Categorically generalizing bundles
Abstract: Vector bundles and principal bundles are important objects in differential geometry. Vector bundles over a manifold M are manifolds that are locally isomorphic to the Cartesian product M times V for some vector space V, while principal bundles over M are manifolds that are locally isomorphic to M times G for some Lie group G. I will explain some of the many ways to formulate these ideas categorically which generalize different aspects.
Tangent categories are the categorical generalization of the smooth structure giving rise to the tangent bundle. In them differential bundles generalize vector bundles.
On the other hand, join-restriction categories generalize the concept of locality from differential geometry and can be used to define principal bundles.
In the end I will give an outlook about how to generalize these concepts to infinity categories.
Title: Quillen-Barr-Beck cohomology of divided power algebras over an operad
Abstract: Quillen-Barr-Beck (co)homology is a theory which studies the objects of a category where we can make sense of such notions as “modules” and “derivations”. More precisely, in his thesis, Beck defined a general notion of modules and derivations in a sufficiently nice category. These notions where popularised by Quillen, who introduced a cohomology theory for commutative rings, known as the André-Quillen cohomology, by studying something called the cotangent complex for these rings.
An operad is a device which encodes types of algebras. We can also use operads to define categories of divided power algebras, which have additional monomial operations. These divided power structures appear notably in the simplicial setting.
The aim of this talk is to show how André-Quillen cohomology generalises to several categories of algebras using the notion of operad. We will introduce modules and derivations, but also a representing object for modules – known as the universal envelopping algebra – and for derivations – known as the module of Kähler differentials – which will allow us to build an analogue of the cotangent complex. We will see how these notions allow us to recover known cohomology theories on many categories of algebras, while they provide somewhat exotic new notions when applied to divided power algebras.
Title: Semantics for Non-Determinism in Categorical Message Passing Language
Abstract: Categorical Message Passing Language (CaMPL) is a functional style concurrent programming language with a categorical semantics. In this talk, we explore the categorical semantics, programming syntax, and proof theory representations for CaMPL. This includes the sequential functions with input and output values (which become messages), concurrent processes, communication channels, message passing along channels between processes, and races which introduce non-determinism in CaMPL.
Slides: https://www.dropbox.com/s/8rcwzh6lm9j41qt/Calgary_Peripatetic_Seminar_2023-08-02_Little.pdf?dl=0
Title: Normalizing resistor circuits
Abstract: A classical Electrical Engineering problem is to determine whether two networks of resistors are equivalent. The standard solution is to use a process of eliminating internal nodes (the star/mesh transformation) which may be seen as a rewriting procedure. In the EE literature this is organized into a matrix problem which can be solved by a Gaussian elimination procedure. This approach essentially works for resistances taken from the positive reals while secretly using negatives. However, it cannot handle negative resistances. Negative resistances, while counter-intuitive, arise in stabilizer quantum mechanics where networks of “resistors” over finite fields occur. The rewriting approach as compared to the matrix approach is more general and works for any positive division rig. We shall discuss how the rewriting theory can be modified to handle negatives.
In this talk we shall start by introducing categories of resistors. These are “hypergraph categories” whose maps are generated by resistors. Resistors are then self-dual maps satisfying certain formal properties (including an infinite family of star-mesh equalities). The problem of network equivalence is, thus, the decision problem for maps in these categories. The fact that there is a terminating and confluent rewriting system not only solves the decision problem (up to certain equalities) but also has the effect of guaranteeing, very basically, the associativity of the composition.
Work with: Robin Cockett and Amolak Kalra
Abstract courtesy: Robin (at FMCS ’23)
Title: Partial monoids
Abstract: A partial monoid is a set A with a multiplication and a unit, but the multiplication is only defined on a certain subset of pairs. This means the multiplication m:AxA -> A is a partial map, a map that is only defined on a certain subset of its domain. The category of finite commutative partial monoids is an important ingredient for the construction of tangent infinity categories where a bicategory of spans of partial monoids encodes a weakly commutative ring structure. As partial maps are generalized by restriction categories one can directly generalize the definition of a partial monoid in any restriction category.
I will present a certain restriction category B of bags (a.k.a. multisets) with a partial monoid in it. Any partial monoid in any join restriction category X is induced through a functor from B to X which means the partial monoid in B is the generic partial monoid. This characterization of partial monoids is analogous to the concept of a Lawvere theory of an algebraic structure.
