src/ZF/Sum.thy
author haftmann
Mon Mar 01 13:40:23 2010 +0100 (2010-03-01)
changeset 35416 d8d7d1b785af
parent 32960 69916a850301
child 38514 bd9c4e8281ec
permissions -rw-r--r--
replaced a couple of constsdefs by definitions (also some old primrecs by modern ones)
clasohm@1478
     1
(*  Title:      ZF/sum.thy
clasohm@1478
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     3
    Copyright   1993  University of Cambridge
clasohm@0
     4
*)
clasohm@0
     5
paulson@13356
     6
header{*Disjoint Sums*}
paulson@13356
     7
haftmann@16417
     8
theory Sum imports Bool equalities begin
wenzelm@3923
     9
paulson@13356
    10
text{*And the "Part" primitive for simultaneous recursive type definitions*}
paulson@13356
    11
wenzelm@3923
    12
global
wenzelm@3923
    13
haftmann@35416
    14
definition sum :: "[i,i]=>i" (infixr "+" 65) where
paulson@13240
    15
     "A+B == {0}*A Un {1}*B"
paulson@13240
    16
haftmann@35416
    17
definition Inl :: "i=>i" where
paulson@13240
    18
     "Inl(a) == <0,a>"
paulson@13240
    19
haftmann@35416
    20
definition Inr :: "i=>i" where
paulson@13240
    21
     "Inr(b) == <1,b>"
paulson@13240
    22
haftmann@35416
    23
definition "case" :: "[i=>i, i=>i, i]=>i" where
paulson@13240
    24
     "case(c,d) == (%<y,z>. cond(y, d(z), c(z)))"
paulson@13240
    25
paulson@13240
    26
  (*operator for selecting out the various summands*)
haftmann@35416
    27
definition Part :: "[i,i=>i] => i" where
paulson@13240
    28
     "Part(A,h) == {x: A. EX z. x = h(z)}"
clasohm@0
    29
wenzelm@3940
    30
local
wenzelm@3923
    31
paulson@13356
    32
subsection{*Rules for the @{term Part} Primitive*}
paulson@13240
    33
paulson@13240
    34
lemma Part_iff: 
paulson@13240
    35
    "a : Part(A,h) <-> a:A & (EX y. a=h(y))"
paulson@13240
    36
apply (unfold Part_def)
paulson@13240
    37
apply (rule separation)
paulson@13240
    38
done
paulson@13240
    39
paulson@13240
    40
lemma Part_eqI [intro]: 
paulson@13240
    41
    "[| a : A;  a=h(b) |] ==> a : Part(A,h)"
paulson@13255
    42
by (unfold Part_def, blast)
paulson@13240
    43
paulson@13240
    44
lemmas PartI = refl [THEN [2] Part_eqI]
paulson@13240
    45
paulson@13240
    46
lemma PartE [elim!]: 
paulson@13240
    47
    "[| a : Part(A,h);  !!z. [| a : A;  a=h(z) |] ==> P   
paulson@13240
    48
     |] ==> P"
paulson@13255
    49
apply (unfold Part_def, blast)
paulson@13240
    50
done
paulson@13240
    51
paulson@13240
    52
lemma Part_subset: "Part(A,h) <= A"
paulson@13240
    53
apply (unfold Part_def)
paulson@13240
    54
apply (rule Collect_subset)
paulson@13240
    55
done
paulson@13240
    56
paulson@13240
    57
paulson@13356
    58
subsection{*Rules for Disjoint Sums*}
paulson@13240
    59
paulson@13240
    60
lemmas sum_defs = sum_def Inl_def Inr_def case_def
paulson@13240
    61
paulson@13240
    62
lemma Sigma_bool: "Sigma(bool,C) = C(0) + C(1)"
paulson@13255
    63
by (unfold bool_def sum_def, blast)
paulson@13240
    64
paulson@13240
    65
(** Introduction rules for the injections **)
paulson@13240
    66
paulson@13240
    67
lemma InlI [intro!,simp,TC]: "a : A ==> Inl(a) : A+B"
paulson@13255
    68
by (unfold sum_defs, blast)
paulson@13240
    69
paulson@13240
    70
lemma InrI [intro!,simp,TC]: "b : B ==> Inr(b) : A+B"
paulson@13255
    71
by (unfold sum_defs, blast)
paulson@13240
    72
paulson@13240
    73
(** Elimination rules **)
paulson@13240
    74
paulson@13240
    75
lemma sumE [elim!]:
paulson@13240
    76
    "[| u: A+B;   
paulson@13240
    77
        !!x. [| x:A;  u=Inl(x) |] ==> P;  
paulson@13240
    78
        !!y. [| y:B;  u=Inr(y) |] ==> P  
paulson@13240
    79
     |] ==> P"
paulson@13255
    80
by (unfold sum_defs, blast) 
paulson@13240
    81
paulson@13240
    82
(** Injection and freeness equivalences, for rewriting **)
paulson@13240
    83
paulson@13240
    84
lemma Inl_iff [iff]: "Inl(a)=Inl(b) <-> a=b"
paulson@13255
    85
by (simp add: sum_defs)
paulson@13240
    86
paulson@13240
    87
lemma Inr_iff [iff]: "Inr(a)=Inr(b) <-> a=b"
paulson@13255
    88
by (simp add: sum_defs)
paulson@13240
    89
paulson@13823
    90
lemma Inl_Inr_iff [simp]: "Inl(a)=Inr(b) <-> False"
paulson@13255
    91
by (simp add: sum_defs)
paulson@13240
    92
paulson@13823
    93
lemma Inr_Inl_iff [simp]: "Inr(b)=Inl(a) <-> False"
paulson@13255
    94
by (simp add: sum_defs)
paulson@13240
    95
paulson@13240
    96
lemma sum_empty [simp]: "0+0 = 0"
paulson@13255
    97
by (simp add: sum_defs)
paulson@13240
    98
paulson@13240
    99
(*Injection and freeness rules*)
paulson@13240
   100
paulson@13240
   101
lemmas Inl_inject = Inl_iff [THEN iffD1, standard]
paulson@13240
   102
lemmas Inr_inject = Inr_iff [THEN iffD1, standard]
paulson@13823
   103
lemmas Inl_neq_Inr = Inl_Inr_iff [THEN iffD1, THEN FalseE, elim!]
paulson@13823
   104
lemmas Inr_neq_Inl = Inr_Inl_iff [THEN iffD1, THEN FalseE, elim!]
paulson@13240
   105
paulson@13240
   106
paulson@13240
   107
lemma InlD: "Inl(a): A+B ==> a: A"
paulson@13255
   108
by blast
paulson@13240
   109
paulson@13240
   110
lemma InrD: "Inr(b): A+B ==> b: B"
paulson@13255
   111
by blast
paulson@13240
   112
paulson@13240
   113
lemma sum_iff: "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))"
paulson@13255
   114
by blast
paulson@13255
   115
paulson@13255
   116
lemma Inl_in_sum_iff [simp]: "(Inl(x) \<in> A+B) <-> (x \<in> A)";
paulson@13255
   117
by auto
paulson@13255
   118
paulson@13255
   119
lemma Inr_in_sum_iff [simp]: "(Inr(y) \<in> A+B) <-> (y \<in> B)";
paulson@13255
   120
by auto
paulson@13240
   121
paulson@13240
   122
lemma sum_subset_iff: "A+B <= C+D <-> A<=C & B<=D"
paulson@13255
   123
by blast
paulson@13240
   124
paulson@13240
   125
lemma sum_equal_iff: "A+B = C+D <-> A=C & B=D"
paulson@13255
   126
by (simp add: extension sum_subset_iff, blast)
paulson@13240
   127
paulson@13240
   128
lemma sum_eq_2_times: "A+A = 2*A"
paulson@13255
   129
by (simp add: sum_def, blast)
paulson@13240
   130
paulson@13240
   131
paulson@13356
   132
subsection{*The Eliminator: @{term case}*}
clasohm@0
   133
paulson@13240
   134
lemma case_Inl [simp]: "case(c, d, Inl(a)) = c(a)"
paulson@13255
   135
by (simp add: sum_defs)
paulson@13240
   136
paulson@13240
   137
lemma case_Inr [simp]: "case(c, d, Inr(b)) = d(b)"
paulson@13255
   138
by (simp add: sum_defs)
paulson@13240
   139
paulson@13240
   140
lemma case_type [TC]:
paulson@13240
   141
    "[| u: A+B;  
paulson@13240
   142
        !!x. x: A ==> c(x): C(Inl(x));    
paulson@13240
   143
        !!y. y: B ==> d(y): C(Inr(y))  
paulson@13240
   144
     |] ==> case(c,d,u) : C(u)"
paulson@13255
   145
by auto
paulson@13240
   146
paulson@13240
   147
lemma expand_case: "u: A+B ==>    
paulson@13240
   148
        R(case(c,d,u)) <->  
paulson@13240
   149
        ((ALL x:A. u = Inl(x) --> R(c(x))) &  
paulson@13240
   150
        (ALL y:B. u = Inr(y) --> R(d(y))))"
paulson@13240
   151
by auto
paulson@13240
   152
paulson@13240
   153
lemma case_cong:
paulson@13240
   154
  "[| z: A+B;    
paulson@13240
   155
      !!x. x:A ==> c(x)=c'(x);   
paulson@13240
   156
      !!y. y:B ==> d(y)=d'(y)    
paulson@13240
   157
   |] ==> case(c,d,z) = case(c',d',z)"
paulson@13255
   158
by auto 
paulson@13240
   159
paulson@13240
   160
lemma case_case: "z: A+B ==>    
wenzelm@32960
   161
        case(c, d, case(%x. Inl(c'(x)), %y. Inr(d'(y)), z)) =  
paulson@13240
   162
        case(%x. c(c'(x)), %y. d(d'(y)), z)"
paulson@13240
   163
by auto
paulson@13240
   164
paulson@13240
   165
paulson@13356
   166
subsection{*More Rules for @{term "Part(A,h)"}*}
paulson@13240
   167
paulson@13240
   168
lemma Part_mono: "A<=B ==> Part(A,h)<=Part(B,h)"
paulson@13255
   169
by blast
paulson@13240
   170
paulson@13240
   171
lemma Part_Collect: "Part(Collect(A,P), h) = Collect(Part(A,h), P)"
paulson@13255
   172
by blast
paulson@13240
   173
paulson@13240
   174
lemmas Part_CollectE =
paulson@13240
   175
     Part_Collect [THEN equalityD1, THEN subsetD, THEN CollectE, standard]
paulson@13240
   176
paulson@13240
   177
lemma Part_Inl: "Part(A+B,Inl) = {Inl(x). x: A}"
paulson@13255
   178
by blast
paulson@13240
   179
paulson@13240
   180
lemma Part_Inr: "Part(A+B,Inr) = {Inr(y). y: B}"
paulson@13255
   181
by blast
paulson@13240
   182
paulson@13240
   183
lemma PartD1: "a : Part(A,h) ==> a : A"
paulson@13255
   184
by (simp add: Part_def)
paulson@13240
   185
paulson@13240
   186
lemma Part_id: "Part(A,%x. x) = A"
paulson@13255
   187
by blast
paulson@13240
   188
paulson@13240
   189
lemma Part_Inr2: "Part(A+B, %x. Inr(h(x))) = {Inr(y). y: Part(B,h)}"
paulson@13255
   190
by blast
paulson@13240
   191
paulson@13240
   192
lemma Part_sum_equality: "C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C"
paulson@13255
   193
by blast
paulson@13240
   194
clasohm@0
   195
end