I'm wondering, are there any examples of hereditary substitution in a dependently typed system with a universe hierarchy? i.e. where $ True : Set_0 : Set_1:Set_2$ etc.
I'm wondering in particular how to establish an induction measure in such a system. The simply typed version is structurally decreasing in the type of the variable being replaced. This doesn't work work with dependent types, to for LF the paper I linked uses the simply-typed erasure of the terms, performing induction on the shape of the type.
However, erasing to simple types doesn't work with a universe hierarchy, since if you have something like this:
- $ f : (x : Set_1)\to x \to True$ implies that
- $ f\ ((y : True) \to True \to True ): True \to True \to True$
i.e. applying a function resulted in a structurally larger type.
I'm assuming the solution has something to do with the universe indexes, but if there's an existing technique for establishing that the induction is well founded, I'd prefer to cite it rather than coming up with something up on my own.