src/HOL/Fun.ML
author paulson
Fri, 10 Sep 1999 18:37:04 +0200
changeset 7536 5c094aec523d
parent 7514 3235863a069a
child 7876 1b3b683c092e
permissions -rw-r--r--
new theorem image_image_eq_UN
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
4656
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
     9
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    10
Goal "(f = g) = (! x. f(x)=g(x))";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    11
by (rtac iffI 1);
1264
3eb91524b938 added local simpsets; removed IOA from 'make test'
clasohm
parents: 923
diff changeset
    12
by (Asm_simp_tac 1);
3eb91524b938 added local simpsets; removed IOA from 'make test'
clasohm
parents: 923
diff changeset
    13
by (rtac ext 1 THEN Asm_simp_tac 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    14
qed "expand_fun_eq";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    15
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    16
val prems = Goal
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    17
    "[| 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
    18
by (rtac (arg_cong RS box_equals) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    19
by (REPEAT (resolve_tac (prems@[refl]) 1));
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    20
qed "apply_inverse";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    21
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    22
4656
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    23
(** "Axiom" of Choice, proved using the description operator **)
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    24
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    25
Goal "!!Q. ALL x. EX y. Q x y ==> EX f. ALL x. Q x (f x)";
4656
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    26
by (fast_tac (claset() addEs [selectI]) 1);
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    27
qed "choice";
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    28
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
    29
Goal "!!S. ALL x:S. EX y. Q x y ==> EX f. ALL x:S. Q x (f x)";
4656
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    30
by (fast_tac (claset() addEs [selectI]) 1);
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    31
qed "bchoice";
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    32
134d24ddaad3 Proved choice and bchoice; changed Fun.thy -> thy
paulson
parents: 4089
diff changeset
    33
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    34
section "id";
5441
45bd13b15d80 added Id_apply
oheimb
parents: 5318
diff changeset
    35
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    36
Goalw [id_def] "id x = x";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    37
by (rtac refl 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    38
qed "id_apply";
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    39
Addsimps [id_apply];
5441
45bd13b15d80 added Id_apply
oheimb
parents: 5318
diff changeset
    40
45bd13b15d80 added Id_apply
oheimb
parents: 5318
diff changeset
    41
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    42
section "o";
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    43
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    44
Goalw [o_def] "(f o g) x = f (g x)";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    45
by (rtac refl 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    46
qed "o_apply";
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    47
Addsimps [o_apply];
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    48
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    49
Goalw [o_def] "f o (g o h) = f o g o h";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    50
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    51
by (rtac refl 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    52
qed "o_assoc";
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    53
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    54
Goalw [id_def] "id o g = g";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    55
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    56
by (Simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    57
qed "id_o";
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    58
Addsimps [id_o];
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    59
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    60
Goalw [id_def] "f o id = f";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    61
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    62
by (Simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    63
qed "o_id";
5608
a82a038a3e7a id <-> Id
nipkow
parents: 5441
diff changeset
    64
Addsimps [o_id];
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    65
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    66
Goalw [o_def] "(f o g)``r = f``(g``r)";
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    67
by (Blast_tac 1);
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    68
qed "image_compose";
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    69
7536
5c094aec523d new theorem image_image_eq_UN
paulson
parents: 7514
diff changeset
    70
Goal "f``g``A = (UN x:A. {f (g x)})";
5c094aec523d new theorem image_image_eq_UN
paulson
parents: 7514
diff changeset
    71
by (Blast_tac 1);
5c094aec523d new theorem image_image_eq_UN
paulson
parents: 7514
diff changeset
    72
qed "image_image_eq_UN";
5c094aec523d new theorem image_image_eq_UN
paulson
parents: 7514
diff changeset
    73
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
    74
Goalw [o_def] "UNION A (g o f) = UNION (f``A) g";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
    75
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
    76
qed "UN_o";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
    77
7014
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    78
(** lemma for proving injectivity of representation functions for **)
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    79
(** datatypes involving function types                            **)
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    80
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    81
Goalw [o_def]
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    82
  "[| ! 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
    83
by (rtac ext 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    84
by (etac allE 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    85
by (etac allE 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    86
by (etac mp 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
    87
by (etac fun_cong 1);
7014
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    88
qed "inj_fun_lemma";
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
    89
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    90
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    91
section "inj";
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    92
(**NB: inj now just translates to inj_on**)
5306
3d1368a3a2a2 added theorems Id_o, o_Id
oheimb
parents: 5305
diff changeset
    93
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    94
(*** inj(f): f is a one-to-one function ***)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    95
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    96
(*for Tools/datatype_rep_proofs*)
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    97
val [prem] = Goalw [inj_on_def]
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
    98
    "(!! 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
    99
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
   100
qed "datatype_injI";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   101
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   102
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
   103
by (Blast_tac 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   104
qed "injD";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   105
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   106
(*Useful with the simplifier*)
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   107
Goal "inj(f) ==> (f(x) = f(y)) = (x=y)";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   108
by (rtac iffI 1);
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   109
by (etac arg_cong 2);
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   110
by (etac injD 1);
5318
72bf8039b53f expandshort
paulson
parents: 5316
diff changeset
   111
by (assume_tac 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   112
qed "inj_eq";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   113
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   114
Goal "inj(f) ==> (@x. f(x)=f(y)) = y";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   115
by (etac injD 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   116
by (rtac selectI 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   117
by (rtac refl 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   118
qed "inj_select";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   119
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   120
(*A one-to-one function has an inverse (given using select).*)
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   121
Goalw [inv_def] "inj(f) ==> inv f (f x) = x";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   122
by (etac inj_select 1);
2912
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   123
qed "inv_f_f";
7338
b275ae194e5a new theorem inv_f_eq
paulson
parents: 7089
diff changeset
   124
Addsimps [inv_f_f];
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   125
7338
b275ae194e5a new theorem inv_f_eq
paulson
parents: 7089
diff changeset
   126
Goal "[| inj(f);  f x = y |] ==> inv f y = x";
b275ae194e5a new theorem inv_f_eq
paulson
parents: 7089
diff changeset
   127
by (etac subst 1);
b275ae194e5a new theorem inv_f_eq
paulson
parents: 7089
diff changeset
   128
by (etac inv_f_f 1);
b275ae194e5a new theorem inv_f_eq
paulson
parents: 7089
diff changeset
   129
qed "inv_f_eq";
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   130
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   131
(* Useful??? *)
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   132
val [oneone,minor] = Goal
2912
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   133
    "[| inj(f); !!y. y: range(f) ==> P(inv f y) |] ==> P(x)";
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   134
by (res_inst_tac [("t", "x")] (oneone RS (inv_f_f RS subst)) 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   135
by (rtac (rangeI RS minor) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   136
qed "inj_transfer";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   137
7014
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   138
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
   139
by (rtac ext 1);
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   140
by (etac injD 1);
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   141
by (etac fun_cong 1);
11ee650edcd2 Added some definitions and theorems needed for the
berghofe
parents: 6829
diff changeset
   142
qed "inj_o";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   143
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   144
(*** 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
   145
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   146
val prems = Goalw [inj_on_def]
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   147
    "(!! x y. [| f(x) = f(y);  x:A;  y:A |] ==> x=y) ==> inj_on f A";
4089
96fba19bcbe2 isatool fixclasimp;
wenzelm
parents: 4059
diff changeset
   148
by (blast_tac (claset() addIs prems) 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   149
qed "inj_onI";
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   150
val injI = inj_onI;                  (*for compatibility*)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   151
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   152
val [major] = Goal 
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   153
    "(!!x. x:A ==> g(f(x)) = x) ==> inj_on f A";
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   154
by (rtac inj_onI 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   155
by (etac (apply_inverse RS trans) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   156
by (REPEAT (eresolve_tac [asm_rl,major] 1));
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   157
qed "inj_on_inverseI";
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   158
val inj_inverseI = inj_on_inverseI;   (*for compatibility*)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   159
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   160
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
   161
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   162
qed "inj_onD";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   163
5143
b94cd208f073 Removal of leading "\!\!..." from most Goal commands
paulson
parents: 5069
diff changeset
   164
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
   165
by (blast_tac (claset() addSDs [inj_onD]) 1);
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   166
qed "inj_on_iff";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   167
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   168
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
   169
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   170
qed "inj_on_contraD";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   171
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   172
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
   173
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   174
qed "subset_inj_on";
3341
89fe22bf9f54 New theorem subset_inj_onto
paulson
parents: 2935
diff changeset
   175
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   176
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   177
(** surj **)
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   178
6267
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   179
val [prem] = Goalw [surj_def] "(!! x. g(f x) = x) ==> surj g";
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   180
by (blast_tac (claset() addIs [prem RS sym]) 1);
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   181
qed "surjI";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   182
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   183
Goalw [surj_def] "surj f ==> range f = UNIV";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   184
by Auto_tac;
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   185
qed "surj_range";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   186
6267
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   187
Goalw [surj_def] "surj f ==> EX x. y = f x";
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   188
by (Blast_tac 1);
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   189
qed "surjD";
a3098667b9b6 new lemma surjD
paulson
parents: 6235
diff changeset
   190
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   191
7374
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   192
(** Bijections **)
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   193
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   194
Goalw [bij_def] "[| inj f; surj f |] ==> bij f";
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   195
by (Blast_tac 1);
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   196
qed "bijI";
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   197
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   198
Goalw [bij_def] "bij f ==> inj f";
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   199
by (Blast_tac 1);
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   200
qed "bij_is_inj";
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   201
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   202
Goalw [bij_def] "bij f ==> surj f";
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   203
by (Blast_tac 1);
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   204
qed "bij_is_surj";
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   205
dec7b838f5cb the bij predicate (at last)
paulson
parents: 7338
diff changeset
   206
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   207
(*** Lemmas about injective functions and inv ***)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   208
7051
9b6bdced3dc6 Mod by Norber Voelcker
nipkow
parents: 7014
diff changeset
   209
Goalw [o_def] "[| inj_on f A;  inj_on g (f``A) |] ==> inj_on (g o f) A";
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   210
by (fast_tac (claset() addIs [inj_onI] addEs [inj_onD]) 1);
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   211
qed "comp_inj_on";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   212
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   213
Goalw [inv_def] "y : range(f) ==> f(inv f y) = y";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   214
by (fast_tac (claset() addIs [selectI]) 1);
2912
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   215
qed "f_inv_f";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   216
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   217
Goal "surj f ==> f(inv f y) = y";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   218
by (asm_simp_tac (simpset() addsimps [f_inv_f, surj_range]) 1);
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   219
qed "surj_f_inv_f";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   220
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   221
Goal "[| inv f x = inv f y;  x: range(f);  y: range(f) |] ==> x=y";
2912
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   222
by (rtac (arg_cong RS box_equals) 1);
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5306
diff changeset
   223
by (REPEAT (ares_tac [f_inv_f] 1));
2912
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   224
qed "inv_injective";
3fac3e8d5d3e moved inj and surj from Set to Fun and Inv -> inv.
nipkow
parents: 2890
diff changeset
   225
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   226
Goal "A <= range(f) ==> inj_on (inv f) A";
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   227
by (fast_tac (claset() addIs [inj_onI] 
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   228
                       addEs [inv_injective, injD]) 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   229
qed "inj_on_inv";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   230
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   231
Goal "surj f ==> inj (inv f)";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   232
by (asm_simp_tac (simpset() addsimps [inj_on_inv, surj_range]) 1);
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   233
qed "surj_imp_inj_inv";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   234
7514
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   235
(** 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
   236
    arise by rewriting, while id may be used explicitly. **)
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   237
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   238
Goal "(%x. x) `` Y = Y";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   239
by (Blast_tac 1);
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   240
qed "image_ident";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   241
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   242
Goalw [id_def] "id `` Y = Y";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   243
by (Blast_tac 1);
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   244
qed "image_id";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   245
Addsimps [image_ident, image_id];
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   246
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   247
Goal "(%x. x) -`` Y = Y";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   248
by (Blast_tac 1);
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   249
qed "vimage_ident";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   250
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   251
Goalw [id_def] "id -`` A = A";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   252
by Auto_tac;
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   253
qed "vimage_id";
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   254
Addsimps [vimage_ident, vimage_id];
3235863a069a images and preimages of the identity function
paulson
parents: 7445
diff changeset
   255
6290
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   256
Goal "f``(A Int B) <= f``A Int f``B";
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   257
by (Blast_tac 1);
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   258
qed "image_Int_subset";
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   259
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   260
Goal "f``A - f``B <= f``(A - B)";
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   261
by (Blast_tac 1);
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   262
qed "image_diff_subset";
31483ca40e91 new image laws
paulson
parents: 6267
diff changeset
   263
5069
3ea049f7979d isatool fixgoal;
wenzelm
parents: 4830
diff changeset
   264
Goalw [inj_on_def]
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5143
diff changeset
   265
   "[| 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
   266
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   267
qed "inj_on_image_Int";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   268
5069
3ea049f7979d isatool fixgoal;
wenzelm
parents: 4830
diff changeset
   269
Goalw [inj_on_def]
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5143
diff changeset
   270
   "[| 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
   271
by (Blast_tac 1);
4830
bd73675adbed Added a few lemmas.
nipkow
parents: 4656
diff changeset
   272
qed "inj_on_image_set_diff";
4059
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   273
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   274
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
   275
by (Blast_tac 1);
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   276
qed "image_Int";
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   277
6171
cd237a10cbf8 inj is now a translation of inj_on
paulson
parents: 5865
diff changeset
   278
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
   279
by (Blast_tac 1);
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   280
qed "image_set_diff";
59c1422c9da5 New Blast_tac (and minor tidying...)
paulson
parents: 3842
diff changeset
   281
6235
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   282
Goalw [image_def] "inj(f) ==> inv(f)``(f``X) = X";
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   283
by Auto_tac;
c8a69ecafb99 new surj rules
paulson
parents: 6171
diff changeset
   284
qed "inv_image_comp";
5847
17c869f24c5f proved surjI
paulson
parents: 5608
diff changeset
   285
6301
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   286
Goal "inj f ==> (f a : f``A) = (a : A)";
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   287
by (blast_tac (claset() addDs [injD]) 1);
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   288
qed "inj_image_mem_iff";
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   289
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   290
Goal "inj f ==> (f``A = f``B) = (A = B)";
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   291
by (blast_tac (claset() addSEs [equalityE] addDs [injD]) 1);
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   292
qed "inj_image_eq_iff";
08245f5a436d expandshort
paulson
parents: 6290
diff changeset
   293
6829
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   294
Goal  "(f `` (UNION A B)) = (UN x:A.(f `` (B x)))";
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   295
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
   296
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
   297
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   298
(*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
   299
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
   300
   "[| inj_on f C;  ALL x:A. B x <= C;  j:A |] \
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   301
\   ==> f `` (INTER A B) = (INT x:A. f `` B x)";
50459a995aa3 renamed UNION_o to UN_o (to fit the convention) and added image_UN, image_INT
paulson
parents: 6301
diff changeset
   302
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
   303
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
   304
4089
96fba19bcbe2 isatool fixclasimp;
wenzelm
parents: 4059
diff changeset
   305
val set_cs = claset() delrules [equalityI];
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   306
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   307
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   308
section "fun_upd";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   309
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   310
Goalw [fun_upd_def] "(f(x:=y) = f) = (f x = y)";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   311
by Safe_tac;
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   312
by (etac subst 1);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   313
by (rtac ext 2);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   314
by Auto_tac;
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   315
qed "fun_upd_idem_iff";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   316
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   317
(* f x = y ==> f(x:=y) = f *)
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   318
bind_thm("fun_upd_idem", fun_upd_idem_iff RS iffD2);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   319
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   320
(* f(x := f x) = f *)
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   321
AddIffs [refl RS fun_upd_idem];
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   322
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   323
Goal "(f(x:=y))z = (if z=x then y else f z)";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   324
by (simp_tac (simpset() addsimps [fun_upd_def]) 1);
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   325
qed "fun_upd_apply";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   326
Addsimps [fun_upd_apply];
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   327
7445
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   328
(*fun_upd_apply supersedes these two*)
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   329
Goal "(f(x:=y)) x = y";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   330
by (Simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   331
qed "fun_upd_same";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   332
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   333
Goal "z~=x ==> (f(x:=y)) z = f z";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   334
by (Asm_simp_tac 1);
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   335
qed "fun_upd_other";
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   336
7445
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   337
Goal "f(x:=y,x:=z) = f(x:=z)";
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   338
by (rtac ext 1);
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   339
by (Simp_tac 1);
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   340
qed "fun_upd_upd";
6dd6110968c9 new theorem fun_upd_upd
paulson
parents: 7374
diff changeset
   341
Addsimps [fun_upd_upd];
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   342
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   343
Goal "a ~= c ==> m(a:=b)(c:=d) = m(c:=d)(a:=b)";
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   344
by (rtac ext 1);
7089
9bfb8e218b99 expandshort and tidying
paulson
parents: 7051
diff changeset
   345
by Auto_tac;
5305
513925de8962 cleanup for Fun.thy:
oheimb
parents: 5148
diff changeset
   346
qed "fun_upd_twist";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   347
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   348
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   349
(*** -> and Pi, by Florian Kammueller and LCP ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   350
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   351
val prems = Goalw [Pi_def]
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   352
"[| !!x. x: A ==> f x: B x; !!x. x ~: A  ==> f(x) = (@ y. True)|] \
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   353
\    ==> f: Pi A B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   354
by (auto_tac (claset(), simpset() addsimps prems));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   355
qed "Pi_I";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   356
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   357
val prems = Goal 
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   358
"[| !!x. x: A ==> f x: B; !!x. x ~: A  ==> f(x) = (@ y. True)|] ==> f: A funcset B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   359
by (blast_tac (claset() addIs Pi_I::prems) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   360
qed "funcsetI";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   361
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   362
Goalw [Pi_def] "[|f: Pi A B; x: A|] ==> f x: B x";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   363
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   364
qed "Pi_mem";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   365
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   366
Goalw [Pi_def] "[|f: A funcset B; x: A|] ==> f x: B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   367
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   368
qed "funcset_mem";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   369
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   370
Goalw [Pi_def] "[|f: Pi A B; x~: A|] ==> f x = (@ y. True)";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   371
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   372
qed "apply_arb";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   373
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   374
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
   375
by (rtac ext 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   376
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   377
val Pi_extensionality = ballI RSN (3, result());
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   378
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   379
(*** compose ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   380
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   381
Goalw [Pi_def, compose_def, restrict_def]
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   382
     "[| 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
   383
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   384
qed "funcset_compose";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   385
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   386
Goal "[| f: A funcset B; g: B funcset C; h: C funcset D |]\
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   387
\     ==> compose A h (compose A g f) = compose A (compose B h g) f";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   388
by (res_inst_tac [("A","A")] Pi_extensionality 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   389
by (blast_tac (claset() addIs [funcset_compose]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   390
by (blast_tac (claset() addIs [funcset_compose]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   391
by (rewrite_goals_tac [Pi_def, compose_def, restrict_def]);  
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   392
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   393
qed "compose_assoc";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   394
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   395
Goal "[| f: A funcset B; g: B funcset C; x: A |]==> compose A g f x = g(f(x))";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   396
by (asm_full_simp_tac (simpset() addsimps [compose_def, restrict_def]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   397
qed "compose_eq";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   398
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   399
Goal "[| f : A funcset B; f `` A = B; g: B funcset C; g `` B = C |]\
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   400
\     ==> compose A g f `` A = C";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   401
by (auto_tac (claset(),
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   402
	      simpset() addsimps [image_def, compose_eq]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   403
qed "surj_compose";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   404
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   405
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   406
Goal "[| f : A funcset B; g: B funcset C; f `` A = B; inj_on f A; inj_on g B |]\
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   407
\     ==> inj_on (compose A g f) A";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   408
by (auto_tac (claset(),
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   409
	      simpset() addsimps [inj_on_def, compose_eq]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   410
qed "inj_on_compose";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   411
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   412
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   413
(*** restrict / lam ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   414
Goal "[| f `` A <= B |] ==> (lam x: A. f x) : A funcset B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   415
by (auto_tac (claset(),
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   416
	      simpset() addsimps [restrict_def, Pi_def]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   417
qed "restrict_in_funcset";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   418
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   419
val prems = Goalw [restrict_def, Pi_def]
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   420
     "(!!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
   421
by (asm_simp_tac (simpset() addsimps prems) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   422
qed "restrictI";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   423
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   424
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   425
Goal "x: A ==> (lam y: A. f y) x = f x";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   426
by (asm_simp_tac (simpset() addsimps [restrict_def]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   427
qed "restrict_apply1";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   428
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   429
Goal "[| x: A; f : A funcset B |] ==> (lam y: A. f y) x : B";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   430
by (asm_full_simp_tac (simpset() addsimps [restrict_apply1,Pi_def]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   431
qed "restrict_apply1_mem";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   432
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   433
Goal "x ~: A ==> (lam y: A. f y) x =  (@ y. True)";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   434
by (asm_simp_tac (simpset() addsimps [restrict_def]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   435
qed "restrict_apply2";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   436
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   437
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   438
val prems = Goal
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   439
    "(!!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
   440
by (rtac ext 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   441
by (auto_tac (claset(),
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   442
	      simpset() addsimps prems@[restrict_def, Pi_def]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   443
qed "restrict_ext";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   444
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   445
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   446
(*** Inverse ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   447
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   448
Goal "[|f `` A = B;  x: B |] ==> ? y: A. f y = x";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   449
by (Blast_tac 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   450
qed "surj_image";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   451
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   452
Goalw [Inv_def] "[| f `` A = B; f : A funcset B |] \
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   453
\                ==> (lam x: B. (Inv A f) x) : B funcset A";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   454
by (fast_tac (claset() addIs [restrict_in_funcset, selectI2]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   455
qed "Inv_funcset";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   456
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   457
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   458
Goal "[| f: A funcset B;  inj_on f A;  f `` A = B;  x: A |] \
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   459
\     ==> (lam y: B. (Inv A f) y) (f x) = x";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   460
by (asm_simp_tac (simpset() addsimps [restrict_apply1, funcset_mem]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   461
by (asm_full_simp_tac (simpset() addsimps [Inv_def, inj_on_def]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   462
by (rtac selectI2 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   463
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   464
qed "Inv_f_f";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   465
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   466
Goal "[| f: A funcset B;  f `` A = B;  x: B |] \
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   467
\     ==> f ((lam y: B. (Inv A f y)) x) = x";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   468
by (asm_simp_tac (simpset() addsimps [Inv_def, restrict_apply1]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   469
by (fast_tac (claset() addIs [selectI2]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   470
qed "f_Inv_f";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   471
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   472
Goal "[| f: A funcset B;  inj_on f A;  f `` A = B |]\
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   473
\     ==> compose A (lam y:B. (Inv A f) y) f = (lam x: A. x)";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   474
by (rtac Pi_extensionality 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   475
by (blast_tac (claset() addIs [funcset_compose, Inv_funcset]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   476
by (blast_tac (claset() addIs [restrict_in_funcset]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   477
by (asm_simp_tac
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   478
    (simpset() addsimps [restrict_apply1, compose_def, Inv_f_f]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   479
qed "compose_Inv_id";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   480
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   481
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   482
(*** Pi and Applyall ***)
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   483
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   484
Goalw [Pi_def] "[| B(x) = {};  x: A |] ==> (PI x: A. B x) = {}";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   485
by Auto_tac;
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   486
qed "Pi_eq_empty";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   487
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   488
Goal "[| (PI x: A. B x) ~= {};  x: A |] ==> B(x) ~= {}";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   489
by (blast_tac (HOL_cs addIs [Pi_eq_empty]) 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   490
qed "Pi_total1";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   491
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   492
Goal "[| a : A; Pi A B ~= {} |] ==> Applyall (Pi A B) a = B a";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   493
by (auto_tac (claset(), simpset() addsimps [Applyall_def, Pi_def]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   494
by (rename_tac "g z" 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   495
by (res_inst_tac [("x","%y. if  (y = a) then z else g y")] exI 1);
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   496
by (auto_tac (claset(), simpset() addsimps [split_if_mem1, split_if_eq1]));
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   497
qed "Applyall_beta";
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   498
5865
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   499
Goal "Pi {} B = { (%x. @ y. True) }";
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   500
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
   501
qed "Pi_empty";
5852
4d7320490be4 the function space operator
paulson
parents: 5847
diff changeset
   502
5865
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   503
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
   504
by (auto_tac (claset(),
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   505
	      simpset() addsimps [impOfSubs major]));
2303f5a3036d moved some facts about Pi from ex/PiSets to Fun.ML
paulson
parents: 5852
diff changeset
   506
qed "Pi_mono";