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