src/HOL/Integ/Equiv.ML
changeset 10834 a7897aebbffc
parent 10797 028d22926a41
child 13482 2bb7200a99cf
equal deleted inserted replaced
10833:c0844a30ea4e 10834:a7897aebbffc
    35 
    35 
    36 (** Equivalence classes **)
    36 (** Equivalence classes **)
    37 
    37 
    38 (*Lemma for the next result*)
    38 (*Lemma for the next result*)
    39 Goalw [equiv_def,trans_def,sym_def]
    39 Goalw [equiv_def,trans_def,sym_def]
    40      "[| equiv A r;  (a,b): r |] ==> r```{a} <= r```{b}";
    40      "[| equiv A r;  (a,b): r |] ==> r``{a} <= r``{b}";
    41 by (Blast_tac 1);
    41 by (Blast_tac 1);
    42 qed "equiv_class_subset";
    42 qed "equiv_class_subset";
    43 
    43 
    44 Goal "[| equiv A r;  (a,b): r |] ==> r```{a} = r```{b}";
    44 Goal "[| equiv A r;  (a,b): r |] ==> r``{a} = r``{b}";
    45 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1));
    45 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1));
    46 by (rewrite_goals_tac [equiv_def,sym_def]);
    46 by (rewrite_goals_tac [equiv_def,sym_def]);
    47 by (Blast_tac 1);
    47 by (Blast_tac 1);
    48 qed "equiv_class_eq";
    48 qed "equiv_class_eq";
    49 
    49 
    50 Goalw [equiv_def,refl_def] "[| equiv A r;  a: A |] ==> a: r```{a}";
    50 Goalw [equiv_def,refl_def] "[| equiv A r;  a: A |] ==> a: r``{a}";
    51 by (Blast_tac 1);
    51 by (Blast_tac 1);
    52 qed "equiv_class_self";
    52 qed "equiv_class_self";
    53 
    53 
    54 (*Lemma for the next result*)
    54 (*Lemma for the next result*)
    55 Goalw [equiv_def,refl_def]
    55 Goalw [equiv_def,refl_def]
    56     "[| equiv A r;  r```{b} <= r```{a};  b: A |] ==> (a,b): r";
    56     "[| equiv A r;  r``{b} <= r``{a};  b: A |] ==> (a,b): r";
    57 by (Blast_tac 1);
    57 by (Blast_tac 1);
    58 qed "subset_equiv_class";
    58 qed "subset_equiv_class";
    59 
    59 
    60 Goal "[| r```{a} = r```{b};  equiv A r;  b: A |] ==> (a,b): r";
    60 Goal "[| r``{a} = r``{b};  equiv A r;  b: A |] ==> (a,b): r";
    61 by (REPEAT (ares_tac [equalityD2, subset_equiv_class] 1));
    61 by (REPEAT (ares_tac [equalityD2, subset_equiv_class] 1));
    62 qed "eq_equiv_class";
    62 qed "eq_equiv_class";
    63 
    63 
    64 (*thus r```{a} = r```{b} as well*)
    64 (*thus r``{a} = r``{b} as well*)
    65 Goalw [equiv_def,trans_def,sym_def]
    65 Goalw [equiv_def,trans_def,sym_def]
    66      "[| equiv A r;  x: (r```{a} Int r```{b}) |] ==> (a,b): r";
    66      "[| equiv A r;  x: (r``{a} Int r``{b}) |] ==> (a,b): r";
    67 by (Blast_tac 1);
    67 by (Blast_tac 1);
    68 qed "equiv_class_nondisjoint";
    68 qed "equiv_class_nondisjoint";
    69 
    69 
    70 Goalw [equiv_def,refl_def] "equiv A r ==> r <= A <*> A";
    70 Goalw [equiv_def,refl_def] "equiv A r ==> r <= A <*> A";
    71 by (Blast_tac 1);
    71 by (Blast_tac 1);
    72 qed "equiv_type";
    72 qed "equiv_type";
    73 
    73 
    74 Goal "equiv A r ==> ((x,y): r) = (r```{x} = r```{y} & x:A & y:A)";
    74 Goal "equiv A r ==> ((x,y): r) = (r``{x} = r``{y} & x:A & y:A)";
    75 by (blast_tac (claset() addSIs [equiv_class_eq]
    75 by (blast_tac (claset() addSIs [equiv_class_eq]
    76 	                addDs [eq_equiv_class, equiv_type]) 1);
    76 	                addDs [eq_equiv_class, equiv_type]) 1);
    77 qed "equiv_class_eq_iff";
    77 qed "equiv_class_eq_iff";
    78 
    78 
    79 Goal "[| equiv A r;  x: A;  y: A |] ==> (r```{x} = r```{y}) = ((x,y): r)";
    79 Goal "[| equiv A r;  x: A;  y: A |] ==> (r``{x} = r``{y}) = ((x,y): r)";
    80 by (blast_tac (claset() addSIs [equiv_class_eq]
    80 by (blast_tac (claset() addSIs [equiv_class_eq]
    81 	                addDs [eq_equiv_class, equiv_type]) 1);
    81 	                addDs [eq_equiv_class, equiv_type]) 1);
    82 qed "eq_equiv_class_iff";
    82 qed "eq_equiv_class_iff";
    83 
    83 
    84 (*** Quotients ***)
    84 (*** Quotients ***)
    85 
    85 
    86 (** Introduction/elimination rules -- needed? **)
    86 (** Introduction/elimination rules -- needed? **)
    87 
    87 
    88 Goalw [quotient_def] "x:A ==> r```{x}: A//r";
    88 Goalw [quotient_def] "x:A ==> r``{x}: A//r";
    89 by (Blast_tac 1);
    89 by (Blast_tac 1);
    90 qed "quotientI";
    90 qed "quotientI";
    91 
    91 
    92 val [major,minor] = Goalw [quotient_def]
    92 val [major,minor] = Goalw [quotient_def]
    93     "[| X:(A//r);  !!x. [| X = r```{x};  x:A |] ==> P |]  \
    93     "[| X:(A//r);  !!x. [| X = r``{x};  x:A |] ==> P |]  \
    94 \    ==> P";
    94 \    ==> P";
    95 by (resolve_tac [major RS UN_E] 1);
    95 by (resolve_tac [major RS UN_E] 1);
    96 by (rtac minor 1);
    96 by (rtac minor 1);
    97 by (assume_tac 2);
    97 by (assume_tac 2);
    98 by (Fast_tac 1);   (*Blast_tac FAILS to prove it*)
    98 by (Fast_tac 1);   (*Blast_tac FAILS to prove it*)
   125      equiv A r;  congruent r b
   125      equiv A r;  congruent r b
   126 **)
   126 **)
   127 
   127 
   128 (*Conversion rule*)
   128 (*Conversion rule*)
   129 Goal "[| equiv A r;  congruent r b;  a: A |] \
   129 Goal "[| equiv A r;  congruent r b;  a: A |] \
   130 \     ==> (UN x:r```{a}. b(x)) = b(a)";
   130 \     ==> (UN x:r``{a}. b(x)) = b(a)";
   131 by (rtac (equiv_class_self RS UN_constant_eq) 1 THEN REPEAT (assume_tac 1));
   131 by (rtac (equiv_class_self RS UN_constant_eq) 1 THEN REPEAT (assume_tac 1));
   132 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]);
   132 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]);
   133 by (blast_tac (claset() delrules [equalityI]) 1);
   133 by (blast_tac (claset() delrules [equalityI]) 1);
   134 qed "UN_equiv_class";
   134 qed "UN_equiv_class";
   135 
   135 
   136 (*type checking of  UN x:r``{a}. b(x) *)
   136 (*type checking of  UN x:r`{a}. b(x) *)
   137 val prems = Goalw [quotient_def]
   137 val prems = Goalw [quotient_def]
   138     "[| equiv A r;  congruent r b;  X: A//r;     \
   138     "[| equiv A r;  congruent r b;  X: A//r;     \
   139 \       !!x.  x : A ==> b(x) : B |]             \
   139 \       !!x.  x : A ==> b(x) : B |]             \
   140 \    ==> (UN x:X. b(x)) : B";
   140 \    ==> (UN x:X. b(x)) : B";
   141 by (cut_facts_tac prems 1);
   141 by (cut_facts_tac prems 1);
   169 by (Blast_tac 1);
   169 by (Blast_tac 1);
   170 qed "congruent2_implies_congruent";
   170 qed "congruent2_implies_congruent";
   171 
   171 
   172 Goalw [congruent_def]
   172 Goalw [congruent_def]
   173     "[| equiv A r;  congruent2 r b;  a: A |] ==> \
   173     "[| equiv A r;  congruent2 r b;  a: A |] ==> \
   174 \    congruent r (%x1. UN x2:r```{a}. b x1 x2)";
   174 \    congruent r (%x1. UN x2:r``{a}. b x1 x2)";
   175 by (Clarify_tac 1);
   175 by (Clarify_tac 1);
   176 by (rtac (equiv_type RS subsetD RS SigmaE2) 1 THEN REPEAT (assume_tac 1));
   176 by (rtac (equiv_type RS subsetD RS SigmaE2) 1 THEN REPEAT (assume_tac 1));
   177 by (asm_simp_tac (simpset() addsimps [UN_equiv_class,
   177 by (asm_simp_tac (simpset() addsimps [UN_equiv_class,
   178                                      congruent2_implies_congruent]) 1);
   178                                      congruent2_implies_congruent]) 1);
   179 by (rewrite_goals_tac [congruent2_def,equiv_def,refl_def]);
   179 by (rewrite_goals_tac [congruent2_def,equiv_def,refl_def]);
   180 by (blast_tac (claset() delrules [equalityI]) 1);
   180 by (blast_tac (claset() delrules [equalityI]) 1);
   181 qed "congruent2_implies_congruent_UN";
   181 qed "congruent2_implies_congruent_UN";
   182 
   182 
   183 Goal "[| equiv A r;  congruent2 r b;  a1: A;  a2: A |]  \
   183 Goal "[| equiv A r;  congruent2 r b;  a1: A;  a2: A |]  \
   184 \    ==> (UN x1:r```{a1}. UN x2:r```{a2}. b x1 x2) = b a1 a2";
   184 \    ==> (UN x1:r``{a1}. UN x2:r``{a2}. b x1 x2) = b a1 a2";
   185 by (asm_simp_tac (simpset() addsimps [UN_equiv_class,
   185 by (asm_simp_tac (simpset() addsimps [UN_equiv_class,
   186                                      congruent2_implies_congruent,
   186                                      congruent2_implies_congruent,
   187                                      congruent2_implies_congruent_UN]) 1);
   187                                      congruent2_implies_congruent_UN]) 1);
   188 qed "UN_equiv_class2";
   188 qed "UN_equiv_class2";
   189 
   189