agda

Inductive relations: Explicit proof that inverse relation is refl


In PLFA they define the inverse relation:

inv-z≤n :   ∀ {m : ℕ} 
            → m ≤ zero 
        ----------------------
            → m ≡ zero

And then assert that:

inv-z≤n z≤n = refl

My question is, how could I give an explicit proof of m ≡ zero? I'm looking something that looks like this:

inv-z≤n {m} (z≤n) = 
    begin
        m
    ≡⟨⟩
        .....
    ≡⟨⟩
        zero
    ∎

but completing the intermediate steps with something. Of course simply writing

inv-z≤n {m} (z≤n) = 
    begin
        m
    ≡⟨⟩
        zero
    ∎

compiles, but I don't find it satisfying. I want to know why m ≡ zero instead of just writing that refl is a proof.


Solution

  • @Matematiflo's answer is pretty comprehensive (and the gist of my more long-winded account below is already present in their first line of explanation), but intuitively/informally one can gain confidence in the unimpeachable formality of the Agda by thinking out loud as follows (and learning to do so whenever faced with a formal proof that seems hard to understand: leave the machine behind and 'reckon it out' in your own mind):

    In terms of your Agda fragment

    inv-z≤n {m} (z≤n) = 
        begin
            m
        ≡⟨⟩
            zero
        ∎
    

    what 'is going on' is that the pattern (z≤n) is actually forcing the prior binding {m} in fact to be of the form {m@zero} or {m = zero}... in the Good Old Days, such 'forced' bindings were marked with a dot (and interactively such bindings, and marks on bindings, would be inserted by the typechecker), so that the following would typecheck

    inv-z≤n {.zero} (z≤n) = 
        begin
            zero
        ≡⟨⟩
            zero
        ∎
    

    but the @-pattern or telescopic {m = ...} forms work just as well. But just because the typechecker accepts it doesn't really answer the question as to why?, does it?

    There's maybe the additional meta-level why? as to "why is such reasoning sound in the first place?" which touches on our willingness to accept proof by induction on complicated inductive definitions, and the justification of dependently-typed pattern-matching as a mechanism to instrument such reasoning (and unification along with it as the means by which we can say what form(s) m must take in the course of such reasoning)... but