Rewrite Taktik versagt Vorkommen innerhalb Muster finden

Question

In Coq passend, ich habe Probleme mit der Anwendung die rewrite Taktik in der folgenden Situation:

Section Test. 

Hypothesis s t  : nat -> nat. 
Hypothesis s_ext_eq_t : forall (x : nat), s x = t x. 

Definition dummy_s : nat -> nat := 
    fun n => match n with 
     | O => 42 
     | S np => s np 
     end. 

Definition dummy_t : nat -> nat := 
    fun n => match n with 
     | O => 42 
     | S np => t np 
     end. 

Goal forall (n : nat), dummy_s n = dummy_t n. 
Proof. 
    intro n. unfold dummy_s. unfold dummy_t. 

In diesem Stadium des lokalen Kontext und aktuellem Ziel aussehen, als folgt:

1 subgoals, subgoal 1 (ID 6) 

s : nat -> nat 
t : nat -> nat 
s_ext_eq_t : forall x : nat, s x = t x 
n : nat 
============================ 
match n with 
| 0 => 42 
| S np => s np 
end = match n with 
     | 0 => 42 
     | S np => t np 
     end 

Nun sollte es möglich sein, die rewrite Taktik anzuwenden, um das Auftreten von s np im Ziel durch t np, dadurch zu ersetzen, es möglich zu lösen, das Ziel zu machen mit reflexivity. Allerdings

rewrite s_ext_eq_t. 

gibt

Toplevel input, characters 0-18: 
Error: Found no subterm matching "s ?190" in the current goal. 

Was mache ich falsch? Ich bin vor, mehr solcher zerstört wäre notwendig, und ich frage mich, ob rewrite oder eine Variante davon ist in der Lage zu tun, anwendbar ist ein kann in eine Situation geraten, wo rewrite über

destruct n. 
    (* n = 0 *) 
    reflexivity. 
    (* n > 0 *) 
    rewrite s_ext_eq_t. 
    reflexivity. 
Qed. 

aber in der aktuellen Situation dies automatisch.

---

Addendum die obige Situation tritt natürlich bei, dass eine Funktion über fundierte Rekursion definiert beweist die Fixpunkteigenschaft erwünscht:

Angenommen A: Type und dass R: A -> A -> Prop eine fundierte Beziehung, dh wir haben Rwf: well_founded R. Dann, da eine Art Familie P: A -> Type wir

Fix : forall (x : A), P a 

durch Rekursion über R einen Abschnitt konstruieren können, mit dem Rekursion Schritt als eine Funktion gegeben

F : forall x:A, (forall y:A, R y x -> P y) -> P x 

Siehe https://coq.inria.fr/library/Coq.Init.Wf.html jedoch zu zeigen, dass Fix in der Tat das hat Fixpunkt Eigenschaft

forall (x : A), Fix x = F (fun (y:A) _ => Fix y)` 

wir brauchen einen Zeugen zur Verfügung zu stellen

F_ext : forall (x:A) (f g:forall y:A, R y x -> P y), 
      (forall (y:A) (p:R y x), f y p = g y p) -> F f = F g. 

das heißt wir müssen zeigen, dass F nichts anderes aus dem gegebenen f: forall y:A, R y x -> P y zu verwenden ist, aber seine Werte. Natürlich sollte dies in jeder konkreten Situation trivial sein, aber wenn man versucht, es zu beweisen, stößt man auf eine Situation, von der ich oben ein minimales Beispiel vorgestellt habe: Man steht vor einer riesigen Gleichheit von zwei Kopien des Codes für den Rekursionsschritt einmal mit f und ein anderes Mal mit g. Ihre Annahme besagt, dass f und g extensionally gleich sind, also sollte man in der Lage sein, sie neu zu schreiben. In dem Code für den Rekursionsschritt könnte es jedoch eine große Anzahl von Musteranpassungen und neuen Variablen geben, die im lokalen Kontext keinen Sinn ergeben, daher wäre es (unnötig) ziemlich doof zu destruct dutzende Male vor dem Sein darf anwenden rewrite.

Answer 1

Wie oben in einem Kommentar erwähnt, ist es nicht möglich, die Rewrite direkt auf dem Zweig der match Anweisung auszuführen, weil np in ihrem Umfang nicht in der Top-Level-Umgebung ist. Soweit Coq Theorie betrifft, muss ein Beweis Ihrer Aussage irgendwann n zerstören.

Ich bin zwar nicht bekannt, dass Taktik für diese Art von Problem zu automatisieren, ist es nicht zu hart mit einigen benutzerdefinierten LTAC Code zu kommen für Ihr Problem ohne zu viel Schmerz zu lösen:

Ltac solve_eq := 
    try reflexivity; 
    match goal with 
    | |- match ?x with _ => _ end 
     = match ?x with _ => _ end => 
    destruct x; auto 
    end. 

Goal forall (n : nat), dummy_s n = dummy_t n. 
Proof. 
    intro n. unfold dummy_s. unfold dummy_t. 
    solve_eq. 
Qed. 

Wenn Ihr Extensional Equality Ergebnisse sind Hypothesen, die in Ihrem Kontext erscheinen, dann solve_eq sollte in der Lage sein, viele Ziele dieser Form zu lösen; Falls nicht, müssen Sie möglicherweise zusätzliche Lemmas zu Ihrer Tipp-Datenbank hinzufügen.