Zulip Chat Archive

Stream: lean4

Topic: Question about universes and typeclasses


Andy Soffer (Apr 21 2024 at 16:57):

I'm trying to prove that function composition preserves injectivity, and I was able to produce the following

def Injective {α: Sort u₁} {β: Sort u₂} (f: α  β): Prop :=
  x y: α, f x = f y  x = y

theorem inj {α: Sort u₁} {β: Sort u₂} {γ: Sort u₃}:
   f: β  γ,  g: α  β, Injective f  Injective g  Injective (fg) := by {
  -- omitted for brevity
}

This works just fine, but what I really want is a typeclass CompositionPreserves and then an instance of CompositionPreserves Injective to provide a bit more structure. (I'm open to the idea that I don't actually want this, but it seems nice to be able to talk generically about properties preserved by composition). So what I've tried is

class CompositionPreserves (property: {α: Sort u₁}  {β: Sort u₂}  (α  β)  Prop) where
  proof {α: Sort u₁} {β: Sort u₂} {γ: Sort u₃} (f: β  γ) (g: α  β):
    property f  property g  property (fg)

This doesn't seem to type-check and I'm unclear as to what's going wrong. It says that f has type β → γ but should have type β → ?m.128, which I would expect to unify. Indeed, these symbols actually have mismatched sorts, where β → γ: Sort (imax u₂ u₃) but should match β → ?m.128 : Sort u₂.

I'm unclear as to why the imax is coming in to play and why the universe constraints can't be resolved. Any pointers would be greatly appreciated.

Henrik Böving (Apr 21 2024 at 17:03):

Your declaration of property says that it expects alpha to have sort u1 and beta to have sort u2 but clearly in the case of f that is not the case, its first argument has sort u2 and the result has sort u3

Henrik Böving (Apr 21 2024 at 17:05):

In order to write this down in the most general way that you are aiming here Lean would have to support universe level parameters at that position which, afaik, it doesn't. You can aim for a lesser level of generality by saying that all should be in the same universe and that would typecheck.

Andy Soffer (Apr 21 2024 at 17:12):

This is super helpful, thank you. I expected the universe variables to be shadowed, but I don't think that's what was going on. Renaming them does resolve that particular issue, and forcing all the types into the same universe does typecheck properly!

Henrik Böving (Apr 21 2024 at 17:17):

universe variables are only declared per declaration. So if you have a class all universe variables that you mention in its body will be paramters of the class itself, not individual parts of the body


Last updated: May 02 2025 at 03:31 UTC