1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 set "baseuri" "cic:/matita/ordered_sets/".
17 include "ordered_sets.ma".
19 record is_porder_relation (C:Type) (le:C→C→Prop) (eq:C→C→Prop) : Type ≝ {
20 por_reflexive: reflexive ? le;
21 por_transitive: transitive ? le;
22 por_antisimmetric: antisymmetric ? le eq
25 record pordered_set: Type ≝ {
27 pos_order_relation_properties:> is_porder_relation ? (le pos_carr) (eq pos_carr)
30 lemma pordered_set_of_excedence: excedence → pordered_set.
31 intros (E); apply (mk_pordered_set E); apply (mk_is_porder_relation);
32 [apply le_reflexive|apply le_transitive|apply le_antisymmetric]
35 definition total_order : ∀E:excedence. Type ≝
36 λE:excedence. ∀a,b:E. a ≰ b → a < b.
38 alias id "transitive" = "cic:/matita/higher_order_defs/relations/transitive.con".
39 alias id "cotransitive" = "cic:/matita/higher_order_defs/relations/cotransitive.con".
40 alias id "antisymmetric" = "cic:/matita/higher_order_defs/relations/antisymmetric.con".
41 theorem antisimmetric_to_cotransitive_to_transitive:
42 ∀C:Type.∀le:C→C→Prop. antisymmetric ? le → cotransitive ? le → transitive ? le.
43 intros (T f Af cT); unfold transitive; intros (x y z fxy fyz);
44 lapply (cT ? ? fxy z) as H; cases H; [assumption] cases (Af ? ? fyz H1);
47 definition is_increasing ≝ λO:pordered_set.λa:nat→O.∀n:nat.a n ≤ a (S n).
48 definition is_decreasing ≝ λO:pordered_set.λa:nat→O.∀n:nat.a (S n) ≤ a n.
50 definition is_upper_bound ≝ λO:pordered_set.λa:nat→O.λu:O.∀n:nat.a n ≤ u.
51 definition is_lower_bound ≝ λO:pordered_set.λa:nat→O.λu:O.∀n:nat.u ≤ a n.
53 record is_sup (O:pordered_set) (a:nat→O) (u:O) : Prop ≝
54 { sup_upper_bound: is_upper_bound O a u;
55 sup_least_upper_bound: ∀v:O. is_upper_bound O a v → u≤v
58 record is_inf (O:pordered_set) (a:nat→O) (u:O) : Prop ≝
59 { inf_lower_bound: is_lower_bound O a u;
60 inf_greatest_lower_bound: ∀v:O. is_lower_bound O a v → v≤u
63 record is_bounded_below (O:pordered_set) (a:nat→O) : Type ≝
65 ib_lower_bound_is_lower_bound: is_lower_bound ? a ib_lower_bound
68 record is_bounded_above (O:pordered_set) (a:nat→O) : Type ≝
70 ib_upper_bound_is_upper_bound: is_upper_bound ? a ib_upper_bound
73 record is_bounded (O:pordered_set) (a:nat→O) : Type ≝
74 { ib_bounded_below:> is_bounded_below ? a;
75 ib_bounded_above:> is_bounded_above ? a
78 record bounded_below_sequence (O:pordered_set) : Type ≝
80 bbs_is_bounded_below:> is_bounded_below ? bbs_seq
83 record bounded_above_sequence (O:pordered_set) : Type ≝
85 bas_is_bounded_above:> is_bounded_above ? bas_seq
88 record bounded_sequence (O:pordered_set) : Type ≝
90 bs_is_bounded_below: is_bounded_below ? bs_seq;
91 bs_is_bounded_above: is_bounded_above ? bs_seq
94 definition bounded_below_sequence_of_bounded_sequence ≝
95 λO:pordered_set.λb:bounded_sequence O.
96 mk_bounded_below_sequence ? b (bs_is_bounded_below ? b).
98 coercion cic:/matita/ordered_sets/bounded_below_sequence_of_bounded_sequence.con.
100 definition bounded_above_sequence_of_bounded_sequence ≝
101 λO:pordered_set.λb:bounded_sequence O.
102 mk_bounded_above_sequence ? b (bs_is_bounded_above ? b).
104 coercion cic:/matita/ordered_sets/bounded_above_sequence_of_bounded_sequence.con.
106 definition lower_bound ≝
107 λO:ordered_set.λb:bounded_below_sequence O.
108 ib_lower_bound ? b (bbs_is_bounded_below ? b).
110 lemma lower_bound_is_lower_bound:
111 ∀O:ordered_set.∀b:bounded_below_sequence O.
112 is_lower_bound ? b (lower_bound ? b).
115 apply ib_lower_bound_is_lower_bound.
118 definition upper_bound ≝
119 λO:ordered_set.λb:bounded_above_sequence O.
120 ib_upper_bound ? b (bas_is_bounded_above ? b).
122 lemma upper_bound_is_upper_bound:
123 ∀O:ordered_set.∀b:bounded_above_sequence O.
124 is_upper_bound ? b (upper_bound ? b).
127 apply ib_upper_bound_is_upper_bound.
130 definition lt ≝ λO:ordered_set.λa,b:O.a ≤ b ∧ a ≠ b.
132 interpretation "Ordered set lt" 'lt a b =
133 (cic:/matita/ordered_sets/lt.con _ a b).
135 definition reverse_ordered_set: ordered_set → ordered_set.
137 apply mk_ordered_set;
138 [2:apply (λx,y:o.y ≤ x)
140 | apply mk_is_order_relation;
143 apply (or_reflexive ? ? o)
146 apply (or_transitive ? ? o);
153 apply (or_antisimmetric ? ? o);
159 interpretation "Ordered set ge" 'geq a b =
160 (cic:/matita/ordered_sets/os_le.con _
161 (cic:/matita/ordered_sets/os_pre_ordered_set.con _
162 (cic:/matita/ordered_sets/reverse_ordered_set.con _ _)) a b).
164 lemma is_lower_bound_reverse_is_upper_bound:
165 ∀O:ordered_set.∀a:nat→O.∀l:O.
166 is_lower_bound O a l → is_upper_bound (reverse_ordered_set O) a l.
171 unfold reverse_ordered_set;
176 lemma is_upper_bound_reverse_is_lower_bound:
177 ∀O:ordered_set.∀a:nat→O.∀l:O.
178 is_upper_bound O a l → is_lower_bound (reverse_ordered_set O) a l.
183 unfold reverse_ordered_set;
188 lemma reverse_is_lower_bound_is_upper_bound:
189 ∀O:ordered_set.∀a:nat→O.∀l:O.
190 is_lower_bound (reverse_ordered_set O) a l → is_upper_bound O a l.
193 unfold reverse_ordered_set in H;
197 lemma reverse_is_upper_bound_is_lower_bound:
198 ∀O:ordered_set.∀a:nat→O.∀l:O.
199 is_upper_bound (reverse_ordered_set O) a l → is_lower_bound O a l.
202 unfold reverse_ordered_set in H;
207 lemma is_inf_to_reverse_is_sup:
208 ∀O:ordered_set.∀a:bounded_below_sequence O.∀l:O.
209 is_inf O a l → is_sup (reverse_ordered_set O) a l.
211 apply (mk_is_sup (reverse_ordered_set O));
212 [ apply is_lower_bound_reverse_is_upper_bound;
213 apply inf_lower_bound;
216 change in v with (os_carrier O);
218 apply (inf_greatest_lower_bound ? ? ? H);
219 apply reverse_is_upper_bound_is_lower_bound;
224 lemma is_sup_to_reverse_is_inf:
225 ∀O:ordered_set.∀a:bounded_above_sequence O.∀l:O.
226 is_sup O a l → is_inf (reverse_ordered_set O) a l.
228 apply (mk_is_inf (reverse_ordered_set O));
229 [ apply is_upper_bound_reverse_is_lower_bound;
230 apply sup_upper_bound;
233 change in v with (os_carrier O);
235 apply (sup_least_upper_bound ? ? ? H);
236 apply reverse_is_lower_bound_is_upper_bound;
241 lemma reverse_is_sup_to_is_inf:
242 ∀O:ordered_set.∀a:bounded_above_sequence O.∀l:O.
243 is_sup (reverse_ordered_set O) a l → is_inf O a l.
246 [ apply reverse_is_upper_bound_is_lower_bound;
247 change in l with (os_carrier (reverse_ordered_set O));
248 apply sup_upper_bound;
251 change in l with (os_carrier (reverse_ordered_set O));
252 change in v with (os_carrier (reverse_ordered_set O));
253 change with (os_le (reverse_ordered_set O) l v);
254 apply (sup_least_upper_bound ? ? ? H);
255 change in v with (os_carrier O);
256 apply is_lower_bound_reverse_is_upper_bound;
261 lemma reverse_is_inf_to_is_sup:
262 ∀O:ordered_set.∀a:bounded_above_sequence O.∀l:O.
263 is_inf (reverse_ordered_set O) a l → is_sup O a l.
266 [ apply reverse_is_lower_bound_is_upper_bound;
267 change in l with (os_carrier (reverse_ordered_set O));
268 apply (inf_lower_bound ? ? ? H)
270 change in l with (os_carrier (reverse_ordered_set O));
271 change in v with (os_carrier (reverse_ordered_set O));
272 change with (os_le (reverse_ordered_set O) v l);
273 apply (inf_greatest_lower_bound ? ? ? H);
274 change in v with (os_carrier O);
275 apply is_upper_bound_reverse_is_lower_bound;
280 record cotransitively_ordered_set: Type :=
281 { cos_ordered_set :> ordered_set;
282 cos_cotransitive: cotransitive ? (os_le cos_ordered_set)