Search code examples
lambdaisabelletheorem-proving

Normal constant definition versus lambda constant definition


I have these two definitions. Why are they unfolding differently? How can I prove the "oops"-ed lemmas? (And in general, what is the difference between these two definitions in Isabelle, internally?)

(Please don't direct me to external links because I usually get swamped by the information there.)

  definition "f x y = x+y"
  definition "g ≡ λx y. x+y"

  value "f 1 2" (* "1 + (1 + 1)" :: "'a" *)
  value "g 1 2" (* "1 + (1 + 1)" :: "'a" *)

  value "f 1"   (* "op + 1" :: "'a ⇒ 'a" *)
  value "g 1"   (* "op + 1" :: "'a ⇒ 'a" *)

  value "f"     (* "op +" :: "'a ⇒ 'a ⇒ 'a" *)
  value "g"     (* "op +" :: "'a ⇒ 'a ⇒ 'a" *)


  lemma "f x y≡g x y" 
    apply (simp add:f_def g_def)
  done 

  lemma "f x ≡g x"
    apply (simp add:f_def g_def)
    (* f x ≡ op + x *)
  oops

  lemma "f ≡ g"
    apply (simp add:f_def g_def)
    (* f ≡ op + *)
  oops

Solution

  • The difference between a definition with explicit arguments on the left (like f x y = x + y) and one with lambdas on the right (like g = (%x y. x + y)) is what kind of defining equation you get out of it.

    For the former it is

    f_def: "f ?x ?y = ?x + ?y"
    

    (i.e., this equation is only applicable if all arguments of f are present, thus it is neither applicable to f alone nor to the partially applied f x, for example) and for the latter

    g_def: "g = op +"
    

    (where op + is just syntactic sugar for %x y. x + y; note that this equation, in contrast to the former, is applicable to every occurrence of g whatsoever).

    There are two common techniques that can be used to handle partially applied functions vs. functions with explicit argument list.

    1. The attribute [abs_def] transforms an equation with arguments into one with lambdas. E.g., f_def [abs_def] results in f = op +.

    2. The lemma ext (for extensionality) explicitly adds arguments to equations between functions.

      ext: "(!!x. ?f x = ?g x) ⟹ ?f = ?g"
      

    For your lemmas either of this techniques suffices. Either add [abs_def] to every occurrence of f_def in your proof attempts or do the following.

    lemma "f x = g x"
    apply (intro ext)
    apply (simp add: f_def g_def)
    done
    
    lemma "f = g"
    apply (intro ext)
    apply (simp add: f_def g_def)
    done
    

    Where intro applies ext as often as possible (as determined by the type of a function).

    Note that I used HOL equality (op =) rather than Pure equality (op ≡) in the above proofs. While both are logically equivalent, the lemma ext only applies to the former. As a general rule: for Isabelle/HOL stick to op = whenever possible.