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
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.
The attribute [abs_def]
transforms an equation with arguments into one with lambdas. E.g., f_def [abs_def]
results in f = op +
.
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.