Search code examples
isabelle

How to prove elimination rules using Isar?


Here is a simple theory:

datatype t1 = A | B | C
datatype t2 = D | E t1 | F | G

inductive R where
  "R A B"
| "R B C"

inductive_cases [elim]: "R x B" "R x A" "R x C"

inductive S where
  "S D (E _)"
| "R x y ⟹ S (E x) (E y)"

inductive_cases [elim]: "S x D" "S x (E y)"

I can prove lemma elim using two helper lemmas:

lemma tranclp_S_x_E:
  "S⇧+⇧+ x (E y) ⟹ x = D ∨ (∃z. x = E z)"
  by (induct rule: converse_tranclp_induct; auto)

(* Let's assume that it's proven *)
lemma reflect_tranclp_E:
  "S⇧+⇧+ (E x) (E y) ⟹ R⇧+⇧+ x y"
  sorry

lemma elim:
  "S⇧+⇧+ x (E y) ⟹
   (x = D ⟹ P) ⟹ (⋀z. x = E z ⟹ R⇧+⇧+ z y ⟹ P) ⟹ P"
  using reflect_tranclp_E tranclp_S_x_E by blast

I need to prove elim using Isar:

lemma elim:
  assumes "S⇧+⇧+ x (E y)"
    shows "(x = D ⟹ P) ⟹ (⋀z. x = E z ⟹ R⇧+⇧+ z y ⟹ P) ⟹ P"
proof -
  assume "S⇧+⇧+ x (E y)"
  then obtain z where "x = D ∨ x = E z"
    by (induct rule: converse_tranclp_induct; auto)
  also have "S⇧+⇧+ (E z) (E y) ⟹ R⇧+⇧+ z y"
    sorry
  finally show ?thesis

But I get the following errors:

No matching trans rules for calculation:
    x = D ∨ x = E z
    S⇧+⇧+ (E z) (E y) ⟹ R⇧+⇧+ z y

Failed to refine any pending goal 
Local statement fails to refine any pending goal
Failed attempt to solve goal by exported rule:
  (S⇧+⇧+ x (E y)) ⟹ P

How to fix them?

I guess that this lemma could have a simpler proof. But I need to prove it in two steps:

  1. Show the possible values of x
  2. Show that E reflects transitive closure

I think also that this lemma could be proven by cases on x. But my real data types have too many cases. So, it's not a preferred solution.


Solution

  • This variant seems to work:

    lemma elim:
      assumes "S⇧+⇧+ x (E y)"
          and "x = D ⟹ P"
          and "⋀z. x = E z ⟹ R⇧+⇧+ z y ⟹ P"
        shows "P"
    proof -
      have "S⇧+⇧+ x (E y)" by (simp add: assms(1))
      then obtain z where "x = D ∨ x = E z"
        by (induct rule: converse_tranclp_induct; auto)
      moreover
      have "S⇧+⇧+ (E z) (E y) ⟹ R⇧+⇧+ z y"
        sorry
      ultimately show ?thesis
        using assms by auto
    qed
    
    • Assumptions should be separated from the goal.
    • As a first statement I shoud use have instead of assume. It's not a new assumption, just the existing one.
    • Instead of finally I should use ultimately. It seems that the later one has a simpler application logic.