src/HOL/Library/Ramsey.thy
changeset 44890 22f665a2e91c
parent 40695 1b2573c3b222
child 46575 f1e387195a56
equal deleted inserted replaced
44889:340df9f3491f 44890:22f665a2e91c
    62       let ?M = "{w : V. w\<noteq>v & {v,w} : E}"
    62       let ?M = "{w : V. w\<noteq>v & {v,w} : E}"
    63       let ?N = "{w : V. w\<noteq>v & {v,w} ~: E}"
    63       let ?N = "{w : V. w\<noteq>v & {v,w} ~: E}"
    64       have "V = insert v (?M \<union> ?N)" using `v : V` by auto
    64       have "V = insert v (?M \<union> ?N)" using `v : V` by auto
    65       hence "card V = card(insert v (?M \<union> ?N))" by metis
    65       hence "card V = card(insert v (?M \<union> ?N))" by metis
    66       also have "\<dots> = card ?M + card ?N + 1" using `finite V`
    66       also have "\<dots> = card ?M + card ?N + 1" using `finite V`
    67         by(fastsimp intro: card_Un_disjoint)
    67         by(fastforce intro: card_Un_disjoint)
    68       finally have "card V = card ?M + card ?N + 1" .
    68       finally have "card V = card ?M + card ?N + 1" .
    69       hence "r1+r2 \<le> card ?M + card ?N + 1" using `r1+r2 \<le> card V` by simp
    69       hence "r1+r2 \<le> card ?M + card ?N + 1" using `r1+r2 \<le> card V` by simp
    70       hence "r1 \<le> card ?M \<or> r2 \<le> card ?N" by arith
    70       hence "r1 \<le> card ?M \<or> r2 \<le> card ?N" by arith
    71       moreover
    71       moreover
    72       { assume "r1 \<le> card ?M"
    72       { assume "r1 \<le> card ?M"
   323       and part: "\<forall>x\<in>Z. \<forall>y\<in>Z. x\<noteq>y --> f{x,y} < s"
   323       and part: "\<forall>x\<in>Z. \<forall>y\<in>Z. x\<noteq>y --> f{x,y} < s"
   324   shows
   324   shows
   325    "\<exists>Y t. Y \<subseteq> Z & infinite Y & t < s & (\<forall>x\<in>Y. \<forall>y\<in>Y. x\<noteq>y --> f{x,y} = t)"
   325    "\<exists>Y t. Y \<subseteq> Z & infinite Y & t < s & (\<forall>x\<in>Y. \<forall>y\<in>Y. x\<noteq>y --> f{x,y} = t)"
   326 proof -
   326 proof -
   327   have part2: "\<forall>X. X \<subseteq> Z & finite X & card X = 2 --> f X < s"
   327   have part2: "\<forall>X. X \<subseteq> Z & finite X & card X = 2 --> f X < s"
   328     using part by (fastsimp simp add: eval_nat_numeral card_Suc_eq)
   328     using part by (fastforce simp add: eval_nat_numeral card_Suc_eq)
   329   obtain Y t 
   329   obtain Y t 
   330     where "Y \<subseteq> Z" "infinite Y" "t < s"
   330     where "Y \<subseteq> Z" "infinite Y" "t < s"
   331           "(\<forall>X. X \<subseteq> Y & finite X & card X = 2 --> f X = t)"
   331           "(\<forall>X. X \<subseteq> Y & finite X & card X = 2 --> f X = t)"
   332     by (insert Ramsey [OF infZ part2]) auto
   332     by (insert Ramsey [OF infZ part2]) auto
   333   moreover from this have  "\<forall>x\<in>Y. \<forall>y\<in>Y. x \<noteq> y \<longrightarrow> f {x, y} = t" by auto
   333   moreover from this have  "\<forall>x\<in>Y. \<forall>y\<in>Y. x \<noteq> y \<longrightarrow> f {x, y} = t" by auto