Atascado en incluso lema con existe

Question

Estoy atrapado en un lema "dejado como ejercicio" de esta conferencia.Dice así:

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

Dónde even es un predicado inductivo definido así:

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

¿Ayuda por favor?siempre termino con (S (S p) = 2 o similar.

EDITAR

Algunos lemas y tácticas que utilicé (no prueba completa):

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

Answer 1

Después de tu paso de inducción, deberías tener dos objetivos.

El primero (caso base para even0) debería ser fácil de probar.El testigo existencial debe ser elegido para ser 0, después de lo cual el objetivo debe mantenerse por reflexividad.

El segundo caso (por evenS) se vería así:

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

IHeven dice que existe un número (llamémoslo k1) tal que p = 2 * k1.

Su objetivo es exhibir un número (digamos, k2) de modo que puedas probar S (S p) = 2 * k2.

Si haces los cálculos, deberías ver eso. (S k1) Sería el candidato perfecto.

Entonces, para proceder puedes utilizar las siguientes tácticas:

• destruct destruir IHeven separar a un testigo k1 y una prueba de que p = 2 * k1.
• exists exhibir (S k1) como testigo existencial de tu objetivo.
• luego algo de trabajo para demostrar que se cumple la igualdad.