Proving non-existence of an infinite inductive value in Coq

Question

Suppose I have a very simple inductive type:

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

and I'd like to prove that certain values can't exist. Specifically, that there can't be non-well-founded values: ~exists i, i = ind1 i.

 

I've looked around a bit on the internet and came up with nothing. I was able to write:

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.

which works, but seems really ugly and non-general.

Answer 1

I don't think there is a general method for proving such goals. From my experience, this has not seemed to be such a problem, however. In your case, there is a simpler proof, using the congruence tactic:

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

Goal ~exists i, i = ind1 i.
Proof.
  intros [x Hx]. induction x; congruence.
Qed.

Answer 2

Alternatively, you could program your proofs.

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'.

Answer 3

I would prove forall n1, n1 = Succ n1 <-> False instead, and put it in an autorewrite database.

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.