Skip to Content.
Sympa Menu

coq-club - Re: [Coq-Club] beginners problem with well_foundness

coq-club AT inria.fr

Subject: The Coq mailing list

List archive

Re: [Coq-Club] beginners problem with well_foundness


chronological Thread 
  • From: Thery Laurent <thery AT ns.di.univaq.it>
  • To: Karol Oslowski <ko181282 AT zodiac.mimuw.edu.pl>
  • Cc: Coq Club <coq-club AT pauillac.inria.fr>
  • Subject: Re: [Coq-Club] beginners problem with well_foundness
  • Date: Fri, 22 Apr 2005 15:19:53 +0200 (CEST)
  • List-archive: <http://pauillac.inria.fr/pipermail/coq-club/>



Hi,

And I want to proove the theorem:
"
inductive A R /\ increasing A R -> well_founded ( RInv R ).
"
I guess it should be very easy. I'm not giving the definitions of inductive

Here is something somewhat similar to what you try to do:

Require Import Inclusion.
Require Import Transitive_Closure.
Require Import Relation_Operators.
Require Import Relation_Definitions.
Require Import List.

Section Group.
Variable A : Set.
Variable R : A -> A ->  Prop.

Inductive Group_L : nat -> A -> A ->  Prop :=
  Group_L_0: forall (x y : A), R x y ->  Group_L 0 x y
| Group_L_n: forall n (x y z : A), Group_L n x y -> R y z -> Group_L (S n) x z .
Hint Resolve Group_L_0 .

Theorem Group_L_inclusion_clos_trans:
 forall n,  inclusion _ (Group_L n) (clos_trans A R).
intros n; elim n; simpl; auto.
intros x y H; inversion_clear H.
apply t_step; auto.
intros n0 H x y H0.
inversion_clear H0 as [|t1 t2 y0].
apply t_trans with y0; auto.
apply t_step; auto.
Qed.

Theorem Acc_R_Group_L: forall n x, Acc R x ->  Acc (Group_L n) x.
intros n x H; apply Acc_incl with (clos_trans A R); auto.
apply Group_L_inclusion_clos_trans; auto.
apply Acc_clos_trans; auto.
Qed.

Theorem wf_R_Group_L: forall n, well_founded R -> well_founded (Group_L n).
intros n; unfold well_founded; intros H y; apply Acc_R_Group_L; auto.
Qed.

--
Laurent Théry



Archive powered by MhonArc 2.6.16.

Top of Page