Nicolai Kraus

University of Nottingham, School of Computer Science, Office A06

Cambridge

I am a PhD student of Thorsten Altenkirch at the Functional Programming Laboratory (School of Computer Science, University of Nottingham). My main interests are Homotopy Type Theory and related subjects.

Feel free to contact me: ngk at cs.nott.ac.uk

Some of my work (in reversed chronological order)

Any comments are highly appreciated.

Main work

Truncation Levels in Homotopy Type Theory [pdf][formalisation (html)][formalisation (source, zip)]
PhD thesis.
The General Universal Property of the Propositional Truncation [arXiv]
The universal property of the propositional truncation says that the types A -> B and ||A|| -> B are equivalent if B is propositional. I consider the case that B is not necessarily propositional, but only an n-type for some fixed n, or not known to be truncated at all. Assuming a type theory with Reedy omega-limits, I define a type of constant functions A -> B which satisfy an infinite tower of coherence conditions. I then show that this type is homotopy equivalent to the type ||A|| -> B without any conditions on B. If B is an n-type, the equivalence can be stated and proved in "standard HoTT" (without the assumption of nontrivial Reedy limits).
Notions of Anonymous Existencs in Martin-Löf Type Theory [pdf preprint][formalisation (html)][formalisation (source, zip)]
With Martin Escardo, Thierry Coquand and Thorsten Altenkirch. Contribution to the special issue of TLCA 2013 (submitted to LMCS).
We discuss weakly constant functions, in particular endofunctions, and different related notions of existence.
Higher Homotopies in a Hierarchy of Univalent Universes [article and formalisation, arXiv]
With Christian Sattler. To appear in Transactions on Computational Logic.
For Martin-Löf type theory with a hierarchy U(0): U(1): U(2): ... of univalent universes, we show that U(n) is not an n-type. Our construction also solves the problem of finding a type that strictly has some high truncation level without using higher inductive types. In particular, U(n) is such a type if we restrict it to n-types. We have fully formalised and verified our results within the dependently typed language and proof assistant Agda.
This is a shortened version of the manuscript "On the Hierarchy of Univalent Universes: U(n) is not n-Truncated" [arXiv v1], which is superseded by my PhD thesis (Chapter 7).
Generalizations of Hedberg’s Theorem [pdf preprint][formalisation (html) on ME's website][HoTT blog post]
With Martin Escardo, Thierry Coquand and Thorsten Altenkirch. TLCA 2013.
Hedberg's Theorem states that a type with decidable equality has unique identity proofs. This statement is strengthened in several ways. The blog post only contains a small part of the contents, while the Agda file includes additional thoughts. The final publication is available at link.springer.com.

Some Talks (for which I have slides - I actually prefer blackboards)

Omega Constancy and Truncations [slides]
My talk for the FP Away Day 2014 in Buxton, July 2014.
Generalizations of Hedberg's Theorem [slides]
My talk at TLCA in Eindhoven, June 2013.
I have given a similar talk with the same title at the FP Away Day in Buxton, June 2013 (the original slides are on the event homepage).
Universe n is not an n-Type
Talk at the Univalent Foundations Program at the IAS in Princeton, April 2013. No slides available, but there are some notes to the talk on the UF-wiki. Abstract.
Homotopy Type Theory and Hedberg's Theorem [slides]
Talk for my visit in Birmingham, November 2012. Contains generalizations of the theorem, based on joint work with T. Altenkirch, T. Coquand, M. Escardo. Abstract.
On Hedberg's theorem: Proving and Painting [slides]
My talk for the FP Away Day 2012 in Hathersage. An attempt to provide some more intuition for HoTT, together with Hedberg's theorem as an application.
Equality in the Dependently Typed Lambda Calculus: An Introduction to Homotopy Type Theory [slides]
Talk at Computing 2011, Karlsruhe. Abstract.
Homotopy Type Theory [slides]
Talk for the FP Away Day 2011 in Buxton - just a presentation of very basic ideas and intuition.
A Lambda Term Representation Inspired by Linear Ordered Logic [slides]
My talk at the workshop LFMTP in Nijmegen, August 2011.

Other Drafts, Notes, Miscellaneous Contents

Eliminating Higher Truncations via Constancy - at TYPES 2014 with Paolo Capriotti
We generalize the universal property of n-truncations.
Isomorphism of Finitary Inductive Types - at TYPES 2014 with Christian Sattler
We present an algorithm for deciding isomorphism of finitary inductive types.
A Haskell script to generate the type of n-truncated semi-simplicial types. (Haskell) (Agda)
One can use the Haskell script to generate Agda code for n-truncated semi-simplicial types. To type-check, the strings can be copied into the Agda file. However, this is really only a proof of concept and could be done much more professionally.
The Truncation Map on Nat is Nearly Invertible (blog post) (Agda formalisation and explanation, html)
We construct a term which pretends to be an inverse of the truncation projection Nat -> ||Nat||.
1-Types and Set-Based Groupoids
We compare two notions of groupoids: 1-types, and the one of a set of objects, together with sets of hom-set (indexed over the objects).
Non-Normalizability of Cauchy Sequences
We prove that there is no definable (or continuous) endofunction on the set of Cauchy sequences such that f(s)~s and s~t -> f(s)=f(t), where s~t means that the difference of the Cauchy sequences s and t converges to 0. In general, all definable functions from the Cauchy-real into a discrete type are constant.
Some Families of Categories with Propositional Hom-Sets
A list defining complete partial orders, Heyting algebras and so on in terms of categories, to make up for my memory.
Setoids are not a LCCC
With Thorsten Altenkirch. A short proof of the well-known fact that neither the category of small groupoids nor its full subcategory of setoids is locally cartesian closed.
Yoneda Groupoids
My Yoneda Groupoids are special weak omega groupoids that have a simple and short formalisation.
First Year Report, extended version
The shorter version of my report is an abridged version of the extended one. Mainly those contents that are not central to HoTT are left out. (Note on the extended version: for the part about Yoneda Groupoids I would recommend to look at the separate note above).
Homotopy Type Theory - An overview
My introduction to HoTT (also the main part of my first year report). Caveat: When I wrote this, I was quite new to HoTT and teaching it to myself. Today, there are certainly better introductions (in particular the book, although my introduction focusses on models, which the book does not).
A direct proof of Hedberg's theorem in Coq, see also my post on the HoTT blog
Hedberg's theorem states that decidability of equality implies UIP. Reading through the original proof, I noticed that this can be done more directly, using that "decidable equality" looks literally similar to "contractible". There is also a slight improvement, namely "local decidability implies local UIP".
On String Rewriting Systems (draft)
Unfinished draft, joint work with Christian Sattler. We define a translation for non-confluent String Rewriting Systems systems, enabling us to normalize derivation sequences to some extent. We had developed the described techniques in order to tackle a famous problem on one-rule string rewriting systems (see the RTA open problems list). Our techniques seem to be insufficient to solve the problem, and are probably already known.
A Lambda Term Representation Inspired by Linear Ordered Logic [arXiv]
Together with Andreas Abel. Appeared at LFMTP 2011,

Last update: June 2015