src/HOL/Fun.ML
changeset 4089 96fba19bcbe2
parent 4059 59c1422c9da5
child 4656 134d24ddaad3
equal deleted inserted replaced
4088:9be9e39fd862 4089:96fba19bcbe2
    21 
    21 
    22 (*** inj(f): f is a one-to-one function ***)
    22 (*** inj(f): f is a one-to-one function ***)
    23 
    23 
    24 val prems = goalw Fun.thy [inj_def]
    24 val prems = goalw Fun.thy [inj_def]
    25     "[| !! x y. f(x) = f(y) ==> x=y |] ==> inj(f)";
    25     "[| !! x y. f(x) = f(y) ==> x=y |] ==> inj(f)";
    26 by (blast_tac (!claset addIs prems) 1);
    26 by (blast_tac (claset() addIs prems) 1);
    27 qed "injI";
    27 qed "injI";
    28 
    28 
    29 val [major] = goal Fun.thy "(!!x. g(f(x)) = x) ==> inj(f)";
    29 val [major] = goal Fun.thy "(!!x. g(f(x)) = x) ==> inj(f)";
    30 by (rtac injI 1);
    30 by (rtac injI 1);
    31 by (etac (arg_cong RS box_equals) 1);
    31 by (etac (arg_cong RS box_equals) 1);
    67 
    67 
    68 (*** inj_onto f A: f is one-to-one over A ***)
    68 (*** inj_onto f A: f is one-to-one over A ***)
    69 
    69 
    70 val prems = goalw Fun.thy [inj_onto_def]
    70 val prems = goalw Fun.thy [inj_onto_def]
    71     "(!! x y. [| f(x) = f(y);  x:A;  y:A |] ==> x=y) ==> inj_onto f A";
    71     "(!! x y. [| f(x) = f(y);  x:A;  y:A |] ==> x=y) ==> inj_onto f A";
    72 by (blast_tac (!claset addIs prems) 1);
    72 by (blast_tac (claset() addIs prems) 1);
    73 qed "inj_ontoI";
    73 qed "inj_ontoI";
    74 
    74 
    75 val [major] = goal Fun.thy 
    75 val [major] = goal Fun.thy 
    76     "(!!x. x:A ==> g(f(x)) = x) ==> inj_onto f A";
    76     "(!!x. x:A ==> g(f(x)) = x) ==> inj_onto f A";
    77 by (rtac inj_ontoI 1);
    77 by (rtac inj_ontoI 1);
    84 by (rtac (major RS bspec RS bspec RS mp) 1);
    84 by (rtac (major RS bspec RS bspec RS mp) 1);
    85 by (REPEAT (resolve_tac prems 1));
    85 by (REPEAT (resolve_tac prems 1));
    86 qed "inj_ontoD";
    86 qed "inj_ontoD";
    87 
    87 
    88 goal Fun.thy "!!x y.[| inj_onto f A;  x:A;  y:A |] ==> (f(x)=f(y)) = (x=y)";
    88 goal Fun.thy "!!x y.[| inj_onto f A;  x:A;  y:A |] ==> (f(x)=f(y)) = (x=y)";
    89 by (blast_tac (!claset addSDs [inj_ontoD]) 1);
    89 by (blast_tac (claset() addSDs [inj_ontoD]) 1);
    90 qed "inj_onto_iff";
    90 qed "inj_onto_iff";
    91 
    91 
    92 val major::prems = goal Fun.thy
    92 val major::prems = goal Fun.thy
    93     "[| inj_onto f A;  ~x=y;  x:A;  y:A |] ==> ~ f(x)=f(y)";
    93     "[| inj_onto f A;  ~x=y;  x:A;  y:A |] ==> ~ f(x)=f(y)";
    94 by (rtac contrapos 1);
    94 by (rtac contrapos 1);
   104 
   104 
   105 (*** Lemmas about inj ***)
   105 (*** Lemmas about inj ***)
   106 
   106 
   107 goalw Fun.thy [o_def]
   107 goalw Fun.thy [o_def]
   108     "!!f g. [| inj(f);  inj_onto g (range f) |] ==> inj(g o f)";
   108     "!!f g. [| inj(f);  inj_onto g (range f) |] ==> inj(g o f)";
   109 by (fast_tac (!claset addIs [injI] addEs [injD, inj_ontoD]) 1);
   109 by (fast_tac (claset() addIs [injI] addEs [injD, inj_ontoD]) 1);
   110 qed "comp_inj";
   110 qed "comp_inj";
   111 
   111 
   112 val [prem] = goal Fun.thy "inj(f) ==> inj_onto f A";
   112 val [prem] = goal Fun.thy "inj(f) ==> inj_onto f A";
   113 by (blast_tac (!claset addIs [prem RS injD, inj_ontoI]) 1);
   113 by (blast_tac (claset() addIs [prem RS injD, inj_ontoI]) 1);
   114 qed "inj_imp";
   114 qed "inj_imp";
   115 
   115 
   116 val [prem] = goalw Fun.thy [inv_def] "y : range(f) ==> f(inv f y) = y";
   116 val [prem] = goalw Fun.thy [inv_def] "y : range(f) ==> f(inv f y) = y";
   117 by (EVERY1 [rtac (prem RS rangeE), rtac selectI, etac sym]);
   117 by (EVERY1 [rtac (prem RS rangeE), rtac selectI, etac sym]);
   118 qed "f_inv_f";
   118 qed "f_inv_f";
   122 by (rtac (arg_cong RS box_equals) 1);
   122 by (rtac (arg_cong RS box_equals) 1);
   123 by (REPEAT (resolve_tac (prems @ [f_inv_f]) 1));
   123 by (REPEAT (resolve_tac (prems @ [f_inv_f]) 1));
   124 qed "inv_injective";
   124 qed "inv_injective";
   125 
   125 
   126 goal Fun.thy "!!f. [| inj(f);  A<=range(f) |] ==> inj_onto (inv f) A";
   126 goal Fun.thy "!!f. [| inj(f);  A<=range(f) |] ==> inj_onto (inv f) A";
   127 by (fast_tac (!claset addIs [inj_ontoI] 
   127 by (fast_tac (claset() addIs [inj_ontoI] 
   128                       addEs [inv_injective,injD]) 1);
   128                       addEs [inv_injective,injD]) 1);
   129 qed "inj_onto_inv";
   129 qed "inj_onto_inv";
   130 
   130 
   131 goalw thy [inj_onto_def]
   131 goalw thy [inj_onto_def]
   132    "!!f. [| inj_onto f C;  A<=C;  B<=C |] ==> f``(A Int B) = f``A Int f``B";
   132    "!!f. [| inj_onto f C;  A<=C;  B<=C |] ==> f``(A Int B) = f``A Int f``B";
   145 goalw thy [inj_def] "!!f. inj f ==> f``(A-B) = f``A - f``B";
   145 goalw thy [inj_def] "!!f. inj f ==> f``(A-B) = f``A - f``B";
   146 by (Blast_tac 1);
   146 by (Blast_tac 1);
   147 qed "image_set_diff";
   147 qed "image_set_diff";
   148 
   148 
   149 
   149 
   150 val set_cs = !claset delrules [equalityI];
   150 val set_cs = claset() delrules [equalityI];