src/HOL/Datatype.thy
changeset 45607 16b4f5774621
parent 42163 392fd6c4669c
child 45694 4a8743618257
equal deleted inserted replaced
45606:b1e1508643b1 45607:16b4f5774621
   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