Попробую ещё лемму с существующим

Question

Я застрял на лемме "оставил как упражнение" из этой лекции. Это выглядит так:

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

куда even индуктивный предикат, определенный следующим образом:

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

Помогите, пожалуйста? Я всегда заканчиваю с (S (S p) = 2 или похожие.

РЕДАКТИРОВАТЬ

Некоторые леммы и тактики, которые я использовал (не полное доказательство):

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

Answer 1

После вашего вводного шага у вас должно быть две цели.

Первый (базовый вариант для even0) должно быть легко доказать. Экзистенциальный свидетель должен быть выбран 0, после чего цель должна пройти рефлексивностью.

Второй случай (для evenS) будет выглядеть так:

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

IHeven говорит, что существует номер (назовем его k1) такой что p = 2 * k1,

Ваша цель - выставить номер (скажем, k2) такое, что ты можешь доказать S (S p) = 2 * k2,

Если вы делаете математику, вы должны увидеть, что (S k1) был бы идеальным кандидатом.

Поэтому для продолжения вы можете использовать следующую тактику:

• destruct разрушать IHeven отделить свидетеля k1 и доказательство того, что p = 2 * k1,
• exists выставлять (S k1) в качестве экзистенциального свидетеля для вашей цели.
• затем некоторые работы, чтобы доказать, что равенство выполнено.