Coq simple для программы Fixpoint

Question

Есть ли что-то вроде тактики simpl за Program Fixpoints?

В частности, как можно доказать следующее тривиальное утверждение?

Program Fixpoint bla (n:nat) {measure n} :=
match n with
| 0 => 0
| S n' => S (bla n')
end.

Lemma obvious: forall n, bla n = n. 
induction n. reflexivity.
(* I'm stuck here. For a normal fixpoint, I could for instance use 
simpl. rewrite IHn. reflexivity. But here, I couldn't find a tactic 
transforming bla (S n) to S (bla n).*)

Очевидно, нет Program Fixpoint необходимо для этого примера игрушки, но я сталкиваюсь с той же проблемой в более сложной обстановке, где мне нужно доказать прекращение Program Fixpoint вручную.

Answer 1

Я не привык использовать Program так что, вероятно, есть лучшее решение, но это то, что я придумал, развернув blaвидя, что это было внутренне определено с помощью Fix_sub и глядя на теоремы об этой функции с помощью SearchAbout Fix_sub,

Lemma obvious: forall n, bla n = n.
Proof.
intro n ; induction n.
 reflexivity.
 unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
 rewrite IHn ; reflexivity.

(* This can probably be automated using Ltac *)
 intros x f g Heq.
  destruct x.
  reflexivity.
  f_equal ; apply Heq.
Qed.

В вашем примере из реальной жизни вы, вероятно, захотите ввести редукционные леммы, чтобы вам не приходилось каждый раз выполнять одну и ту же работу. Например:

Lemma blaS_red : forall n, bla (S n) = S (bla n).
Proof.
intro n.
 unfold bla ; rewrite fix_sub_eq ; simpl ; fold (bla n).
 reflexivity.

(* This can probably be automated using Ltac *)
 intros x f g Heq.
  destruct x.
  reflexivity.
  f_equal ; apply Heq.
Qed.

Таким образом, в следующий раз у вас есть bla (S _)можно просто rewrite blaS_red,