How can I prove the lemma in Exercise 4.6 in “Programming and Proving in Isabelle/HOL”?

1
votes

I am trying to solve Exercise 4.6 in “Programming and Proving in Isabelle/HOL”. It asks to define a function elems :: "'a list ⇒ 'a set" that converts a list into a set, and to prove the lemma "x ∈ elems xs ⟹ ∃ ys zs . xs = ys @ x # zs ∧ x ∉ elems ys". Until now, I have come that far:

fun elems :: "'a list ⇒ 'a set" where
  "elems [] = {}" |
  "elems (x # xs) = {x} ∪ elems xs"

lemma first_occ: "x ∈ elems xs ⟹ ∃ ys zs . xs = ys @ x # zs ∧ x ∉ elems ys"
proof (induction xs)
  case Nil
  thus ?case by simp
next
  case (Cons u us)
  show ?case
  proof cases
    assume "x = u"
    thus ?case
    proof
    ⟨…⟩

At this point, I get the error message “Failed to apply initial proof method”. This is strange, since the goal, ?case, is the proposition ∃ ys zs . u # us = ys @ x # zs ∧ x ∉ elems ys, and it should be possible to prove existential propositions by showing the proposition under the ∃ for a specific witness.

1
isabellequantifiersisar

1 Answers

0
votes

the problem with your line proof is that it proof is meant to apply some default rule. In the above proof, Isabelle is not able to figure out that you want to perform existential introduction. So, you probably want to explicitly tell the system to do so, e.g., by continue with something like proof (intro exI).

I hope, this helps, René