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