src/ZF/ex/Ramsey.ML
changeset 4152 451104c223e2
parent 4091 771b1f6422a8
child 5068 fb28eaa07e01
equal deleted inserted replaced
4151:5c19cd418c33 4152:451104c223e2
    86 by (rtac ballI 1);
    86 by (rtac ballI 1);
    87 by (rename_tac "n" 1);          (*simplifier does NOT preserve bound names!*)
    87 by (rename_tac "n" 1);          (*simplifier does NOT preserve bound names!*)
    88 by (nat_ind_tac "n" [] 1);
    88 by (nat_ind_tac "n" [] 1);
    89 by (fast_tac (claset() addSIs [Atleast0]) 1);
    89 by (fast_tac (claset() addSIs [Atleast0]) 1);
    90 by (asm_simp_tac (simpset() addsimps [add_succ_right]) 1);
    90 by (asm_simp_tac (simpset() addsimps [add_succ_right]) 1);
    91 by (safe_tac (claset()));
    91 by Safe_tac;
    92 by (etac (Atleast_succD RS bexE) 1);
    92 by (etac (Atleast_succD RS bexE) 1);
    93 by (etac UnE 1);
    93 by (etac UnE 1);
    94 (**case x:B.  Instantiate the 'ALL A B' induction hypothesis. **)
    94 (**case x:B.  Instantiate the 'ALL A B' induction hypothesis. **)
    95 by (dres_inst_tac [("x1","A"), ("x","B-{x}")] (spec RS spec) 2);
    95 by (dres_inst_tac [("x1","A"), ("x","B-{x}")] (spec RS spec) 2);
    96 by (etac (mp RS disjE) 2);
    96 by (etac (mp RS disjE) 2);
   163 (*Published proofs gloss over the need for Ramsey numbers to be POSITIVE.*)
   163 (*Published proofs gloss over the need for Ramsey numbers to be POSITIVE.*)
   164 val ram1::ram2::prems = goalw Ramsey.thy [Ramsey_def] 
   164 val ram1::ram2::prems = goalw Ramsey.thy [Ramsey_def] 
   165    "[| Ramsey(succ(m), succ(i), j);  Ramsey(n, i, succ(j));  \
   165    "[| Ramsey(succ(m), succ(i), j);  Ramsey(n, i, succ(j));  \
   166 \      m: nat;  n: nat |] ==> \
   166 \      m: nat;  n: nat |] ==> \
   167 \   Ramsey(succ(m#+n), succ(i), succ(j))";
   167 \   Ramsey(succ(m#+n), succ(i), succ(j))";
   168 by (safe_tac (claset()));
   168 by Safe_tac;
   169 by (etac (Atleast_succD RS bexE) 1);
   169 by (etac (Atleast_succD RS bexE) 1);
   170 by (eres_inst_tac [("P1","%z.<x,z>:E")] (Atleast_partition RS disjE) 1);
   170 by (eres_inst_tac [("P1","%z.<x,z>:E")] (Atleast_partition RS disjE) 1);
   171 by (REPEAT (resolve_tac prems 1));
   171 by (REPEAT (resolve_tac prems 1));
   172 (*case m*)
   172 (*case m*)
   173 by (rtac (ram1 RS spec RS spec RS mp RS disjE) 1);
   173 by (rtac (ram1 RS spec RS spec RS mp RS disjE) 1);
   174 by (Fast_tac 1);
   174 by (Fast_tac 1);
   175 by (fast_tac (claset() addEs [Clique_superset]) 1); (*easy -- given a Clique*)
   175 by (fast_tac (claset() addEs [Clique_superset]) 1); (*easy -- given a Clique*)
   176 by (safe_tac (claset()));
   176 by Safe_tac;
   177 by (eresolve_tac (swapify [exI]) 1);             (*ignore main EX quantifier*)
   177 by (eresolve_tac (swapify [exI]) 1);             (*ignore main EX quantifier*)
   178 by (REPEAT (ares_tac [Indept_succ] 1));          (*make a bigger Indept*)
   178 by (REPEAT (ares_tac [Indept_succ] 1));          (*make a bigger Indept*)
   179 (*case n*)
   179 (*case n*)
   180 by (rtac (ram2 RS spec RS spec RS mp RS disjE) 1);
   180 by (rtac (ram2 RS spec RS spec RS mp RS disjE) 1);
   181 by (Fast_tac 1);
   181 by (Fast_tac 1);
   182 by (safe_tac (claset()));
   182 by Safe_tac;
   183 by (rtac exI 1);
   183 by (rtac exI 1);
   184 by (REPEAT (ares_tac [Clique_succ] 1));          (*make a bigger Clique*)
   184 by (REPEAT (ares_tac [Clique_succ] 1));          (*make a bigger Clique*)
   185 by (fast_tac (claset() addEs [Indept_superset]) 1); (*easy -- given an Indept*)
   185 by (fast_tac (claset() addEs [Indept_superset]) 1); (*easy -- given an Indept*)
   186 qed "Ramsey_step_lemma";
   186 qed "Ramsey_step_lemma";
   187 
   187