1

假设我有一个非常简单的归纳类型：

Inductive ind : Set :=
    | ind0 : ind
    | ind1 : ind -> ind.

我想证明某些价值观是不存在的。具体来说，不能有没有根据的价值观：~exists i, i = ind1 i.

 

我在互联网上环顾了一下，什么也没想到。我能够写：

Fixpoint depth (i : ind) : nat :=
    match i with
    | ind0 => 0
    | ind1 i2 => 1 + depth i2
    end.

Goal ~exists i, i = ind1 i.
Proof.
    intro. inversion_clear H.
    remember (depth x) as d.
    induction d.
        rewrite H0 in Heqd; simpl in Heqd. discriminate.
        rewrite H0 in Heqd; simpl in Heqd. injection Heqd. assumption.
Qed.

这有效，但看起来真的很丑陋且不一般。

4

3 回答 3

1

我不认为有证明这些目标的通用方法。然而，根据我的经验，这似乎不是一个问题。在您的情况下，使用以下congruence策略有一个更简单的证明：

Inductive ind : Type :=
| ind0 : ind
| ind1 : ind -> ind.

Goal ~exists i, i = ind1 i.
Proof.
  intros [x Hx]. induction x; congruence.
Qed.
于 2013-05-03T13:07:03.400 回答
0

相反，我会证明forall n1, n1 = Succ n1 <-> False，并将其放入自动重写数据库中。

Require Import Coq.Setoids.Setoid.

Lemma L1 : forall P1, (P1 <-> P1) <-> True.
Proof. tauto. Qed.

Hint Rewrite L1 : LogHints.

Lemma L2 : forall (S1 : Set) (e1 : S1), e1 = e1 <-> True.
Proof. tauto. Qed.

Hint Rewrite L2 : LogHints.

Lemma L3 : forall n1, O = S n1 <-> False.
Proof.
intros. split.
  intros H1. inversion H1.
  tauto.
Qed.

Lemma L4 : forall n1, S n1 = O <-> False.
Proof.
intros. split.
  intros H1. inversion H1.
  tauto.
Qed.

Lemma L5 : forall n1 n2, S n1 = S n2 <-> n1 = n2.
Proof.
intros. split.
  intros H1. inversion H1 as [H2]. tauto.
  intros H1. rewrite H1. tauto.
Qed.

Hint Rewrite L3 L4 L5 : NatHints.

Lemma L6 : forall n1, n1 = S n1 <-> False.
Proof.
induction n1 as [| n1 H1];
  autorewrite with LogHints NatHints;
  tauto.
Qed.

Lemma L7 : forall n1, S n1 = n1 <-> False.
Proof.
induction n1 as [| n1 H1];
  autorewrite with LogHints NatHints;
  tauto.
Qed.

Hint Rewrite L6 L7 : NatHints.
于 2013-05-04T23:25:19.320 回答
0

或者，您可以对证明进行编程。

Definition IsO (n1 : nat) : Prop :=
  match n1 with
  | O   => True
  | S _ => False
  end.

Definition eq_O {n1 : nat} (H1 : O = n1) : IsO n1 :=
  match H1 with
  | eq_refl => I
  end.

Definition O_S_impl {n1 : nat} (H1 : O = S n1) : False := eq_O H1.

Definition S_S_impl {n1 n2 : nat} (H1 : S n1 = S n2) : n1 = n2 :=
  match H1 with
  | eq_refl => eq_refl
  end.

Fixpoint nat_inf'' {n1 : nat} : n1 = S n1 -> False :=
  match n1 with
  | O   => fun H1 => O_S_impl H1
  | S _ => fun H1 => nat_inf'' (S_S_impl H1)
  end.

Definition nat_inf' (H1 : exists n1, n1 = S n1) : False :=
  match H1 with
  | ex_intro _ H2 => nat_inf'' H2
  end.

Definition nat_inf : ~ exists n1, n1 = S n1 := nat_inf'.
于 2013-07-17T20:37:27.190 回答