Nicolai Kraus
University of Nottingham, School of Computer Science, Office A06
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

Functions out of Higher Truncations

With Paolo Capriotti and Andrea Vezzosi. To appear at CSL'15.

Truncation Levels in Homotopy Type Theory [pdf][formalisation (html)][formalisation (source, zip)]

PhD thesis.

The General Universal Property of the Propositional Truncation [arXiv]

To appear in the postproceedings of TYPES'14.
What is the type A > B? The universal property of the propositional truncation says that it is equivalent to A > B if B is propositional. I consider the case that B is not necessarily propositional, but only an ntype for some fixed n, or not known to be truncated at all. Assuming a type theory with Reedy omegalimits, 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 ntype, the equivalence can be stated and proved in "standard HoTT" (without the assumption of nontrivial Reedy limits).

Notions of Anonymous Existencs in MartinLö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 MartinLöf type theory with a hierarchy U(0): U(1): U(2): ... of univalent universes, we show that U(n) is not an ntype. 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 ntypes. 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 nTruncated" [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)

Eliminating out of Truncations [slides]

Talk at the HoTT/UF workshop in Warsaw, 30 June 2015.

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 nType

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 UFwiki.
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 ntruncations.

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 ntruncated semisimplicial types. (Haskell) (Agda)

One can use the Haskell script to generate Agda code for ntruncated semisimplicial types. To typecheck, 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.

1Types and SetBased Groupoids

We compare two notions of groupoids: 1types, and the one of a set of objects, together with sets of homset (indexed over the objects).

NonNormalizability 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 Cauchyreal into a discrete type are constant.

Some Families of Categories with Propositional HomSets

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 wellknown 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 nonconfluent 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 onerule 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