'The induction proof in Isabelle: given a subgoal, how to create the right auxiliary lemma

I have defined a labeled transition system, and the function which accpets the list that system could reach. For convinence, I defined another funtion used for collecting reachable states. And I want to prove the relation between these two functions.

type_synonym ('q,'a) LTS = "('q * 'a set * 'q) set"

primrec LTS_is_reachable :: "('q, 'a) LTS \<Rightarrow> 'q \<Rightarrow> 'a list \<Rightarrow> 'q \<Rightarrow> bool" where
   "LTS_is_reachable \<Delta> q [] q' = (q = q')"|
   "LTS_is_reachable \<Delta> q (a # w) q' =
      (\<exists>q'' \<sigma>. a \<in> \<sigma> \<and> (q, \<sigma>, q'') \<in> \<Delta> \<and> LTS_is_reachable \<Delta> q'' w q')"


primrec LTS_is_reachable_set :: "('q, 'a) LTS ⇒ 'q ⇒ 'a list ⇒ 'q set" where    
  "LTS_is_reachable_set Δ q [] = {q}"|
  "LTS_is_reachable_set Δ q (a # w) = \<Union> ((λ(q, σ, q''). if a \<in> σ then LTS_is_reachable_set Δ q'' w else {}) ` Δ)"

lemma "LTS_is_reachable Δ q1 w q2 \<Longrightarrow> q2\<in>(LTS_is_reachable_set Δ  q1 w)"
  apply (induct w)
   apply simp

Have such a lemma, I don't know how to prove it.

The subgoal is here:

 ⋀a w. (LTS_is_reachable Δ q1 w q2 ⟹ q2 ∈ LTS_is_reachable_set Δ q1 w) ⟹
           ∃q'' σ. a ∈ σ ∧ (q1, σ, q'') ∈ Δ ∧ LTS_is_reachable Δ q'' w q2 ⟹
           ∃x∈Δ. q2 ∈ (case x of (q, σ, q'') ⇒ if a ∈ σ then LTS_is_reachable_set Δ q'' w else {})
isabelle


Solution 1:[1]

There is a problem with your example beyond how to prove the lemma: Your definition of LTS_is_reachable_set is buggy. Consider the second equation of this definition:

"LTS_is_reachable_set ? q (a # w) = ? ((?(q, ?, q''). ...

The issue here is that variable q in ?(q, ?, q'') is not the same as the parameter q in the left-hand side. Therefore, you should rename q in the right-hand side to, for example, q' and explicitly check that q and q' are equal as follows:

"LTS_is_reachable_set ? q (a # w) = ? ((?(q', ?, q''). if a ? ? ? q' = q then ...

Now, you can prove your lemma by induction on w as you intended to do it. However, you need to weaken the induction hypotheses by making q1 an arbitrary value so you can effectively apply it in your proof. Here's an example of how you can prove your lemma:

lemma "LTS_is_reachable ? q1 w q2 ? q2 ? LTS_is_reachable_set ? q1 w"
proof (induction w arbitrary: q1)
  case Nil
  then show ?case
    by simp
next
  case (Cons a w)
  from `LTS_is_reachable ? q1 (a # w) q2`
  obtain q'' and ?
  where "a ? ?" and "(q1, ?, q'') ? ?" and "LTS_is_reachable ? q'' w q2"
    by auto
  moreover from `LTS_is_reachable ? q'' w q2` and Cons.IH
  have "q2 ? LTS_is_reachable_set ? q'' w"
    by simp
  ultimately show ?case
    by fastforce
qed

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Javier Díaz

Related Questions