Stream: Beginner Questions

Topic: some confuse about induction


view this post on Zulip Hongjian Jiang (Feb 06 2024 at 20:29):

I am trying to use induction to prove a lemma, but stuck with some problems.

lemma a_equal_b:
  assumes 1:"vec n a" and  2:"vec n b" and 3:"vec n l" and 4:"∀i∈set [0..<n]. vec n (m!i)"  and 5:"∀i∈set [0..<n]. ewp_vec (m!i)" and
    6:"∀i∈set [0..<n].   equations a (m!i) + l!i = a!i"  and
    7:"∀i∈set [0..<n].   equations b (m!i) + l!i = b!i"
  shows "∀i∈set [0..<n]. a!i = b!i" using assms
proof (induct n)
  case 0
  then show ?case using assms by simp
next
  case (Suc n)
  then show ?case
  proof (induct n)
    case 0
    then show ?case apply auto
      by (smt (verit, del_insts) "0.prems"(5) "0.prems"(6) "1" "6" "7" One_nat_def base_case vec_def)
  next
    case (Suc n)
    then show ?case
    proof -
      assume i1:"vec (Suc (Suc n)) a" and i2:"vec (Suc (Suc n)) b" and i3:"vec (Suc (Suc n)) l" and
        i4:"∀i∈set [0..<Suc (Suc n)]. vec (Suc (Suc n)) (m ! i)" and
        i5:"∀i∈set [0..<Suc (Suc n)]. ewp_vec (m ! i)" and
        i6:"∀i∈set [0..<Suc (Suc n)]. equations a (m ! i) + l ! i = a ! i" and
        i7: "∀i∈set [0..<Suc (Suc n)]. equations b (m ! i) + l ! i = b ! i"
      have co6:"∀i∈set [0..<(Suc n)].  a!i = equations (butlast a) (map2 (+) (butlast (m!i)) (map (λr. r * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n))) (butlast (m!(Suc n)))))  +
          l!(Suc n) * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n)) + l!i" using i1 i3 i4 i6 i5 m12[of "Suc n" a l m] by blast
      from co6 i1 have cof1:"∀i∈set [0..<(Suc n)].  equations (butlast a) (map2 (+) (butlast (m!i)) (map (λr. r * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n))) (butlast (m!(Suc n)))))  +
          l!(Suc n) * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n)) + l!i = (butlast a)!i "
        by (simp add: nth_butlast vec_def)

      have c07:"∀i∈set [0..<(Suc n)].  b!i = equations (butlast b) (map2 (+) (butlast (m!i)) (map (λr. r * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n))) (butlast (m!(Suc n)))))  +
          l!(Suc n) * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n)) + l!i" using i2 i3 i4 i7 i5 m12[of "Suc n" b l m] by blast
      from c07 i2 have cof2:"∀i∈set [0..<(Suc n)].  equations (butlast b) (map2 (+) (butlast (m!i)) (map (λr. r * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n))) (butlast (m!(Suc n)))))  +
          l!(Suc n) * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n)) + l!i = (butlast b)!i"
        by (simp add: nth_butlast vec_def)

      have co1: "vec (Suc n) (butlast a)" using i1 by(simp add:vec_def)
      have co2: "vec (Suc n) (butlast b)" using i2 by(simp add:vec_def)
      have co3: "∀i∈set [0..<Suc n]. vec (Suc n) (map (λi. l!(Suc n) * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n)) + l!i) [0..<Suc n])" using i4 sorry
      have co4: "∀i∈set [0..<Suc n]. ewp_vec (map2 (+) (butlast (m!i)) (map (λr. r * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n))) (butlast (m!(Suc n)))))" using i5 sorry
      have c1: "∀i∈set [0..<(Suc n)]. a ! i = b ! i" using co1 co2 co3 co4 cof1 cof2 Suc.hyps sledgehammer
        using co6 by fastforce
      moreover have "a !(Suc n) = b ! (Suc n)" using i1 i2 i3 i4 i5 i6 i7 proof -
        have cc1:"a!(Suc n) = (equations (butlast a) (butlast (m!(Suc n))) + l!(Suc n)) * (m!(Suc n)!(Suc n))⇧⋆"
          using i1 i3 i4 i5 i6 m5 by blast
        moreover have cc2: "b!(Suc n) = (equations (butlast b) (butlast (m!(Suc n))) + l!(Suc n)) * (m!(Suc n)!(Suc n))⇧⋆"
          using i2 i3 i4 i5 i7 m5 by blast
        moreover have "(butlast a) = (butlast b)" using c1 i1 i2 apply (simp add:vec_def)
        proof -
          have "take (length a - 1) a  = take (length b - 1) b"  using c1 i1 i2 apply (simp add:vec_def)
            using aux_2 by blast
          then show ?thesis
            by (metis take_replace)
        qed
         ultimately show ?thesis
          by presburger
      qed
      ultimately show ?thesis
        by simp
    qed
  qed
qed

When to prove ∀i∈set [0..<(Suc n)]. a ! i = b ! i, I am trying to rewrite the inductive assumption?

The assumption says that the conclusion could reach by

 vec (Suc n) a 
    vec (Suc n) b 
    vec (Suc n) l 
    ∀i∈set [0..<Suc n]. vec (Suc n) (m ! i) 
    ∀i∈set [0..<Suc n]. ewp_vec (m ! i) 
    ∀i∈set [0..<Suc n]. equations a (m ! i) + l ! i = a ! i  ∀i∈set [0..<Suc n]. equations b (m ! i) + l ! i = b ! i  ∀i∈set [0..<Suc n]. a ! i = b ! i

And I got the a as (butlast a), b as (butlast b) and so to l, m. But isabelle tells me can't rewrite it.

 have co1: "vec (Suc n) (butlast a)" using i1 by(simp add:vec_def)
      have co2: "vec (Suc n) (butlast b)" using i2 by(simp add:vec_def)
      have co3: "∀i∈set [0..<Suc n]. vec (Suc n) (map (λi. l!(Suc n) * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n)) + l!i) [0..<Suc n])" using i4 sorry
      have co4: "∀i∈set [0..<Suc n]. ewp_vec (map2 (+) (butlast (m!i)) (map (λr. r * (m!(Suc n)!(Suc n))⇧⋆ * (m!i!(Suc n))) (butlast (m!(Suc n)))))" using i5 sorry
      have c1: "∀i∈set [0..<(Suc n)]. a ! i = b ! i" using co1 co2 co3 co4 cof1 cof2 Suc.hyps sorry

So my question here is how to explioit the inductive hypothesis among the induction proof. Thanks a lot

view this post on Zulip Mathias Fleury (Feb 06 2024 at 20:57):

a as (butlast a)

and here lies your problem. If your variable is a, Isabelle wants a. No other option

view this post on Zulip Mathias Fleury (Feb 06 2024 at 20:58):

If your IH was forall a. ... then you could instantiate a with butlast a


Last updated: May 07 2024 at 01:07 UTC