src/HOL/Library/Ramsey.thy
changeset 61585 a9599d3d7610
parent 60510 64d27b9f00a0
child 63060 293ede07b775
equal deleted inserted replaced
61584:f06e5a5a4b46 61585:a9599d3d7610
   118 subsection \<open>Preliminaries\<close>
   118 subsection \<open>Preliminaries\<close>
   119 
   119 
   120 subsubsection \<open>``Axiom'' of Dependent Choice\<close>
   120 subsubsection \<open>``Axiom'' of Dependent Choice\<close>
   121 
   121 
   122 primrec choice :: "('a => bool) => ('a * 'a) set => nat => 'a" where
   122 primrec choice :: "('a => bool) => ('a * 'a) set => nat => 'a" where
   123   --\<open>An integer-indexed chain of choices\<close>
   123   \<comment>\<open>An integer-indexed chain of choices\<close>
   124     choice_0:   "choice P r 0 = (SOME x. P x)"
   124     choice_0:   "choice P r 0 = (SOME x. P x)"
   125   | choice_Suc: "choice P r (Suc n) = (SOME y. P y & (choice P r n, y) \<in> r)"
   125   | choice_Suc: "choice P r (Suc n) = (SOME y. P y & (choice P r n, y) \<in> r)"
   126 
   126 
   127 lemma choice_n:
   127 lemma choice_n:
   128   assumes P0: "P x0"
   128   assumes P0: "P x0"
   155 
   155 
   156 
   156 
   157 subsubsection \<open>Partitions of a Set\<close>
   157 subsubsection \<open>Partitions of a Set\<close>
   158 
   158 
   159 definition part :: "nat => nat => 'a set => ('a set => nat) => bool"
   159 definition part :: "nat => nat => 'a set => ('a set => nat) => bool"
   160   --\<open>the function @{term f} partitions the @{term r}-subsets of the typically
   160   \<comment>\<open>the function @{term f} partitions the @{term r}-subsets of the typically
   161        infinite set @{term Y} into @{term s} distinct categories.\<close>
   161        infinite set @{term Y} into @{term s} distinct categories.\<close>
   162 where
   162 where
   163   "part r s Y f = (\<forall>X. X \<subseteq> Y & finite X & card X = r --> f X < s)"
   163   "part r s Y f = (\<forall>X. X \<subseteq> Y & finite X & card X = r --> f X < s)"
   164 
   164 
   165 text\<open>For induction, we decrease the value of @{term r} in partitions.\<close>
   165 text\<open>For induction, we decrease the value of @{term r} in partitions.\<close>