src/ZF/Sum.thy
author paulson
Sun Jun 23 10:14:13 2002 +0200 (2002-06-23)
changeset 13240 bb5f4faea1f3
parent 13220 62c899c77151
child 13255 407ad9c3036d
permissions -rw-r--r--
conversion of Sum, pair to Isar script
clasohm@1478
     1
(*  Title:      ZF/sum.thy
clasohm@0
     2
    ID:         $Id$
clasohm@1478
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     4
    Copyright   1993  University of Cambridge
clasohm@0
     5
clasohm@0
     6
Disjoint sums in Zermelo-Fraenkel Set Theory 
clasohm@0
     7
"Part" primitive for simultaneous recursive type definitions
clasohm@0
     8
*)
clasohm@0
     9
paulson@13240
    10
theory Sum = Bool + equalities:
wenzelm@3923
    11
wenzelm@3923
    12
global
wenzelm@3923
    13
paulson@13240
    14
constdefs
paulson@13240
    15
  sum     :: "[i,i]=>i"                     (infixr "+" 65)
paulson@13240
    16
     "A+B == {0}*A Un {1}*B"
paulson@13240
    17
paulson@13240
    18
  Inl     :: "i=>i"
paulson@13240
    19
     "Inl(a) == <0,a>"
paulson@13240
    20
paulson@13240
    21
  Inr     :: "i=>i"
paulson@13240
    22
     "Inr(b) == <1,b>"
paulson@13240
    23
paulson@13240
    24
  "case"  :: "[i=>i, i=>i, i]=>i"
paulson@13240
    25
     "case(c,d) == (%<y,z>. cond(y, d(z), c(z)))"
paulson@13240
    26
paulson@13240
    27
  (*operator for selecting out the various summands*)
paulson@13240
    28
  Part    :: "[i,i=>i] => i"
paulson@13240
    29
     "Part(A,h) == {x: A. EX z. x = h(z)}"
clasohm@0
    30
wenzelm@3940
    31
local
wenzelm@3923
    32
paulson@13240
    33
(*** Rules for the Part primitive ***)
paulson@13240
    34
paulson@13240
    35
lemma Part_iff: 
paulson@13240
    36
    "a : Part(A,h) <-> a:A & (EX y. a=h(y))"
paulson@13240
    37
apply (unfold Part_def)
paulson@13240
    38
apply (rule separation)
paulson@13240
    39
done
paulson@13240
    40
paulson@13240
    41
lemma Part_eqI [intro]: 
paulson@13240
    42
    "[| a : A;  a=h(b) |] ==> a : Part(A,h)"
paulson@13240
    43
apply (unfold Part_def)
paulson@13240
    44
apply blast
paulson@13240
    45
done
paulson@13240
    46
paulson@13240
    47
lemmas PartI = refl [THEN [2] Part_eqI]
paulson@13240
    48
paulson@13240
    49
lemma PartE [elim!]: 
paulson@13240
    50
    "[| a : Part(A,h);  !!z. [| a : A;  a=h(z) |] ==> P   
paulson@13240
    51
     |] ==> P"
paulson@13240
    52
apply (unfold Part_def)
paulson@13240
    53
apply blast
paulson@13240
    54
done
paulson@13240
    55
paulson@13240
    56
lemma Part_subset: "Part(A,h) <= A"
paulson@13240
    57
apply (unfold Part_def)
paulson@13240
    58
apply (rule Collect_subset)
paulson@13240
    59
done
paulson@13240
    60
paulson@13240
    61
paulson@13240
    62
(*** Rules for Disjoint Sums ***)
paulson@13240
    63
paulson@13240
    64
lemmas sum_defs = sum_def Inl_def Inr_def case_def
paulson@13240
    65
paulson@13240
    66
lemma Sigma_bool: "Sigma(bool,C) = C(0) + C(1)"
paulson@13240
    67
apply (unfold bool_def sum_def)
paulson@13240
    68
apply blast
paulson@13240
    69
done
paulson@13240
    70
paulson@13240
    71
(** Introduction rules for the injections **)
paulson@13240
    72
paulson@13240
    73
lemma InlI [intro!,simp,TC]: "a : A ==> Inl(a) : A+B"
paulson@13240
    74
apply (unfold sum_defs)
paulson@13240
    75
apply blast
paulson@13240
    76
done
paulson@13240
    77
paulson@13240
    78
lemma InrI [intro!,simp,TC]: "b : B ==> Inr(b) : A+B"
paulson@13240
    79
apply (unfold sum_defs)
paulson@13240
    80
apply blast
paulson@13240
    81
done
paulson@13240
    82
paulson@13240
    83
(** Elimination rules **)
paulson@13240
    84
paulson@13240
    85
lemma sumE [elim!]:
paulson@13240
    86
    "[| u: A+B;   
paulson@13240
    87
        !!x. [| x:A;  u=Inl(x) |] ==> P;  
paulson@13240
    88
        !!y. [| y:B;  u=Inr(y) |] ==> P  
paulson@13240
    89
     |] ==> P"
paulson@13240
    90
apply (unfold sum_defs)
paulson@13240
    91
apply (blast intro: elim:); 
paulson@13240
    92
done
paulson@13240
    93
paulson@13240
    94
(** Injection and freeness equivalences, for rewriting **)
paulson@13240
    95
paulson@13240
    96
lemma Inl_iff [iff]: "Inl(a)=Inl(b) <-> a=b"
paulson@13240
    97
apply (simp add: sum_defs)
paulson@13240
    98
done
paulson@13240
    99
paulson@13240
   100
lemma Inr_iff [iff]: "Inr(a)=Inr(b) <-> a=b"
paulson@13240
   101
apply (simp add: sum_defs)
paulson@13240
   102
done
paulson@13240
   103
paulson@13240
   104
lemma Inl_Inr_iff [iff]: "Inl(a)=Inr(b) <-> False"
paulson@13240
   105
apply (simp add: sum_defs)
paulson@13240
   106
done
paulson@13240
   107
paulson@13240
   108
lemma Inr_Inl_iff [iff]: "Inr(b)=Inl(a) <-> False"
paulson@13240
   109
apply (simp add: sum_defs)
paulson@13240
   110
done
paulson@13240
   111
paulson@13240
   112
lemma sum_empty [simp]: "0+0 = 0"
paulson@13240
   113
apply (simp add: sum_defs)
paulson@13240
   114
done
paulson@13240
   115
paulson@13240
   116
(*Injection and freeness rules*)
paulson@13240
   117
paulson@13240
   118
lemmas Inl_inject = Inl_iff [THEN iffD1, standard]
paulson@13240
   119
lemmas Inr_inject = Inr_iff [THEN iffD1, standard]
paulson@13240
   120
lemmas Inl_neq_Inr = Inl_Inr_iff [THEN iffD1, THEN FalseE]
paulson@13240
   121
lemmas Inr_neq_Inl = Inr_Inl_iff [THEN iffD1, THEN FalseE]
paulson@13240
   122
paulson@13240
   123
paulson@13240
   124
lemma InlD: "Inl(a): A+B ==> a: A"
paulson@13240
   125
apply blast
paulson@13240
   126
done
paulson@13240
   127
paulson@13240
   128
lemma InrD: "Inr(b): A+B ==> b: B"
paulson@13240
   129
apply blast
paulson@13240
   130
done
paulson@13240
   131
paulson@13240
   132
lemma sum_iff: "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))"
paulson@13240
   133
apply blast
paulson@13240
   134
done
paulson@13240
   135
paulson@13240
   136
lemma sum_subset_iff: "A+B <= C+D <-> A<=C & B<=D"
paulson@13240
   137
apply blast
paulson@13240
   138
done
paulson@13240
   139
paulson@13240
   140
lemma sum_equal_iff: "A+B = C+D <-> A=C & B=D"
paulson@13240
   141
apply (simp add: extension sum_subset_iff)
paulson@13240
   142
apply blast
paulson@13240
   143
done
paulson@13240
   144
paulson@13240
   145
lemma sum_eq_2_times: "A+A = 2*A"
paulson@13240
   146
apply (simp add: sum_def)
paulson@13240
   147
apply blast
paulson@13240
   148
done
paulson@13240
   149
paulson@13240
   150
paulson@13240
   151
(*** Eliminator -- case ***)
clasohm@0
   152
paulson@13240
   153
lemma case_Inl [simp]: "case(c, d, Inl(a)) = c(a)"
paulson@13240
   154
apply (simp add: sum_defs)
paulson@13240
   155
done
paulson@13240
   156
paulson@13240
   157
lemma case_Inr [simp]: "case(c, d, Inr(b)) = d(b)"
paulson@13240
   158
apply (simp add: sum_defs)
paulson@13240
   159
done
paulson@13240
   160
paulson@13240
   161
lemma case_type [TC]:
paulson@13240
   162
    "[| u: A+B;  
paulson@13240
   163
        !!x. x: A ==> c(x): C(Inl(x));    
paulson@13240
   164
        !!y. y: B ==> d(y): C(Inr(y))  
paulson@13240
   165
     |] ==> case(c,d,u) : C(u)"
paulson@13240
   166
apply (auto );  
paulson@13240
   167
done
paulson@13240
   168
paulson@13240
   169
lemma expand_case: "u: A+B ==>    
paulson@13240
   170
        R(case(c,d,u)) <->  
paulson@13240
   171
        ((ALL x:A. u = Inl(x) --> R(c(x))) &  
paulson@13240
   172
        (ALL y:B. u = Inr(y) --> R(d(y))))"
paulson@13240
   173
by auto
paulson@13240
   174
paulson@13240
   175
lemma case_cong:
paulson@13240
   176
  "[| z: A+B;    
paulson@13240
   177
      !!x. x:A ==> c(x)=c'(x);   
paulson@13240
   178
      !!y. y:B ==> d(y)=d'(y)    
paulson@13240
   179
   |] ==> case(c,d,z) = case(c',d',z)"
paulson@13240
   180
by (auto ); 
paulson@13240
   181
paulson@13240
   182
lemma case_case: "z: A+B ==>    
paulson@13240
   183
        case(c, d, case(%x. Inl(c'(x)), %y. Inr(d'(y)), z)) =  
paulson@13240
   184
        case(%x. c(c'(x)), %y. d(d'(y)), z)"
paulson@13240
   185
by auto
paulson@13240
   186
paulson@13240
   187
paulson@13240
   188
(*** More rules for Part(A,h) ***)
paulson@13240
   189
paulson@13240
   190
lemma Part_mono: "A<=B ==> Part(A,h)<=Part(B,h)"
paulson@13240
   191
apply blast
paulson@13240
   192
done
paulson@13240
   193
paulson@13240
   194
lemma Part_Collect: "Part(Collect(A,P), h) = Collect(Part(A,h), P)"
paulson@13240
   195
apply blast
paulson@13240
   196
done
paulson@13240
   197
paulson@13240
   198
lemmas Part_CollectE =
paulson@13240
   199
     Part_Collect [THEN equalityD1, THEN subsetD, THEN CollectE, standard]
paulson@13240
   200
paulson@13240
   201
lemma Part_Inl: "Part(A+B,Inl) = {Inl(x). x: A}"
paulson@13240
   202
apply blast
paulson@13240
   203
done
paulson@13240
   204
paulson@13240
   205
lemma Part_Inr: "Part(A+B,Inr) = {Inr(y). y: B}"
paulson@13240
   206
apply blast
paulson@13240
   207
done
paulson@13240
   208
paulson@13240
   209
lemma PartD1: "a : Part(A,h) ==> a : A"
paulson@13240
   210
apply (simp add: Part_def)
paulson@13240
   211
done
paulson@13240
   212
paulson@13240
   213
lemma Part_id: "Part(A,%x. x) = A"
paulson@13240
   214
apply blast
paulson@13240
   215
done
paulson@13240
   216
paulson@13240
   217
lemma Part_Inr2: "Part(A+B, %x. Inr(h(x))) = {Inr(y). y: Part(B,h)}"
paulson@13240
   218
apply blast
paulson@13240
   219
done
paulson@13240
   220
paulson@13240
   221
lemma Part_sum_equality: "C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C"
paulson@13240
   222
apply blast
paulson@13240
   223
done
paulson@13240
   224
paulson@13240
   225
ML
paulson@13240
   226
{*
paulson@13240
   227
val sum_def = thm "sum_def";
paulson@13240
   228
val Inl_def = thm "Inl_def";
paulson@13240
   229
val Inr_def = thm "Inr_def";
paulson@13240
   230
val sum_defs = thms "sum_defs";
paulson@13240
   231
paulson@13240
   232
val Part_iff = thm "Part_iff";
paulson@13240
   233
val Part_eqI = thm "Part_eqI";
paulson@13240
   234
val PartI = thm "PartI";
paulson@13240
   235
val PartE = thm "PartE";
paulson@13240
   236
val Part_subset = thm "Part_subset";
paulson@13240
   237
val Sigma_bool = thm "Sigma_bool";
paulson@13240
   238
val InlI = thm "InlI";
paulson@13240
   239
val InrI = thm "InrI";
paulson@13240
   240
val sumE = thm "sumE";
paulson@13240
   241
val Inl_iff = thm "Inl_iff";
paulson@13240
   242
val Inr_iff = thm "Inr_iff";
paulson@13240
   243
val Inl_Inr_iff = thm "Inl_Inr_iff";
paulson@13240
   244
val Inr_Inl_iff = thm "Inr_Inl_iff";
paulson@13240
   245
val sum_empty = thm "sum_empty";
paulson@13240
   246
val Inl_inject = thm "Inl_inject";
paulson@13240
   247
val Inr_inject = thm "Inr_inject";
paulson@13240
   248
val Inl_neq_Inr = thm "Inl_neq_Inr";
paulson@13240
   249
val Inr_neq_Inl = thm "Inr_neq_Inl";
paulson@13240
   250
val InlD = thm "InlD";
paulson@13240
   251
val InrD = thm "InrD";
paulson@13240
   252
val sum_iff = thm "sum_iff";
paulson@13240
   253
val sum_subset_iff = thm "sum_subset_iff";
paulson@13240
   254
val sum_equal_iff = thm "sum_equal_iff";
paulson@13240
   255
val sum_eq_2_times = thm "sum_eq_2_times";
paulson@13240
   256
val case_Inl = thm "case_Inl";
paulson@13240
   257
val case_Inr = thm "case_Inr";
paulson@13240
   258
val case_type = thm "case_type";
paulson@13240
   259
val expand_case = thm "expand_case";
paulson@13240
   260
val case_cong = thm "case_cong";
paulson@13240
   261
val case_case = thm "case_case";
paulson@13240
   262
val Part_mono = thm "Part_mono";
paulson@13240
   263
val Part_Collect = thm "Part_Collect";
paulson@13240
   264
val Part_CollectE = thm "Part_CollectE";
paulson@13240
   265
val Part_Inl = thm "Part_Inl";
paulson@13240
   266
val Part_Inr = thm "Part_Inr";
paulson@13240
   267
val PartD1 = thm "PartD1";
paulson@13240
   268
val Part_id = thm "Part_id";
paulson@13240
   269
val Part_Inr2 = thm "Part_Inr2";
paulson@13240
   270
val Part_sum_equality = thm "Part_sum_equality";
paulson@13240
   271
paulson@13240
   272
*}
paulson@13240
   273
paulson@13240
   274
paulson@13240
   275
clasohm@0
   276
end