129 by (blast dest: Push_inject1 Push_inject2) |
129 by (blast dest: Push_inject1 Push_inject2) |
130 |
130 |
131 lemma Push_neq_K0: "Push (Inr (Suc k)) f = (%z. Inr 0) ==> P" |
131 lemma Push_neq_K0: "Push (Inr (Suc k)) f = (%z. Inr 0) ==> P" |
132 by (auto simp add: Push_def fun_eq_iff split: nat.split_asm) |
132 by (auto simp add: Push_def fun_eq_iff split: nat.split_asm) |
133 |
133 |
134 lemmas Abs_Node_inj = Abs_Node_inject [THEN [2] rev_iffD1, standard] |
134 lemmas Abs_Node_inj = Abs_Node_inject [THEN [2] rev_iffD1] |
135 |
135 |
136 |
136 |
137 (*** Introduction rules for Node ***) |
137 (*** Introduction rules for Node ***) |
138 |
138 |
139 lemma Node_K0_I: "(%k. Inr 0, a) : Node" |
139 lemma Node_K0_I: "(%k. Inr 0, a) : Node" |
153 unfolding Atom_def Scons_def Push_Node_def One_nat_def |
153 unfolding Atom_def Scons_def Push_Node_def One_nat_def |
154 by (blast intro: Node_K0_I Rep_Node [THEN Node_Push_I] |
154 by (blast intro: Node_K0_I Rep_Node [THEN Node_Push_I] |
155 dest!: Abs_Node_inj |
155 dest!: Abs_Node_inj |
156 elim!: apfst_convE sym [THEN Push_neq_K0]) |
156 elim!: apfst_convE sym [THEN Push_neq_K0]) |
157 |
157 |
158 lemmas Atom_not_Scons [iff] = Scons_not_Atom [THEN not_sym, standard] |
158 lemmas Atom_not_Scons [iff] = Scons_not_Atom [THEN not_sym] |
159 |
159 |
160 |
160 |
161 (*** Injectiveness ***) |
161 (*** Injectiveness ***) |
162 |
162 |
163 (** Atomic nodes **) |
163 (** Atomic nodes **) |
164 |
164 |
165 lemma inj_Atom: "inj(Atom)" |
165 lemma inj_Atom: "inj(Atom)" |
166 apply (simp add: Atom_def) |
166 apply (simp add: Atom_def) |
167 apply (blast intro!: inj_onI Node_K0_I dest!: Abs_Node_inj) |
167 apply (blast intro!: inj_onI Node_K0_I dest!: Abs_Node_inj) |
168 done |
168 done |
169 lemmas Atom_inject = inj_Atom [THEN injD, standard] |
169 lemmas Atom_inject = inj_Atom [THEN injD] |
170 |
170 |
171 lemma Atom_Atom_eq [iff]: "(Atom(a)=Atom(b)) = (a=b)" |
171 lemma Atom_Atom_eq [iff]: "(Atom(a)=Atom(b)) = (a=b)" |
172 by (blast dest!: Atom_inject) |
172 by (blast dest!: Atom_inject) |
173 |
173 |
174 lemma inj_Leaf: "inj(Leaf)" |
174 lemma inj_Leaf: "inj(Leaf)" |
175 apply (simp add: Leaf_def o_def) |
175 apply (simp add: Leaf_def o_def) |
176 apply (rule inj_onI) |
176 apply (rule inj_onI) |
177 apply (erule Atom_inject [THEN Inl_inject]) |
177 apply (erule Atom_inject [THEN Inl_inject]) |
178 done |
178 done |
179 |
179 |
180 lemmas Leaf_inject [dest!] = inj_Leaf [THEN injD, standard] |
180 lemmas Leaf_inject [dest!] = inj_Leaf [THEN injD] |
181 |
181 |
182 lemma inj_Numb: "inj(Numb)" |
182 lemma inj_Numb: "inj(Numb)" |
183 apply (simp add: Numb_def o_def) |
183 apply (simp add: Numb_def o_def) |
184 apply (rule inj_onI) |
184 apply (rule inj_onI) |
185 apply (erule Atom_inject [THEN Inr_inject]) |
185 apply (erule Atom_inject [THEN Inr_inject]) |
186 done |
186 done |
187 |
187 |
188 lemmas Numb_inject [dest!] = inj_Numb [THEN injD, standard] |
188 lemmas Numb_inject [dest!] = inj_Numb [THEN injD] |
189 |
189 |
190 |
190 |
191 (** Injectiveness of Push_Node **) |
191 (** Injectiveness of Push_Node **) |
192 |
192 |
193 lemma Push_Node_inject: |
193 lemma Push_Node_inject: |
233 (** Scons vs Leaf **) |
233 (** Scons vs Leaf **) |
234 |
234 |
235 lemma Scons_not_Leaf [iff]: "Scons M N \<noteq> Leaf(a)" |
235 lemma Scons_not_Leaf [iff]: "Scons M N \<noteq> Leaf(a)" |
236 unfolding Leaf_def o_def by (rule Scons_not_Atom) |
236 unfolding Leaf_def o_def by (rule Scons_not_Atom) |
237 |
237 |
238 lemmas Leaf_not_Scons [iff] = Scons_not_Leaf [THEN not_sym, standard] |
238 lemmas Leaf_not_Scons [iff] = Scons_not_Leaf [THEN not_sym] |
239 |
239 |
240 (** Scons vs Numb **) |
240 (** Scons vs Numb **) |
241 |
241 |
242 lemma Scons_not_Numb [iff]: "Scons M N \<noteq> Numb(k)" |
242 lemma Scons_not_Numb [iff]: "Scons M N \<noteq> Numb(k)" |
243 unfolding Numb_def o_def by (rule Scons_not_Atom) |
243 unfolding Numb_def o_def by (rule Scons_not_Atom) |
244 |
244 |
245 lemmas Numb_not_Scons [iff] = Scons_not_Numb [THEN not_sym, standard] |
245 lemmas Numb_not_Scons [iff] = Scons_not_Numb [THEN not_sym] |
246 |
246 |
247 |
247 |
248 (** Leaf vs Numb **) |
248 (** Leaf vs Numb **) |
249 |
249 |
250 lemma Leaf_not_Numb [iff]: "Leaf(a) \<noteq> Numb(k)" |
250 lemma Leaf_not_Numb [iff]: "Leaf(a) \<noteq> Numb(k)" |
251 by (simp add: Leaf_def Numb_def) |
251 by (simp add: Leaf_def Numb_def) |
252 |
252 |
253 lemmas Numb_not_Leaf [iff] = Leaf_not_Numb [THEN not_sym, standard] |
253 lemmas Numb_not_Leaf [iff] = Leaf_not_Numb [THEN not_sym] |
254 |
254 |
255 |
255 |
256 (*** ndepth -- the depth of a node ***) |
256 (*** ndepth -- the depth of a node ***) |
257 |
257 |
258 lemma ndepth_K0: "ndepth (Abs_Node(%k. Inr 0, x)) = 0" |
258 lemma ndepth_K0: "ndepth (Abs_Node(%k. Inr 0, x)) = 0" |
355 (** Injection **) |
355 (** Injection **) |
356 |
356 |
357 lemma In0_not_In1 [iff]: "In0(M) \<noteq> In1(N)" |
357 lemma In0_not_In1 [iff]: "In0(M) \<noteq> In1(N)" |
358 unfolding In0_def In1_def One_nat_def by auto |
358 unfolding In0_def In1_def One_nat_def by auto |
359 |
359 |
360 lemmas In1_not_In0 [iff] = In0_not_In1 [THEN not_sym, standard] |
360 lemmas In1_not_In0 [iff] = In0_not_In1 [THEN not_sym] |
361 |
361 |
362 lemma In0_inject: "In0(M) = In0(N) ==> M=N" |
362 lemma In0_inject: "In0(M) = In0(N) ==> M=N" |
363 by (simp add: In0_def) |
363 by (simp add: In0_def) |
364 |
364 |
365 lemma In1_inject: "In1(M) = In1(N) ==> M=N" |
365 lemma In1_inject: "In1(M) = In1(N) ==> M=N" |
501 (*** Bounding theorems ***) |
501 (*** Bounding theorems ***) |
502 |
502 |
503 lemma dprod_Sigma: "(dprod (A <*> B) (C <*> D)) <= (uprod A C) <*> (uprod B D)" |
503 lemma dprod_Sigma: "(dprod (A <*> B) (C <*> D)) <= (uprod A C) <*> (uprod B D)" |
504 by blast |
504 by blast |
505 |
505 |
506 lemmas dprod_subset_Sigma = subset_trans [OF dprod_mono dprod_Sigma, standard] |
506 lemmas dprod_subset_Sigma = subset_trans [OF dprod_mono dprod_Sigma] |
507 |
507 |
508 (*Dependent version*) |
508 (*Dependent version*) |
509 lemma dprod_subset_Sigma2: |
509 lemma dprod_subset_Sigma2: |
510 "(dprod (Sigma A B) (Sigma C D)) <= |
510 "(dprod (Sigma A B) (Sigma C D)) <= |
511 Sigma (uprod A C) (Split (%x y. uprod (B x) (D y)))" |
511 Sigma (uprod A C) (Split (%x y. uprod (B x) (D y)))" |
512 by auto |
512 by auto |
513 |
513 |
514 lemma dsum_Sigma: "(dsum (A <*> B) (C <*> D)) <= (usum A C) <*> (usum B D)" |
514 lemma dsum_Sigma: "(dsum (A <*> B) (C <*> D)) <= (usum A C) <*> (usum B D)" |
515 by blast |
515 by blast |
516 |
516 |
517 lemmas dsum_subset_Sigma = subset_trans [OF dsum_mono dsum_Sigma, standard] |
517 lemmas dsum_subset_Sigma = subset_trans [OF dsum_mono dsum_Sigma] |
518 |
518 |
519 |
519 |
520 text {* hides popular names *} |
520 text {* hides popular names *} |
521 hide_type (open) node item |
521 hide_type (open) node item |
522 hide_const (open) Push Node Atom Leaf Numb Lim Split Case |
522 hide_const (open) Push Node Atom Leaf Numb Lim Split Case |