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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
(***********************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * INRIA-Rocquencourt & LRI-CNRS-Orsay *)
(* \VV/ *************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(***********************************************************************)
(* Finite sets library.
* Authors: Pierre Letouzey and Jean-Christophe Filliâtre
* Institution: LRI, CNRS UMR 8623 - Université Paris Sud
* 91405 Orsay, France *)
(* $Id: FSetToFiniteSet.v 11735 2009-01-02 17:22:31Z herbelin $ *)
Require Import Ensembles Finite_sets.
Require Import FSetInterface FSetProperties OrderedTypeEx DecidableTypeEx.
(** * Going from [FSets] with usual Leibniz equality
to the good old [Ensembles] and [Finite_sets] theory. *)
Module WS_to_Finite_set (U:UsualDecidableType)(M: WSfun U).
Module MP:= WProperties_fun U M.
Import M MP FM Ensembles Finite_sets.
Definition mkEns : M.t -> Ensemble M.elt :=
fun s x => M.In x s.
Notation " !! " := mkEns.
Lemma In_In : forall s x, M.In x s <-> In _ (!!s) x.
Proof.
unfold In; compute; auto with extcore.
Qed.
Lemma Subset_Included : forall s s', s[<=]s' <-> Included _ (!!s) (!!s').
Proof.
unfold Subset, Included, In, mkEns; intuition.
Qed.
Notation " a === b " := (Same_set M.elt a b) (at level 70, no associativity).
Lemma Equal_Same_set : forall s s', s[=]s' <-> !!s === !!s'.
Proof.
intros.
rewrite double_inclusion.
unfold Subset, Included, Same_set, In, mkEns; intuition.
Qed.
Lemma empty_Empty_Set : !!M.empty === Empty_set _.
Proof.
unfold Same_set, Included, mkEns, In.
split; intro; set_iff; inversion 1.
Qed.
Lemma Empty_Empty_set : forall s, Empty s -> !!s === Empty_set _.
Proof.
unfold Same_set, Included, mkEns, In.
split; intros.
destruct(H x H0).
inversion H0.
Qed.
Lemma singleton_Singleton : forall x, !!(M.singleton x) === Singleton _ x .
Proof.
unfold Same_set, Included, mkEns, In.
split; intro; set_iff; inversion 1; try constructor; auto.
Qed.
Lemma union_Union : forall s s', !!(union s s') === Union _ (!!s) (!!s').
Proof.
unfold Same_set, Included, mkEns, In.
split; intro; set_iff; inversion 1; [ constructor 1 | constructor 2 | | ]; auto.
Qed.
Lemma inter_Intersection : forall s s', !!(inter s s') === Intersection _ (!!s) (!!s').
Proof.
unfold Same_set, Included, mkEns, In.
split; intro; set_iff; inversion 1; try constructor; auto.
Qed.
Lemma add_Add : forall x s, !!(add x s) === Add _ (!!s) x.
Proof.
unfold Same_set, Included, mkEns, In.
split; intro; set_iff; inversion 1; auto with sets.
inversion H0.
constructor 2; constructor.
constructor 1; auto.
Qed.
Lemma Add_Add : forall x s s', MP.Add x s s' -> !!s' === Add _ (!!s) x.
Proof.
unfold Same_set, Included, mkEns, In.
split; intros.
red in H; rewrite H in H0.
destruct H0.
inversion H0.
constructor 2; constructor.
constructor 1; auto.
red in H; rewrite H.
inversion H0; auto.
inversion H1; auto.
Qed.
Lemma remove_Subtract : forall x s, !!(remove x s) === Subtract _ (!!s) x.
Proof.
unfold Same_set, Included, mkEns, In.
split; intro; set_iff; inversion 1; auto with sets.
split; auto.
contradict H1.
inversion H1; auto.
Qed.
Lemma mkEns_Finite : forall s, Finite _ (!!s).
Proof.
intro s; pattern s; apply set_induction; clear s; intros.
intros; replace (!!s) with (Empty_set elt); auto with sets.
symmetry; apply Extensionality_Ensembles.
apply Empty_Empty_set; auto.
replace (!!s') with (Add _ (!!s) x).
constructor 2; auto.
symmetry; apply Extensionality_Ensembles.
apply Add_Add; auto.
Qed.
Lemma mkEns_cardinal : forall s, cardinal _ (!!s) (M.cardinal s).
Proof.
intro s; pattern s; apply set_induction; clear s; intros.
intros; replace (!!s) with (Empty_set elt); auto with sets.
rewrite cardinal_1; auto with sets.
symmetry; apply Extensionality_Ensembles.
apply Empty_Empty_set; auto.
replace (!!s') with (Add _ (!!s) x).
rewrite (cardinal_2 H0 H1); auto with sets.
symmetry; apply Extensionality_Ensembles.
apply Add_Add; auto.
Qed.
(** we can even build a function from Finite Ensemble to FSet
... at least in Prop. *)
Lemma Ens_to_FSet : forall e : Ensemble M.elt, Finite _ e ->
exists s:M.t, !!s === e.
Proof.
induction 1.
exists M.empty.
apply empty_Empty_Set.
destruct IHFinite as (s,Hs).
exists (M.add x s).
apply Extensionality_Ensembles in Hs.
rewrite <- Hs.
apply add_Add.
Qed.
End WS_to_Finite_set.
Module S_to_Finite_set (U:UsualOrderedType)(M: Sfun U) :=
WS_to_Finite_set U M.
|
