| 1 |
needs "Formal_ineqs/lib/ssreflect/ssreflect.hl";; |
| 2 |
needs "Formal_ineqs/lib/ssreflect/sections.hl";; |
| 3 |
|
| 4 |
(* Module Ssrfun*) |
| 5 |
module Ssrfun = struct |
| 6 |
|
| 7 |
open Ssreflect;; |
| 8 |
|
| 9 |
let oapp = define `!f x y. oapp f x (SOME y) = f y /\ oapp f x NONE = x`;; |
| 10 |
let odflt = new_definition `odflt = oapp I`;; |
| 11 |
let obind = new_definition `obind f = oapp f NONE`;; |
| 12 |
let omap = new_definition `omap f = obind (\x. SOME (f x))`;; |
| 13 |
let pcomp = new_definition `pcomp f g x = obind f (g x)`;; |
| 14 |
|
| 15 |
(* Lemma odflt_alt *) |
| 16 |
let odflt_alt = Sections.section_proof ["x"] |
| 17 |
`(!y. odflt x (SOME y) = y) /\ odflt x NONE = x` |
| 18 |
[ |
| 19 |
(((((use_arg_then2 ("odflt", [odflt]))(thm_tac (new_rewrite [] [])))) THEN (repeat_tactic 1 9 (((use_arg_then2 ("oapp", [oapp]))(thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("I_THM", [I_THM]))(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 20 |
];; |
| 21 |
|
| 22 |
(* Lemma obind_alt *) |
| 23 |
let obind_alt = Sections.section_proof ["f"] |
| 24 |
`obind f NONE = NONE /\ (!x. obind f (SOME x) = f x)` |
| 25 |
[ |
| 26 |
(((((use_arg_then2 ("obind", [obind]))(thm_tac (new_rewrite [] [])))) THEN (repeat_tactic 1 9 (((use_arg_then2 ("oapp", [oapp]))(thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 27 |
];; |
| 28 |
|
| 29 |
(* Lemma omap_alt *) |
| 30 |
let omap_alt = Sections.section_proof ["f"] |
| 31 |
`omap f NONE = NONE /\ (!x. omap f (SOME x) = SOME (f x))` |
| 32 |
[ |
| 33 |
(((((use_arg_then2 ("omap", [omap]))(thm_tac (new_rewrite [] [])))) THEN (((use_arg_then2 ("obind", [obind]))(thm_tac (new_rewrite [] [])))) THEN (repeat_tactic 1 9 (((use_arg_then2 ("oapp", [oapp]))(thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 34 |
];; |
| 35 |
|
| 36 |
(* Lemma eq_sym *) |
| 37 |
let eq_sym = Sections.section_proof ["x";"y"] |
| 38 |
`x = y ==> y = x` |
| 39 |
[ |
| 40 |
((BETA_TAC THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 41 |
];; |
| 42 |
|
| 43 |
(* Lemma eq_trans *) |
| 44 |
let eq_trans = Sections.section_proof ["x";"y";"z"] |
| 45 |
`x = y ==> y = z ==> x = z` |
| 46 |
[ |
| 47 |
((BETA_TAC THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] [])))) THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 48 |
];; |
| 49 |
|
| 50 |
(* Lemma f_equal *) |
| 51 |
let f_equal = Sections.section_proof ["f";"x";"y"] |
| 52 |
`x = y ==> f x = f y` |
| 53 |
[ |
| 54 |
((BETA_TAC THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 55 |
];; |
| 56 |
|
| 57 |
(* Lemma f_equal2 *) |
| 58 |
let f_equal2 = Sections.section_proof ["f";"x1";"y1";"x2";"y2"] |
| 59 |
`x1 = y1 ==> x2 = y2 ==> f x1 x2 = f y1 y2` |
| 60 |
[ |
| 61 |
((BETA_TAC THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] [])))) THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 62 |
];; |
| 63 |
let erefl = eq_sym;; |
| 64 |
let esym = eq_sym;; |
| 65 |
let etrans = eq_trans;; |
| 66 |
let congr1 = f_equal;; |
| 67 |
let congr2 = f_equal2;; |
| 68 |
|
| 69 |
(* Lemma eq_ext *) |
| 70 |
let eq_ext = Sections.section_proof ["f";"g"] |
| 71 |
`(!x. f x = g x) <=> f = g` |
| 72 |
[ |
| 73 |
(((THENL) (split_tac) [(DISCH_THEN (fun snd_th -> (use_arg_then2 ("EQ_EXT", [EQ_EXT])) (thm_tac (match_mp_then snd_th MP_TAC)))); (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))]) THEN (done_tac)); |
| 74 |
];; |
| 75 |
|
| 76 |
(* Section Injections *) |
| 77 |
Sections.begin_section "Injections";; |
| 78 |
(Sections.add_section_var (mk_var ("f", (`:A -> R`))));; |
| 79 |
let injective = new_definition `injective f <=> (!x1 x2. f x1 = f x2 ==> x1 = x2)`;; |
| 80 |
let cancel = new_definition `cancel f g <=> !x. g (f x) = x`;; |
| 81 |
let pcancel = new_definition `pcancel f g <=> !x. g (f x) = SOME x`;; |
| 82 |
let ocancel = new_definition `ocancel g h <=> !x. oapp h x (g x) = x`;; |
| 83 |
|
| 84 |
(* Lemma can_pcan *) |
| 85 |
let can_pcan = Sections.section_proof ["g"] |
| 86 |
`cancel f g ==> pcancel f (\y. SOME (g y))` |
| 87 |
[ |
| 88 |
(((((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] [])))) THEN (((use_arg_then2 ("pcancel", [pcancel]))(thm_tac (new_rewrite [] [])))) THEN (simp_tac)) THEN (done_tac)); |
| 89 |
];; |
| 90 |
|
| 91 |
(* Lemma pcan_inj *) |
| 92 |
let pcan_inj = Sections.section_proof ["g"] |
| 93 |
`pcancel f g ==> injective f` |
| 94 |
[ |
| 95 |
(((((use_arg_then2 ("pcancel", [pcancel]))(thm_tac (new_rewrite [] [])))) THEN (((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] []))))) THEN (move ["can"]) THEN (move ["x1"]) THEN (move ["x2"]) THEN (move ["f_eq"])); |
| 96 |
((((fun arg_tac -> (use_arg_then2 ("can", [])) (fun fst_arg -> (use_arg_then2 ("x2", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (disch_tac [])) THEN ((fun arg_tac -> (use_arg_then2 ("can", [])) (fun fst_arg -> (use_arg_then2 ("x1", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (disch_tac [])) THEN BETA_TAC) THEN ((((use_arg_then2 ("f_eq", []))(thm_tac (new_rewrite [] [])))) THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN (((fun arg_tac -> arg_tac (Arg_theorem (injectivity "option")))(thm_tac (new_rewrite [] [])))) THEN (done_tac)); |
| 97 |
];; |
| 98 |
|
| 99 |
(* Lemma can_inj *) |
| 100 |
let can_inj = Sections.section_proof ["g"] |
| 101 |
`cancel f g ==> injective f` |
| 102 |
[ |
| 103 |
(((((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] [])))) THEN (((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] []))))) THEN (move ["can"]) THEN (move ["x1"]) THEN (move ["x2"]) THEN (move ["f_eq"])); |
| 104 |
(((((fun arg_tac -> (use_arg_then2 ("can", [])) (fun fst_arg -> (use_arg_then2 ("x1", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg)))(gsym_then (thm_tac (new_rewrite [] []))))) THEN (((fun arg_tac -> (use_arg_then2 ("can", [])) (fun fst_arg -> (use_arg_then2 ("x2", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg)))(gsym_then (thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("f_eq", []))(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 105 |
];; |
| 106 |
|
| 107 |
(* Lemma canLR *) |
| 108 |
let canLR = Sections.section_proof ["g";"x";"y"] |
| 109 |
`cancel f g ==> x = f y ==> g x = y` |
| 110 |
[ |
| 111 |
(((((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] [])))) THEN (move ["can"]) THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 112 |
];; |
| 113 |
|
| 114 |
(* Lemma canRL *) |
| 115 |
let canRL = Sections.section_proof ["g";"x";"y"] |
| 116 |
`cancel f g ==> f x = y ==> x = g y` |
| 117 |
[ |
| 118 |
(((((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] [])))) THEN (move ["can"]) THEN (((conv_thm_tac DISCH_THEN)(gsym_then (thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 119 |
];; |
| 120 |
|
| 121 |
(* Finalization of the section Injections *) |
| 122 |
let can_pcan = Sections.finalize_theorem can_pcan;; |
| 123 |
let pcan_inj = Sections.finalize_theorem pcan_inj;; |
| 124 |
let can_inj = Sections.finalize_theorem can_inj;; |
| 125 |
let canLR = Sections.finalize_theorem canLR;; |
| 126 |
let canRL = Sections.finalize_theorem canRL;; |
| 127 |
Sections.end_section "Injections";; |
| 128 |
|
| 129 |
(* Lemma some_inj *) |
| 130 |
let some_inj = Sections.section_proof [] |
| 131 |
`injective SOME` |
| 132 |
[ |
| 133 |
(((((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] [])))) THEN (((fun arg_tac -> arg_tac (Arg_theorem (injectivity "option")))(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 134 |
];; |
| 135 |
|
| 136 |
(* Section InjectionsTheory *) |
| 137 |
Sections.begin_section "InjectionsTheory";; |
| 138 |
(Sections.add_section_var (mk_var ("f", (`:B -> A`))); Sections.add_section_var (mk_var ("g", (`:B -> A`))));; |
| 139 |
(Sections.add_section_var (mk_var ("h", (`:C -> B`))));; |
| 140 |
|
| 141 |
(* Lemma inj_id *) |
| 142 |
let inj_id = Sections.section_proof [] |
| 143 |
`injective I` |
| 144 |
[ |
| 145 |
(((((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] [])))) THEN (repeat_tactic 1 9 (((use_arg_then2 ("I_THM", [I_THM]))(thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 146 |
];; |
| 147 |
|
| 148 |
(* Lemma inj_can_sym *) |
| 149 |
let inj_can_sym = Sections.section_proof ["f'"] |
| 150 |
`cancel f f' ==> injective f' ==> cancel f' f` |
| 151 |
[ |
| 152 |
(((repeat_tactic 2 0 (((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] []))))) THEN (move ["can1"]) THEN (move ["inj"]) THEN (move ["x"])); |
| 153 |
((((use_arg_then2 ("inj", [])) (disch_tac [])) THEN (clear_assumption "inj") THEN (DISCH_THEN apply_tac)) THEN (((use_arg_then2 ("can1", []))(thm_tac (new_rewrite [] [])))) THEN (done_tac)); |
| 154 |
];; |
| 155 |
|
| 156 |
(* Lemma inj_comp *) |
| 157 |
let inj_comp = Sections.section_proof [] |
| 158 |
`injective f ==> injective h ==> injective (f o h)` |
| 159 |
[ |
| 160 |
(((repeat_tactic 3 0 (((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] []))))) THEN (repeat_tactic 2 0 (((use_arg_then2 ("o_THM", [o_THM]))(thm_tac (new_rewrite [] [])))))) THEN (move ["inj_f"]) THEN (move ["inj_h"]) THEN (move ["x1"]) THEN (move ["x2"])); |
| 161 |
((BETA_TAC THEN (DISCH_THEN (fun snd_th -> (use_arg_then2 ("inj_f", [])) (thm_tac (match_mp_then snd_th MP_TAC)))) THEN (DISCH_THEN (fun snd_th -> (use_arg_then2 ("inj_h", [])) (thm_tac (match_mp_then snd_th MP_TAC))))) THEN (done_tac)); |
| 162 |
];; |
| 163 |
|
| 164 |
(* Lemma can_comp *) |
| 165 |
let can_comp = Sections.section_proof ["f'";"h'"] |
| 166 |
`cancel f f' ==> cancel h h' ==> cancel (f o h) (h' o f')` |
| 167 |
[ |
| 168 |
((((repeat_tactic 3 0 (((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] []))))) THEN (repeat_tactic 2 0 (((use_arg_then2 ("o_THM", [o_THM]))(thm_tac (new_rewrite [] [])))))) THEN (move ["f_can"]) THEN (move ["h_can"]) THEN (move ["x"])) THEN (done_tac)); |
| 169 |
];; |
| 170 |
|
| 171 |
(* Lemma pcan_pcomp *) |
| 172 |
let pcan_pcomp = Sections.section_proof ["f'";"h'"] |
| 173 |
`pcancel f f' ==> pcancel h h' ==> pcancel (f o h) (pcomp h' f')` |
| 174 |
[ |
| 175 |
((((repeat_tactic 3 0 (((use_arg_then2 ("pcancel", [pcancel]))(thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("pcomp", [pcomp]))(thm_tac (new_rewrite [] [])))) THEN (((use_arg_then2 ("o_THM", [o_THM]))(thm_tac (new_rewrite [] []))))) THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))) THEN ((((use_arg_then2 ("obind", [obind]))(thm_tac (new_rewrite [] [])))) THEN (((use_arg_then2 ("oapp", [oapp]))(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 176 |
];; |
| 177 |
|
| 178 |
(* Lemma eq_inj *) |
| 179 |
let eq_inj = Sections.section_proof [] |
| 180 |
`injective f ==> (!x. f x = g x) ==> injective g` |
| 181 |
[ |
| 182 |
(((((use_arg_then2 ("eq_ext", [eq_ext]))(thm_tac (new_rewrite [] [])))) THEN (move ["inj"]) THEN (((conv_thm_tac DISCH_THEN)(gsym_then (thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 183 |
];; |
| 184 |
|
| 185 |
(* Lemma eq_can *) |
| 186 |
let eq_can = Sections.section_proof ["f'";"g'"] |
| 187 |
`cancel f f' ==> (!x. f x = g x) ==> (!x. f' x = g' x) ==> cancel g g'` |
| 188 |
[ |
| 189 |
(((repeat_tactic 1 9 (((use_arg_then2 ("eq_ext", [eq_ext]))(thm_tac (new_rewrite [] []))))) THEN (move ["can"]) THEN (((conv_thm_tac DISCH_THEN)(gsym_then (thm_tac (new_rewrite [] []))))) THEN (((conv_thm_tac DISCH_THEN)(gsym_then (thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 190 |
];; |
| 191 |
|
| 192 |
(* Lemma inj_can_eq *) |
| 193 |
let inj_can_eq = Sections.section_proof ["f'"] |
| 194 |
`cancel f f' ==> injective f' ==> cancel g f' ==> f = g` |
| 195 |
[ |
| 196 |
((((repeat_tactic 2 0 (((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("injective", [injective]))(thm_tac (new_rewrite [] []))))) THEN (move ["f_can"]) THEN (move ["inj"]) THEN (move ["g_can"])) THEN ((((use_arg_then2 ("eq_ext", [eq_ext]))(gsym_then (thm_tac (new_rewrite [] []))))) THEN (move ["x"]))); |
| 197 |
((((use_arg_then2 ("inj", [])) (disch_tac [])) THEN (clear_assumption "inj") THEN (DISCH_THEN apply_tac)) THEN (done_tac)); |
| 198 |
];; |
| 199 |
|
| 200 |
(* Finalization of the section InjectionsTheory *) |
| 201 |
let inj_id = Sections.finalize_theorem inj_id;; |
| 202 |
let inj_can_sym = Sections.finalize_theorem inj_can_sym;; |
| 203 |
let inj_comp = Sections.finalize_theorem inj_comp;; |
| 204 |
let can_comp = Sections.finalize_theorem can_comp;; |
| 205 |
let pcan_pcomp = Sections.finalize_theorem pcan_pcomp;; |
| 206 |
let eq_inj = Sections.finalize_theorem eq_inj;; |
| 207 |
let eq_can = Sections.finalize_theorem eq_can;; |
| 208 |
let inj_can_eq = Sections.finalize_theorem inj_can_eq;; |
| 209 |
Sections.end_section "InjectionsTheory";; |
| 210 |
|
| 211 |
(* Section Bijections *) |
| 212 |
Sections.begin_section "Bijections";; |
| 213 |
(Sections.add_section_var (mk_var ("f", (`:B -> A`))));; |
| 214 |
let bijective = new_definition `bijective f <=> ?g. cancel f g /\ cancel g f`;; |
| 215 |
(Sections.add_section_hyp "bijf" (`bijective f`));; |
| 216 |
|
| 217 |
(* Lemma bij_inj *) |
| 218 |
let bij_inj = Sections.section_proof [] |
| 219 |
`injective f` |
| 220 |
[ |
| 221 |
((((use_arg_then2 ("bijf", [])) (disch_tac [])) THEN (clear_assumption "bijf") THEN BETA_TAC) THEN ((((use_arg_then2 ("bijective", [bijective]))(thm_tac (new_rewrite [] [])))) THEN ALL_TAC THEN (case THEN (move ["g"])) THEN (case THEN ((DISCH_THEN (fun snd_th -> (use_arg_then2 ("can_inj", [can_inj])) (thm_tac (match_mp_then snd_th MP_TAC)))) THEN (((conv_thm_tac DISCH_THEN)(thm_tac (new_rewrite [] []))))))) THEN (done_tac)); |
| 222 |
];; |
| 223 |
|
| 224 |
(* Lemma bij_can_sym *) |
| 225 |
let bij_can_sym = Sections.section_proof ["f'"] |
| 226 |
`cancel f' f <=> cancel f f'` |
| 227 |
[ |
| 228 |
((THENL_FIRST) (split_tac) (((DISCH_THEN (fun snd_th -> (use_arg_then2 ("inj_can_sym", [inj_can_sym])) (thm_tac (match_mp_then snd_th MP_TAC)))) THEN BETA_TAC THEN ((fun arg_tac -> (conv_thm_tac DISCH_THEN) (fun fst_arg -> (use_arg_then2 ("bij_inj", [bij_inj])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (thm_tac MP_TAC))) THEN (done_tac))); |
| 229 |
((((use_arg_then2 ("bijf", [])) (disch_tac [])) THEN (clear_assumption "bijf") THEN BETA_TAC) THEN ((((use_arg_then2 ("bijective", [bijective]))(thm_tac (new_rewrite [] [])))) THEN ALL_TAC THEN (case THEN (move ["g"])) THEN (case THEN ALL_TAC)) THEN ((repeat_tactic 1 9 (((use_arg_then2 ("cancel", [cancel]))(thm_tac (new_rewrite [] []))))) THEN (move ["gf"]) THEN (move ["fg"]) THEN (move ["f'f"]) THEN (move ["x"]))); |
| 230 |
(((((fun arg_tac -> (use_arg_then2 ("fg", [])) (fun fst_arg -> (use_arg_then2 ("x", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg)))(gsym_then (thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("f'f", []))(thm_tac (new_rewrite [] []))))) THEN (done_tac)); |
| 231 |
];; |
| 232 |
|
| 233 |
(* Lemma bij_can_eq *) |
| 234 |
let bij_can_eq = Sections.section_proof ["f'";"f''"] |
| 235 |
`cancel f f' ==> cancel f f'' ==> f' = f''` |
| 236 |
[ |
| 237 |
(((((fun arg_tac -> (use_arg_then2 ("bij_can_sym", [bij_can_sym])) (fun fst_arg -> (use_arg_then2 ("f''", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg)))(gsym_then (thm_tac (new_rewrite [] []))))) THEN (((use_arg_then2 ("bij_can_sym", [bij_can_sym]))(gsym_then (thm_tac (new_rewrite [] [])))))) THEN (move ["can1"]) THEN (move ["can2"])); |
| 238 |
((((fun arg_tac -> (fun arg_tac -> (fun arg_tac -> (use_arg_then2 ("inj_can_eq", [inj_can_eq])) (fun fst_arg -> (use_arg_then2 ("can1", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("bij_inj", [bij_inj])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("can2", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (disch_tac [])) THEN BETA_TAC) THEN (done_tac)); |
| 239 |
];; |
| 240 |
|
| 241 |
(* Finalization of the section Bijections *) |
| 242 |
let bij_inj = Sections.finalize_theorem bij_inj;; |
| 243 |
let bij_can_sym = Sections.finalize_theorem bij_can_sym;; |
| 244 |
let bij_can_eq = Sections.finalize_theorem bij_can_eq;; |
| 245 |
Sections.end_section "Bijections";; |
| 246 |
|
| 247 |
(* Section BijectionsTheory *) |
| 248 |
Sections.begin_section "BijectionsTheory";; |
| 249 |
(Sections.add_section_var (mk_var ("f", (`:BB -> AA`))));; |
| 250 |
(Sections.add_section_var (mk_var ("h", (`:CC -> BB`))));; |
| 251 |
|
| 252 |
(* Lemma eq_bij *) |
| 253 |
let eq_bij = Sections.section_proof [] |
| 254 |
`bijective f ==> !g. (!x. f x = g x) ==> bijective g` |
| 255 |
[ |
| 256 |
(((((use_arg_then2 ("eq_ext", [eq_ext]))(thm_tac (new_rewrite [] [])))) THEN (move ["bij"]) THEN (move ["g"]) THEN (((conv_thm_tac DISCH_THEN)(gsym_then (thm_tac (new_rewrite [] [])))))) THEN (done_tac)); |
| 257 |
];; |
| 258 |
|
| 259 |
(* Lemma bij_comp *) |
| 260 |
let bij_comp = Sections.section_proof [] |
| 261 |
`bijective f ==> bijective h ==> bijective (f o h)` |
| 262 |
[ |
| 263 |
((repeat_tactic 3 0 (((use_arg_then2 ("bijective", [bijective]))(thm_tac (new_rewrite [] []))))) THEN ALL_TAC THEN (case THEN (move ["g"])) THEN (case THEN ((move ["can_fg"]) THEN (move ["can_gf"]))) THEN (case THEN ((move ["r"]) THEN (case THEN ((move ["can_hr"]) THEN (move ["can_rh"])))))); |
| 264 |
(((fun arg_tac -> arg_tac (Arg_term (`r o g`))) (term_tac exists_tac)) THEN (split_tac)); |
| 265 |
(((fun arg_tac -> (fun arg_tac -> (fun arg_tac -> (fun arg_tac -> (use_arg_then2 ("can_comp", [can_comp])) (fun fst_arg -> (use_arg_then2 ("f", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("h", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("g", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("r", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (disch_tac [])) THEN BETA_TAC); |
| 266 |
((((fun arg_tac -> (conv_thm_tac DISCH_THEN) (fun fst_arg -> (use_arg_then2 ("can_fg", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (thm_tac MP_TAC)) THEN BETA_TAC) THEN (DISCH_THEN apply_tac) THEN (done_tac)); |
| 267 |
(((fun arg_tac -> (fun arg_tac -> (fun arg_tac -> (fun arg_tac -> (use_arg_then2 ("can_comp", [can_comp])) (fun fst_arg -> (use_arg_then2 ("r", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("g", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("h", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (fun fst_arg -> (use_arg_then2 ("f", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (disch_tac [])) THEN BETA_TAC); |
| 268 |
((((fun arg_tac -> (conv_thm_tac DISCH_THEN) (fun fst_arg -> (use_arg_then2 ("can_rh", [])) (fun snd_arg -> combine_args_then arg_tac fst_arg snd_arg))) (thm_tac MP_TAC)) THEN BETA_TAC) THEN (DISCH_THEN apply_tac) THEN (done_tac)); |
| 269 |
];; |
| 270 |
|
| 271 |
(* Lemma bij_can_bij *) |
| 272 |
let bij_can_bij = Sections.section_proof [] |
| 273 |
`bijective f ==> !f'. cancel f f' ==> bijective f'` |
| 274 |
[ |
| 275 |
(((DISCH_THEN (fun snd_th -> (use_arg_then2 ("bij_can_sym", [bij_can_sym])) (thm_tac (match_mp_then snd_th MP_TAC)))) THEN BETA_TAC THEN (move ["can_sym"]) THEN (move ["f'"]) THEN (move ["can_ff'"])) THEN (((use_arg_then2 ("bijective", [bijective]))(thm_tac (new_rewrite [] []))))); |
| 276 |
(((use_arg_then2 ("f", [])) (term_tac exists_tac)) THEN (((use_arg_then2 ("can_sym", []))(thm_tac (new_rewrite [] [])))) THEN (done_tac)); |
| 277 |
];; |
| 278 |
|
| 279 |
(* Finalization of the section BijectionsTheory *) |
| 280 |
let eq_bij = Sections.finalize_theorem eq_bij;; |
| 281 |
let bij_comp = Sections.finalize_theorem bij_comp;; |
| 282 |
let bij_can_bij = Sections.finalize_theorem bij_can_bij;; |
| 283 |
Sections.end_section "BijectionsTheory";; |
| 284 |
|
| 285 |
(* Section Involutions *) |
| 286 |
Sections.begin_section "Involutions";; |
| 287 |
(Sections.add_section_var (mk_var ("f", (`:A -> A`))));; |
| 288 |
let involutive = new_definition `involutive f <=> cancel f f`;; |
| 289 |
(Sections.add_section_hyp "Hf" (`involutive f`));; |
| 290 |
|
| 291 |
(* Lemma inv_inj *) |
| 292 |
let inv_inj = Sections.section_proof [] |
| 293 |
`injective f` |
| 294 |
[ |
| 295 |
((((use_arg_then2 ("Hf", [])) (disch_tac [])) THEN (clear_assumption "Hf") THEN BETA_TAC) THEN ((((use_arg_then2 ("involutive", [involutive]))(thm_tac (new_rewrite [] [])))) THEN (DISCH_THEN (fun snd_th -> (use_arg_then2 ("can_inj", [can_inj])) (thm_tac (match_mp_then snd_th MP_TAC))))) THEN (done_tac)); |
| 296 |
];; |
| 297 |
|
| 298 |
(* Lemma inv_bij *) |
| 299 |
let inv_bij = Sections.section_proof [] |
| 300 |
`bijective f` |
| 301 |
[ |
| 302 |
((((use_arg_then2 ("bijective", [bijective]))(thm_tac (new_rewrite [] [])))) THEN ((use_arg_then2 ("f", [])) (term_tac exists_tac)) THEN (((use_arg_then2 ("Hf", [])) (disch_tac [])) THEN (clear_assumption "Hf") THEN BETA_TAC) THEN (((use_arg_then2 ("involutive", [involutive]))(thm_tac (new_rewrite [] [])))) THEN (done_tac)); |
| 303 |
];; |
| 304 |
|
| 305 |
(* Finalization of the section Involutions *) |
| 306 |
let inv_inj = Sections.finalize_theorem inv_inj;; |
| 307 |
let inv_bij = Sections.finalize_theorem inv_bij;; |
| 308 |
Sections.end_section "Involutions";; |
| 309 |
|
| 310 |
(* Section OperationProperties *) |
| 311 |
Sections.begin_section "OperationProperties";; |
| 312 |
|
| 313 |
(* Section SopTisR *) |
| 314 |
Sections.begin_section "SopTisR";; |
| 315 |
let left_inverse = new_definition `left_inverse e inv op = !x. op (inv x) x = e`;; |
| 316 |
let right_inverse = new_definition `right_inverse e inv op = !x. op x (inv x) = e`;; |
| 317 |
let left_injective = new_definition `left_injective op = !x. injective (\y. op y x)`;; |
| 318 |
let right_injective = new_definition `right_injective op = !y. injective (op y)`;; |
| 319 |
|
| 320 |
(* Finalization of the section SopTisR *) |
| 321 |
Sections.end_section "SopTisR";; |
| 322 |
|
| 323 |
(* Section SopTisS *) |
| 324 |
Sections.begin_section "SopTisS";; |
| 325 |
let right_id = new_definition `right_id e op = !x. op x e = x`;; |
| 326 |
let left_zero = new_definition `left_zero z op = !x. op z x = z`;; |
| 327 |
let right_commutative = new_definition |
| 328 |
`right_commutative op = !x y z. op (op x y) z = op (op x z) y`;; |
| 329 |
let left_distributive = new_definition |
| 330 |
`left_distributive op add = !x y z. op (add x y) z = add (op x z) (op y z)`;; |
| 331 |
let right_loop = new_definition |
| 332 |
`right_loop inv op = !y. cancel (\x. op x y) (\x. op x (inv y))`;; |
| 333 |
let rev_right_loop = new_definition |
| 334 |
`rev_right_loop inv op = !y. cancel (\x. op x (inv y)) (\x. op x y)`;; |
| 335 |
|
| 336 |
(* Finalization of the section SopTisS *) |
| 337 |
Sections.end_section "SopTisS";; |
| 338 |
|
| 339 |
(* Section SopTisT *) |
| 340 |
Sections.begin_section "SopTisT";; |
| 341 |
let left_id = new_definition `left_id e op = !x. op e x = x`;; |
| 342 |
let right_zero = new_definition `right_zero z op = !x. op x z = z`;; |
| 343 |
let left_commutative = new_definition |
| 344 |
`left_commutative op = !x y z. op x (op y z) = op y (op x z)`;; |
| 345 |
let right_distributive = new_definition |
| 346 |
`right_distributive op add = !x y z. op x (add y z) = add (op x y) (op x z)`;; |
| 347 |
let left_loop = new_definition |
| 348 |
`left_loop inv op = !x. cancel (op x) (op (inv x))`;; |
| 349 |
let rev_left_loop = new_definition |
| 350 |
`rev_left_loop inv op = !x. cancel (op (inv x)) (op x)`;; |
| 351 |
|
| 352 |
(* Finalization of the section SopTisT *) |
| 353 |
Sections.end_section "SopTisT";; |
| 354 |
|
| 355 |
(* Section SopSisT *) |
| 356 |
Sections.begin_section "SopSisT";; |
| 357 |
let self_inverse = new_definition `self_inverse e op = !x. op x x = e`;; |
| 358 |
let commutative = new_definition `commutative op = !x y. op x y = op y x`;; |
| 359 |
|
| 360 |
(* Finalization of the section SopSisT *) |
| 361 |
Sections.end_section "SopSisT";; |
| 362 |
|
| 363 |
(* Section SopSisS *) |
| 364 |
Sections.begin_section "SopSisS";; |
| 365 |
let idempotent = new_definition `idempotent op = !x. op x x = x`;; |
| 366 |
let associative = new_definition `associative op = !x y z. op x (op y z) = op (op x y) z`;; |
| 367 |
|
| 368 |
(* Finalization of the section SopSisS *) |
| 369 |
Sections.end_section "SopSisS";; |
| 370 |
|
| 371 |
(* Finalization of the section OperationProperties *) |
| 372 |
Sections.end_section "OperationProperties";; |
| 373 |
|
| 374 |
(* Close the module *) |
| 375 |
end;; |