src/HOL/Induct/QuoDataType.thy
changeset 69597 ff784d5a5bfb
parent 63167 0909deb8059b
child 75287 7add2d5322a7
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
   113   "freediscrim (NONCE N) = 0"
   113   "freediscrim (NONCE N) = 0"
   114 | "freediscrim (MPAIR X Y) = 1"
   114 | "freediscrim (MPAIR X Y) = 1"
   115 | "freediscrim (CRYPT K X) = freediscrim X + 2"
   115 | "freediscrim (CRYPT K X) = freediscrim X + 2"
   116 | "freediscrim (DECRYPT K X) = freediscrim X - 2"
   116 | "freediscrim (DECRYPT K X) = freediscrim X - 2"
   117 
   117 
   118 text\<open>This theorem helps us prove @{term "Nonce N \<noteq> MPair X Y"}\<close>
   118 text\<open>This theorem helps us prove \<^term>\<open>Nonce N \<noteq> MPair X Y\<close>\<close>
   119 theorem msgrel_imp_eq_freediscrim:
   119 theorem msgrel_imp_eq_freediscrim:
   120      "U \<sim> V \<Longrightarrow> freediscrim U = freediscrim V"
   120      "U \<sim> V \<Longrightarrow> freediscrim U = freediscrim V"
   121   by (induct set: msgrel) auto
   121   by (induct set: msgrel) auto
   122 
   122 
   123 
   123 
   149   Decrypt :: "[nat,msg] \<Rightarrow> msg" where
   149   Decrypt :: "[nat,msg] \<Rightarrow> msg" where
   150    "Decrypt K X =
   150    "Decrypt K X =
   151        Abs_Msg (\<Union>U \<in> Rep_Msg X. msgrel``{DECRYPT K U})"
   151        Abs_Msg (\<Union>U \<in> Rep_Msg X. msgrel``{DECRYPT K U})"
   152 
   152 
   153 
   153 
   154 text\<open>Reduces equality of equivalence classes to the @{term msgrel} relation:
   154 text\<open>Reduces equality of equivalence classes to the \<^term>\<open>msgrel\<close> relation:
   155   @{term "(msgrel `` {x} = msgrel `` {y}) = ((x,y) \<in> msgrel)"}\<close>
   155   \<^term>\<open>(msgrel `` {x} = msgrel `` {y}) = ((x,y) \<in> msgrel)\<close>\<close>
   156 lemmas equiv_msgrel_iff = eq_equiv_class_iff [OF equiv_msgrel UNIV_I UNIV_I]
   156 lemmas equiv_msgrel_iff = eq_equiv_class_iff [OF equiv_msgrel UNIV_I UNIV_I]
   157 
   157 
   158 declare equiv_msgrel_iff [simp]
   158 declare equiv_msgrel_iff [simp]
   159 
   159 
   160 
   160 
   225 
   225 
   226 lemma nonces_congruent: "freenonces respects msgrel"
   226 lemma nonces_congruent: "freenonces respects msgrel"
   227 by (auto simp add: congruent_def msgrel_imp_eq_freenonces) 
   227 by (auto simp add: congruent_def msgrel_imp_eq_freenonces) 
   228 
   228 
   229 
   229 
   230 text\<open>Now prove the four equations for @{term nonces}\<close>
   230 text\<open>Now prove the four equations for \<^term>\<open>nonces\<close>\<close>
   231 
   231 
   232 lemma nonces_Nonce [simp]: "nonces (Nonce N) = {N}"
   232 lemma nonces_Nonce [simp]: "nonces (Nonce N) = {N}"
   233 by (simp add: nonces_def Nonce_def 
   233 by (simp add: nonces_def Nonce_def 
   234               UN_equiv_class [OF equiv_msgrel nonces_congruent]) 
   234               UN_equiv_class [OF equiv_msgrel nonces_congruent]) 
   235  
   235  
   259    "left X = Abs_Msg (\<Union>U \<in> Rep_Msg X. msgrel``{freeleft U})"
   259    "left X = Abs_Msg (\<Union>U \<in> Rep_Msg X. msgrel``{freeleft U})"
   260 
   260 
   261 lemma left_congruent: "(\<lambda>U. msgrel `` {freeleft U}) respects msgrel"
   261 lemma left_congruent: "(\<lambda>U. msgrel `` {freeleft U}) respects msgrel"
   262 by (auto simp add: congruent_def msgrel_imp_eqv_freeleft) 
   262 by (auto simp add: congruent_def msgrel_imp_eqv_freeleft) 
   263 
   263 
   264 text\<open>Now prove the four equations for @{term left}\<close>
   264 text\<open>Now prove the four equations for \<^term>\<open>left\<close>\<close>
   265 
   265 
   266 lemma left_Nonce [simp]: "left (Nonce N) = Nonce N"
   266 lemma left_Nonce [simp]: "left (Nonce N) = Nonce N"
   267 by (simp add: left_def Nonce_def 
   267 by (simp add: left_def Nonce_def 
   268               UN_equiv_class [OF equiv_msgrel left_congruent]) 
   268               UN_equiv_class [OF equiv_msgrel left_congruent]) 
   269 
   269 
   293    "right X = Abs_Msg (\<Union>U \<in> Rep_Msg X. msgrel``{freeright U})"
   293    "right X = Abs_Msg (\<Union>U \<in> Rep_Msg X. msgrel``{freeright U})"
   294 
   294 
   295 lemma right_congruent: "(\<lambda>U. msgrel `` {freeright U}) respects msgrel"
   295 lemma right_congruent: "(\<lambda>U. msgrel `` {freeright U}) respects msgrel"
   296 by (auto simp add: congruent_def msgrel_imp_eqv_freeright) 
   296 by (auto simp add: congruent_def msgrel_imp_eqv_freeright) 
   297 
   297 
   298 text\<open>Now prove the four equations for @{term right}\<close>
   298 text\<open>Now prove the four equations for \<^term>\<open>right\<close>\<close>
   299 
   299 
   300 lemma right_Nonce [simp]: "right (Nonce N) = Nonce N"
   300 lemma right_Nonce [simp]: "right (Nonce N) = Nonce N"
   301 by (simp add: right_def Nonce_def 
   301 by (simp add: right_def Nonce_def 
   302               UN_equiv_class [OF equiv_msgrel right_congruent]) 
   302               UN_equiv_class [OF equiv_msgrel right_congruent]) 
   303 
   303 
   323 subsection\<open>Injectivity Properties of Some Constructors\<close>
   323 subsection\<open>Injectivity Properties of Some Constructors\<close>
   324 
   324 
   325 lemma NONCE_imp_eq: "NONCE m \<sim> NONCE n \<Longrightarrow> m = n"
   325 lemma NONCE_imp_eq: "NONCE m \<sim> NONCE n \<Longrightarrow> m = n"
   326 by (drule msgrel_imp_eq_freenonces, simp)
   326 by (drule msgrel_imp_eq_freenonces, simp)
   327 
   327 
   328 text\<open>Can also be proved using the function @{term nonces}\<close>
   328 text\<open>Can also be proved using the function \<^term>\<open>nonces\<close>\<close>
   329 lemma Nonce_Nonce_eq [iff]: "(Nonce m = Nonce n) = (m = n)"
   329 lemma Nonce_Nonce_eq [iff]: "(Nonce m = Nonce n) = (m = n)"
   330 by (auto simp add: Nonce_def msgrel_refl dest: NONCE_imp_eq)
   330 by (auto simp add: Nonce_def msgrel_refl dest: NONCE_imp_eq)
   331 
   331 
   332 lemma MPAIR_imp_eqv_left: "MPAIR X Y \<sim> MPAIR X' Y' \<Longrightarrow> X \<sim> X'"
   332 lemma MPAIR_imp_eqv_left: "MPAIR X Y \<sim> MPAIR X' Y' \<Longrightarrow> X \<sim> X'"
   333 by (drule msgrel_imp_eqv_freeleft, simp)
   333 by (drule msgrel_imp_eqv_freeleft, simp)
   428    "discrim X = the_elem (\<Union>U \<in> Rep_Msg X. {freediscrim U})"
   428    "discrim X = the_elem (\<Union>U \<in> Rep_Msg X. {freediscrim U})"
   429 
   429 
   430 lemma discrim_congruent: "(\<lambda>U. {freediscrim U}) respects msgrel"
   430 lemma discrim_congruent: "(\<lambda>U. {freediscrim U}) respects msgrel"
   431 by (auto simp add: congruent_def msgrel_imp_eq_freediscrim) 
   431 by (auto simp add: congruent_def msgrel_imp_eq_freediscrim) 
   432 
   432 
   433 text\<open>Now prove the four equations for @{term discrim}\<close>
   433 text\<open>Now prove the four equations for \<^term>\<open>discrim\<close>\<close>
   434 
   434 
   435 lemma discrim_Nonce [simp]: "discrim (Nonce N) = 0"
   435 lemma discrim_Nonce [simp]: "discrim (Nonce N) = 0"
   436 by (simp add: discrim_def Nonce_def 
   436 by (simp add: discrim_def Nonce_def 
   437               UN_equiv_class [OF equiv_msgrel discrim_congruent]) 
   437               UN_equiv_class [OF equiv_msgrel discrim_congruent]) 
   438 
   438