src/HOL/List.thy
changeset 63540 f8652d0534fa
parent 63521 32da860241b8
child 63561 fba08009ff3e
equal deleted inserted replaced
63539:70d4d9e5707b 63540:f8652d0534fa
  3540         and f_nth: "\<And>i. i < size [x] \<Longrightarrow> [x]!i = ys!(f i)"
  3540         and f_nth: "\<And>i. i < size [x] \<Longrightarrow> [x]!i = ys!(f i)"
  3541       by blast
  3541       by blast
  3542 
  3542 
  3543     have "length ys = card (f ` {0 ..< size [x]})"
  3543     have "length ys = card (f ` {0 ..< size [x]})"
  3544       using f_img by auto
  3544       using f_img by auto
  3545     then have "length ys = 1" by auto
  3545     then have *: "length ys = 1" by auto
  3546     moreover
       
  3547     then have "f 0 = 0" using f_img by auto
  3546     then have "f 0 = 0" using f_img by auto
  3548     ultimately show ?case using f_nth by (cases ys) auto
  3547     with * show ?case using f_nth by (cases ys) auto
  3549   next
  3548   next
  3550     case (3 x1 x2 xs)
  3549     case (3 x1 x2 xs)
  3551     from "3.prems" obtain f where f_mono: "mono f"
  3550     from "3.prems" obtain f where f_mono: "mono f"
  3552       and f_img: "f ` {0..<length (x1 # x2 # xs)} = {0..<length ys}"
  3551       and f_img: "f ` {0..<length (x1 # x2 # xs)} = {0..<length ys}"
  3553       and f_nth:
  3552       and f_nth:
  5497       unfolding cs as bs by auto
  5496       unfolding cs as bs by auto
  5498     ultimately show ?thesis using n n' unfolding lexn_conv by auto
  5497     ultimately show ?thesis using n n' unfolding lexn_conv by auto
  5499   next
  5498   next
  5500     let ?k = "length abs"
  5499     let ?k = "length abs"
  5501     case eq
  5500     case eq
  5502     hence "abs = bcs" "b = b'" using bs bs' by auto
  5501     hence *: "abs = bcs" "b = b'" using bs bs' by auto
  5503     moreover hence "(a, c') \<in> r"
  5502     hence "(a, c') \<in> r"
  5504       using abr b'c'r assms unfolding trans_def by blast
  5503       using abr b'c'r assms unfolding trans_def by blast
  5505     ultimately show ?thesis using n n' unfolding lexn_conv as bs cs by auto
  5504     with * show ?thesis using n n' unfolding lexn_conv as bs cs by auto
  5506   qed
  5505   qed
  5507 qed
  5506 qed
  5508 
  5507 
  5509 lemma lex_conv:
  5508 lemma lex_conv:
  5510   "lex r =
  5509   "lex r =
  5838 
  5837 
  5839 lemma lexordp_conv_lexordp_eq: "lexordp xs ys \<longleftrightarrow> lexordp_eq xs ys \<and> \<not> lexordp_eq ys xs"
  5838 lemma lexordp_conv_lexordp_eq: "lexordp xs ys \<longleftrightarrow> lexordp_eq xs ys \<and> \<not> lexordp_eq ys xs"
  5840   (is "?lhs \<longleftrightarrow> ?rhs")
  5839   (is "?lhs \<longleftrightarrow> ?rhs")
  5841 proof
  5840 proof
  5842   assume ?lhs
  5841   assume ?lhs
  5843   moreover hence "\<not> lexordp_eq ys xs" by induct simp_all
  5842   hence "\<not> lexordp_eq ys xs" by induct simp_all
  5844   ultimately show ?rhs by(simp add: lexordp_into_lexordp_eq)
  5843   with \<open>?lhs\<close> show ?rhs by (simp add: lexordp_into_lexordp_eq)
  5845 next
  5844 next
  5846   assume ?rhs
  5845   assume ?rhs
  5847   hence "lexordp_eq xs ys" "\<not> lexordp_eq ys xs" by simp_all
  5846   hence "lexordp_eq xs ys" "\<not> lexordp_eq ys xs" by simp_all
  5848   thus ?lhs by induct simp_all
  5847   thus ?lhs by induct simp_all
  5849 qed
  5848 qed