equal
deleted
inserted
replaced
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> |