Australian Category Seminar

Traces, Kleene wands, and co-universal natural number objects

Robin Cockettยท27 May 2026

In a lextensive restriction category with a natural number object, there are three conditions which are equivalent: having an inductive trace on the coproduct, having an inductive Kleene wand, and having the natural number object be co-universal. Any of these properties ensure that the setting can represent all computable functions.

An open problem is to show that there is a suitable internal notion of computability allowing one to extract from any such setting a Turing category with the same properties (i.e.. a natural number object with a co-universal property).

Back