src/HOL/Integ/Equiv.ML
changeset 5143 b94cd208f073
parent 5069 3ea049f7979d
child 5148 74919e8f221c
equal deleted inserted replaced
5142:c56aa8b59dc0 5143:b94cd208f073
    47 Goalw [equiv_def,trans_def,sym_def]
    47 Goalw [equiv_def,trans_def,sym_def]
    48     "!!A r. [| equiv A r;  (a,b): r |] ==> r^^{a} <= r^^{b}";
    48     "!!A r. [| equiv A r;  (a,b): r |] ==> r^^{a} <= r^^{b}";
    49 by (Blast_tac 1);
    49 by (Blast_tac 1);
    50 qed "equiv_class_subset";
    50 qed "equiv_class_subset";
    51 
    51 
    52 Goal "!!A r. [| equiv A r;  (a,b): r |] ==> r^^{a} = r^^{b}";
    52 Goal "[| equiv A r;  (a,b): r |] ==> r^^{a} = r^^{b}";
    53 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1));
    53 by (REPEAT (ares_tac [equalityI, equiv_class_subset] 1));
    54 by (rewrite_goals_tac [equiv_def,sym_def]);
    54 by (rewrite_goals_tac [equiv_def,sym_def]);
    55 by (Blast_tac 1);
    55 by (Blast_tac 1);
    56 qed "equiv_class_eq";
    56 qed "equiv_class_eq";
    57 
    57 
    96 
    96 
    97 (*** Quotients ***)
    97 (*** Quotients ***)
    98 
    98 
    99 (** Introduction/elimination rules -- needed? **)
    99 (** Introduction/elimination rules -- needed? **)
   100 
   100 
   101 Goalw [quotient_def] "!!A. x:A ==> r^^{x}: A/r";
   101 Goalw [quotient_def] "x:A ==> r^^{x}: A/r";
   102 by (Blast_tac 1);
   102 by (Blast_tac 1);
   103 qed "quotientI";
   103 qed "quotientI";
   104 
   104 
   105 val [major,minor] = goalw Equiv.thy [quotient_def]
   105 val [major,minor] = goalw Equiv.thy [quotient_def]
   106     "[| X:(A/r);  !!x. [| X = r^^{x};  x:A |] ==> P |]  \
   106     "[| X:(A/r);  !!x. [| X = r^^{x};  x:A |] ==> P |]  \
   137 (** These proofs really require the local premises
   137 (** These proofs really require the local premises
   138      equiv A r;  congruent r b
   138      equiv A r;  congruent r b
   139 **)
   139 **)
   140 
   140 
   141 (*Conversion rule*)
   141 (*Conversion rule*)
   142 Goal "!!A r. [| equiv A r;  congruent r b;  a: A |] \
   142 Goal "[| equiv A r;  congruent r b;  a: A |] \
   143 \                      ==> (UN x:r^^{a}. b(x)) = b(a)";
   143 \                      ==> (UN x:r^^{a}. b(x)) = b(a)";
   144 by (rtac (equiv_class_self RS UN_singleton) 1 THEN REPEAT (assume_tac 1));
   144 by (rtac (equiv_class_self RS UN_singleton) 1 THEN REPEAT (assume_tac 1));
   145 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]);
   145 by (rewrite_goals_tac [equiv_def,congruent_def,sym_def]);
   146 by (Blast_tac 1);
   146 by (Blast_tac 1);
   147 qed "UN_equiv_class";
   147 qed "UN_equiv_class";
   242 
   242 
   243 
   243 
   244 (*** Cardinality results suggested by Florian Kammueller ***)
   244 (*** Cardinality results suggested by Florian Kammueller ***)
   245 
   245 
   246 (*Recall that  equiv A r  implies  r <= A Times A   (equiv_type) *)
   246 (*Recall that  equiv A r  implies  r <= A Times A   (equiv_type) *)
   247 Goal "!!A. [| finite A; r <= A Times A |] ==> finite (A/r)";
   247 Goal "[| finite A; r <= A Times A |] ==> finite (A/r)";
   248 by (rtac finite_subset 1);
   248 by (rtac finite_subset 1);
   249 by (etac (finite_Pow_iff RS iffD2) 2);
   249 by (etac (finite_Pow_iff RS iffD2) 2);
   250 by (rewtac quotient_def);
   250 by (rewtac quotient_def);
   251 by (Blast_tac 1);
   251 by (Blast_tac 1);
   252 qed "finite_quotient";
   252 qed "finite_quotient";
   256 by (rtac finite_subset 1);
   256 by (rtac finite_subset 1);
   257 by (assume_tac 2);
   257 by (assume_tac 2);
   258 by (Blast_tac 1);
   258 by (Blast_tac 1);
   259 qed "finite_equiv_class";
   259 qed "finite_equiv_class";
   260 
   260 
   261 Goal "!!A. [| finite A;  equiv A r;  ! X : A/r. k dvd card(X) |] \
   261 Goal "[| finite A;  equiv A r;  ! X : A/r. k dvd card(X) |] \
   262 \              ==> k dvd card(A)";
   262 \              ==> k dvd card(A)";
   263 by (rtac (Union_quotient RS subst) 1);
   263 by (rtac (Union_quotient RS subst) 1);
   264 by (assume_tac 1);
   264 by (assume_tac 1);
   265 by (rtac dvd_partition 1);
   265 by (rtac dvd_partition 1);
   266 by (blast_tac (claset() delrules [equalityI] addEs [quotient_disj RS disjE]) 4);
   266 by (blast_tac (claset() delrules [equalityI] addEs [quotient_disj RS disjE]) 4);