CODEWITHSUNDEEP
isabelle
Attila Karoly
Attila Karoly

Reputation: 1021

Is induction required in this Isabelle proof?

I'm trying to prove that generator functions produce certain, still very simple, patterns. pattern_0_1 generates a list of alternating 0s and 1s. I've succeeded to prove that the first item is zero for any list whose length is greater than 0. Applying the same technique, however, failed to prove the 2nd element is always 1. My guess is induction is not at all required here. I'd appreciate any help on the right approach to complete the second lemma.

fun pattern_0_1 :: "nat ⇒ nat ⇒ nat list" where
"pattern_0_1 0 item  = []" |
"pattern_0_1 len item =  item # (pattern_0_1 (len - 1) (if item = 0 then 1 else 0))"

lemma item_0_is_0 : "lng ≥ 1 ⟹ pattern_0_1 lng 0 ! 0 = 0"
  apply(induction lng)
  apply(simp)
  by auto

lemma item_1_is_1 : "lng ≥ 2 ⟹ pattern_0_1 lng 0 ! 1 = 1"
  apply(induction lng)
  apply(simp)
  sorry

Upvotes: 0

Views: 58

Answers (1)

René Thiemann
René Thiemann

Reputation: 1271

Induction is not required (it would be, would you show something about all even or all odd positions). Here, case analysis is enough, so that you get the cases 0, 1, and >= 2. So, your proof can be done via

apply(cases lng; cases "lng - 1"; auto)

where the first cases will be on being 0 or >= 1, and the second cases will distinguish between 1 and >= 2.

Upvotes: 2

Related Questions