src/HOL/Library/Ramsey.thy
changeset 73709 58bd53caf800
parent 73655 26a1d66b9077
child 76987 4c275405faae
equal deleted inserted replaced
73708:2e3a60ce5a9f 73709:58bd53caf800
     7 theory Ramsey
     7 theory Ramsey
     8   imports Infinite_Set FuncSet
     8   imports Infinite_Set FuncSet
     9 begin
     9 begin
    10 
    10 
    11 subsection \<open>Preliminary definitions\<close>
    11 subsection \<open>Preliminary definitions\<close>
       
    12 
       
    13 abbreviation strict_sorted :: "'a::linorder list \<Rightarrow> bool" where
       
    14   "strict_sorted \<equiv> sorted_wrt (<)" 
    12 
    15 
    13 subsubsection \<open>The $n$-element subsets of a set $A$\<close>
    16 subsubsection \<open>The $n$-element subsets of a set $A$\<close>
    14 
    17 
    15 definition nsets :: "['a set, nat] \<Rightarrow> 'a set set" ("([_]\<^bsup>_\<^esup>)" [0,999] 999)
    18 definition nsets :: "['a set, nat] \<Rightarrow> 'a set set" ("([_]\<^bsup>_\<^esup>)" [0,999] 999)
    16   where "nsets A n \<equiv> {N. N \<subseteq> A \<and> finite N \<and> card N = n}"
    19   where "nsets A n \<equiv> {N. N \<subseteq> A \<and> finite N \<and> card N = n}"
   990     with ij have k: "k = transition_idx s T {?i, ?j}" by (simp add: allk)
   993     with ij have k: "k = transition_idx s T {?i, ?j}" by (simp add: allk)
   991     from s_in_T [OF ij] obtain k' where "(s ?j, s ?i) \<in> T k'" "k'<n" by blast
   994     from s_in_T [OF ij] obtain k' where "(s ?j, s ?i) \<in> T k'" "k'<n" by blast
   992     then show "(s ?j, s ?i) \<in> T k" by (simp add: k transition_idx_in ij)
   995     then show "(s ?j, s ?i) \<in> T k" by (simp add: k transition_idx_in ij)
   993   qed
   996   qed
   994   then have "\<not> wf (T k)"
   997   then have "\<not> wf (T k)"
   995     by (meson wf_iff_no_infinite_down_chain)
   998     unfolding wf_iff_no_infinite_down_chain by iprover
   996   with wfT \<open>k < n\<close> show False by blast
   999   with wfT \<open>k < n\<close> show False by blast
   997 qed
  1000 qed
   998 
  1001 
   999 end
  1002 end