recursively invert hypotheses in coq

Question

I am having trouble defining a tactic to recursively invert hypotheses in a proof context. For instance, suppose I have a proof context containing a hypothesis like:

H1 : search_tree (node a (node b ll lr) (node c rl rr))

and would like to repeatedly invert the hypothesis to obtain a proof context containing the hypotheses

H1 : search_tree (node a (node b ll lr) (node c rl rr))
H2 : search_tree (node b ll lr)
H3 : search_tree (node c rl rr)
H4 : lt_tree a (node b ll lr)
H5 : gt_tree a (node c rl rr)
H6 : lt_tree b ll
H7 : gt_tree b lr
H8 : lt_tree c rl
H9 : gt_tree c rr

Of course, obtaining this proof context is easy by repeatedly applying the inversion tactic. However, sometimes inverting a hypothesis will put different hypotheses into different subgoals, and whether to invert each depends on the nature of the information provided by inversion.

The obvious problem is that indiscriminately pattern matching against the proof context will cause nontermination. For instance, the following won't work if one wishes to retain the original hypotheses after inverting them:

Ltac invert_all :=
  match goal with
    | [ H1 : context [ node ?a ?l ?r ] |- ?goal ] => invert H1; invert_all
    | _ => idtac
  end.

Is there an easy way to do this? The obvious solution would be to keep a stack of already inverted hypotheses. Another solution is to only invert hypotheses up to a particular depth, which would remove recursive calls in Ltac.

some guy on the street some guy on the street · Accepted Answer · 2012-01-26T04:26:56

If that's really what you want to do, I suspect you want first to prove a helper Fixpoint subtreelist (st : searchtree): list (...) that returns a list of all these subtrees, and then a tactic that calls subtreelist and recursively destructs the list untill you have all the extra hypotheses you want.

Good luck with that!

recursively invert hypotheses in coq

1 Answers