src/HOL/Library/Sublist.thy
changeset 67614 560fbd6bc047
parent 67612 e4e57da0583a
parent 67613 ce654b0e6d69
child 68406 6beb45f6cf67
equal deleted inserted replaced
67612:e4e57da0583a 67614:560fbd6bc047
   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)