equal
deleted
inserted
replaced
243 oops |
243 oops |
244 |
244 |
245 text \<open>``The transitive closure of an arbitrary relation is non-empty.''\<close> |
245 text \<open>``The transitive closure of an arbitrary relation is non-empty.''\<close> |
246 |
246 |
247 definition "trans" :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool" where |
247 definition "trans" :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool" where |
248 "trans P \<equiv> (ALL x y z. P x y \<longrightarrow> P y z \<longrightarrow> P x z)" |
248 "trans P \<equiv> (\<forall>x y z. P x y \<longrightarrow> P y z \<longrightarrow> P x z)" |
249 |
249 |
250 definition |
250 definition |
251 "subset" :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool" where |
251 "subset" :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool" where |
252 "subset P Q \<equiv> (ALL x y. P x y \<longrightarrow> Q x y)" |
252 "subset P Q \<equiv> (\<forall>x y. P x y \<longrightarrow> Q x y)" |
253 |
253 |
254 definition |
254 definition |
255 "trans_closure" :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool" where |
255 "trans_closure" :: "('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> bool" where |
256 "trans_closure P Q \<equiv> (subset Q P) \<and> (trans P) \<and> (ALL R. subset Q R \<longrightarrow> trans R \<longrightarrow> subset P R)" |
256 "trans_closure P Q \<equiv> (subset Q P) \<and> (trans P) \<and> (\<forall>R. subset Q R \<longrightarrow> trans R \<longrightarrow> subset P R)" |
257 |
257 |
258 lemma "trans_closure T P \<longrightarrow> (\<exists>x y. T x y)" |
258 lemma "trans_closure T P \<longrightarrow> (\<exists>x y. T x y)" |
259 nitpick [expect = genuine] |
259 nitpick [expect = genuine] |
260 oops |
260 oops |
261 |
261 |