case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = ([], o, L₂)
⊢ Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
    { l := some q, var := o, stk := update S k L₂ }

case cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (a :: L₁, o, L₂)
⊢ Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
    { l := some q, var := o, stk := update S k L₂ }
p : Γ' → Bool
k : K'
q : Λ'
s : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (L₁, o, L₂)
⊢ Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
    { l := some q, var := o, stk := update S k L₂ }
induction' L₁ with a L₁ IH generalizing S s
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = ([], o, L₂)
⊢ ReflTransGen (fun a b => b ∈ TM2.step tr a) (TM2.stepAux (tr (Λ'.clear p k q)) s S)
    { l := some q, var := o, stk := update S k L₂ }
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = ([], o, L₂)
⊢ Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
    { l := some q, var := o, stk := update S k L₂ }
refine' TransGen.head' rfl _
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (S k), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (S k), stk := update S k (List.tail (S k)) }
    else { l := some (Λ'.clear p k q), var := List.head? (S k), stk := update S k (List.tail (S k)) })
    { l := some q, var := o, stk := update S k L₂ }
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = ([], o, L₂)
⊢ ReflTransGen (fun a b => b ∈ TM2.step tr a) (TM2.stepAux (tr (Λ'.clear p k q)) s S)
    { l := some q, var := o, stk := update S k L₂ }
simp
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
⊢ splitAtPred p (S k) = ([], o, L₂) →
    ReflTransGen
      (fun a b =>
        (match a with
          | { l := none, var := var, stk := stk } => none
          | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
          some b)
      (bif
          match List.head? (S k), true, p with
          | some x, x_1, f => f x
          | none, y, x => y then
        { l := some q, var := List.head? (S k), stk := update S k (List.tail (S k)) }
      else { l := some (Λ'.clear p k q), var := List.head? (S k), stk := update S k (List.tail (S k)) })
      { l := some q, var := o, stk := update S k L₂ }
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (S k), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (S k), stk := update S k (List.tail (S k)) }
    else { l := some (Λ'.clear p k q), var := List.head? (S k), stk := update S k (List.tail (S k)) })
    { l := some q, var := o, stk := update S k L₂ }
revert e
case nil.nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p [] = ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? [], true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? [], stk := update S k (List.tail []) }
    else { l := some (Λ'.clear p k q), var := List.head? [], stk := update S k (List.tail []) })
    { l := some q, var := o, stk := update S k L₂ }

case nil.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e : splitAtPred p (a :: Sk) = ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
case nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
⊢ splitAtPred p (S k) = ([], o, L₂) →
    ReflTransGen
      (fun a b =>
        (match a with
          | { l := none, var := var, stk := stk } => none
          | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
          some b)
      (bif
          match List.head? (S k), true, p with
          | some x, x_1, f => f x
          | none, y, x => y then
        { l := some q, var := List.head? (S k), stk := update S k (List.tail (S k)) }
      else { l := some (Λ'.clear p k q), var := List.head? (S k), stk := update S k (List.tail (S k)) })
      { l := some q, var := o, stk := update S k L₂ }
cases' S k with a Sk <;> intro e
case nil.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e :
  (bif p a then ([], some a, Sk)
    else (a :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd)) =
    ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif p a then { l := some q, var := some a, stk := update S k Sk }
    else { l := some (Λ'.clear p k q), var := some a, stk := update S k Sk })
    { l := some q, var := o, stk := update S k L₂ }
case nil.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e : splitAtPred p (a :: Sk) = ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
simp only [splitAtPred, Option.elim, List.head?, List.tail_cons] at e ⊢
case nil.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
⊢ (bif p a then ([], some a, Sk)
      else (a :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd)) =
      ([], o, L₂) →
    ReflTransGen
      (fun a b =>
        (match a with
          | { l := none, var := var, stk := stk } => none
          | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
          some b)
      (bif p a then { l := some q, var := some a, stk := update S k Sk }
      else { l := some (Λ'.clear p k q), var := some a, stk := update S k Sk })
      { l := some q, var := o, stk := update S k L₂ }
case nil.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e :
  (bif p a then ([], some a, Sk)
    else (a :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd)) =
    ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif p a then { l := some q, var := some a, stk := update S k Sk }
    else { l := some (Λ'.clear p k q), var := some a, stk := update S k Sk })
    { l := some q, var := o, stk := update S k L₂ }
revert e
case nil.cons.true
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e : some a = o ∧ Sk = L₂
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    { l := some q, var := some a, stk := update S k Sk } { l := some q, var := o, stk := update S k L₂ }
case nil.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
⊢ (bif p a then ([], some a, Sk)
      else (a :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd)) =
      ([], o, L₂) →
    ReflTransGen
      (fun a b =>
        (match a with
          | { l := none, var := var, stk := stk } => none
          | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
          some b)
      (bif p a then { l := some q, var := some a, stk := update S k Sk }
      else { l := some (Λ'.clear p k q), var := some a, stk := update S k Sk })
      { l := some q, var := o, stk := update S k L₂ }
cases p a <;> intro e <;>
simp only [cond_false, cond_true, Prod.mk.injEq, true_and, false_and] at e ⊢
case nil.nil.refl
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
S✝ : K' → List Γ'
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, none, [])
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? [], true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? [], stk := update S k (List.tail []) }
    else { l := some (Λ'.clear p k q), var := List.head? [], stk := update S k (List.tail []) })
    { l := some q, var := none, stk := update S k [] }
case nil.nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p [] = ([], o, L₂)
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? [], true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? [], stk := update S k (List.tail []) }
    else { l := some (Λ'.clear p k q), var := List.head? [], stk := update S k (List.tail []) })
    { l := some q, var := o, stk := update S k L₂ }
cases e
no goals
case nil.nil.refl
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
S✝ : K' → List Γ'
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, none, [])
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? [], true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? [], stk := update S k (List.tail []) }
    else { l := some (Λ'.clear p k q), var := List.head? [], stk := update S k (List.tail []) })
    { l := some q, var := none, stk := update S k [] }
rfl
case nil.cons.true.intro
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e₁ : some a = o
e₂ : Sk = L₂
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    { l := some q, var := some a, stk := update S k Sk } { l := some q, var := o, stk := update S k L₂ }
case nil.cons.true
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e : some a = o ∧ Sk = L₂
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    { l := some q, var := some a, stk := update S k Sk } { l := some q, var := o, stk := update S k L₂ }
rcases e with ⟨e₁, e₂⟩
no goals
case nil.cons.true.intro
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e : splitAtPred p (S✝ k) = (L₁, o, L₂)
s : Option Γ'
S : K' → List Γ'
a : Γ'
Sk : List Γ'
e₁ : some a = o
e₂ : Sk = L₂
⊢ ReflTransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    { l := some q, var := some a, stk := update S k Sk } { l := some q, var := o, stk := update S k L₂ }
rw [e₁, e₂]
case cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (a :: L₁, o, L₂)
⊢ TransGen (fun a b => b ∈ TM2.step tr a) (TM2.stepAux (tr (Λ'.clear p k q)) s S)
    { l := some q, var := o, stk := update S k L₂ }
case cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (a :: L₁, o, L₂)
⊢ Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
    { l := some q, var := o, stk := update S k L₂ }
refine' TransGen.head rfl _
case cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (S k), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (S k), stk := update S k (List.tail (S k)) }
    else { l := some (Λ'.clear p k q), var := List.head? (S k), stk := update S k (List.tail (S k)) })
    { l := some q, var := o, stk := update S k L₂ }
case cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (a :: L₁, o, L₂)
⊢ TransGen (fun a b => b ∈ TM2.step tr a) (TM2.stepAux (tr (Λ'.clear p k q)) s S)
    { l := some q, var := o, stk := update S k L₂ }
simp
case cons.nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : ([], none, []) = (a :: L₁, o, L₂)
e₁ : S k = []
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? [], true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? [], stk := update S k (List.tail []) }
    else { l := some (Λ'.clear p k q), var := List.head? [], stk := update S k (List.tail []) })
    { l := some q, var := o, stk := update S k L₂ }

case cons.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e :
  (bif p a' then ([], some a', Sk)
    else
      match splitAtPred p Sk with
      | (l₁, o, l₂) => (a' :: l₁, o, l₂)) =
    (a :: L₁, o, L₂)
e₁ : S k = a' :: Sk
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
case cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : splitAtPred p (S k) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (S k), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (S k), stk := update S k (List.tail (S k)) }
    else { l := some (Λ'.clear p k q), var := List.head? (S k), stk := update S k (List.tail (S k)) })
    { l := some q, var := o, stk := update S k L₂ }
cases' e₁ : S k with a' Sk <;> rw [e₁, splitAtPred] at e
case cons.cons.false
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
e : (a' :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }

case cons.cons.true
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = true
e : ([], some a', Sk) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
case cons.cons
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e :
  (bif p a' then ([], some a', Sk)
    else
      match splitAtPred p Sk with
      | (l₁, o, l₂) => (a' :: l₁, o, l₂)) =
    (a :: L₁, o, L₂)
e₁ : S k = a' :: Sk
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
cases e₂ : p a' <;> simp only [e₂, cond] at e
case cons.cons.true
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = true
e : ([], some a', Sk) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }

case cons.cons.false
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
e : (a' :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
case cons.cons.false
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
e : (a' :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }

case cons.cons.true
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = true
e : ([], some a', Sk) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
swap
case cons.cons.false.mk.mk
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
e : (a' :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd) = (a :: L₁, o, L₂)
fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
case cons.cons.false
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
e : (a' :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
rcases e₃ : splitAtPred p Sk with ⟨_, _, _⟩
case cons.cons.false.mk.mk
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e : (a' :: (fst✝¹, fst✝, snd✝).fst, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd) = (a :: L₁, o, L₂)
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
case cons.cons.false.mk.mk
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
e : (a' :: (splitAtPred p Sk).fst, (splitAtPred p Sk).2.fst, (splitAtPred p Sk).2.snd) = (a :: L₁, o, L₂)
fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
rw [e₃] at e
case cons.cons.false.mk.mk.refl
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
S✝ : K' → List Γ'
a : Γ'
s : Option Γ'
S : K' → List Γ'
Sk fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
e₁ : S k = a :: Sk
e₂ : p a = false
e : splitAtPred p (S✝ k) = (L₁, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd)
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = ((fst✝¹, fst✝, snd✝).fst, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := (fst✝¹, fst✝, snd✝).2.fst, stk := update S k (fst✝¹, fst✝, snd✝).2.snd }
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) })
    { l := some q, var := (fst✝¹, fst✝, snd✝).2.fst, stk := update S k (fst✝¹, fst✝, snd✝).2.snd }
case cons.cons.false.mk.mk
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = false
fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e : (a' :: (fst✝¹, fst✝, snd✝).fst, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd) = (a :: L₁, o, L₂)
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
cases e
case cons.cons.false.mk.mk.refl
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
S✝ : K' → List Γ'
a : Γ'
s : Option Γ'
S : K' → List Γ'
Sk fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
e₁ : S k = a :: Sk
e₂ : p a = false
e : splitAtPred p (S✝ k) = (L₁, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd)
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = ((fst✝¹, fst✝, snd✝).fst, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := (fst✝¹, fst✝, snd✝).2.fst, stk := update S k (fst✝¹, fst✝, snd✝).2.snd }
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    { l := some (Λ'.clear p k q), var := some a, stk := update S k Sk }
    { l := some q, var := fst✝, stk := update S k snd✝ }
case cons.cons.false.mk.mk.refl
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
S✝ : K' → List Γ'
a : Γ'
s : Option Γ'
S : K' → List Γ'
Sk fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
e₁ : S k = a :: Sk
e₂ : p a = false
e : splitAtPred p (S✝ k) = (L₁, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd)
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = ((fst✝¹, fst✝, snd✝).fst, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := (fst✝¹, fst✝, snd✝).2.fst, stk := update S k (fst✝¹, fst✝, snd✝).2.snd }
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a :: Sk), stk := update S k (List.tail (a :: Sk)) })
    { l := some q, var := (fst✝¹, fst✝, snd✝).2.fst, stk := update S k (fst✝¹, fst✝, snd✝).2.snd }
simp [e₂]
no goals
case cons.cons.false.mk.mk.refl
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁ : List Γ'
S✝ : K' → List Γ'
a : Γ'
s : Option Γ'
S : K' → List Γ'
Sk fst✝¹ : List Γ'
fst✝ : Option Γ'
snd✝ : List Γ'
e₃ : splitAtPred p Sk = (fst✝¹, fst✝, snd✝)
e₁ : S k = a :: Sk
e₂ : p a = false
e : splitAtPred p (S✝ k) = (L₁, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd)
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = ((fst✝¹, fst✝, snd✝).fst, (fst✝¹, fst✝, snd✝).2.fst, (fst✝¹, fst✝, snd✝).2.snd) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := (fst✝¹, fst✝, snd✝).2.fst, stk := update S k (fst✝¹, fst✝, snd✝).2.snd }
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    { l := some (Λ'.clear p k q), var := some a, stk := update S k Sk }
    { l := some q, var := fst✝, stk := update S k snd✝ }
convert @IH _ (update S k Sk) _ using 2 <;> simp [e₃]
no goals
case cons.nil
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
e : ([], none, []) = (a :: L₁, o, L₂)
e₁ : S k = []
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? [], true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? [], stk := update S k (List.tail []) }
    else { l := some (Λ'.clear p k q), var := List.head? [], stk := update S k (List.tail []) })
    { l := some q, var := o, stk := update S k L₂ }
cases e
no goals
case cons.cons.true
p : Γ' → Bool
k : K'
q : Λ'
s✝ : Option Γ'
L₁✝ : List Γ'
o : Option Γ'
L₂ : List Γ'
S✝ : K' → List Γ'
e✝ : splitAtPred p (S✝ k) = (L₁✝, o, L₂)
a : Γ'
L₁ : List Γ'
IH :
  ∀ {s : Option Γ'} {S : K' → List Γ'},
    splitAtPred p (S k) = (L₁, o, L₂) →
      Reaches₁ (TM2.step tr) { l := some (Λ'.clear p k q), var := s, stk := S }
        { l := some q, var := o, stk := update S k L₂ }
s : Option Γ'
S : K' → List Γ'
a' : Γ'
Sk : List Γ'
e₁ : S k = a' :: Sk
e₂ : p a' = true
e : ([], some a', Sk) = (a :: L₁, o, L₂)
⊢ TransGen
    (fun a b =>
      (match a with
        | { l := none, var := var, stk := stk } => none
        | { l := some l, var := v, stk := S } => some (TM2.stepAux (tr l) v S)) =
        some b)
    (bif
        match List.head? (a' :: Sk), true, p with
        | some x, x_1, f => f x
        | none, y, x => y then
      { l := some q, var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) }
    else { l := some (Λ'.clear p k q), var := List.head? (a' :: Sk), stk := update S k (List.tail (a' :: Sk)) })
    { l := some q, var := o, stk := update S k L₂ }
cases e