src/HOL/Fun.ML
author wenzelm
Thu, 27 Sep 2001 22:22:08 +0200
changeset 11601 9273cef990f5
parent 11459 1b6258b288ba
child 12338 de0f4a63baa5
permissions -rw-r--r--
added surjE;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1465
5d7a7e439cec expanded tabs
clasohm
parents: 1264
diff changeset
     1
(*  Title:      HOL/Fun
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1465
5d7a7e439cec expanded tabs
clasohm
parents: 1264
diff changeset
     3
    Author:     Tobias Nipkow, Cambridge University Computer Laboratory
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     4
    Copyright   1993  University of Cambridge
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     5
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     6
Lemmas about functions.
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     7
*)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     8
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
     9
Goal "(f = g) = (! x. f(x)=g(x))";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    10
by (rtac iffI 1);
1264
3eb91524b938 added local simpsets; removed IOA from 'make test'
clasohm
parents: 923
diff changeset
    11
by (Asm_simp_tac 1);
3eb91524b938 added local simpsets; removed IOA from 'make test'
clasohm
parents: 923
diff changeset
    12
by (rtac ext 1 THEN Asm_simp_tac 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    13
qed "expand_fun_eq";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    14
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    15
val prems = Goal
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    16
    "[| f(x)=u;  !!x. P(x) ==> g(f(x)) = x;  P(x) |] ==> x=g(u)";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    17
by (rtac (arg_cong RS box_equals) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    18
by (REPEAT (resolve_tac (prems@[refl]) 1));
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    19
qed "apply_inverse";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    20
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    21
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    22
section "id";
5441
45bd13b15d80 added Id_apply
oheimb
parents: 5318
diff changeset
    23
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    24
Goalw [id_def] "id x = x";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    25
by (rtac refl 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    26
qed "id_apply";
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    27
Addsimps [id_apply];
5441
45bd13b15d80 added Id_apply
oheimb
parents: 5318
diff changeset
    28
45bd13b15d80 added Id_apply
oheimb
parents: 5318
diff changeset
    29
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    30
section "o";
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    31
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    32
Goalw [o_def] "(f o g) x = f (g x)";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    33
by (rtac refl 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    34
qed "o_apply";
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    35
Addsimps [o_apply];
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    36
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    37
Goalw [o_def] "f o (g o h) = f o g o h";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    38
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    39
by (rtac refl 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    40
qed "o_assoc";
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    41
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    42
Goalw [id_def] "id o g = g";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    43
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    44
by (Simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    45
qed "id_o";
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    46
Addsimps [id_o];
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    47
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    48
Goalw [id_def] "f o id = f";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    49
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    50
by (Simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    51
qed "o_id";
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    52
Addsimps [o_id];
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    53
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
    54
Goalw [o_def] "(f o g)`r = f`(g`r)";
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    55
by (Blast_tac 1);
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    56
qed "image_compose";
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    57
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
    58
Goal "f`A = (UN x:A. {f x})";
7536
5c094aec523d new theorem image_image_eq_UN
paulson
parents: 7514
diff changeset
    59
by (Blast_tac 1);
7916
3cb310f40a3a replaced image_image_eq_UN by image_eq_UN
paulson
parents: 7876
diff changeset
    60
qed "image_eq_UN";
7536
5c094aec523d new theorem image_image_eq_UN
paulson
parents: 7514
diff changeset
    61
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
    62
Goalw [o_def] "UNION A (g o f) = UNION (f`A) g";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
    63
by (Blast_tac 1);
6829
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
    64
qed "UN_o";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
    65
7014
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    66
(** lemma for proving injectivity of representation functions for **)
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    67
(** datatypes involving function types                            **)
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    68
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    69
Goalw [o_def]
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    70
  "[| ! x y. g (f x) = g y --> f x = y; g o f = g o fa |] ==> f = fa";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    71
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    72
by (etac allE 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    73
by (etac allE 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    74
by (etac mp 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    75
by (etac fun_cong 1);
7014
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    76
qed "inj_fun_lemma";
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    77
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    78
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    79
section "inj";
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    80
(**NB: inj now just translates to inj_on**)
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    81
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    82
(*** inj(f): f is a one-to-one function ***)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    83
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    84
(*for Tools/datatype_rep_proofs*)
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    85
val [prem] = Goalw [inj_on_def]
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    86
    "(!! x. ALL y. f(x) = f(y) --> x=y) ==> inj(f)";
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    87
by (blast_tac (claset() addIs [prem RS spec RS mp]) 1);
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    88
qed "datatype_injI";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    89
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    90
Goalw [inj_on_def] "[| inj(f); f(x) = f(y) |] ==> x=y";
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    91
by (Blast_tac 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    92
qed "injD";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    93
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    94
(*Useful with the simplifier*)
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    95
Goal "inj(f) ==> (f(x) = f(y)) = (x=y)";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    96
by (rtac iffI 1);
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    97
by (etac arg_cong 2);
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    98
by (etac injD 1);
5318
72bf8039b53f expandshort
paulson
parents: 5316
diff changeset
    99
by (assume_tac 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   100
qed "inj_eq";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   101
7014
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   102
Goalw [o_def] "[| inj f; f o g = f o h |] ==> g = h";
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   103
by (rtac ext 1);
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   104
by (etac injD 1);
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   105
by (etac fun_cong 1);
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   106
qed "inj_o";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   107
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   108
(*** inj_on f A: f is one-to-one over A ***)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   109
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   110
val prems = Goalw [inj_on_def]
11395
2eeaa1077b73 better treatment of restrict (lam)
paulson
parents: 10832
diff changeset
   111
    "(!! x y. [|  x:A;  y:A;  f(x) = f(y) |] ==> x=y) ==> inj_on f A";
4089
96fba19bcbe2 isatool fixclasimp;
wenzelm
parents: 4059
diff changeset
   112
by (blast_tac (claset() addIs prems) 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   113
qed "inj_onI";
9108
9fff97d29837 bind_thm(s);
wenzelm
parents: 8767
diff changeset
   114
bind_thm ("injI", inj_onI);                  (*for compatibility*)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   115
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   116
val [major] = Goal 
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   117
    "(!!x. x:A ==> g(f(x)) = x) ==> inj_on f A";
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   118
by (rtac inj_onI 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   119
by (etac (apply_inverse RS trans) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   120
by (REPEAT (eresolve_tac [asm_rl,major] 1));
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   121
qed "inj_on_inverseI";
9108
9fff97d29837 bind_thm(s);
wenzelm
parents: 8767
diff changeset
   122
bind_thm ("inj_inverseI", inj_on_inverseI);   (*for compatibility*)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   123
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   124
Goalw [inj_on_def] "[| inj_on f A;  f(x)=f(y);  x:A;  y:A |] ==> x=y";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   125
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   126
qed "inj_onD";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   127
5143
b94cd208f073 Removal of leading "\!\!..." from most Goal commands
paulson
parents: 5069
diff changeset
   128
Goal "[| inj_on f A;  x:A;  y:A |] ==> (f(x)=f(y)) = (x=y)";
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   129
by (blast_tac (claset() addSDs [inj_onD]) 1);
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   130
qed "inj_on_iff";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   131
11459
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   132
Goalw [o_def, inj_on_def]
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   133
     "[| inj_on f A;  inj_on g (f`A) |] ==> inj_on (g o f) A";
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   134
by (Blast_tac 1);
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   135
qed "comp_inj_on";
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   136
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   137
Goalw [inj_on_def] "[| inj_on f A;  ~x=y;  x:A;  y:A |] ==> ~ f(x)=f(y)";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   138
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   139
qed "inj_on_contraD";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   140
8156
33d23d0a300e added inj_singleton
oheimb
parents: 8138
diff changeset
   141
Goal "inj (%s. {s})";
8253
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   142
by (rtac injI 1);
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   143
by (etac singleton_inject 1);
8156
33d23d0a300e added inj_singleton
oheimb
parents: 8138
diff changeset
   144
qed "inj_singleton";
33d23d0a300e added inj_singleton
oheimb
parents: 8138
diff changeset
   145
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   146
Goalw [inj_on_def] "[| A<=B; inj_on f B |] ==> inj_on f A";
3341
89fe22bf9f54 New theorem subset_inj_onto
paulson
parents: 2935
diff changeset
   147
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   148
qed "subset_inj_on";
3341
89fe22bf9f54 New theorem subset_inj_onto
paulson
parents: 2935
diff changeset
   149
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   150
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   151
(** surj **)
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   152
6267
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   153
val [prem] = Goalw [surj_def] "(!! x. g(f x) = x) ==> surj g";
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   154
by (blast_tac (claset() addIs [prem RS sym]) 1);
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   155
qed "surjI";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   156
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   157
Goalw [surj_def] "surj f ==> range f = UNIV";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   158
by Auto_tac;
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   159
qed "surj_range";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   160
6267
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   161
Goalw [surj_def] "surj f ==> EX x. y = f x";
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   162
by (Blast_tac 1);
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   163
qed "surjD";
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   164
11601
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   165
val [p1, p2] = Goal "surj f ==> (!!x. y = f x ==> C) ==> C";
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   166
by (cut_facts_tac [p1 RS surjD] 1);
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   167
by (etac exE 1);
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   168
by (rtac p2 1);
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   169
by (atac 1);
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   170
qed "surjE";
9273cef990f5 added surjE;
wenzelm
parents: 11459
diff changeset
   171
11459
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   172
Goalw [o_def, surj_def] "[| surj f;  surj g |] ==> surj (g o f)";
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   173
by (Clarify_tac 1); 
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   174
by (dres_inst_tac [("x","y")] spec 1); 
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   175
by (Clarify_tac 1); 
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   176
by (dres_inst_tac [("x","x")] spec 1); 
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   177
by (Blast_tac 1); 
1b6258b288ba new result comp_surj
paulson
parents: 11451
diff changeset
   178
qed "comp_surj";
10066
2f5686cf8c9a new theorems and comment
paulson
parents: 9970
diff changeset
   179
8253
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   180
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   181
(** Bijections **)
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   182
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   183
Goalw [bij_def] "[| inj f; surj f |] ==> bij f";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   184
by (Blast_tac 1);
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   185
qed "bijI";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   186
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   187
Goalw [bij_def] "bij f ==> inj f";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   188
by (Blast_tac 1);
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   189
qed "bij_is_inj";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   190
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   191
Goalw [bij_def] "bij f ==> surj f";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   192
by (Blast_tac 1);
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   193
qed "bij_is_surj";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   194
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   195
7514
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   196
(** We seem to need both the id-forms and the (%x. x) forms; the latter can
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   197
    arise by rewriting, while id may be used explicitly. **)
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   198
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   199
Goal "(%x. x) ` Y = Y";
7514
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   200
by (Blast_tac 1);
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   201
qed "image_ident";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   202
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   203
Goalw [id_def] "id ` Y = Y";
7514
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   204
by (Blast_tac 1);
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   205
qed "image_id";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   206
Addsimps [image_ident, image_id];
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   207
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   208
Goal "(%x. x) -` Y = Y";
7514
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   209
by (Blast_tac 1);
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   210
qed "vimage_ident";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   211
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   212
Goalw [id_def] "id -` A = A";
7514
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   213
by Auto_tac;
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   214
qed "vimage_id";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   215
Addsimps [vimage_ident, vimage_id];
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   216
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   217
Goal "f -` (f ` A) = {y. EX x:A. f x = f y}";
7876
1b3b683c092e new thm vimage_image_eq
paulson
parents: 7536
diff changeset
   218
by (blast_tac (claset() addIs [sym]) 1);
1b3b683c092e new thm vimage_image_eq
paulson
parents: 7536
diff changeset
   219
qed "vimage_image_eq";
1b3b683c092e new thm vimage_image_eq
paulson
parents: 7536
diff changeset
   220
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   221
Goal "f ` (f -` A) <= A";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   222
by (Blast_tac 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   223
qed "image_vimage_subset";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   224
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   225
Goal "f ` (f -` A) = A Int range f";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   226
by (Blast_tac 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   227
qed "image_vimage_eq";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   228
Addsimps [image_vimage_eq];
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   229
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   230
Goal "surj f ==> f ` (f -` A) = A";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   231
by (asm_simp_tac (simpset() addsimps [surj_range]) 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   232
qed "surj_image_vimage_eq";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   233
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   234
Goalw [inj_on_def] "inj f ==> f -` (f ` A) = A";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   235
by (Blast_tac 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   236
qed "inj_vimage_image_eq";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   237
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   238
Goalw [surj_def] "surj f ==> f -` B <= A ==> B <= f ` A";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   239
by (blast_tac (claset() addIs [sym]) 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   240
qed "vimage_subsetD";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   241
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   242
Goalw [inj_on_def] "inj f ==> B <= f ` A ==> f -` B <= A";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   243
by (Blast_tac 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   244
qed "vimage_subsetI";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   245
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   246
Goalw [bij_def] "bij f ==> (f -` B <= A) = (B <= f ` A)";
8173
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   247
by (blast_tac (claset() delrules [subsetI]
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   248
			addIs [vimage_subsetI, vimage_subsetD]) 1);
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   249
qed "vimage_subset_eq";
a9966d5ab84d various theorems about image and inverse image
paulson
parents: 8156
diff changeset
   250
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   251
Goal "f`(A Int B) <= f`A Int f`B";
6290
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   252
by (Blast_tac 1);
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   253
qed "image_Int_subset";
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   254
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   255
Goal "f`A - f`B <= f`(A - B)";
6290
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   256
by (Blast_tac 1);
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   257
qed "image_diff_subset";
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   258
5069
3ea049f7979d isatool fixgoal;
wenzelm
parents: 4830
diff changeset
   259
Goalw [inj_on_def]
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   260
   "[| inj_on f C;  A<=C;  B<=C |] ==> f`(A Int B) = f`A Int f`B";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   261
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   262
qed "inj_on_image_Int";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   263
5069
3ea049f7979d isatool fixgoal;
wenzelm
parents: 4830
diff changeset
   264
Goalw [inj_on_def]
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   265
   "[| inj_on f C;  A<=C;  B<=C |] ==> f`(A-B) = f`A - f`B";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   266
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   267
qed "inj_on_image_set_diff";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   268
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   269
Goalw [inj_on_def] "inj f ==> f`(A Int B) = f`A Int f`B";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   270
by (Blast_tac 1);
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   271
qed "image_Int";
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   272
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   273
Goalw [inj_on_def] "inj f ==> f`(A-B) = f`A - f`B";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   274
by (Blast_tac 1);
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   275
qed "image_set_diff";
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   276
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   277
Goal "inj f ==> (f a : f`A) = (a : A)";
6301
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   278
by (blast_tac (claset() addDs [injD]) 1);
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   279
qed "inj_image_mem_iff";
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   280
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   281
Goalw [inj_on_def] "inj f ==> (f`A <= f`B) = (A<=B)";
8253
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   282
by (Blast_tac 1);
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   283
qed "inj_image_subset_iff";
975eb12aa040 many new theorems about inj, surj etc.
paulson
parents: 8226
diff changeset
   284
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   285
Goal "inj f ==> (f`A = f`B) = (A = B)";
6301
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   286
by (blast_tac (claset() addSEs [equalityE] addDs [injD]) 1);
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   287
qed "inj_image_eq_iff";
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   288
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   289
Goal  "(f ` (UNION A B)) = (UN x:A.(f ` (B x)))";
6829
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   290
by (Blast_tac 1);
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   291
qed "image_UN";
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   292
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   293
(*injectivity's required.  Left-to-right inclusion holds even if A is empty*)
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   294
Goalw [inj_on_def]
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   295
   "[| inj_on f C;  ALL x:A. B x <= C;  j:A |] \
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   296
\   ==> f ` (INTER A B) = (INT x:A. f ` B x)";
6829
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   297
by (Blast_tac 1);
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   298
qed "image_INT";
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   299
8309
a054d5c98b21 more bijection theorems
paulson
parents: 8285
diff changeset
   300
(*Compare with image_INT: no use of inj_on, and if f is surjective then
a054d5c98b21 more bijection theorems
paulson
parents: 8285
diff changeset
   301
  it doesn't matter whether A is empty*)
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   302
Goalw [bij_def] "bij f ==> f ` (INTER A B) = (INT x:A. f ` B x)";
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   303
by (asm_full_simp_tac (simpset() addsimps [inj_on_def, surj_def]) 1);
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   304
by (Blast_tac 1);  
8309
a054d5c98b21 more bijection theorems
paulson
parents: 8285
diff changeset
   305
qed "bij_image_INT";
a054d5c98b21 more bijection theorems
paulson
parents: 8285
diff changeset
   306
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   307
Goal "surj f ==> -(f`A) <= f`(-A)";
10076
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   308
by (auto_tac (claset(), simpset() addsimps [surj_def]));  
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   309
qed "surj_Compl_image_subset";
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   310
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   311
Goal "inj f ==> f`(-A) <= -(f`A)";
10076
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   312
by (auto_tac (claset(), simpset() addsimps [inj_on_def]));  
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   313
qed "inj_image_Compl_subset";
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   314
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   315
Goalw [bij_def] "bij f ==> f`(-A) = -(f`A)";
10076
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   316
by (rtac equalityI 1); 
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   317
by (ALLGOALS (asm_simp_tac (simpset() addsimps [inj_image_Compl_subset, 
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   318
                                                surj_Compl_image_subset]))); 
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   319
qed "bij_image_Compl_eq";
2683ff181047 removed the obsolete (and badly named) inj_select
paulson
parents: 10066
diff changeset
   320
4089
96fba19bcbe2 isatool fixclasimp;
wenzelm
parents: 4059
diff changeset
   321
val set_cs = claset() delrules [equalityI];
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   322
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   323
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   324
section "fun_upd";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   325
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   326
Goalw [fun_upd_def] "(f(x:=y) = f) = (f x = y)";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   327
by Safe_tac;
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   328
by (etac subst 1);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   329
by (rtac ext 2);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   330
by Auto_tac;
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   331
qed "fun_upd_idem_iff";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   332
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   333
(* f x = y ==> f(x:=y) = f *)
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   334
bind_thm("fun_upd_idem", fun_upd_idem_iff RS iffD2);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   335
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   336
(* f(x := f x) = f *)
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   337
AddIffs [refl RS fun_upd_idem];
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   338
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   339
Goal "(f(x:=y))z = (if z=x then y else f z)";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   340
by (simp_tac (simpset() addsimps [fun_upd_def]) 1);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   341
qed "fun_upd_apply";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   342
Addsimps [fun_upd_apply];
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   343
9339
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   344
(* fun_upd_apply supersedes these two,   but they are useful 
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   345
   if fun_upd_apply is intentionally removed from the simpset *)
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   346
Goal "(f(x:=y)) x = y";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   347
by (Simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   348
qed "fun_upd_same";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   349
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   350
Goal "z~=x ==> (f(x:=y)) z = f z";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   351
by (Asm_simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   352
qed "fun_upd_other";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   353
7445
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   354
Goal "f(x:=y,x:=z) = f(x:=z)";
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   355
by (rtac ext 1);
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   356
by (Simp_tac 1);
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   357
qed "fun_upd_upd";
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   358
Addsimps [fun_upd_upd];
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   359
9339
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   360
(* simplifies terms of the form f(...,x:=y,...,x:=z,...) to f(...,x:=z,...) *)
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   361
local 
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   362
  fun gen_fun_upd  None    T _ _ = None
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   363
  |   gen_fun_upd (Some f) T x y = Some (Const ("Fun.fun_upd",T) $ f $ x $ y)
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   364
  fun dest_fun_T1 (Type (_,T::Ts)) = T
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   365
  fun find_double (t as Const ("Fun.fun_upd",T) $ f $ x $ y) = let
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   366
      fun find         (Const ("Fun.fun_upd",T) $ g $ v $ w) = 
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   367
          if v aconv x then Some g else gen_fun_upd (find g) T v w
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   368
      |   find t = None
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   369
      in (dest_fun_T1 T, gen_fun_upd (find f) T x y) end
9422
4b6bc2b347e5 avoid referencing thy value;
wenzelm
parents: 9339
diff changeset
   370
  val ss = simpset ();
9339
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   371
  val fun_upd_prover = K [rtac eq_reflection 1, rtac ext 1, 
9422
4b6bc2b347e5 avoid referencing thy value;
wenzelm
parents: 9339
diff changeset
   372
                          simp_tac ss 1]
9339
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   373
  fun mk_eq_cterm sg T l r = Thm.cterm_of sg (equals T $ l $ r)
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   374
in 
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   375
  val fun_upd2_simproc = Simplifier.mk_simproc "fun_upd2"
9422
4b6bc2b347e5 avoid referencing thy value;
wenzelm
parents: 9339
diff changeset
   376
   [Thm.read_cterm (sign_of (the_context ())) ("f(v:=w,x:=y)", HOLogic.termT)]
9339
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   377
   (fn sg => (K (fn t => case find_double t of (T,None)=> None | (T,Some rhs)=> 
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   378
       Some (prove_goalw_cterm [] (mk_eq_cterm sg T t rhs) fun_upd_prover))))
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   379
end;
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   380
Addsimprocs[fun_upd2_simproc];
0d8b0eb2932d added fun_upd2_simproc
oheimb
parents: 9108
diff changeset
   381
8258
666d3a4f3b9d changed precedence of function update
oheimb
parents: 8253
diff changeset
   382
Goal "a ~= c ==> (m(a:=b))(c:=d) = (m(c:=d))(a:=b)";
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   383
by (rtac ext 1);
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   384
by Auto_tac;
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   385
qed "fun_upd_twist";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   386
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   387
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   388
(*** -> and Pi, by Florian Kammueller and LCP ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   389
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   390
val prems = Goalw [Pi_def]
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   391
"[| !!x. x: A ==> f x: B x; !!x. x ~: A  ==> f(x) = arbitrary|] \
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   392
\    ==> f: Pi A B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   393
by (auto_tac (claset(), simpset() addsimps prems));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   394
qed "Pi_I";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   395
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   396
val prems = Goal 
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   397
"[| !!x. x: A ==> f x: B; !!x. x ~: A  ==> f(x) = arbitrary|] ==> f: A funcset B";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   398
by (blast_tac (claset() addIs Pi_I::prems) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   399
qed "funcsetI";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   400
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   401
Goalw [Pi_def] "[|f: Pi A B; x: A|] ==> f x: B x";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   402
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   403
qed "Pi_mem";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   404
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   405
Goalw [Pi_def] "[|f: A funcset B; x: A|] ==> f x: B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   406
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   407
qed "funcset_mem";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   408
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   409
Goalw [Pi_def] "[|f: Pi A B; x~: A|] ==> f x = arbitrary";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   410
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   411
qed "apply_arb";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   412
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   413
Goalw [Pi_def] "[| f: Pi A B; g: Pi A B; ! x: A. f x = g x |] ==> f = g";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   414
by (rtac ext 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   415
by Auto_tac;
9108
9fff97d29837 bind_thm(s);
wenzelm
parents: 8767
diff changeset
   416
bind_thm ("Pi_extensionality", ballI RSN (3, result()));
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   417
8138
1e4cb069b19d new theorem inj_on_restrict_eq
paulson
parents: 8081
diff changeset
   418
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   419
(*** compose ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   420
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   421
Goalw [Pi_def, compose_def, restrict_def]
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   422
     "[| f: A funcset B; g: B funcset C |]==> compose A g f: A funcset C";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   423
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   424
qed "funcset_compose";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   425
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   426
Goal "[| f: A funcset B; g: B funcset C; h: C funcset D |]\
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   427
\     ==> compose A h (compose A g f) = compose A (compose B h g) f";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   428
by (res_inst_tac [("A","A")] Pi_extensionality 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   429
by (blast_tac (claset() addIs [funcset_compose]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   430
by (blast_tac (claset() addIs [funcset_compose]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   431
by (rewrite_goals_tac [Pi_def, compose_def, restrict_def]);  
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   432
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   433
qed "compose_assoc";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   434
11446
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   435
Goal "x : A ==> compose A g f x = g(f(x))";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   436
by (asm_simp_tac (simpset() addsimps [compose_def, restrict_def]) 1);
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   437
qed "compose_eq";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   438
11446
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   439
Goal "[| f ` A = B; g ` B = C |] ==> compose A g f ` A = C";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   440
by (auto_tac (claset(), simpset() addsimps [image_def, compose_eq]));
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   441
qed "surj_compose";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   442
11446
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   443
Goal "[| f ` A = B; inj_on f A; inj_on g B |] ==> inj_on (compose A g f) A";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   444
by (auto_tac (claset(), simpset() addsimps [inj_on_def, compose_eq]));
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   445
qed "inj_on_compose";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   446
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   447
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   448
(*** restrict / lam ***)
8138
1e4cb069b19d new theorem inj_on_restrict_eq
paulson
parents: 8081
diff changeset
   449
10832
e33b47e4246d `` -> and ``` -> ``
nipkow
parents: 10826
diff changeset
   450
Goal "f`A <= B ==> (lam x: A. f x) : A funcset B";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   451
by (auto_tac (claset(),
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   452
	      simpset() addsimps [restrict_def, Pi_def]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   453
qed "restrict_in_funcset";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   454
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   455
val prems = Goalw [restrict_def, Pi_def]
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   456
     "(!!x. x: A ==> f x: B x) ==> (lam x: A. f x) : Pi A B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   457
by (asm_simp_tac (simpset() addsimps prems) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   458
qed "restrictI";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   459
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   460
Goal "(lam y: A. f y) x = (if x : A then f x else arbitrary)";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   461
by (asm_simp_tac (simpset() addsimps [restrict_def]) 1);
11395
2eeaa1077b73 better treatment of restrict (lam)
paulson
parents: 10832
diff changeset
   462
qed "restrict_apply";
2eeaa1077b73 better treatment of restrict (lam)
paulson
parents: 10832
diff changeset
   463
Addsimps [restrict_apply];
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   464
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   465
val prems = Goal
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   466
    "(!!x. x: A ==> f x = g x) ==> (lam x: A. f x) = (lam x: A. g x)";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   467
by (rtac ext 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   468
by (auto_tac (claset(),
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   469
	      simpset() addsimps prems@[restrict_def, Pi_def]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   470
qed "restrict_ext";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   471
8138
1e4cb069b19d new theorem inj_on_restrict_eq
paulson
parents: 8081
diff changeset
   472
Goalw [inj_on_def, restrict_def] "inj_on (restrict f A) A = inj_on f A";
1e4cb069b19d new theorem inj_on_restrict_eq
paulson
parents: 8081
diff changeset
   473
by Auto_tac;
1e4cb069b19d new theorem inj_on_restrict_eq
paulson
parents: 8081
diff changeset
   474
qed "inj_on_restrict_eq";
1e4cb069b19d new theorem inj_on_restrict_eq
paulson
parents: 8081
diff changeset
   475
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   476
11446
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   477
Goal "f : A funcset B ==> compose A (lam y:B. y) f = f";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   478
by (rtac ext 1); 
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   479
by (auto_tac (claset(), simpset() addsimps [compose_def, Pi_def])); 
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   480
qed "Id_compose";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   481
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   482
Goal "g : A funcset B ==> compose A g (lam x:A. x) = g";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   483
by (rtac ext 1); 
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   484
by (auto_tac (claset(), simpset() addsimps [compose_def, Pi_def])); 
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   485
qed "compose_Id";
882d6b54cebf improved version of the Pi-theorems
paulson
parents: 11395
diff changeset
   486
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   487
10826
f3b7201dda27 Removed Applyall
nipkow
parents: 10076
diff changeset
   488
(*** Pi ***)
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   489
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   490
Goalw [Pi_def] "[| B(x) = {};  x: A |] ==> (PI x: A. B x) = {}";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   491
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   492
qed "Pi_eq_empty";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   493
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   494
Goal "[| (PI x: A. B x) ~= {};  x: A |] ==> B(x) ~= {}";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   495
by (blast_tac (HOL_cs addIs [Pi_eq_empty]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   496
qed "Pi_total1";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   497
11451
8abfb4f7bd02 partial restructuring to reduce dependence on Axiom of Choice
paulson
parents: 11446
diff changeset
   498
Goal "Pi {} B = { %x. arbitrary }";
5865
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   499
by (auto_tac (claset() addIs [ext], simpset() addsimps [Pi_def]));
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   500
qed "Pi_empty";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   501
5865
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   502
val [major] = Goalw [Pi_def] "(!!x. x: A ==> B x <= C x) ==> Pi A B <= Pi A C";
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   503
by (auto_tac (claset(),
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   504
	      simpset() addsimps [impOfSubs major]));
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   505
qed "Pi_mono";