isabelle - Datatype equality in higher order logic -

isabelle - Datatype equality in higher order logic -

having next theory:

theory bitvector imports main begin datatype bitvector = btm | bitv bool bitvector lemma "∀ x1 x2 y1 y2. (bitv x1 x2 = bitv y1 y2) = (x1=y1) ∧ (x2=y2)"

i next proof state:

proof (prove): step 0 goal (1 subgoal): 1. ∀x1 x2 y1 y2. (bitv x1 x2 = bitv y1 y2) = (x1 = y1) ∧ x2 = y2 auto quickcheck found counterexample: x1 = false x2 = bitv true btm y1 = false y2 = btm

what kind of equality here? obvious not structural equality of standard ml. or, there bug in formalisation?

be careful equality of boolean-type expressions. due operator precedence, proposition of lemma following:

lemma "∀ x1 x2 y1 y2. ((bitv x1 x2 = bitv y1 y2) = (x1=y1)) ∧ (x2=y2)"

this false. should write is:

lemma "∀ x1 x2 y1 y2. (bitv x1 x2 = bitv y1 y2) = ((x1=y1) ∧ (x2=y2))"

in fact, due these operator precedence issues, prefer using ⟷ equality of boolean expressions:

lemma "∀ x1 x2 y1 y2. bitv x1 x2 = bitv y1 y2 ⟷ x1 = y1 ∧ x2 = y2"

moreover, 1 write lemma such without hol universal quantifiers , instead utilize following, equivalent:

lemma "bitv x1 x2 = bitv y1 y2 ⟷ x1 = y1 ∧ x2 = y2"

all of these lemmas proven simplifier, direct consequences of injectivity lemmas automatically provided datatype command.

i should mention instead of defining bit vectors yourself, may want utilize predefined formalisation of bit vectors in src/hol/word. examples exist in src/hol/word/examples.

isabelle