指导完成证明

Question

我希望得到一些指导来完成这个证明。我卡在了最后admit（其他的我都完成了没有问题，但是我省略了真正的证明）

我根据我的推理添加了评论，因为我认为它解释得比我试图在一个段落中描述它更好。

这是正在使用的函数的定义：

In = 
fix In (A : Type) (x : A) (l : list A) {struct l} : Prop := match l with
                                                            | [ ] => False
                                                            | x' :: l' => x' = x \/ In A x l'
                                                            end
     : forall A : Type, A -> list A -> Prop

Argument A is implicit and maximally inserted
Argument scopes are [type_scope _ _]

map = 
fix map (X Y : Type) (f : X -> Y) (l : list X) {struct l} : list Y := match l with
                                                                      | [ ] => [ ]
                                                                      | h :: t => f h :: map X Y f t
                                                                      end
     : forall X Y : Type, (X -> Y) -> list X -> list Y

Arguments X, Y are implicit and maximally inserted
Argument scopes are [type_scope type_scope function_scope _]

这是引理：

Lemma foo :
  forall (A B : Type) (f : A -> B) (l : list A) (y : B),
    In y (map f l) <->
    exists x, f x = y /\ In x l.
Proof.
  intros A B f l y. split.
  - admit.
  - induction l as [|x0 l' HIl'].
    * admit.
    * (*
      HIl': (exists x : A, f x = y /\ In x l') -> In y (map f l')
      Goal: (exists x : A, f x = y /\ In x (x0 :: l')) -> In y (map f (x0 :: l'))
      *)
      intros H. simpl.
      (*
      Goal: f x0 = y \/ In y (map f l')
      *)
      right.
      (*
      Taking the right side, because if `f x0 = y`, then the induction
      hypothesis would tell us nothing.
      *)
      apply HIl'.
      (*
      Goal: exists x : A, f x = y /\ In x l'
      *)
      destruct H as [x1 H']. exists x1.
      (*
      This `x1` should be the element that is in both `l'` and `x0 ::
      l'`, because we discarded the case when `f x0 = y`.

      Goal: f x1 = y /\ In x1 l'
      *)
      destruct H' as [H'l H'r]. split.
      + (* Goal: fx1 = y *) apply H'l .
      + (* Goal: In x1 l' *)
        (*
           `x1` must be in `l'`, because we know it is in x0 :: l` by H'r:
           H'r: In x1 (x0 :: l')
           and we discarded the case where `f x0 = y`.
        *)
        destruct H'r as [H'rl | H'rr].
        { (* Stuck!!! *) admit. }
        { apply H'rr. } Abort.

Answer 1

Lemma foo :
  forall (A B : Type) (f : A -> B) (l : list A) (y : B),
    In y (map f l) <->
    exists x, f x = y /\ In x l.
Proof.
  - admit.
  - induction l as [|x0 l' HIl'].
    * admit.
    * (*
      -- HIl': (exists x : A, f x = y /\ In x l') -> In y (map f l')
      -- Goal: (exists x : A, f x = y /\ In x (x0 :: l')) -> In y (map f (x0 :: l'))
      *)
      intros H. simpl.
      (*
      -- Goal: f x0 = y \/ In y (map f l')

      you might need to destruct H first.
       *)
      destruct H.
      destruct H.
      (* right. *)
      (*
      -- Taking the right side, because if `f x0 = y`, then the induction
      -- hypothesis would tell us nothing.
      acatually, consider x = x0, we can subst and just apply H here.
      we will destruct on H0 to analysis case x = x0 || In x l'.
       *)
      destruct H0. {
        left.
        rewrite H0.
        assumption.
      }
      (* in this case we select rhs. *)
      {
        right.
        apply HIl'.
        exists x.
        split. {
          assumption.
        }
        {
          assumption.
        }
      }
Admitted.

抱歉我在工作，我想我会在一分钟内编辑它。

你会注意到In x l的假设应该被推翻然后单独分析。当您对 l 进行归纳时，它会替换为 In x (x0 :: l)，对于 x = x0 或 In x l.

，合取应该成立

Answer 2

Lemma foo :
  forall (A B : Type) (f : A -> B) (l : list A) (y : B),
    In y (map f l) <->
    exists x, f x = y /\ In x l.
Proof.
  induction l; split; intros.
  - now inversion H.
  - now firstorder.
  - inversion H.
    + now exists a; firstorder.
    + apply IHl in H0.
      destruct H0 as [x Hx].
      now exists x; firstorder.
  - destruct H as [x [Hx [Hi | Hi]]].
    + now left; subst.
    + right.
      apply IHl.
      exists x.
      firstorder.
Qed.

Answer 3

right. 战术太早了。此时 H 告诉我们 x 在 (x0 :: l) 中，但如果那是因为 x = x0 呢？那么就没有办法证明正确的选择，但在那种情况下左边的选择是正确的。因此，在选择 left 或 right 方面之前，您必须解构 H。

指导完成证明

Guidance completing a proof

proof

theorem-proving

coq