Date & Time

January 26 

Liquid Tensor Experiment

In December 2020, Peter Scholze posed a challenge to formally verify the main theorem on liquid R-vector spaces, which is part of his joint work with Dustin Clausen on condensed mathematics. I took up this challenge with a team of mathematicians to verify the theorem in the Lean proof assistant. Half a year later, we reached a major milestone, and in the summer of 2022 we have completed the full challenge. 

In this talk I will give a brief motivation for condensed/liquid mathematics, report on our experiences formalizing state-of-the-art research in mathematics, and discuss some new insights in the proof of the main theorem.

February 9

TBA

TBA

February 23

TBA

TBA

March 9

TBA

TBA

March 23

TBA

TBA

April 6

TBA

TBA

December 15

December 15

December 1

Media: video, slides. 

Central H-spaces and banded types

We give a simple description of the type of H-space structures on a pointed type A. If A is an H-space, we obtain an untruncated version of a formula of Arkowitz--Curjel and Copeland for counting H-space structures on a space. This formula underlies the classical computations of the number of H-space structures on various spaces. As an example, we easily deduce that the type of H-space structures on the 3-sphere is equivalent to the six-fold loop space of the 3-sphere.

Our formula for the type of H-space structures on A leads us to define and study what we call "central" types, which are generalisations of Eilenberg--Mac Lane types. Central types admit a unique H-space structure which can be explicitly delooped by a tensor product of "types banded by A." Given an abelian group A, we iterate this process to give an independent construction of K(A,n) along with a description of its H-space structure that is useful for certain cohomology computations.

These results are part of joint, ongoing work with Ulrik Buchholtz, Dan Christensen, David Jaz Myers, and Egbert Rijke. Most of the results have been formalized using the Coq-HoTT library.

Media: video, slides. 

Acyclic types and epimorphisms in HoTT

It is well known that the epimorphisms in the category of sets are exactly the surjections. But what are the epimorphisms of types? Thinking of types as spaces, and following literature in algebraic topology, we characterise epimorphisms of types in HoTT as so-called acyclic maps. An acyclic map is a map whose fibres are acyclic types, and a type is acyclic if its suspension is contractible. We also consider a weaker notion: a type is k-acyclic (for k ≥ -2) if its suspension is k-connected. We show, for example, that the classifying type of a group G is 2-acyclic if and only if the group G is perfect, i.e. its abelianisation is trivial. Finally, we comment on the relations between acyclic and connected maps and sketch directions for future research.

This is joint work with Ulrik Buchholtz and Egbert Rijke.

Media: video, slides.

Hofmann-Streicher Universes via Coalgebra

Hofmann-Streicher universes (Hofmann and Streicher 1999) are a standard tool for modeling universes in presheaf models of dependent type theory. They have been used in the semantics of HoTT, e.g. in the cubical set model of Cohen et al. (2015).

Hofmann and Streicher (op. cit.) noted that their approach to universes does not extend from presheaf models to arbitrary sheaf models. In this talk, we nevertheless extend the approach of Hofmann and Streicher to sheaf models *with enough points*. Consequently, we can handle many sheaf models without resorting to alternatives such as the stack semantics of Coquand et al. (2020). In particular, any model of sheaves on a topological space has enough points.

Our approach will be to recover any sheaf model with enough points as a 'topos model of coalgebras' for an appropriate notion of comonad. This construction 'lifts' the universe in the topos model carrying the comonad to the sheaf model in question, yielding a Hofmann-Streicher universe. Our 'topos model of coalgebras' is a refinement of the well-known topos of coalgebras (Kock and Wraith 1971).

Media: video, slides.

 November 3

Cubes with one connection and relative elegance

Given a cube category with cartesian structure (faces, degeneracies, diagonals, and permutations), we know that its category of presheaves supports (constructively!) both an interpretation of homotopy type theory and a compatible Quillen model structure. Here we consider the cube category with cartesian structure and one connection. I will present a proof that the model structure obtained for this cube category is Quillen equivalent to the Kan-Quillen model structure on simplicial sets. The obstacle to overcome is that this cube category is not a Reedy category: its morphisms do not factor into well-behaved "degeneracy" and "face" maps. We observe that it does, however, embed in a Reedy category in a nice way. We adapt the theory of so-called elegant Reedy categories to this relativized case, then use these results to prove the equivalence with simplicial sets. This is joint work with Christian Sattler.

Media: video, slides.

October 20

Calculating a Brunerie Number

In his PhD thesis, Brunerie defined the notorious 'Brunerie number' -- an integer n such that the fourth homotopy group of the 3-sphere is isomorphic to Z/n. He then managed to, with a lot of machinery, prove that |n| = 2. In an ideal world, this part of the proof is unnecessary: the fact that |n| = 2 should follow immediately by normalising n in a constructive proof assistant like Cubical Agda. In the real world, however, it's not that easy: Cubical Agda is too slow. So we have two obvious choices: we either give up, or we formalise all of Brunerie's original proof (me and my supervisor, Anders Mörtberg, have accepted both options at different points in time). Recently, however, I found a third option: even though normalisation doesn't work, there is still a very direct way of showing that |n| = 2. In fact, with my definition of n, we can show that n = -2. In this talk, I will give a sketch of this argument. If time permits, I will mention why this argument also shows that the fourth homotopy group of the 3-sphere is a subgroup of Z/2.

Media: video, slides.

October 20

A univalent formalization of affine schemes

Schemes are the corner stone of modern algebraic geometry and have been formalized in various proof assistants. However, the most prominent existing formalizations all follow the inherently non-constructive approach of Hartshorne's classic "Algebraic Geometry" textbook. Working in Cubical Agda, we want to give a constructive formalization of affine schemes in a univalent setting. We follow an approach due to Coquand, Lombardi and Schuster that uses a point-free description of the Zariski spectrum but otherwise proceeds by defining the structure sheaf on basic opens first and then lifting it to the whole spectrum. In this talk we will focus on the construction of the structure sheaf on basic opens as it is at this point that working in a univalent setting raises perhaps surprising issues while at the same time offering insightful solutions.

Media: video, slides.

Univalent Category Theory

Category theory is the study of structure across mathematics. Being a mathematical subject itself, category theory should also encompass the study of its own structural aspects.

A promising approach (Gray 1974; Di Liberti & Loregian 2019) is formal category theory: studying the properties of the bicategory of categories which make it possible to study category theory from a structural perspective.

A different idea is to approach categories as groupoids with extra structure, something which finds itself naturally at home in HoTT, where "groupoids" are particular types. This approach lends itself particularly well to formalization in a proof assistant.

In the context of Cubical Agda, we recap the basic theory of univalent categories (Ahrens, Kapulkin & Shulman 2013) and the move towards higher univalent category theory (Capriotti & Kraus 2017; Ahrens et all 2019), particularly the application of cubical syntax to fibred categories (following Sterling & Angiuli 2021; Ahrens & Lumsdaine 2017).

Media: slides, video.

Where are the open sets? Comparing HoTT with Classical Topology

It's often said that Homotopy Type Theory is a synthetic description of homotopy theory, but how do we know that the theorems we prove in HoTT are true for mathematicians working classically? In this expository talk we will outline the relationship between HoTT and classical homotopy theory by first using the simplicial set semantics and then transporting along a certain equivalence between (the homotopy categories of) simplicial sets and topological spaces. We will assume no background besides some basic knowledge of HoTT and classical topology.

Media: slides, video.

Date

Speaker

Talk information

Assia Mahboubi

Inria, Nantes

Continuity in dependent type theory
(joint work with Pierre-Marie Pédrot and Martin Baillon)

A result due to M. Escardó establishes the continuity of all functionals definable in Gödel's system T. In this talk, we discuss how to generalize the result to a richer, dependent type theory. Via the construction of a syntactic model, akin to the effectful forcing of Escardó's proof, we obtain an external proof of continuity for any functional |- f : (nat -> nat) -> nat definable in this type theory.

Media: slides, no video.

Chaitanya Leena Subramaniam

University of San Diego

Dependently typed algebraic theories and their homotopy algebras

Dependently typed algebraic theories are a generalisation of ordinary multisorted algebraic theories (finite-product theories). When it comes to models valued in Set, they are just as expressive as essentially algebraic theories (finite-limit theories). They also combine well with homotopy theory, and have a canonical notion of model up-to-homotopy in spaces, or "homotopy algebra", via a left Bousfield localisation of a global model structure on simplicial presheaves.

In this talk, I will consider dependently typed algebraic theories to be a strict subclass of contextual categories. With respect to models valued in Set, this strict subclass is nevertheless just as expressive as essentially algebraic theories. Moreover, contextual categories in this subclass have a nice description of their homotopy algebras, generalising a definition of homotopy algebras of ordinary algebraic theories due to Badzioch and Bergner.

Homotopy algebras of ordinary algebraic theories enjoy a rigidification theorem stating that every homotopy algebra is weakly equivalent to a strict simplicial algebra. I will report on recent joint work with S. Henry showing that the same is true for homotopy algebras of dependently typed algebraic theories. This result uses a weak factorisation system introduced by Henry on the category of Set-models of a contextual category, as well as Henry's notion of weak model category. 

Media: video, slides.

Fredrik Nordvall Forsberg

University of Strathclyde

Different Notions of Ordinals in Homotopy Type Theory

Ordinals are a powerful tool when justifying induction and recursion, proving that processes terminate, or in mathematics generally. In classical set theory, there are many equivalent ways to introduce them, but in a constructive setting, the different notions split apart, with different advantages and disadvantages for each. I will consider three different notions of ordinals in homotopy theory theory: a "syntactic" notation system based on Cantor normal forms, a quotient inductive-inductive type of Brouwer trees, and wellfounded extensional orders from the HoTT book. Although defined very differently, all three notions have properties expected of ordinals: their order relations are extensional and wellfounded (and thus support transfinite induction), and the usual arithmetic operations can be defined in each case. Furthermore, the notions are connected in the sense that there are structure preserving non-surjective embeddings of Cantor normal forms into Brouwer trees, and of Brouwer trees into wellfounded extensional orders.

This is joint work with Nicolai Kraus and Chuangjie Xu.

Media: video, slides. 

Marcelo Fiore

University of Cambridge

Mathematical and Computational Metatheory of Second-Order Algebraic Theories

I will present a further step in my ongoing research programme on Algebraic Type Theory, the overall aim of which is to develop a mathematical theory understanding type theories algebraically while supporting practical foundations. The talk will centre on Second-Order Algebraic Theories, which are equational presentations in languages with (first-order) algebraic type structure and (second-order) term structure with variable-binding operators and parametrised metavariables. Examples include: first-order logic, simply-typed computational calculi, and the calculus of partial differentiation.

Specifically, I will present a new categorical model for Second-Order Algebraic Theories: it is based on indexed families and founded upon the initial-algebra approach. A main motivation for and crucial aspect of the mathematical theory is that it is directly programmable in languages supporting inductive families; and, indeed, was developed in unison with building a formally-verified computer implementation for second-order semantics, computation, and deduction. As such, the work resulted in a framework within the Agda proof assistant for the automatic generation of generic second-order abstract syntax and provably correct metaoperations for manipulating it; to wit, algebraic models together with compositional interpretations, capture-avoiding and metavariable substitution operations, and equational and/or rewriting reasoning. This is joint work with Dmitrij Szamozvancev; a paper, source code, documentation, and case studies are available at the project page <tinyurl.com/agda-soas>.

Media: video, slides.

Jonas Frey

Carnegie Mellon University

Characterizing clan-algebraic categories

Media: video, slides.

HoTTEST Event for

Junior Researchers 2022

Date

Speaker

Talk information

Dec 2

Taichi Uemura

Stockholm University

∞-type theories and internal language conjectures

HoTT is expected to give internal languages for elementary ∞-toposes. As the first step towards this goal, Kapulkin and Lumsdaine made a precise formulation of the conjecture that dependent type theory with intensional identity types gives internal languages for finitely complete ∞-categories. This simple version of the internal language conjecture is still difficult due to the coherence problem. In ∞-categories, most equations hold up to homotopies, but type theories have a stricter notion of equality, judgmental equality.

In this talk, we introduce an ∞-dimensional generalization of type theories which we call ∞-type theories to prove Kapulkin and Lumsdaine's conjecture. An ∞-type theory is like a type theory, but judgmental equality behaves like homotopies rather than strict equality, so there is no coherence problem between ∞-type theories and ∞-categories. The internal language conjecture is then reduced to a coherence problem between the type theory and a suitable ∞-type theory. We solve the new coherence problem by developing a splitting technique for models of the ∞-type theory.

An advantage of our approach is that one can easily formulate internal language conjectures for richer type theories, for example type theories with function types, inductive types, and universes. Any internal language conjecture is then reduced to a coherence problem between a type theory and an ∞-type theory. Unfortunately, we have not yet found a general solution to the coherence problem (the splitting technique we present only works for intensional identity types). If time permits, we will discuss possible approaches to the general coherence problem.

Joint work with Hoang Kim Nguyen. 

Media: video, slides. 

Raffael Stenzel

Masaryk University 

Kristina Sojakova

Inria Paris 

Hugo Moeneclaey

IRIF Paris

Media: video, slides.

Matthieu Sozeau

Inria Nantes 

The MetaCoq Project

Proof assistants are getting more widespread use in research and industry to provide certified and independently checkable guarantees about theories, designs, systems and implementations. However, proof assistant implementations themselves are seldom formally verified, although they take a major share of the trusted code base in any such certification effort. In this area, proof assistants based on Higher-Order Logic enjoy stronger guarantees than the ones based on Dependent Type Theory, as self-certified implementations have been available for some years. One cause of this difference is the inherent complexity of dependent type theories together with their extensions with (co)-inductive types, universe polymorphism and complex sort or dimension systems. Another is the gap between theory on paper and practical implementations in efficient programming languages. In particular, an efficient implementation of definitional equality checking can be far away from its ideal specification.

The MetaCoq project aims to tackle these difficulties in the case of the Coq proof assistant. It provides the first fully-certified realistic implementation of a type checker for the calculus underlying the Coq proof assistant. I will present how we refined the sometimes blurry, if not incorrect, specification and implementation of the system to produce:

- A specification of Coq's syntax and type theory, the Polymorphic Cumulative Calculus of (Co)-Inductive Constructions (PCUIC)
- A monad for the manipulation of raw syntax and interaction with the Coq system
- A verification of PCUIC's metatheory, whose main results are the confluence of reduction, type preservation and principality of typing
- A realistic, correct and complete type-checker for PCUIC

Finally, I will focus on work in progress to relate the current specification of PCUIC to a presentation of type theory with typed equality.

http://metacoq.github.io

Media: video, slides. 

Rafaël Bocquet

Eötvös Loránd University

Coherence of definitional equality in type theory

Hofmann has proven that the extension of intensional type theory (with Uniqueness of Identity Proofs) by the equality reflection rule is conservative. For HoTT or other type theories without UIP, we can consider extensions that replace some typal equalities by definitional equalities, such as the extension of HoTT by a strictly associative and unital addition on natural numbers. 

In this talk I will show that conservativity holds whenever the base type theory satisfies "external univalence" and the definitional equalities added by the extension are coherent, that is when "every formal composition of these equalities is trivial." The formal statements of these conditions involve some type-theoretic infinity-categories, i.e. infinity-categories that are presented by models of type theory. 

Media: video, slides.

Date

Speaker

Talk information

April 22

Ulrik Buchholtz

TU Darmstadt

(Co)cartesian families in simplicial type theory

Using Riehl–Shulman's simplicial type theory for synthetic higher category theory, I'll describe how to define and work with (co)cartesian families. These represent functors from a higher category to the category of categories. As an application, I'll derive a (dependent) Yoneda lemma for such families. This is joint work with Jonathan Weinberger.

Media: video, slides.

April 8

Egbert Rijke

University of Ljubljana

A higher encode decode method

The Postnikov tower of a pointed type X induces a fiber sequence $K(G,n+1) -> \|X\|_{n+1} -> \|X\|_n$ for every n, where G is the (n+1)-st homotopy group of X. This fiber sequence suggests a general approach to computations of higher homotopy groups of types, by encoding a family of n-connected (n+1)-truncated types over the type $\|X\|_n$. While I do not yet have any finished computations of homotopy groups of types via this approach, it does suggest a fruitful line of research with interesting intermediate results.

Media: video, slides. 

March 25

Håkon Robbestad Gylterud

Universitetet i Bergen

Defining and relating theories

Since the advent of homotopy type theory, many different formal theories for HoTT (such variations of Martin-Löf’s theory, cubical type theory, ⋯) have joined the already plentiful ranks of formal theories. In this talk, we will try to outline a general, algebraic and combinatorial notion of formal theory – geared towards dependent type theories – based on work by Cartmell, Makkai and others.

The notion of theory we present is being implemented in a software framework aimed at working with different theories and translations between them, called Myott. Thus, part of the presentation will focus on the Haskell implementation of the theoretical notions.

Media: video, slides.

March 11

 Andrea Vezzosi

IT University of Copehagen

Cubical Agda and its Extensions

Cubical Agda is a dependently typed language with Univalence and Higher Inductive Types based on Cubical Type Theory. In this talk we will see how its features interact with pattern matching, copatterns, and interactive development. 

We will then introduce the universe of non-fibrant types, where the  interval of cubical type theory lives, and which will let us talk  about strict equality from within the type theory. 

Finally we will see the extension with a modality for guarded recursion, providing a type-based approach to productivity of corecursive definitions and an abstract way to construct step-indexed models of programming languages. 

Media: video, "slides".

February 25

Carlo Angiuli

Carnegie Mellon University

Internalizing Representation Independence with Univalence

In programming language theory, the principle of representation independence states that programs indexed by structured types are invariant under a wide range of structure-preserving correspondences. The Structure Identity Principle (SIP) states that constructions in HoTT respect structured isomorphisms, but many instances of representation independence involve non-isomorphic types.

In this talk, I will motivate representation independence, explain its connection to proof reuse and transfer, and recall the basics of cubical type theory and the SIP. Then, I will describe our recent work on a relational variant of the SIP that uses HIT quotients to improve representation independence scenarios into  structured isomorphisms and thence equalities of structured types. Our results are formalized in Cubical Agda.

Joint work with Evan Cavallo, Anders Mörtberg, and Max Zeuner. Available at
  https://dl.acm.org/doi/10.1145/3434293.

Media: video, slides.

February 11 

Norihiro Yamada

University of Minnesota 

Game semantics of homotopy type theory

In this talk, I sketch my recent work on game semantics of homotopy type theory (HoTT). My aim is to extend the BHK-interpretation of Martin-Löf type theory to HoTT so that one can better understand HoTT as a foundation of constructive mathematics. In fact, this game semantics can be seen as a mathematical formalisation of the BHK-interpretation of HoTT: It interprets terms in HoTT as constructive "dialogical arguments" on the truths of formulas, i.e., constructive proofs, and in particular terms of Id-types as constructive proofs on the equality between constructive proofs. Further, the game semantics shows that the extension of HoTT by equational univalence, i.e., the judgemental equality between Id-type on a universe and type equivalence, is consistent, and Markov's principle is independent from this extended HoTT.

Media: video, slides. 

January 28

Thierry Coquand

Chalmers University

Sheaf models and constructive mathematics

In the first part of this talk, I will try to motivate why sheaf models are important for constructive mathematics on a specific example: the existence of the (separable) algebraic closure of a field.This is not trivial constructively since for an arbitrary field, it is in general not decidable if a given polynomial is irreducible or not.  One solution, going back to a short note of André Joyal "Les Théorèmes de Chevalley-Tarski et remarques sur l'algèbre constructive", is to use a suitable (effective) sheaf model in which we can build the algebraic closure. I will explain this model and how it can be used to compute with algebraic numbers.

One would like to express such a model using the language of type theory, but this is problematic since the roots of a given polynomial cannot be expressed as a function of the coefficients, and we cannot use strong sum to express existence of roots. This motivates the second part of the talk, where I will present joint work with Fabian Ruch and Christian Sattler on how to extend such sheaf models to sheaf models of (univalent) type theory. One can then express and prove results such that the fact that any Gm-torsor is trivial and start to ask if one can force the line (algebraic closure) to be contractible.

Media: video, slides.

Date

Speaker

Talk information

Dec 3

Jamie Vicary

University of Cambridge

A type theory for strictly unital infinity-categories

Finster and Mimram recently introduced the simple type theory Catt [1], in which terms correspond to cells of a free weak infinity-category on a finite signature. (Alternatively, these terms can be thought of as inhabitants of a directed path type.) We give a decision procedure for determining when two terms are the same "up to units", which we add to the type theory as a definitional equality [2]. This yields a new, strong definition of strictly unital infinity-category, and gives a new type theory Catt_u in which homotopically complex path type inhabitants can be directly constructed, with a vast reduction in complexity compared to the base
type theory. We give some illustrated examples, and speculate about future applications of these ideas to make path types in homotopy type theory easier to handle.

[1] Eric Finster and Samuel Mimram (2017), "A Type Theoretical Definition of Weak \omega-Categories",
http://arxiv.org/abs/1706.02866.
[2] Eric Finster, David Reutter and Jamie Vicary (2020), "A Type Theory for Strictly Unital \infty-Categories",
http://arxiv.org/abs/2007.08307.

Media: video, slides.

Nov 19

Pierre Cagne

Universitetet i Bergen

On the symmetries of the spheres in univalent foundations

In this talk, I will present a joint work with Marc Bezem and Nicolai Kraus that explores the type of symmetries of the n-sphere (n>0), i.e. the type Sⁿ = Sⁿ, in HoTT-UF. I will start by proving that S¹=S¹ is equivalent to S¹+S¹. From there, one can try to generalize the result in higher dimensions. I will treat the case n=2 in details and prove that S²=S² has exactly two connected components, equivalent to one another, with explicit elements (through univalence) for each of the components. The shape of these components though is much more mysterious, but I will outline why we should not expect S²=S² to be equivalent to S²+S². From there, and if time permits, I will generalize further by induction on n, and show that Sⁿ = Sⁿ has exactly two connected components for higher n, and I will end on some insights about the shape of these components.

Media: video, slides.

Nov 5

Nima Rasekh

École Polytechnique Fédérale de Lausanne

Filter Products and Elementary Models of Homotopy Type Theory

Oct 22

Ambrus Kaposi

Eötvös Loránd University

Quotient inductive-inductive types and higher friends

Quotient inductive-inductive types (QIITs) are generalisations of inductive types where we allow multiple sorts indexed over each other and we allow equality constructors. QIITs can also be seen as initial algebras for generalised algebraic theories.

In this talk I will show a simple direct definition of QIITs, explain their categorical semantics and give a survey of the current results about existence of initial algebras.

I will also describe two extensions: higher inductive-inductive types and higher order abstract syntax.

Joint work with Thorsten Altenkirch, Rafaël Bocquet, András Kovács, and Xie Zongpu.

Media: video, slides.

Oct 8

at 8 AM EDT

Yuki Maehara

Macquarie University 

A cubical model for weak ω-categories

A (strict) ω-category is usually defined as a globular set equipped with compositions. But one can instead consider cubical sets equipped with compositions, and Al-Agl, Brown and Steiner proved that these two notions give rise to equivalent categories. Steiner also showed that, in the cubical setting, the compositions may be encoded in a somewhat indirect manner using open boxes. In this joint project with Tim Campion and Chris Kapulkin, we modify this encoding and propose the resulting objects as a model for weak ω-categories (a.k.a. (∞,∞)-categories). We also construct the Gray tensor product and compare our model to a simplicial precursor, i.e. complicial sets.

Sep 24

Jakob von Raumer

University of Nottingham

Coherence via Well-Foundedness

When mapping out of a quotient into a 1-type, we find ourselves in the situation of needing to prove that a function is coherent in the following way: All cycles in the relation we quotient by are mapped to refl. Proving statements about all cycles is notoriously difficult because it does not straightforwardly admit induction.

In practice, we often take quotients by binary relations which resemble reduction relations, and as such are co-wellfounded and locally confluent. In this talk I will show that under these circumstances, we can find an induction principle which can then be used to tackle this kind of coherence problem in HoTT. The main part of the proof is a purely graph theoretic construction, independent from its use in HoTT.

This is joint with Nicolai Kraus.

Media: video, slides. 

Sep 10

Guillaume Brunerie

and

Peter LeFanu Lumsdaine

Stockholm University

Initiality for Martin-Löf type theory

“Initiality” is the principle that the term model of some type theory should be an initial object in the category of models of that type theory.  Thomas Streicher gave a careful proof of initiality for the Calculus of Constructions in 1991.  Since then, initiality for more complex type theories (such as Martin-Löf type theory) has often been treated as established, as a straightforward extension of Streicher’s result, but never written up carefully for a larger theory.

Around 2010, various researchers (notably Voevodsky) raised the question of whether these extensions really were sufficiently straightforward to consider them established without further proof.  Since then, views on the status of initiality have varied within the field; but the issue has been, at least, a frustrating unresolved point.

In this talk, we present a proof of initiality for a full-featured Martin-Löf type theory.  The proof is formalised in Agda, to dispel any question of thoroughness (and also partly formalised in Coq), and is carefully designed for extensibility to other type theories.  The proof is based on Streicher’s, using some improvements of Hofmann and further refinements by the present authors.  The two formalisations present slightly different versions of the statement — using contextual categories in Agda, categories with attributes in Coq — but the core of the proof is parallel.

Joint work with Menno de Boer and Anders Mörtberg.

Media: slides-PLL, slides-GB, video.

Date

Speaker

Talk information

Apr 16

Matthew Weaver

Princeton University

A constructive model of directed univalence in bicubical sets

Directed type theory is an analogue of homotopy type theory where types represent ∞-categories, generalizing groupoids. A bisimplicial approach to directed type theory, developed by Riehl and Shulman, is based on equipping each type with both a notion of path and a separate notion of directed morphism. In this setting, a directed analogue of the univalence axiom asserts that there is a universe of covariant discrete fibrations whose directed morphisms correspond to functions—a higher-categorical analogue of the category of sets and functions. In this talk, I’ll present a constructive model of a directed type theory with directed univalence in bicubical, rather than bisimplicial, sets. We formalize much of this model using Agda as the internal language of a 1-topos, following Orton and Pitts. First, building on the cubical techniques used to give computational models of homotopy type theory, we show that there is a universe of covariant discrete fibrations, with a partial directed univalence principle asserting that functions are a retract of morphisms in this universe. To complete this retraction into an equivalence, we refine the universe of covariant fibrations using the constructive sheaf models by Coquand and Ruch. (Joint work with Dan Licata.)

Media: video, slides.

Apr 2

Denis-Charles Cisinski

Universität Regensburg

Univalence of the universal coCartesian fibration

The model of higher categories given by Joyal's model structure for quasi-categories has univalent universes of coCartesian fibrations. This subsumes the existence of univalent universes of Kan fibrations proved by Voevodsky. Furthermore, the existence of such universes can be used as an alternative to the yoga of homotopy coherent nerves to prove all the essential features of higher category theory, giving a (directed) type theoretic approach to the foundations of higher categories.

Media: video, slides.

Mar 19

Jon Sterling

Carnegie Mellon University

Objective Metatheory of Dependent Type Theories

What type theorists and other researchers in type theory have in common is that they study theorems that hold of the initial model of type theory; but type theorists especially emphasize the theorems whose statements are sufficiently non-type-theoretic that they need not be preserved by homomorphisms of models. These theorems, sometimes called "metatheorems" or "admissibilities", are the means by which we conceive and justify computerized implementations of type theory, including canonicity, normalization, and decidability of type checking and judgmental equality.

The main tool for proving such theorems is Tait's method of computability, which has in the past several years been subject to a rapid campaign of rectification using the categorical language of Artin gluing. I will give an overview of this brave new "objective computability", emphasizing my recent joint work with Angiuli and Gratzer on a general gluing theorem for models of MLTT along flat functors into Grothendieck topoi, with an application to cubical type theory.

Media: video, slides.

Feb 20

 Karol Szumiło

University of Leeds

 The Constructive Kan-Quillen Model Structure

The classical Kan-Quillen model structure on the category of simplicial sets is a fundamental object in homotopy theory. Many proofs of its existence have been found, but (until recently) all of them relied on principles of classical logic: the law of excluded middle and the axiom of choice. For the purposes of interpretation of Homotopy Type Theory, such arguments were insufficient.

A fully constructive proof is possible, but it requires a careful adjustment of the definitions of cofibrations and weak homotopy equivalences of simplicial sets. In the talk, I will outline one such constructive argument, explaining how various standard techniques of simplicial homotopy theory need to be adapted to constructive logic.

This is joint work with Nicola Gambino and Christian Sattler, inspired by Simon Henry who was the first to obtain the result.

Media: video, slides.

Feb 6

Niels van der Weide

Radboud University

Constructing 1-Truncated Finitary Higher Inductive Types as Groupoid Quotients

In homotopy type theory, one can define spaces, such as the spheres and torus, with higher inductive types (HITs). These types generalize inductive types by allowing constructors for (possibly higher) paths beside constructors for points.

One scheme for HITs is defined by Dybjer and Moenclaey. It allows defining HITs by providing arities for constructors for the points, paths, and paths between paths. The arities are allowed to be recursive, but they have to be finitary.

In this talk, we show how to interpet the HITs defined by Dybjer and Moenclaey as 1-types using the grorupoid quotient. Concretely, this means we construct finitary 1-truncated HITs as groupoid quotients within type theory.

Media: video, slides.

Jan 23

Simon Henry

University of Ottawa

The language of a model category

Date

Speaker

Talk information

Dec 11,

4 PM Eastern

Richard Garner

Macquarie University

Polynomial comonads and comodules

To any locally cartesian closed category E one can associate a monoidal category Poly(E) of polynomials; it is (following von Glehn) the fibre over 1 of the free fibration with distributive sums and products on E, or equivalently (following Gambino and Kock) the category of polynomial endofunctors of E.

A result of Ahman and Uustalu shows that comonoids in Poly(E) (i.e., polynomial comonads) are the same as internal categories in E. It is then natural to ask: what is the bicategory of comonoids and bicomodules in Poly(E)? The goal of this talk is to explain the (slightly surprising) answer.

Media: video, slides.

Nov 20

Benno van den Berg

University of Amsterdam

Uniform Kan fibrations in simplicial sets

An important question in homotopy type theory is whether the existence of a model of univalent type theory in simplicial sets (and a model structure) can be proven constructively (say, in CZF with some inaccessibles). One approach would be to take the usual definition of a (trivial) Kan fibration as one's starting point and see how far one gets: this is the approach followed by Henry, Gambino, Szumilo and Sattler in recent work. It turns out that you can get quite far, but some issues remain (especially around the interpretation of Pi-types and coherence). Together with Eric Faber, I am pursuing a different approach in which we add uniformity conditions to the notion of a Kan fibration (as in the cubical sets model). The idea is that classically these conditions can always be satisfied, but not necessarily constructively. This has also been tried by Gambino and Sattler in earlier work, but in our view there are quite a few conditions missing in their definition of a uniform Kan fibration. In this talk, I will try to explain what our definition is, why we believe our definition is better (the idea is that we can prove, constructively, that it is "local"), and how far we are right now. 

Media: video, slides.

Nov 6

Andrew Swan

Carnegie Mellon University

Choice, Collection and Covering in Cubical Sets

In homotopical models of type theory such as cubical sets, propositional truncation has a rich structure. Instead of "identifying points," as in more traditional interpretations of extensional type theory in regular locally cartesian closed categories, one inductively adds new paths, while keeping existing points separate. This extra structure can be particularly clearly exposed by exploiting the fact that cubical sets are valid in a constructive metatheory, and assuming Brouwer's continuity principle, which is an anti-classical axiom stating that all functions from Baire space to the naturals are continuous. In this setting even very weak versions of the axiom of choice, such as WISC and a version of countable choice due to Escardo and Knapp, turn out to be false in the cubical set model. I will also talk about some very weak consequences of countable choice that are false in the model. This includes countable versions of collection and fullness from set theory (providing a solution to exercise 10.12 of the HoTT book). I will also talk about a couple of examples from homotopy theory: the product of countably many copies of the circle is not covered by any hSet and there are examples of hSets that are not covered by any constant cubical set.

Media: video, slides.

Oct 23

Anders Mörtberg

Stockholm University

Unifying Cubical Models of Homotopy Type Theory

(j.w.w. Evan Cavallo, Andrew Swan)

In recent years a wide variety of constructive cubical models of homotopy type theory have been developed. These models all provide constructive meaning to the univalence axiom and higher inductive types, but how are they related? In the talk I will give an answer to this question in the form of a generalization that covers most of the cubical models. The crucial idea of this generalization is to weaken the notion of fibration from the cartesian cubical set model so that it is not necessary to assume that the diagonal on the interval is a cofibration. This notion of fibration also gives rise to a model structure, generalizing earlier work on constructing model structures from cubical models of homotopy type theory.

Media: video, slides.

Oct 9

Andrej Bauer

University of Ljubljana

General type theories

There are many variants of dependent type theory, but it is difficult to find a complete and exact account of what a type theory is, as a formal system. We shall give a precise definition of what a type theory is in general, as a formal system whose components are various syntactic entities. The syntax of terms and types is described by a signature. Arbitrary inference rules are too unwieldy, so we next identify two properties that an acceptable rule must have. We similarly study what makes a family of rules into an acceptable type theory. To test the quality of our definition we prove fundamental meta-theorems about general type theories:

1. Presupposition theorem: if a judgement is derivable then so are its presuppositions.
2. Uniqueness of typing: if a term has type A and type B then A and B are judgmentally equal.
3. Elimination of substitution: every derivable judgement can be
derived without the substitution rule.

JOINT WORK WITH:
Philipp Haselwarter (University of Ljubljana)
Peter LeFanu Lumsdaine (Stockholm University)

Media: video, slides.

Mathieu Anel

Carnegie Mellon University

Descent v. Univalence

The purpose of the talk will be to explain the connection between the notion of descent, characteristic of infinity-topoi, and the notion of univalence, characteristic of homotopy type theory.

Media: video, slides.

Paolo Capriotti

Technische Universität Darmstadt

Polynomial monads as opetopic types

In a previous HoTTEST talk, Eric Finster presented a coinductive definition of polynomial monads that should make it possible to formulate higher algebra internally in HoTT. In my talk, I will show how one can connect Finster's construction to the formalism of opetopes and opetopic objects, and its connection with the Baez-Dolan construction for polynomial monads. More precisely, I will give a reformulation of Finster's definition of polynomial monad in terms of opetopic types satisfying a kind of Segal condition. It will turn out that, once the basic notion of trees over a polynomial is established, Finster's coherence for magmas can be expressed purely in terms of polynomials and their maps. This should hopefully provide a first step towards comparing Finster's definition with the established ∞-categorical notion of polynomial monad.

Media: video, "slides". 

 Joachim Kock

Universitat Autonoma de Barcelona

∞-operads as polynomial monads

I'll present a new model for ∞-operads, namely as analytic monads. This is joint work with David Gepner and Rune Haugseng. In the ∞-world (unlike what happens in the classical case), analytic functors are polynomial, and therefore the theory can be developed within the setting of polynomial functors. I'll talk about some of the features of this theory, trying to focus on aspects that might be of interest to type theory, in particular the construction of free monads, and the relevance of polynomial monads for the semantics of higher inductive types.

Media: video, "slides".

Dan Licata

Wesleyan University 

A Fibrational Framework for Substructural and Modal Dependent Type Theories (joint work with Mitchell Riley and Michael Shulman)

Modal type theory extends type theory with additional unary type constructors, representing functors, monads, and comonads of various sorts.  For example, the modalities discussed in the HoTT book are idempotent monads, while some recent extensions of HoTT make use of idempotent comonads.  Modal types can be used to speak synthetically about topology and geometry, and also have been used in the internal language semantics of cubical type theories. Over the past few years, we have been working on a general framework for modal type theories. In this framework, specific type theories can be specified by a signature---for example, "type theory with an idempotent monad and an idempotent comonad which are themselves adjoint".  Given a signature, instantiating general inference rules provides a syntax for working with the desired modal types.  While the framework does not automatically produce ``optimized'' inference rules for a particular modal discipline (where structural rules are as admissible as possible), it does provide a syntactic setting for investigating such issues, including a general equational theory governing the placement of structural rules in types and in terms.  While this is still work in progress, we hope to give a categorical semantics to the entire framework at once, saving the work of considering each modal type theory individually.

Media: video, slides.

 Evan Cavallo

Carnegie Mellon University

Internal Parametricity and Cubical Type Theory

A polymorphic function is intuitively said to be parametric when it behaves uniformly at all types. This concept was made precise by Reynolds, who defined parametric functions to be those with an action on relations and showed that all polymorphic functions definable in the simply-typed lambda-calculus are parametric. Recently, dependent type theories have been developed that internalize this property, which is known as parametricity; this work is closely connected to cubical type theory, both historically and methodologically. I'll discuss the similarities and differences between internally parametric and cubical type theory, the type theory we designed that combines the two, and potential applications to higher-dimensional theorem proving.

This is joint work with Robert Harper, and details can be found in our preprint arXiv:1901.00489.

Media: video, slides. 

 Simon Huber

University of Gothenburg

 Homotopy canonicity for cubical type theory

Cubical type theory provides a constructive justification of homotopy type theory and satisfies canonicity: every natural number is convertible to a numeral.  A crucial ingredient of cubical type theory is a path lifting operation which is explained computationally by induction on the type involving several non-canonical choices.  In this talk I will present why if we remove these equations for the path lifting operation from the system, we still retain homotopy canonicity: every natural number is path equal to a numeral.  The proof involves proof relevant computability predicates (also known as sconing) and doesn't involve a reduction relation.

This is joint work with Thierry Coquand and Christian Sattler.

Media: video, slides.

Nima Rasekh

MPI Bonn 

Algebraic Topology in an Elementary Higher Topos

An elementary higher topos is a higher category which should sit at the intersection of three concepts: higher category theory, algebraic topology and homotopy type theory. The goal of this talk is to give concrete examples of these connections.
In particular we show how every elementary higher topos has a natural number object, how this can be used to define truncations and how the existence of truncations implies the Blakers-Massey theorem.

Media: video, slides.

Nicola Gambino

University of Leeds

From algebraic weak factorisation systems to models of type theory

Algebraic weak factorisation systems are a refinement of the classical weak factorisation systems in which diagonal fillers are given by a prescribed algebraic structure. The notion of an algebraic weak factorisation system was introduced by Marco Grandis and Walter Tholen, and subsequently refined by Richard Garner, who then developed the theory in a series of joint papers with John Bourke. In this talk, I will explain general methods for constructing weak factorisation systems that can be used for defining models of dependent type theory satisfying all the required strictness conditions. This is based on joint work with Christian Sattler and subsequent work in the Leeds PhD thesis of Marco Larrea.

Media: slides, no video.

Eric Finster

Inria - Rennes

Towards Higher Universal Algebra in Type Theory

I will propose a definition of "coherent cartesian polynomial monad" in type theory.  Special cases of the proposal yield definitions of ∞-operads, ∞-categories and ∞-groupoids.  In addition, I describe a definition of coherent algebra over such a monad, leading to a proposed internal description of objects such as E_n-types and diagrams of types valued in the universe.

I will report on progress towards formalizing the definition and suggest some constructions and applications making use of it. 

Media: video, slides.

Floris van Doorn

University of Pittsburgh

Guillaume Brunerie

Stockholm University

Computer-generated proofs for the monoidal structure of the smash product

The smash product is a very useful operation in algebraic topology and  it can be defined in HoTT as a certain higher inductive type. One of  its basic properties is the fact that it is a (1-coherent) monoidal  product on pointed types, but proving this fact turns out to be very  technical.

Nicolai Kraus

University of Nottingham

  Some connections between open problems

I will give an overview of my plan to construct connections between   several unsolved questions. The following are important constructions   that we would like to perform internally in type theory:
(1) a definition of semi-simplicial types;
(2) developing a theory of infinity-categories;
(3) homotopy type theory "eating itself";
(4) a "minimal/optimal" principle of eliminating truncations;
(5) showing that free higher groups over sets are sets, that the   suspension of a set is a 1-type, and variations/generalizations.

My expectation is that, in type theories where (1) can be solved (e.g.   HTS and 2LTT), the other problems can be solved as well. I will outline  the progress that various members of the HoTT community have made on  some of the questions. The emphasis of the talk will be on a framework  for quotienting by "directed" equivalence relations which I have  developed to attack problem (5), together with partial results and why  (5) is related to (1).

Media: video, slides.

Kuen-Bang Hou (Favonia)

University of Minnesota

Towards efficient cubical type theory

Cubical type theory attracted much attention in the homotopy type theory community because it achieved canonicity in the presence of univalence and higher inductive types. To date, there are many variants of cubical type theory and experimental proof assistants based on them.

It may seem that the remaining task is to reconnect the syntax to standard models, but there are still numerous type-theoretic open problems arising from the concerns over efficiency and usability. In this talk, I will give an overview of several topics we are working on but not publicly presented before, including extension types, empty systems, the interplay between kinds and higher inductive types, and more!

Media: video, slides.

Dimitris Tsementzis

Rutgers University

First-Order Logic with Isomorphism

First-order logic with isomorphism (“FOLiso”) is a formal system which relates to HoTT and the Univalent Foundations in a similar way that first-order logic with equality relates to ZFC and set-theoretic foundations. In particular, FOLiso gives a precise framework in which to study “first-order" theories defined on homotopy types (e.g. precategories, univalent categories), just as first-order logic with equality gives a precise framework in which to study first-order structures and theories defined on sets. I will first introduce the syntax and proof system of FOLiso as an extension of M. Makkai’s FOLDS. Then I will define a semantics for FOLiso in terms of homotopy types and describe a proof of soundness and completeness for this semantics. I will conclude by sketching applications in various directions.

(Most of the material is based on the preprint arXiv:1603.03092 with quite a few new additions based on ongoing work.)

Media: video, slides.

Andy Pitts

University of Cambridge

Axiomatizing Cubical Sets Models of Univalent Foundations

The constructive model of Homotopy Type Theory introduced by Cohen-Coquand-Huber-Mörtberg in 2015 (building on the work of Bezem-Coquand-Huber in 2013) uses a particular presheaf topos of cubical sets.  Since its introduction, much effort has been expended to analyse, simplify and generalize what makes this model of the univalence axiom tick, using a variety of techniques. In this talk I will describe an axiomatic approach -- the isolation of a few elementary axioms about an interval and a universe of fillable shapes that allow a univalent universe to be constructed. Not all the axioms are visible in the original work; and the axioms can be satisfied in toposes other than the original presheaf topos of cubical sets.  The axioms and constructions can almost be expressed in Extensional Martin-Löf Type Theory, except that the global nature of some of them leads to the use of a modal extension of that language.

This is joint work with Ian Orton, Dan Licata and Bas Spitters.

Media: video, slides.

Thierry Coquand

University of Gothenburg

  A survey of constructive models of univalence

I will try to survey what is known at this stage about constructive  models of univalence, and then some metatheoretical applications. Some of  these are: proof theoretic strength of the univalence axiom (with HITs), and   consistency of univalence with continuity principle and fan theorem, and  independence of the axiom of countable choice.

Media: video , slides.

Thorsten Altenkirch

University of Nottingham

Towards higher models and syntax of type theory

We (Ambrus Kaposi and myself) have defined the intrisic (no preterms) syntax of type theory in type theory using quotient inductive inductive types, that is set truncated higher inductive inductive types. Set truncation is necessary because we want to have decidability which we established using normalisation by evaluation. However, this stops us from defining any interesting semantic models, e.g. interpreting contexts as sets, types as families etc, because sets do not from a set (not for size reason but dimension). I suggest that we can overcome this problem by defining higher models of type theory and a higher syntax. I envisage that the higher syntax does form a set without being explicitely truncated, hence decability should still hold. In my talk I will describe the first steps towards this programme.

Media: video, slides.

University of Birmingham

Constructive mathematics in univalent type theory

I want to share my experience of doing constructive mathematics in univalent type theory, compared to my previous experience in e.g. elementary-topos type theory (as in Lambek and Scott), Martin-Löf type theory, Bishop mathematics.
In doing so, I want to compare the old topological view of types and functions in constructive mathematics with the new homotopical view of equality in type theory.
There will be some new constructive theorems, too.

Media: video, slides.

Michael Shulman

University of San Diego

Type 2-theories

Homotopy type theory is hypothesized to be an internal language for (∞,1)-toposes.  However, recent developments suggest that more than this, what is needed is an internal language for collections of several (∞,1)-toposes together with functors between them, such as adjunctions, monads, comonads, non-cartesian monoidal structures, and so on.  For instance, a cohesive (∞,1)-topos comes with an adjoint triple of two monads and a comonad, while a tangent (∞,1)-topos comes with a monad that is also a comonad and also a non-cartesian "smash product" monoidal structure.

Just as ordinary homotopy type theory is a "doctrine" or "2-theory" for (∞,1)-toposes, each such situation should come with its own "2-theory": a dependent type theory with extra information characterizing the additional structure.  But developing even one dependent type theory formally is a lot of work, so we would like a general framework and a general theorem that can then simply be specialized to all such 2-theories.  I will sketch such a framework, which is under development in joint work with Dan Licata and Mitchell Riley.

Media: video, slides.

Ulrik Buchholtz

Technische Universität Darmstadt

From Higher Groups to Homotopy Surfaces

Carlo Angiuli

Carnegie Mellon University

Computational semantics of Cartesian cubical type theory

Dependent types are simultaneously a theory of constructive mathematics and a theory of computer programming: a proof of a proposition is at the same time a program that executes according to a specification. Homotopy type theory reveals a third aspect of dependent types, namely their role as an extensible formalism for reasoning synthetically about objects with homotopical structure.  Unfortunately, axiomatic formulations of univalence and higher inductive types disrupt the computational character of type theory, which pivots on a property called canonicity.

I will discuss Cartesian cubical type theory, a univalent type theory in which the canonicity property holds, based on a judgmental notion of cubes with diagonals, faces, and degeneracies, and uniform Kan operations that compute according to their types. I will consider it primarily through the lens of its computational semantics, defined using a cubical generalization of the technique of logical relations, which licenses reading proofs as programs.

Emily Riehl

Johns Hopkins University

The synthetic theory of  ∞-categories vs the synthetic theory of  ∞-categories

Homotopy type theory provides a “synthetic” framework that is suitable for developing the theory of mathematical objects with natively homotopical content. A famous example is given by (∞,1)-categories — aka “∞-categories” — which are categories given by a collection of objects, a homotopy type of arrows between each pair, and a weak composition law. In this talk we’ll compare two “synthetic” developments of the theory of ∞-categories — the first (joint with Verity) using 2-category theory and the second (joint with Shulman) using a simplicial augmentation of homotopy type theory due to Shulman — by considering in parallel their treatment of the theory of adjunctions between ∞-categories. Afterwards, I hope to launch a discussion about what considerations might motivate the use of homotopy type theory in place of classical approaches to prove theorems in similar settings.

Ideal background: some familiarity with notions of a (ordinary strict 1-)category, functor, natural transformation, and the definition of an adjunction involving a unit and a counit (just look these up on wikipedia). Plus standard type theory syntax and the intuitions from the Curry-Howard-Voevodsky correspondence. I’ll be talking about (∞,1)-categories but won’t assume familiarity with them.

Media: video,  slides.

Peter LeFanu Lumsdaine

Stockholm University

Inverse diagram models of type theory

Diagram models are a flexible tool for studying many logical systems: given a categorical model C and index category I, one hopes that the diagram category C ^I will again be a model.

For the case of intensional type theory, this becomes a little tricky. Since most logical constructors (e.g. Σ-types, Id-types) are not provably strictly functorial, it is difficult to lift them from structure on C to structure in C ^I, for arbitrary I.

However, in case I is an inverse category — roughly, something like the semi-simplicial category Δ _I — this difficulty can be surmounted by taking the types of C ^I to be Reedy types, analogous to Reedy fibrations in homotopy theory.

I will discuss the construction of these models (and slightly more general homotopical diagram models) in the setting of categories with attributes, along with the application of these models to the “homotopy theory of type theories”.

The work of this talk is joint work with Chris Kapulkin, in arXiv:1610.00037 and a forthcoming companion article; see also Shulman arXiv:1203.3253 for a closely related construction.

A basic familiarity with categorical models of type theory will be helpful, i.e. categories with attributes or similar; see  here for an introductory overview of these.

Media:  video, slides.