blob: e9a18e7437b13eb918cb42238e26ffceb03df409 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
(************************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
(*i $Id: Well_Ordering.v 5920 2004-07-16 20:01:26Z herbelin $ i*)
(** Author: Cristina Cornes.
From: Constructing Recursion Operators in Type Theory
L. Paulson JSC (1986) 2, 325-355 *)
Require Import Eqdep.
Section WellOrdering.
Variable A : Set.
Variable B : A -> Set.
Inductive WO : Set :=
sup : forall (a:A) (f:B a -> WO), WO.
Inductive le_WO : WO -> WO -> Prop :=
le_sup : forall (a:A) (f:B a -> WO) (v:B a), le_WO (f v) (sup a f).
Theorem wf_WO : well_founded le_WO.
Proof.
unfold well_founded in |- *; intro.
apply Acc_intro.
elim a.
intros.
inversion H0.
apply Acc_intro.
generalize H4; generalize H1; generalize f0; generalize v.
rewrite H3.
intros.
apply (H v0 y0).
cut (f = f1).
intros E; rewrite E; auto.
symmetry in |- *.
apply (inj_pair2 A (fun a0:A => B a0 -> WO) a0 f1 f H5).
Qed.
End WellOrdering.
Section Characterisation_wf_relations.
(** Wellfounded relations are the inverse image of wellordering types *)
(* in course of development *)
Variable A : Set.
Variable leA : A -> A -> Prop.
Definition B (a:A) := {x : A | leA x a}.
Definition wof : well_founded leA -> A -> WO A B.
Proof.
intros.
apply (well_founded_induction H (fun a:A => WO A B)); auto.
intros.
apply (sup A B x).
unfold B at 1 in |- *.
destruct 1 as [x0].
apply (H1 x0); auto.
Qed.
End Characterisation_wf_relations.
|
