src/HOL/Real/PRat.ML
changeset 10834 a7897aebbffc
parent 10797 028d22926a41
child 11464 ddea204de5bc
equal deleted inserted replaced
10833:c0844a30ea4e 10834:a7897aebbffc
    59                        addSEs [sym, prat_trans_lemma]) 1);
    59                        addSEs [sym, prat_trans_lemma]) 1);
    60 qed "equiv_ratrel";
    60 qed "equiv_ratrel";
    61 
    61 
    62 bind_thm ("equiv_ratrel_iff", [equiv_ratrel, UNIV_I, UNIV_I] MRS eq_equiv_class_iff);
    62 bind_thm ("equiv_ratrel_iff", [equiv_ratrel, UNIV_I, UNIV_I] MRS eq_equiv_class_iff);
    63 
    63 
    64 Goalw  [prat_def,ratrel_def,quotient_def] "ratrel```{(x,y)}:prat";
    64 Goalw  [prat_def,ratrel_def,quotient_def] "ratrel``{(x,y)}:prat";
    65 by (Blast_tac 1);
    65 by (Blast_tac 1);
    66 qed "ratrel_in_prat";
    66 qed "ratrel_in_prat";
    67 
    67 
    68 Goal "inj_on Abs_prat prat";
    68 Goal "inj_on Abs_prat prat";
    69 by (rtac inj_on_inverseI 1);
    69 by (rtac inj_on_inverseI 1);
    93 by Safe_tac;
    93 by Safe_tac;
    94 by (Asm_full_simp_tac 1);
    94 by (Asm_full_simp_tac 1);
    95 qed "inj_prat_of_pnat";
    95 qed "inj_prat_of_pnat";
    96 
    96 
    97 val [prem] = Goal
    97 val [prem] = Goal
    98     "(!!x y. z = Abs_prat(ratrel```{(x,y)}) ==> P) ==> P";
    98     "(!!x y. z = Abs_prat(ratrel``{(x,y)}) ==> P) ==> P";
    99 by (res_inst_tac [("x1","z")] 
    99 by (res_inst_tac [("x1","z")] 
   100     (rewrite_rule [prat_def] Rep_prat RS quotientE) 1);
   100     (rewrite_rule [prat_def] Rep_prat RS quotientE) 1);
   101 by (dres_inst_tac [("f","Abs_prat")] arg_cong 1);
   101 by (dres_inst_tac [("f","Abs_prat")] arg_cong 1);
   102 by (res_inst_tac [("p","x")] PairE 1);
   102 by (res_inst_tac [("p","x")] PairE 1);
   103 by (rtac prem 1);
   103 by (rtac prem 1);
   104 by (asm_full_simp_tac (simpset() addsimps [Rep_prat_inverse]) 1);
   104 by (asm_full_simp_tac (simpset() addsimps [Rep_prat_inverse]) 1);
   105 qed "eq_Abs_prat";
   105 qed "eq_Abs_prat";
   106 
   106 
   107 (**** qinv: inverse on prat ****)
   107 (**** qinv: inverse on prat ****)
   108 
   108 
   109 Goalw [congruent_def] "congruent ratrel (%(x,y). ratrel```{(y,x)})";
   109 Goalw [congruent_def] "congruent ratrel (%(x,y). ratrel``{(y,x)})";
   110 by (auto_tac (claset(), simpset() addsimps [pnat_mult_commute]));  
   110 by (auto_tac (claset(), simpset() addsimps [pnat_mult_commute]));  
   111 qed "qinv_congruent";
   111 qed "qinv_congruent";
   112 
   112 
   113 Goalw [qinv_def]
   113 Goalw [qinv_def]
   114       "qinv (Abs_prat(ratrel```{(x,y)})) = Abs_prat(ratrel ``` {(y,x)})";
   114       "qinv (Abs_prat(ratrel``{(x,y)})) = Abs_prat(ratrel `` {(y,x)})";
   115 by (simp_tac (simpset() addsimps 
   115 by (simp_tac (simpset() addsimps 
   116 	      [equiv_ratrel RS UN_equiv_class, qinv_congruent]) 1);
   116 	      [equiv_ratrel RS UN_equiv_class, qinv_congruent]) 1);
   117 qed "qinv";
   117 qed "qinv";
   118 
   118 
   119 Goal "qinv (qinv z) = z";
   119 Goal "qinv (qinv z) = z";
   143 by (res_inst_tac [("y1","x1")] (pnat_mult_left_commute RS ssubst) 1);
   143 by (res_inst_tac [("y1","x1")] (pnat_mult_left_commute RS ssubst) 1);
   144 by (auto_tac (claset(),simpset() addsimps [pnat_mult_assoc RS sym]));
   144 by (auto_tac (claset(),simpset() addsimps [pnat_mult_assoc RS sym]));
   145 qed "prat_add_congruent2_lemma";
   145 qed "prat_add_congruent2_lemma";
   146 
   146 
   147 Goal "congruent2 ratrel (%p1 p2.                  \
   147 Goal "congruent2 ratrel (%p1 p2.                  \
   148 \        (%(x1,y1). (%(x2,y2). ratrel```{(x1*y2 + x2*y1, y1*y2)}) p2) p1)";
   148 \        (%(x1,y1). (%(x2,y2). ratrel``{(x1*y2 + x2*y1, y1*y2)}) p2) p1)";
   149 by (rtac (equiv_ratrel RS congruent2_commuteI) 1);
   149 by (rtac (equiv_ratrel RS congruent2_commuteI) 1);
   150 by (auto_tac (claset() delrules [equalityI],
   150 by (auto_tac (claset() delrules [equalityI],
   151               simpset() addsimps [prat_add_congruent2_lemma]));
   151               simpset() addsimps [prat_add_congruent2_lemma]));
   152 by (asm_simp_tac (simpset() addsimps [pnat_mult_commute,pnat_add_commute]) 1);
   152 by (asm_simp_tac (simpset() addsimps [pnat_mult_commute,pnat_add_commute]) 1);
   153 qed "prat_add_congruent2";
   153 qed "prat_add_congruent2";
   154 
   154 
   155 Goalw [prat_add_def]
   155 Goalw [prat_add_def]
   156    "Abs_prat((ratrel```{(x1,y1)})) + Abs_prat((ratrel```{(x2,y2)})) =   \
   156    "Abs_prat((ratrel``{(x1,y1)})) + Abs_prat((ratrel``{(x2,y2)})) =   \
   157 \   Abs_prat(ratrel ``` {(x1*y2 + x2*y1, y1*y2)})";
   157 \   Abs_prat(ratrel `` {(x1*y2 + x2*y1, y1*y2)})";
   158 by (simp_tac (simpset() addsimps [UN_UN_split_split_eq, prat_add_congruent2, 
   158 by (simp_tac (simpset() addsimps [UN_UN_split_split_eq, prat_add_congruent2, 
   159 				  equiv_ratrel RS UN_equiv_class2]) 1);
   159 				  equiv_ratrel RS UN_equiv_class2]) 1);
   160 qed "prat_add";
   160 qed "prat_add";
   161 
   161 
   162 Goal "(z::prat) + w = w + z";
   162 Goal "(z::prat) + w = w + z";
   187 
   187 
   188 (*** Congruence property for multiplication ***)
   188 (*** Congruence property for multiplication ***)
   189 
   189 
   190 Goalw [congruent2_def]
   190 Goalw [congruent2_def]
   191     "congruent2 ratrel (%p1 p2.                  \
   191     "congruent2 ratrel (%p1 p2.                  \
   192 \         (%(x1,y1). (%(x2,y2). ratrel```{(x1*x2, y1*y2)}) p2) p1)";
   192 \         (%(x1,y1). (%(x2,y2). ratrel``{(x1*x2, y1*y2)}) p2) p1)";
   193 (*Proof via congruent2_commuteI seems longer*)
   193 (*Proof via congruent2_commuteI seems longer*)
   194 by (Clarify_tac 1);
   194 by (Clarify_tac 1);
   195 by (asm_simp_tac (simpset() addsimps [pnat_mult_assoc]) 1);
   195 by (asm_simp_tac (simpset() addsimps [pnat_mult_assoc]) 1);
   196 (*The rest should be trivial, but rearranging terms is hard*)
   196 (*The rest should be trivial, but rearranging terms is hard*)
   197 by (res_inst_tac [("x1","x1a")] (pnat_mult_left_commute RS ssubst) 1);
   197 by (res_inst_tac [("x1","x1a")] (pnat_mult_left_commute RS ssubst) 1);
   198 by (asm_simp_tac (simpset() addsimps [pnat_mult_assoc RS sym]) 1);
   198 by (asm_simp_tac (simpset() addsimps [pnat_mult_assoc RS sym]) 1);
   199 by (asm_simp_tac (simpset() addsimps pnat_mult_ac) 1);
   199 by (asm_simp_tac (simpset() addsimps pnat_mult_ac) 1);
   200 qed "pnat_mult_congruent2";
   200 qed "pnat_mult_congruent2";
   201 
   201 
   202 Goalw [prat_mult_def]
   202 Goalw [prat_mult_def]
   203   "Abs_prat(ratrel```{(x1,y1)}) * Abs_prat(ratrel```{(x2,y2)}) = \
   203   "Abs_prat(ratrel``{(x1,y1)}) * Abs_prat(ratrel``{(x2,y2)}) = \
   204 \  Abs_prat(ratrel```{(x1*x2, y1*y2)})";
   204 \  Abs_prat(ratrel``{(x1*x2, y1*y2)})";
   205 by (asm_simp_tac 
   205 by (asm_simp_tac 
   206     (simpset() addsimps [UN_UN_split_split_eq, pnat_mult_congruent2,
   206     (simpset() addsimps [UN_UN_split_split_eq, pnat_mult_congruent2,
   207 			 equiv_ratrel RS UN_equiv_class2]) 1);
   207 			 equiv_ratrel RS UN_equiv_class2]) 1);
   208 qed "prat_mult";
   208 qed "prat_mult";
   209 
   209 
   387 
   387 
   388 (* half of positive fraction exists- Gleason p. 120- Proposition 9-2.6(i)*)
   388 (* half of positive fraction exists- Gleason p. 120- Proposition 9-2.6(i)*)
   389 Goal "!(q::prat). EX x. x + x = q";
   389 Goal "!(q::prat). EX x. x + x = q";
   390 by (rtac allI 1);
   390 by (rtac allI 1);
   391 by (res_inst_tac [("z","q")] eq_Abs_prat 1);
   391 by (res_inst_tac [("z","q")] eq_Abs_prat 1);
   392 by (res_inst_tac [("x","Abs_prat (ratrel ``` {(x, y+y)})")] exI 1);
   392 by (res_inst_tac [("x","Abs_prat (ratrel `` {(x, y+y)})")] exI 1);
   393 by (auto_tac (claset(),
   393 by (auto_tac (claset(),
   394 	      simpset() addsimps 
   394 	      simpset() addsimps 
   395               [prat_add,pnat_mult_assoc RS sym,pnat_add_mult_distrib,
   395               [prat_add,pnat_mult_assoc RS sym,pnat_add_mult_distrib,
   396                pnat_add_mult_distrib2]));
   396                pnat_add_mult_distrib2]));
   397 qed "lemma_prat_dense";
   397 qed "lemma_prat_dense";
   398 
   398 
   399 Goal "EX (x::prat). x + x = q";
   399 Goal "EX (x::prat). x + x = q";
   400 by (res_inst_tac [("z","q")] eq_Abs_prat 1);
   400 by (res_inst_tac [("z","q")] eq_Abs_prat 1);
   401 by (res_inst_tac [("x","Abs_prat (ratrel ``` {(x, y+y)})")] exI 1);
   401 by (res_inst_tac [("x","Abs_prat (ratrel `` {(x, y+y)})")] exI 1);
   402 by (auto_tac (claset(),simpset() addsimps 
   402 by (auto_tac (claset(),simpset() addsimps 
   403               [prat_add,pnat_mult_assoc RS sym,pnat_add_mult_distrib,
   403               [prat_add,pnat_mult_assoc RS sym,pnat_add_mult_distrib,
   404                pnat_add_mult_distrib2]));
   404                pnat_add_mult_distrib2]));
   405 qed "prat_lemma_dense";
   405 qed "prat_lemma_dense";
   406 
   406 
   452 by (Fast_tac 1);
   452 by (Fast_tac 1);
   453 qed "qless_Ex";
   453 qed "qless_Ex";
   454 
   454 
   455 (* lemma for proving $< is linear *)
   455 (* lemma for proving $< is linear *)
   456 Goalw [prat_def,prat_less_def] 
   456 Goalw [prat_def,prat_less_def] 
   457       "ratrel ``` {(x, y * ya)} : {p::(pnat*pnat).True}//ratrel";
   457       "ratrel `` {(x, y * ya)} : {p::(pnat*pnat).True}//ratrel";
   458 by (asm_full_simp_tac (simpset() addsimps [ratrel_def,quotient_def]) 1);
   458 by (asm_full_simp_tac (simpset() addsimps [ratrel_def,quotient_def]) 1);
   459 by (Blast_tac 1);
   459 by (Blast_tac 1);
   460 qed "lemma_prat_less_linear";
   460 qed "lemma_prat_less_linear";
   461 
   461 
   462 (* linearity of < -- Gleason p. 120 - Proposition 9-2.6 *)
   462 (* linearity of < -- Gleason p. 120 - Proposition 9-2.6 *)
   468 by (Step_tac 1 THEN REPEAT(dtac (not_ex RS iffD1) 1) 
   468 by (Step_tac 1 THEN REPEAT(dtac (not_ex RS iffD1) 1) 
   469                THEN Auto_tac);
   469                THEN Auto_tac);
   470 by (cut_inst_tac  [("z1.0","x*ya"), ("z2.0","xa*y")] pnat_linear_Ex_eq 1);
   470 by (cut_inst_tac  [("z1.0","x*ya"), ("z2.0","xa*y")] pnat_linear_Ex_eq 1);
   471 by (EVERY1[etac disjE,etac exE]);
   471 by (EVERY1[etac disjE,etac exE]);
   472 by (eres_inst_tac 
   472 by (eres_inst_tac 
   473     [("x","Abs_prat(ratrel```{(xb,ya*y)})")] allE 1);
   473     [("x","Abs_prat(ratrel``{(xb,ya*y)})")] allE 1);
   474 by (asm_full_simp_tac 
   474 by (asm_full_simp_tac 
   475     (simpset() addsimps [prat_add, pnat_mult_assoc 
   475     (simpset() addsimps [prat_add, pnat_mult_assoc 
   476      RS sym,pnat_add_mult_distrib RS sym]) 1);
   476      RS sym,pnat_add_mult_distrib RS sym]) 1);
   477 by (EVERY1[asm_full_simp_tac (simpset() addsimps pnat_mult_ac),
   477 by (EVERY1[asm_full_simp_tac (simpset() addsimps pnat_mult_ac),
   478     etac disjE, assume_tac, etac exE]);
   478     etac disjE, assume_tac, etac exE]);
   479 by (thin_tac "!T. Abs_prat (ratrel ``` {(x, y)}) + T ~= \
   479 by (thin_tac "!T. Abs_prat (ratrel `` {(x, y)}) + T ~= \
   480 \     Abs_prat (ratrel ``` {(xa, ya)})" 1);
   480 \     Abs_prat (ratrel `` {(xa, ya)})" 1);
   481 by (eres_inst_tac [("x","Abs_prat(ratrel```{(xb,y*ya)})")] allE 1);
   481 by (eres_inst_tac [("x","Abs_prat(ratrel``{(xb,y*ya)})")] allE 1);
   482 by (asm_full_simp_tac (simpset() addsimps [prat_add,
   482 by (asm_full_simp_tac (simpset() addsimps [prat_add,
   483       pnat_mult_assoc RS sym,pnat_add_mult_distrib RS sym]) 1);
   483       pnat_mult_assoc RS sym,pnat_add_mult_distrib RS sym]) 1);
   484 by (asm_full_simp_tac (simpset() addsimps pnat_mult_ac) 1);
   484 by (asm_full_simp_tac (simpset() addsimps pnat_mult_ac) 1);
   485 qed "prat_linear";
   485 qed "prat_linear";
   486 
   486 
   694 by (asm_full_simp_tac (simpset() addsimps [prat_add_commute]) 1);
   694 by (asm_full_simp_tac (simpset() addsimps [prat_add_commute]) 1);
   695 qed "prat_add_left_less_cancel";
   695 qed "prat_add_left_less_cancel";
   696 
   696 
   697 (*** lemmas required for lemma_gleason9_34 in PReal : w*y > y/z ***)
   697 (*** lemmas required for lemma_gleason9_34 in PReal : w*y > y/z ***)
   698 Goalw [prat_of_pnat_def] 
   698 Goalw [prat_of_pnat_def] 
   699       "Abs_prat(ratrel```{(x,y)}) = (prat_of_pnat x)*qinv(prat_of_pnat y)";
   699       "Abs_prat(ratrel``{(x,y)}) = (prat_of_pnat x)*qinv(prat_of_pnat y)";
   700 by (auto_tac (claset(),simpset() addsimps [prat_mult,qinv,pnat_mult_1_left,
   700 by (auto_tac (claset(),simpset() addsimps [prat_mult,qinv,pnat_mult_1_left,
   701     pnat_mult_1]));
   701     pnat_mult_1]));
   702 qed "Abs_prat_mult_qinv";
   702 qed "Abs_prat_mult_qinv";
   703 
   703 
   704 Goal "Abs_prat(ratrel```{(x,y)}) <= Abs_prat(ratrel```{(x,Abs_pnat 1)})";
   704 Goal "Abs_prat(ratrel``{(x,y)}) <= Abs_prat(ratrel``{(x,Abs_pnat 1)})";
   705 by (simp_tac (simpset() addsimps [Abs_prat_mult_qinv]) 1);
   705 by (simp_tac (simpset() addsimps [Abs_prat_mult_qinv]) 1);
   706 by (rtac prat_mult_left_le2_mono1 1);
   706 by (rtac prat_mult_left_le2_mono1 1);
   707 by (rtac qinv_prat_le 1);
   707 by (rtac qinv_prat_le 1);
   708 by (pnat_ind_tac "y" 1);
   708 by (pnat_ind_tac "y" 1);
   709 by (dres_inst_tac [("x","prat_of_pnat (Abs_pnat 1)")] prat_add_le2_mono1 2);
   709 by (dres_inst_tac [("x","prat_of_pnat (Abs_pnat 1)")] prat_add_le2_mono1 2);
   711 by (auto_tac (claset() addIs [prat_le_trans],
   711 by (auto_tac (claset() addIs [prat_le_trans],
   712     simpset() addsimps [prat_le_refl,
   712     simpset() addsimps [prat_le_refl,
   713     pSuc_is_plus_one,pnat_one_def,prat_of_pnat_add]));
   713     pSuc_is_plus_one,pnat_one_def,prat_of_pnat_add]));
   714 qed "lemma_Abs_prat_le1";
   714 qed "lemma_Abs_prat_le1";
   715 
   715 
   716 Goal "Abs_prat(ratrel```{(x,Abs_pnat 1)}) <= Abs_prat(ratrel```{(x*y,Abs_pnat 1)})";
   716 Goal "Abs_prat(ratrel``{(x,Abs_pnat 1)}) <= Abs_prat(ratrel``{(x*y,Abs_pnat 1)})";
   717 by (simp_tac (simpset() addsimps [Abs_prat_mult_qinv]) 1);
   717 by (simp_tac (simpset() addsimps [Abs_prat_mult_qinv]) 1);
   718 by (rtac prat_mult_le2_mono1 1);
   718 by (rtac prat_mult_le2_mono1 1);
   719 by (pnat_ind_tac "y" 1);
   719 by (pnat_ind_tac "y" 1);
   720 by (dres_inst_tac [("x","prat_of_pnat x")] prat_add_le2_mono1 2);
   720 by (dres_inst_tac [("x","prat_of_pnat x")] prat_add_le2_mono1 2);
   721 by (cut_inst_tac [("z","prat_of_pnat x")] (prat_self_less_add_self 
   721 by (cut_inst_tac [("z","prat_of_pnat x")] (prat_self_less_add_self 
   724     simpset() addsimps [prat_le_refl,
   724     simpset() addsimps [prat_le_refl,
   725 			pSuc_is_plus_one,pnat_one_def,prat_add_mult_distrib2,
   725 			pSuc_is_plus_one,pnat_one_def,prat_add_mult_distrib2,
   726 			prat_of_pnat_add,prat_of_pnat_mult]));
   726 			prat_of_pnat_add,prat_of_pnat_mult]));
   727 qed "lemma_Abs_prat_le2";
   727 qed "lemma_Abs_prat_le2";
   728 
   728 
   729 Goal "Abs_prat(ratrel```{(x,z)}) <= Abs_prat(ratrel```{(x*y,Abs_pnat 1)})";
   729 Goal "Abs_prat(ratrel``{(x,z)}) <= Abs_prat(ratrel``{(x*y,Abs_pnat 1)})";
   730 by (fast_tac (claset() addIs [prat_le_trans,
   730 by (fast_tac (claset() addIs [prat_le_trans,
   731 			      lemma_Abs_prat_le1,lemma_Abs_prat_le2]) 1);
   731 			      lemma_Abs_prat_le1,lemma_Abs_prat_le2]) 1);
   732 qed "lemma_Abs_prat_le3";
   732 qed "lemma_Abs_prat_le3";
   733 
   733 
   734 Goal "Abs_prat(ratrel```{(x*y,Abs_pnat 1)}) * Abs_prat(ratrel```{(w,x)}) = \
   734 Goal "Abs_prat(ratrel``{(x*y,Abs_pnat 1)}) * Abs_prat(ratrel``{(w,x)}) = \
   735 \         Abs_prat(ratrel```{(w*y,Abs_pnat 1)})";
   735 \         Abs_prat(ratrel``{(w*y,Abs_pnat 1)})";
   736 by (full_simp_tac (simpset() addsimps [prat_mult,
   736 by (full_simp_tac (simpset() addsimps [prat_mult,
   737     pnat_mult_1,pnat_mult_1_left] @ pnat_mult_ac) 1);
   737     pnat_mult_1,pnat_mult_1_left] @ pnat_mult_ac) 1);
   738 qed "pre_lemma_gleason9_34";
   738 qed "pre_lemma_gleason9_34";
   739 
   739 
   740 Goal "Abs_prat(ratrel```{(y*x,Abs_pnat 1*y)}) = \
   740 Goal "Abs_prat(ratrel``{(y*x,Abs_pnat 1*y)}) = \
   741 \         Abs_prat(ratrel```{(x,Abs_pnat 1)})";
   741 \         Abs_prat(ratrel``{(x,Abs_pnat 1)})";
   742 by (auto_tac (claset(),
   742 by (auto_tac (claset(),
   743 	      simpset() addsimps [pnat_mult_1,pnat_mult_1_left] @ pnat_mult_ac));
   743 	      simpset() addsimps [pnat_mult_1,pnat_mult_1_left] @ pnat_mult_ac));
   744 qed "pre_lemma_gleason9_34b";
   744 qed "pre_lemma_gleason9_34b";
   745 
   745 
   746 Goal "(prat_of_pnat n < prat_of_pnat m) = (n < m)";
   746 Goal "(prat_of_pnat n < prat_of_pnat m) = (n < m)";