How do I convince Agda's universe checker that what I'm doing is well-founded?

user_5024557 0
Viewed 248

I have a function that maps natural numbers to their corresponding Agda universe level.

level : Nat -> Level
level zero = lzero
level (suc l) = lsuc (level l)

Setn : (l : Nat) -> Set (level (suc l))
Setn l = Set (level l)

I use this function in the definition an inductive datatype in this manner:

data U l : Setn l where
  ...
  Lift : {l' : Nat} -> {l' <= l} -> U l' -> U l

Here, Agda complains that Set (level l') is not less than or equal to Set (level l), which is clearly false, though I understand that Agda is not equipped to derive that Set (level l') <= Set (level l) from l' <= l. How do I hint to Agda's universe checker that this definition is indeed well-founded?

dependent-type agda functional-programming types
1 Answers

You don't.

That's probably not the answer you want to hear, but there are good reasons Agda rejects this type even though the way you are using universe levels seems to be correct. In particular, if Agda would allow this then strong normalization (and hence decidability of typechecking) would be lost: in an open context with a proof of 1 <= 0, you'd be able to exploit this datatype (or a variant thereof) to define a datatype that does not respect the universe hierarchy, which can then be used (through Girard's paradox) to define a non-terminating term. Since Agda cannot decide whether an assumption is consistent or not, it rules out these kind of user-proven level inequalities altogether and only trusts its own solver.

user_28825160
Related