Ich stecke gerade beim Lemma mit existiert fest

Question

Ich hänge an einem Lemma „als Übung übrig“ fest dieser Vortrag.Es geht so:

Lemma even_double : forall n, even n -> exists k, n = 2 * k.
Proof.
  intros n H.
  induction H.
  ...

Wo even ist ein induktives Prädikat, das wie folgt definiert ist:

Inductive even : nat -> Prop :=
| even0 : even 0
| evenS : forall p:nat, even p -> even (S (S p).

Hilfe bitte?Am Ende habe ich immer (S (S p) = 2 o.ä.

BEARBEITEN

Einige Lemmata und Taktiken, die ich verwendet habe (kein vollständiger Beweis):

destruct IHeven
exists (S x)
rewrite mult_succ_l
apply eq_S
apply plus_n_Sm

Answer 1

Nach Ihrem Einführungsschritt sollten Sie zwei Ziele haben.

Der erste (Basisfall für even0) sollte leicht zu beweisen sein.Der existenzielle Zeuge sollte ausgewählt werden 0, danach sollte das Ziel durch Reflexivität gehalten werden.

Der zweite Fall (z evenS) würde aussehen wie:

p : nat
H : even p
IHeven : exists k : nat, p = 2 * k
============================
 exists k : nat, S (S p) = 2 * k

IHeven sagt, dass es eine Zahl gibt (benennen wir sie). k1) so dass p = 2 * k1.

Ihr Ziel ist es, eine Zahl anzuzeigen (z. B. k2), so dass Sie es beweisen können S (S p) = 2 * k2.

Wenn Sie rechnen, sollten Sie das sehen (S k1) wäre der perfekte Kandidat.

Um fortzufahren, können Sie die folgenden Taktiken anwenden:

• destruct zerstören IHeven einen Zeugen trennen k1 und ein Beweis dafür p = 2 * k1.
• exists ausstellen (S k1) als existenzieller Zeuge für Ihr Ziel.
• Dann arbeiten wir daran, zu beweisen, dass die Gleichheit gilt.