equal
deleted
inserted
replaced
296 lemma Longest_common_prefix_ex: "L \<noteq> {} \<Longrightarrow> |
296 lemma Longest_common_prefix_ex: "L \<noteq> {} \<Longrightarrow> |
297 \<exists>ps. (\<forall>xs \<in> L. prefix ps xs) \<and> (\<forall>qs. (\<forall>xs \<in> L. prefix qs xs) \<longrightarrow> size qs \<le> size ps)" |
297 \<exists>ps. (\<forall>xs \<in> L. prefix ps xs) \<and> (\<forall>qs. (\<forall>xs \<in> L. prefix qs xs) \<longrightarrow> size qs \<le> size ps)" |
298 (is "_ \<Longrightarrow> \<exists>ps. ?P L ps") |
298 (is "_ \<Longrightarrow> \<exists>ps. ?P L ps") |
299 proof(induction "LEAST n. \<exists>xs \<in>L. n = length xs" arbitrary: L) |
299 proof(induction "LEAST n. \<exists>xs \<in>L. n = length xs" arbitrary: L) |
300 case 0 |
300 case 0 |
301 have "[] : L" using "0.hyps" LeastI[of "\<lambda>n. \<exists>xs\<in>L. n = length xs"] \<open>L \<noteq> {}\<close> |
301 have "[] \<in> L" using "0.hyps" LeastI[of "\<lambda>n. \<exists>xs\<in>L. n = length xs"] \<open>L \<noteq> {}\<close> |
302 by auto |
302 by auto |
303 hence "?P L []" by(auto) |
303 hence "?P L []" by(auto) |
304 thus ?case .. |
304 thus ?case .. |
305 next |
305 next |
306 case (Suc n) |
306 case (Suc n) |