[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b a : α
l : List α
p : Chain R a l
⊢ Chain (fun x y => x ∈ a :: l ∧ y ∈ l ∧ R x y) a l
[PROOFSTEP]
induction' p with _ a b l r _ IH <;> constructor <;> [exact ⟨mem_cons_self _ _, mem_cons_self _ _, r⟩;
  exact IH.imp fun a b ⟨am, bm, h⟩ => ⟨mem_cons_of_mem _ am, mem_cons_of_mem _ bm, h⟩]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b a : α
l : List α
p : Chain R a l
⊢ Chain (fun x y => x ∈ a :: l ∧ y ∈ l ∧ R x y) a l
[PROOFSTEP]
induction' p with _ a b l r _ IH
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝¹ b a : α
l : List α
a✝ : α
⊢ Chain (fun x y => x ∈ [a✝] ∧ y ∈ [] ∧ R x y) a✝ []
[PROOFSTEP]
constructor
[GOAL]
case cons
α : Type u
β : Type v
R r✝ : α → α → Prop
l✝¹ l₁ l₂ : List α
a✝² b✝ a✝¹ : α
l✝ : List α
a b : α
l : List α
r : R a b
a✝ : Chain R b l
IH : Chain (fun x y => x ∈ b :: l ∧ y ∈ l ∧ R x y) b l
⊢ Chain (fun x y => x ∈ a :: b :: l ∧ y ∈ b :: l ∧ R x y) a (b :: l)
[PROOFSTEP]
constructor
[GOAL]
case cons.a
α : Type u
β : Type v
R r✝ : α → α → Prop
l✝¹ l₁ l₂ : List α
a✝² b✝ a✝¹ : α
l✝ : List α
a b : α
l : List α
r : R a b
a✝ : Chain R b l
IH : Chain (fun x y => x ∈ b :: l ∧ y ∈ l ∧ R x y) b l
⊢ a ∈ a :: b :: l ∧ b ∈ b :: l ∧ R a b
[PROOFSTEP]
exact ⟨mem_cons_self _ _, mem_cons_self _ _, r⟩
[GOAL]
case cons.a
α : Type u
β : Type v
R r✝ : α → α → Prop
l✝¹ l₁ l₂ : List α
a✝² b✝ a✝¹ : α
l✝ : List α
a b : α
l : List α
r : R a b
a✝ : Chain R b l
IH : Chain (fun x y => x ∈ b :: l ∧ y ∈ l ∧ R x y) b l
⊢ Chain (fun x y => x ∈ a :: b :: l ∧ y ∈ b :: l ∧ R x y) b l
[PROOFSTEP]
exact IH.imp fun a b ⟨am, bm, h⟩ => ⟨mem_cons_of_mem _ am, mem_cons_of_mem _ bm, h⟩
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ a b : α
⊢ Chain R a [b] ↔ R a b
[PROOFSTEP]
simp only [chain_cons, Chain.nil, and_true_iff]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a✝ b✝ a b : α
l₁ l₂ : List α
⊢ Chain R a (l₁ ++ b :: l₂) ↔ Chain R a (l₁ ++ [b]) ∧ Chain R b l₂
[PROOFSTEP]
induction' l₁ with x l₁ IH generalizing a
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂✝ : List α
a✝¹ b✝ a✝ b : α
l₂ : List α
a : α
⊢ Chain R a ([] ++ b :: l₂) ↔ Chain R a ([] ++ [b]) ∧ Chain R b l₂
[PROOFSTEP]
simp only [*, nil_append, cons_append, Chain.nil, chain_cons, and_true_iff, and_assoc]
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a✝¹ b✝ a✝ b : α
l₂ : List α
x : α
l₁ : List α
IH : ∀ {a : α}, Chain R a (l₁ ++ b :: l₂) ↔ Chain R a (l₁ ++ [b]) ∧ Chain R b l₂
a : α
⊢ Chain R a (x :: l₁ ++ b :: l₂) ↔ Chain R a (x :: l₁ ++ [b]) ∧ Chain R b l₂
[PROOFSTEP]
simp only [*, nil_append, cons_append, Chain.nil, chain_cons, and_true_iff, and_assoc]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a✝ b✝ a b c : α
l₁ l₂ : List α
⊢ Chain R a (l₁ ++ b :: c :: l₂) ↔ Chain R a (l₁ ++ [b]) ∧ R b c ∧ Chain R c l₂
[PROOFSTEP]
rw [chain_split, chain_cons]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a✝ b a : α
⊢ Chain R a [] ↔ [] = [] ∨ Forall₂ R (a :: dropLast []) []
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ a b : α
l : List α
⊢ Chain R a (b :: l) ↔ b :: l = [] ∨ Forall₂ R (a :: dropLast (b :: l)) (b :: l)
[PROOFSTEP]
by_cases h : l = []
[GOAL]
case pos
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ a b : α
l : List α
h : l = []
⊢ Chain R a (b :: l) ↔ b :: l = [] ∨ Forall₂ R (a :: dropLast (b :: l)) (b :: l)
[PROOFSTEP]
simp [@chain_iff_forall₂ b l, *]
[GOAL]
case neg
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ a b : α
l : List α
h : ¬l = []
⊢ Chain R a (b :: l) ↔ b :: l = [] ∨ Forall₂ R (a :: dropLast (b :: l)) (b :: l)
[PROOFSTEP]
simp [@chain_iff_forall₂ b l, *]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
⊢ Chain R a (l ++ [b]) ↔ Forall₂ R (a :: l) (l ++ [b])
[PROOFSTEP]
simp [chain_iff_forall₂]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b✝ : α
f : β → α
b : β
l : List β
⊢ Chain R (f b) (map f l) ↔ Chain (fun a b => R (f a) (f b)) b l
[PROOFSTEP]
induction l generalizing b
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b✝ : α
f : β → α
b : β
⊢ Chain R (f b) (map f []) ↔ Chain (fun a b => R (f a) (f b)) b []
[PROOFSTEP]
simp only [map, Chain.nil, chain_cons, *]
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b✝ : α
f : β → α
head✝ : β
tail✝ : List β
tail_ih✝ : ∀ {b : β}, Chain R (f b) (map f tail✝) ↔ Chain (fun a b => R (f a) (f b)) b tail✝
b : β
⊢ Chain R (f b) (map f (head✝ :: tail✝)) ↔ Chain (fun a b => R (f a) (f b)) b (head✝ :: tail✝)
[PROOFSTEP]
simp only [map, Chain.nil, chain_cons, *]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
S : β → β → Prop
p : α → Prop
f : (a : α) → p a → β
H : ∀ (a b : α) (ha : p a) (hb : p b), R a b → S (f a ha) (f b hb)
a : α
l : List α
hl₁ : Chain R a l
ha : p a
hl₂ : ∀ (a : α), a ∈ l → p a
⊢ Chain S (f a ha) (pmap f l hl₂)
[PROOFSTEP]
induction' l with lh lt l_ih generalizing a
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝¹ b : α
S : β → β → Prop
p : α → Prop
f : (a : α) → p a → β
H : ∀ (a b : α) (ha : p a) (hb : p b), R a b → S (f a ha) (f b hb)
a✝ : α
l : List α
hl₁✝ : Chain R a✝ l
ha✝ : p a✝
hl₂✝ : ∀ (a : α), a ∈ l → p a
a : α
hl₁ : Chain R a []
ha : p a
hl₂ : ∀ (a : α), a ∈ [] → p a
⊢ Chain S (f a ha) (pmap f [] hl₂)
[PROOFSTEP]
simp
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝¹ b : α
S : β → β → Prop
p : α → Prop
f : (a : α) → p a → β
H : ∀ (a b : α) (ha : p a) (hb : p b), R a b → S (f a ha) (f b hb)
a✝ : α
l : List α
hl₁✝ : Chain R a✝ l
ha✝ : p a✝
hl₂✝ : ∀ (a : α), a ∈ l → p a
lh : α
lt : List α
l_ih : ∀ {a : α}, Chain R a lt → ∀ (ha : p a) (hl₂ : ∀ (a : α), a ∈ lt → p a), Chain S (f a ha) (pmap f lt hl₂)
a : α
hl₁ : Chain R a (lh :: lt)
ha : p a
hl₂ : ∀ (a : α), a ∈ lh :: lt → p a
⊢ Chain S (f a ha) (pmap f (lh :: lt) hl₂)
[PROOFSTEP]
simp [H _ _ _ _ (rel_of_chain_cons hl₁), l_ih (chain_of_chain_cons hl₁)]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
S : β → β → Prop
p : α → Prop
f : (a : α) → p a → β
l : List α
hl₁ : ∀ (a : α), a ∈ l → p a
a : α
ha : p a
hl₂ : Chain S (f a ha) (pmap f l hl₁)
H : ∀ (a b : α) (ha : p a) (hb : p b), S (f a ha) (f b hb) → R a b
⊢ Chain R a l
[PROOFSTEP]
induction' l with lh lt l_ih generalizing a
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝¹ b : α
S : β → β → Prop
p : α → Prop
f : (a : α) → p a → β
l : List α
hl₁✝ : ∀ (a : α), a ∈ l → p a
a✝ : α
ha✝ : p a✝
hl₂✝ : Chain S (f a✝ ha✝) (pmap f l hl₁✝)
H : ∀ (a b : α) (ha : p a) (hb : p b), S (f a ha) (f b hb) → R a b
hl₁ : ∀ (a : α), a ∈ [] → p a
a : α
ha : p a
hl₂ : Chain S (f a ha) (pmap f [] hl₁)
⊢ Chain R a []
[PROOFSTEP]
simp
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝¹ b : α
S : β → β → Prop
p : α → Prop
f : (a : α) → p a → β
l : List α
hl₁✝ : ∀ (a : α), a ∈ l → p a
a✝ : α
ha✝ : p a✝
hl₂✝ : Chain S (f a✝ ha✝) (pmap f l hl₁✝)
H : ∀ (a b : α) (ha : p a) (hb : p b), S (f a ha) (f b hb) → R a b
lh : α
lt : List α
l_ih : ∀ (hl₁ : ∀ (a : α), a ∈ lt → p a) {a : α} (ha : p a), Chain S (f a ha) (pmap f lt hl₁) → Chain R a lt
hl₁ : ∀ (a : α), a ∈ lh :: lt → p a
a : α
ha : p a
hl₂ : Chain S (f a ha) (pmap f (lh :: lt) hl₁)
⊢ Chain R a (lh :: lt)
[PROOFSTEP]
simp [H _ _ _ _ (rel_of_chain_cons hl₂), l_ih _ _ (chain_of_chain_cons hl₂)]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ : α
inst✝ : IsTrans α R
a b : α
l : List α
h : R a b
hb : Chain R b l
⊢ ∀ (a' : α), a' ∈ b :: l → R a a'
[PROOFSTEP]
simp only [mem_cons, forall_eq_or_imp, h, true_and_iff]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ : α
inst✝ : IsTrans α R
a b : α
l : List α
h : R a b
hb : Chain R b l
⊢ ∀ (a_1 : α), a_1 ∈ l → R a a_1
[PROOFSTEP]
exact fun c hc => _root_.trans h (rel_of_pairwise_cons hb.pairwise hc)
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
inst✝ : IsTrans α R
hl : Chain R a l₂
h : l₁ <+ l₂
⊢ Chain R a l₁
[PROOFSTEP]
rw [chain_iff_pairwise] at hl ⊢
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
inst✝ : IsTrans α R
hl : Pairwise R (a :: l₂)
h : l₁ <+ l₂
⊢ Pairwise R (a :: l₁)
[PROOFSTEP]
exact hl.sublist (h.cons_cons a)
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
inst✝ : IsTrans α R
hl : Chain R a l
hb : b ∈ l
⊢ R a b
[PROOFSTEP]
rw [chain_iff_pairwise] at hl 
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
inst✝ : IsTrans α R
hl : Pairwise R (a :: l)
hb : b ∈ l
⊢ R a b
[PROOFSTEP]
exact rel_of_pairwise_cons hl hb
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
⊢ Chain R a []
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
h : 0 < length []
⊢ R a (get [] { val := 0, isLt := h })
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
x✝ : ℕ
h : x✝ < length [] - 1
⊢ R (get [] { val := x✝, isLt := (_ : x✝ < length []) }) (get [] { val := x✝ + 1, isLt := (_ : succ x✝ < length []) })
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ Chain R a (b :: t) ↔
    (∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })) ∧
      ∀ (i : ℕ) (h : i < length (b :: t) - 1),
        R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
          (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
[PROOFSTEP]
rw [chain_cons, @chain_iff_get _ _ t]
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ (R a b ∧
      (∀ (h : 0 < length t), R b (get t { val := 0, isLt := h })) ∧
        ∀ (i : ℕ) (h : i < length t - 1),
          R (get t { val := i, isLt := (_ : i < length t) })
            (get t { val := i + 1, isLt := (_ : succ i < length t) })) ↔
    (∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })) ∧
      ∀ (i : ℕ) (h : i < length (b :: t) - 1),
        R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
          (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
[PROOFSTEP]
constructor
[GOAL]
case mp
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ (R a b ∧
      (∀ (h : 0 < length t), R b (get t { val := 0, isLt := h })) ∧
        ∀ (i : ℕ) (h : i < length t - 1),
          R (get t { val := i, isLt := (_ : i < length t) })
            (get t { val := i + 1, isLt := (_ : succ i < length t) })) →
    (∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })) ∧
      ∀ (i : ℕ) (h : i < length (b :: t) - 1),
        R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
          (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
[PROOFSTEP]
rintro ⟨R, ⟨h0, h⟩⟩
[GOAL]
case mp.intro.intro
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
⊢ (∀ (h : 0 < length (b :: t)), R✝ a (get (b :: t) { val := 0, isLt := h })) ∧
    ∀ (i : ℕ) (h : i < length (b :: t) - 1),
      R✝ (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
        (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
[PROOFSTEP]
constructor
[GOAL]
case mp.intro.intro.left
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
⊢ ∀ (h : 0 < length (b :: t)), R✝ a (get (b :: t) { val := 0, isLt := h })
[PROOFSTEP]
intro _
[GOAL]
case mp.intro.intro.left
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
h✝ : 0 < length (b :: t)
⊢ R✝ a (get (b :: t) { val := 0, isLt := h✝ })
[PROOFSTEP]
exact R
[GOAL]
case mp.intro.intro.right
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
⊢ ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R✝ (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
[PROOFSTEP]
intro i w
[GOAL]
case mp.intro.intro.right
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
i : ℕ
w : i < length (b :: t) - 1
⊢ R✝ (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
    (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
[PROOFSTEP]
cases' i with i
[GOAL]
case mp.intro.intro.right.zero
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
w : zero < length (b :: t) - 1
⊢ R✝ (get (b :: t) { val := zero, isLt := (_ : zero < length (b :: t)) })
    (get (b :: t) { val := zero + 1, isLt := (_ : succ zero < length (b :: t)) })
[PROOFSTEP]
apply h0
[GOAL]
case mp.intro.intro.right.succ
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
i : ℕ
w : succ i < length (b :: t) - 1
⊢ R✝ (get (b :: t) { val := succ i, isLt := (_ : succ i < length (b :: t)) })
    (get (b :: t) { val := succ i + 1, isLt := (_ : succ (succ i) < length (b :: t)) })
[PROOFSTEP]
exact h i (lt_pred_iff.2 <| by simpa using w)
[GOAL]
α : Type u
β : Type v
R✝¹ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R✝ : α → α → Prop
a b : α
t : List α
R : R✝ a b
h0 : ∀ (h : 0 < length t), R✝ b (get t { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length t - 1),
    R✝ (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
i : ℕ
w : succ i < length (b :: t) - 1
⊢ succ i < Nat.sub (length t) 0
[PROOFSTEP]
simpa using w
[GOAL]
case mpr
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ ((∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })) ∧
      ∀ (i : ℕ) (h : i < length (b :: t) - 1),
        R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
          (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })) →
    R a b ∧
      (∀ (h : 0 < length t), R b (get t { val := 0, isLt := h })) ∧
        ∀ (i : ℕ) (h : i < length t - 1),
          R (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
[PROOFSTEP]
rintro ⟨h0, h⟩
[GOAL]
case mpr.intro
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
⊢ R a b ∧
    (∀ (h : 0 < length t), R b (get t { val := 0, isLt := h })) ∧
      ∀ (i : ℕ) (h : i < length t - 1),
        R (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
[PROOFSTEP]
constructor
[GOAL]
case mpr.intro.left
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
⊢ R a b
[PROOFSTEP]
apply h0
[GOAL]
case mpr.intro.left
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
⊢ 0 < length (b :: t)
[PROOFSTEP]
simp
[GOAL]
case mpr.intro.right
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
⊢ (∀ (h : 0 < length t), R b (get t { val := 0, isLt := h })) ∧
    ∀ (i : ℕ) (h : i < length t - 1),
      R (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
[PROOFSTEP]
constructor
[GOAL]
case mpr.intro.right.left
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
⊢ ∀ (h : 0 < length t), R b (get t { val := 0, isLt := h })
[PROOFSTEP]
apply h 0
[GOAL]
case mpr.intro.right.right
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
⊢ ∀ (i : ℕ) (h : i < length t - 1),
    R (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
[PROOFSTEP]
intro i w
[GOAL]
case mpr.intro.right.right
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
h0 : ∀ (h : 0 < length (b :: t)), R a (get (b :: t) { val := 0, isLt := h })
h :
  ∀ (i : ℕ) (h : i < length (b :: t) - 1),
    R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
      (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })
i : ℕ
w : i < length t - 1
⊢ R (get t { val := i, isLt := (_ : i < length t) }) (get t { val := i + 1, isLt := (_ : succ i < length t) })
[PROOFSTEP]
exact h (i + 1) (lt_pred_iff.mp w)
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
l : List α
⊢ Chain R a l ↔
    (∀ (h : 0 < length l), R a (nthLe l 0 h)) ∧
      ∀ (i : ℕ) (h : i < length l - 1), R (nthLe l i (_ : i < length l)) (nthLe l (i + 1) (_ : succ i < length l))
[PROOFSTEP]
rw [chain_iff_get]
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
l : List α
⊢ ((∀ (h : 0 < length l), R a (get l { val := 0, isLt := h })) ∧
      ∀ (i : ℕ) (h : i < length l - 1),
        R (get l { val := i, isLt := (_ : i < length l) }) (get l { val := i + 1, isLt := (_ : succ i < length l) })) ↔
    (∀ (h : 0 < length l), R a (nthLe l 0 h)) ∧
      ∀ (i : ℕ) (h : i < length l - 1), R (nthLe l i (_ : i < length l)) (nthLe l (i + 1) (_ : succ i < length l))
[PROOFSTEP]
simp [nthLe]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
S : α → α → Prop
H : ∀ (a b : α), R a b → S a b
l : List α
p : Chain' R l
⊢ Chain' S l
[PROOFSTEP]
cases l <;> [trivial; exact Chain.imp H p]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
S : α → α → Prop
H : ∀ (a b : α), R a b → S a b
l : List α
p : Chain' R l
⊢ Chain' S l
[PROOFSTEP]
cases l
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
S : α → α → Prop
H : ∀ (a b : α), R a b → S a b
p : Chain' R []
⊢ Chain' S []
[PROOFSTEP]
trivial
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
S : α → α → Prop
H : ∀ (a b : α), R a b → S a b
head✝ : α
tail✝ : List α
p : Chain' R (head✝ :: tail✝)
⊢ Chain' S (head✝ :: tail✝)
[PROOFSTEP]
exact Chain.imp H p
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ a b : α
l : List α
⊢ [] ++ [a, b] ++ l = a :: b :: l
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ a b : α
l : List α
x y : α
h : [x, y] <:+: b :: l
⊢ [a] ++ b :: l ++ [] = a :: b :: l
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b✝ b c : α
l₁ l₂ : List α
⊢ Chain' R (l₁ ++ b :: c :: l₂) ↔ Chain' R (l₁ ++ [b]) ∧ R b c ∧ Chain' R (c :: l₂)
[PROOFSTEP]
rw [chain'_split, chain'_cons]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
f : β → α
l : List β
⊢ Chain' R (map f l) ↔ Chain' (fun a b => R (f a) (f b)) l
[PROOFSTEP]
cases l <;> [rfl; exact chain_map _]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
f : β → α
l : List β
⊢ Chain' R (map f l) ↔ Chain' (fun a b => R (f a) (f b)) l
[PROOFSTEP]
cases l
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
f : β → α
⊢ Chain' R (map f []) ↔ Chain' (fun a b => R (f a) (f b)) []
[PROOFSTEP]
rfl
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
f : β → α
head✝ : β
tail✝ : List β
⊢ Chain' R (map f (head✝ :: tail✝)) ↔ Chain' (fun a b => R (f a) (f b)) (head✝ :: tail✝)
[PROOFSTEP]
exact chain_map _
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
inst✝ : IsTrans α R
hl : Chain' R l₂
h : l₁ <+ l₂
⊢ Chain' R l₁
[PROOFSTEP]
rw [chain'_iff_pairwise] at hl ⊢
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
inst✝ : IsTrans α R
hl : Pairwise R l₂
h : l₁ <+ l₂
⊢ Pairwise R l₁
[PROOFSTEP]
exact hl.sublist h
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b x : α
l : List α
h : Chain' R (x :: l)
y : α
hy : y ∈ head? l
⊢ R x y
[PROOFSTEP]
rw [← cons_head?_tail hy] at h 
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b x : α
l : List α
y : α
h : Chain' R (x :: y :: List.tail l)
hy : y ∈ head? l
⊢ R x y
[PROOFSTEP]
exact h.rel_head
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
l : List α
⊢ Chain' R ([] ++ l) ↔ Chain' R [] ∧ Chain' R l ∧ ∀ (x : α), x ∈ getLast? [] → ∀ (y : α), y ∈ head? l → R x y
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b a : α
l : List α
⊢ Chain' R ([a] ++ l) ↔ Chain' R [a] ∧ Chain' R l ∧ ∀ (x : α), x ∈ getLast? [a] → ∀ (y : α), y ∈ head? l → R x y
[PROOFSTEP]
simp [chain'_cons', and_comm]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a✝ b✝ a b : α
l₁ l₂ : List α
⊢ Chain' R (a :: b :: l₁ ++ l₂) ↔
    Chain' R (a :: b :: l₁) ∧ Chain' R l₂ ∧ ∀ (x : α), x ∈ getLast? (a :: b :: l₁) → ∀ (y : α), y ∈ head? l₂ → R x y
[PROOFSTEP]
rw [cons_append, cons_append, chain'_cons, chain'_cons, ← cons_append, chain'_append, and_assoc]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a✝ b✝ a b : α
l₁ l₂ : List α
⊢ (R a b ∧ Chain' R (b :: l₁) ∧ Chain' R l₂ ∧ ∀ (x : α), x ∈ getLast? (b :: l₁) → ∀ (y : α), y ∈ head? l₂ → R x y) ↔
    R a b ∧ Chain' R (b :: l₁) ∧ Chain' R l₂ ∧ ∀ (x : α), x ∈ getLast? (a :: b :: l₁) → ∀ (y : α), y ∈ head? l₂ → R x y
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
h : Chain' R l
h' : l₁ <:+: l
⊢ Chain' R l₁
[PROOFSTEP]
rcases h' with ⟨l₂, l₃, rfl⟩
[GOAL]
case intro.intro
α : Type u
β : Type v
R r : α → α → Prop
l₁ l₂✝ : List α
a b : α
l₂ l₃ : List α
h : Chain' R (l₂ ++ l₁ ++ l₃)
⊢ Chain' R l₁
[PROOFSTEP]
exact h.left_of_append.right_of_append
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b x y : α
⊢ Chain' R [x, y] ↔ R x y
[PROOFSTEP]
simp only [chain'_singleton, chain'_cons, and_true_iff]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a✝ b a : α
⊢ Chain' R (reverse [a]) ↔ Chain' (flip R) [a]
[PROOFSTEP]
simp only [chain'_singleton, reverse_singleton]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b✝ a b : α
l : List α
⊢ Chain' R (reverse (a :: b :: l)) ↔ Chain' (flip R) (a :: b :: l)
[PROOFSTEP]
rw [chain'_cons, reverse_cons, reverse_cons, append_assoc, cons_append, nil_append, chain'_split, ← reverse_cons,
  @chain'_reverse (b :: l), and_comm, chain'_pair, flip]
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a b : α
R : α → α → Prop
⊢ Chain' R []
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a b : α
R : α → α → Prop
x✝ : ℕ
h : x✝ < length [] - 1
⊢ R (get [] { val := x✝, isLt := (_ : x✝ < length []) }) (get [] { val := x✝ + 1, isLt := (_ : succ x✝ < length []) })
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
⊢ Chain' R [a]
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b : α
R : α → α → Prop
a : α
x✝ : ℕ
h : x✝ < length [a] - 1
⊢ R (get [a] { val := x✝, isLt := (_ : x✝ < length [a]) })
    (get [a] { val := x✝ + 1, isLt := (_ : succ x✝ < length [a]) })
[PROOFSTEP]
simp at h 
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ Chain' R (a :: b :: t) ↔
    ∀ (i : ℕ) (h : i < length (a :: b :: t) - 1),
      R (get (a :: b :: t) { val := i, isLt := (_ : i < length (a :: b :: t)) })
        (get (a :: b :: t) { val := i + 1, isLt := (_ : succ i < length (a :: b :: t)) })
[PROOFSTEP]
rw [← and_forall_succ, chain'_cons, chain'_iff_get]
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ (R a b ∧
      ∀ (i : ℕ) (h : i < length (b :: t) - 1),
        R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
          (get (b :: t) { val := i + 1, isLt := (_ : succ i < length (b :: t)) })) ↔
    (∀ (h : 0 < length (a :: b :: t) - 1),
        R (get (a :: b :: t) { val := 0, isLt := (_ : 0 < length (a :: b :: t)) })
          (get (a :: b :: t) { val := 0 + 1, isLt := (_ : succ 0 < length (a :: b :: t)) })) ∧
      ∀ (n : ℕ) (h : n + 1 < length (a :: b :: t) - 1),
        R (get (a :: b :: t) { val := n + 1, isLt := (_ : n + 1 < length (a :: b :: t)) })
          (get (a :: b :: t) { val := n + 1 + 1, isLt := (_ : succ (n + 1) < length (a :: b :: t)) })
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ R a b →
    ((∀ (i : ℕ) (h : i < length (b :: t) - 1),
        R (get (b :: t) { val := i, isLt := (_ : i < length (b :: t)) })
          (get t { val := i, isLt := (_ : i < length t) })) ↔
      ∀ (n : ℕ) (h : n + 1 < length (a :: b :: t) - 1),
        R (get (b :: t) { val := n, isLt := (_ : n < length (b :: t)) })
          (get t { val := n, isLt := (_ : n < length t) }))
[PROOFSTEP]
dsimp [succ_sub_one]
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l l₁ l₂ : List α
a✝ b✝ : α
R : α → α → Prop
a b : α
t : List α
⊢ R a b →
    ((∀ (i : ℕ) (h : i < length t),
        R (get (b :: t) { val := i, isLt := (_ : i < succ (length t)) })
          (get t { val := i, isLt := (_ : succ i ≤ length t) })) ↔
      ∀ (n : ℕ) (h : n + 1 < length t + 1),
        R (get (b :: t) { val := n, isLt := (_ : succ n ≤ length (b :: t)) })
          (get t { val := n, isLt := (_ : succ n ≤ length t) }))
[PROOFSTEP]
exact fun _ => ⟨fun h i hi => h i (Nat.lt_of_succ_lt_succ hi), fun h i hi => h i (Nat.succ_lt_succ hi)⟩
[GOAL]
α : Type u
β : Type v
R✝ r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
R : α → α → Prop
l : List α
⊢ (∀ (i : ℕ) (h : i < length l - 1),
      R (get l { val := i, isLt := (_ : i < length l) }) (get l { val := i + 1, isLt := (_ : succ i < length l) })) ↔
    ∀ (i : ℕ) (h : i < length l - 1), R (nthLe l i (_ : i < length l)) (nthLe l (i + 1) (_ : succ i < length l))
[PROOFSTEP]
simp [nthLe]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b : α
l₁ l₂ l₃ : List α
h₁ : Chain' R (l₁ ++ l₂)
h₂ : Chain' R (l₂ ++ l₃)
hn : l₂ ≠ []
⊢ ∀ (x : α), x ∈ getLast? (l₁ ++ l₂) → ∀ (y : α), y ∈ head? l₃ → R x y
[PROOFSTEP]
simpa only [getLast?_append_of_ne_nil _ hn] using (chain'_append.1 h₂).2.2
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
x✝ : ¬[] ∈ []
⊢ Chain' R (join []) ↔
    (∀ (l : List α), l ∈ [] → Chain' R l) ∧
      Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) []
[PROOFSTEP]
simp
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
l : List α
x✝ : ¬[] ∈ [l]
⊢ Chain' R (join [l]) ↔
    (∀ (l_1 : List α), l_1 ∈ [l] → Chain' R l_1) ∧
      Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) [l]
[PROOFSTEP]
simp [join]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b : α
l₁ l₂ : List α
L : List (List α)
hL : ¬[] ∈ l₁ :: l₂ :: L
⊢ Chain' R (join (l₁ :: l₂ :: L)) ↔
    (∀ (l : List α), l ∈ l₁ :: l₂ :: L → Chain' R l) ∧
      Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₁ :: l₂ :: L)
[PROOFSTEP]
rw [mem_cons, not_or, ← Ne.def] at hL 
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b : α
l₁ l₂ : List α
L : List (List α)
hL : [] ≠ l₁ ∧ ¬[] ∈ l₂ :: L
⊢ Chain' R (join (l₁ :: l₂ :: L)) ↔
    (∀ (l : List α), l ∈ l₁ :: l₂ :: L → Chain' R l) ∧
      Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₁ :: l₂ :: L)
[PROOFSTEP]
rw [join, chain'_append, chain'_join hL.2, forall_mem_cons, chain'_cons]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b : α
l₁ l₂ : List α
L : List (List α)
hL : [] ≠ l₁ ∧ ¬[] ∈ l₂ :: L
⊢ (Chain' R l₁ ∧
      ((Chain' R l₂ ∧ ∀ (x : List α), x ∈ L → Chain' R x) ∧
          Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₂ :: L)) ∧
        ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? (join (l₂ :: L)) → R x y) ↔
    (∀ (l : List α), l ∈ l₁ :: l₂ :: L → Chain' R l) ∧
      (∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) ∧
        Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₂ :: L)
[PROOFSTEP]
rw [mem_cons, not_or, ← Ne.def] at hL 
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b : α
l₁ l₂ : List α
L : List (List α)
hL : [] ≠ l₁ ∧ [] ≠ l₂ ∧ ¬[] ∈ L
⊢ (Chain' R l₁ ∧
      ((Chain' R l₂ ∧ ∀ (x : List α), x ∈ L → Chain' R x) ∧
          Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₂ :: L)) ∧
        ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? (join (l₂ :: L)) → R x y) ↔
    (∀ (l : List α), l ∈ l₁ :: l₂ :: L → Chain' R l) ∧
      (∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) ∧
        Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₂ :: L)
[PROOFSTEP]
simp only [forall_mem_cons, and_assoc, join, head?_append_of_ne_nil _ hL.2.1.symm]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁✝ l₂✝ : List α
a b : α
l₁ l₂ : List α
L : List (List α)
hL : [] ≠ l₁ ∧ [] ≠ l₂ ∧ ¬[] ∈ L
⊢ (Chain' R l₁ ∧
      Chain' R l₂ ∧
        (∀ (x : List α), x ∈ L → Chain' R x) ∧
          Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₂ :: L) ∧
            ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) ↔
    Chain' R l₁ ∧
      Chain' R l₂ ∧
        (∀ (x : List α), x ∈ L → Chain' R x) ∧
          (∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) ∧
            Chain' (fun l₁ l₂ => ∀ (x : α), x ∈ getLast? l₁ → ∀ (y : α), y ∈ head? l₂ → R x y) (l₂ :: L)
[PROOFSTEP]
exact Iff.rfl.and (Iff.rfl.and $ Iff.rfl.and and_comm)
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
h : Relation.ReflTransGen r a b
⊢ ∃ l, Chain r a l ∧ getLast (a :: l) (_ : a :: l ≠ []) = b
[PROOFSTEP]
refine' Relation.ReflTransGen.head_induction_on h _ _
[GOAL]
case refine'_1
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
h : Relation.ReflTransGen r a b
⊢ ∃ l, Chain r b l ∧ getLast (b :: l) (_ : b :: l ≠ []) = b
[PROOFSTEP]
exact ⟨[], Chain.nil, rfl⟩
[GOAL]
case refine'_2
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
h : Relation.ReflTransGen r a b
⊢ ∀ {a c : α},
    r a c →
      Relation.ReflTransGen r c b →
        (∃ l, Chain r c l ∧ getLast (c :: l) (_ : c :: l ≠ []) = b) →
          ∃ l, Chain r a l ∧ getLast (a :: l) (_ : a :: l ≠ []) = b
[PROOFSTEP]
intro c d e _ ih
[GOAL]
case refine'_2
α : Type u
β : Type v
R r : α → α → Prop
l l₁ l₂ : List α
a b : α
h : Relation.ReflTransGen r a b
c d : α
e : r c d
h✝ : Relation.ReflTransGen r d b
ih : ∃ l, Chain r d l ∧ getLast (d :: l) (_ : d :: l ≠ []) = b
⊢ ∃ l, Chain r c l ∧ getLast (c :: l) (_ : c :: l ≠ []) = b
[PROOFSTEP]
obtain ⟨l, hl₁, hl₂⟩ := ih
[GOAL]
case refine'_2.intro.intro
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
h : Relation.ReflTransGen r a b
c d : α
e : r c d
h✝ : Relation.ReflTransGen r d b
l : List α
hl₁ : Chain r d l
hl₂ : getLast (d :: l) (_ : d :: l ≠ []) = b
⊢ ∃ l, Chain r c l ∧ getLast (c :: l) (_ : c :: l ≠ []) = b
[PROOFSTEP]
refine' ⟨d :: l, Chain.cons e hl₁, _⟩
[GOAL]
case refine'_2.intro.intro
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
h : Relation.ReflTransGen r a b
c d : α
e : r c d
h✝ : Relation.ReflTransGen r d b
l : List α
hl₁ : Chain r d l
hl₂ : getLast (d :: l) (_ : d :: l ≠ []) = b
⊢ getLast (c :: d :: l) (_ : c :: d :: l ≠ []) = b
[PROOFSTEP]
rwa [getLast_cons_cons]
[GOAL]
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
p : α → Prop
l : List α
h : Chain r a l
hb : getLast (a :: l) (_ : a :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
⊢ ∀ (i : α), i ∈ a :: l → p i
[PROOFSTEP]
induction' l with _ _ l_ih generalizing a
[GOAL]
case nil
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
hb✝ : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
a : α
h : Chain r a []
hb : getLast [a] (_ : [a] ≠ []) = b
⊢ ∀ (i : α), i ∈ [a] → p i
[PROOFSTEP]
cases hb
[GOAL]
case nil.refl
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
a : α
h : Chain r a []
hb : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = getLast [a] (_ : [a] ≠ [])
final : p (getLast [a] (_ : [a] ≠ []))
⊢ ∀ (i : α), i ∈ [a] → p i
[PROOFSTEP]
simpa using final
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
hb✝ : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
head✝ : α
tail✝ : List α
l_ih : ∀ {a : α}, Chain r a tail✝ → getLast (a :: tail✝) (_ : a :: tail✝ ≠ []) = b → ∀ (i : α), i ∈ a :: tail✝ → p i
a : α
h : Chain r a (head✝ :: tail✝)
hb : getLast (a :: head✝ :: tail✝) (_ : a :: head✝ :: tail✝ ≠ []) = b
⊢ ∀ (i : α), i ∈ a :: head✝ :: tail✝ → p i
[PROOFSTEP]
rw [chain_cons] at h 
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
hb✝ : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
head✝ : α
tail✝ : List α
l_ih : ∀ {a : α}, Chain r a tail✝ → getLast (a :: tail✝) (_ : a :: tail✝ ≠ []) = b → ∀ (i : α), i ∈ a :: tail✝ → p i
a : α
h : r a head✝ ∧ Chain r head✝ tail✝
hb : getLast (a :: head✝ :: tail✝) (_ : a :: head✝ :: tail✝ ≠ []) = b
⊢ ∀ (i : α), i ∈ a :: head✝ :: tail✝ → p i
[PROOFSTEP]
simp only [mem_cons]
[GOAL]
case cons
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
hb✝ : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
head✝ : α
tail✝ : List α
l_ih : ∀ {a : α}, Chain r a tail✝ → getLast (a :: tail✝) (_ : a :: tail✝ ≠ []) = b → ∀ (i : α), i ∈ a :: tail✝ → p i
a : α
h : r a head✝ ∧ Chain r head✝ tail✝
hb : getLast (a :: head✝ :: tail✝) (_ : a :: head✝ :: tail✝ ≠ []) = b
⊢ ∀ (i : α), i = a ∨ i = head✝ ∨ i ∈ tail✝ → p i
[PROOFSTEP]
rintro _ (rfl | H)
[GOAL]
case cons.inl
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a b : α
p : α → Prop
l : List α
h✝ : Chain r a l
hb✝ : getLast (a :: l) (_ : a :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
head✝ : α
tail✝ : List α
l_ih : ∀ {a : α}, Chain r a tail✝ → getLast (a :: tail✝) (_ : a :: tail✝ ≠ []) = b → ∀ (i : α), i ∈ a :: tail✝ → p i
i✝ : α
h : r i✝ head✝ ∧ Chain r head✝ tail✝
hb : getLast (i✝ :: head✝ :: tail✝) (_ : i✝ :: head✝ :: tail✝ ≠ []) = b
⊢ p i✝
case cons.inr
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
hb✝ : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
head✝ : α
tail✝ : List α
l_ih : ∀ {a : α}, Chain r a tail✝ → getLast (a :: tail✝) (_ : a :: tail✝ ≠ []) = b → ∀ (i : α), i ∈ a :: tail✝ → p i
a : α
h : r a head✝ ∧ Chain r head✝ tail✝
hb : getLast (a :: head✝ :: tail✝) (_ : a :: head✝ :: tail✝ ≠ []) = b
i✝ : α
H : i✝ = head✝ ∨ i✝ ∈ tail✝
⊢ p i✝
[PROOFSTEP]
apply carries h.1 (l_ih h.2 hb _ (mem_cons.2 (Or.inl rfl)))
[GOAL]
case cons.inr
α : Type u
β : Type v
R r : α → α → Prop
l✝ l₁ l₂ : List α
a✝ b : α
p : α → Prop
l : List α
h✝ : Chain r a✝ l
hb✝ : getLast (a✝ :: l) (_ : a✝ :: l ≠ []) = b
carries : ∀ ⦃x y : α⦄, r x y → p y → p x
final : p b
head✝ : α
tail✝ : List α
l_ih : ∀ {a : α}, Chain r a tail✝ → getLast (a :: tail✝) (_ : a :: tail✝ ≠ []) = b → ∀ (i : α), i ∈ a :: tail✝ → p i
a : α
h : r a head✝ ∧ Chain r head✝ tail✝
hb : getLast (a :: head✝ :: tail✝) (_ : a :: head✝ :: tail✝ ≠ []) = b
i✝ : α
H : i✝ = head✝ ∨ i✝ ∈ tail✝
⊢ p i✝
[PROOFSTEP]
apply l_ih h.2 hb _ (mem_cons.2 H)
[GOAL]
α : Type u_1
r : α → α → Prop
l : List.chains r
acc : ∀ (a : α), a ∈ List.head? ↑l → Acc r a
⊢ Acc (List.lex_chains r) l
[PROOFSTEP]
obtain ⟨_ | ⟨a, l⟩, hl⟩ := l
[GOAL]
case mk.nil
α : Type u_1
r : α → α → Prop
hl : List.Chain' (flip r) []
acc : ∀ (a : α), a ∈ List.head? ↑{ val := [], property := hl } → Acc r a
⊢ Acc (List.lex_chains r) { val := [], property := hl }
[PROOFSTEP]
apply Acc.intro
[GOAL]
case mk.nil.h
α : Type u_1
r : α → α → Prop
hl : List.Chain' (flip r) []
acc : ∀ (a : α), a ∈ List.head? ↑{ val := [], property := hl } → Acc r a
⊢ ∀ (y : List.chains r), List.lex_chains r y { val := [], property := hl } → Acc (List.lex_chains r) y
[PROOFSTEP]
rintro ⟨_⟩ ⟨_⟩
[GOAL]
case mk.cons
α : Type u_1
r : α → α → Prop
a : α
l : List α
hl : List.Chain' (flip r) (a :: l)
acc : ∀ (a_1 : α), a_1 ∈ List.head? ↑{ val := a :: l, property := hl } → Acc r a_1
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
specialize acc a _
[GOAL]
case mk.cons
α : Type u_1
r : α → α → Prop
a : α
l : List α
hl : List.Chain' (flip r) (a :: l)
acc : ∀ (a_1 : α), a_1 ∈ List.head? ↑{ val := a :: l, property := hl } → Acc r a_1
⊢ a ∈ List.head? ↑{ val := a :: l, property := hl }
[PROOFSTEP]
rw [List.head?_cons, Option.mem_some_iff]
  /- For an r-decreasing chain of the form a :: l, apply induction on a -/
[GOAL]
case mk.cons
α : Type u_1
r : α → α → Prop
a : α
l : List α
hl : List.Chain' (flip r) (a :: l)
acc : Acc r a
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
induction acc generalizing l with
| intro a _ ih =>
  /- Bundle l with a proof that it is r-decreasing to form l' -/
  have hl' := (List.chain'_cons'.1 hl).2
  let l' : List.chains r := ⟨l, hl'⟩
  have : Acc (List.lex_chains r) l'
  · cases' l with b l
    · apply Acc.intro;
      rintro ⟨_⟩
        ⟨_⟩
            /- l' is accessible by induction hypothesis -/
    ·
      apply
        ih b
          (List.chain'_cons.1 hl).1
            /- make l' a free variable and induct on l' -/
  revert hl
  rw [(by rfl : l = l'.1)]
  clear_value l'
  induction this with
  | intro l _ ihl =>
    intro hl
    apply Acc.intro
    rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
    · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
    · apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
    · apply ih b hr
[GOAL]
case mk.cons
α : Type u_1
r : α → α → Prop
a : α
l : List α
hl : List.Chain' (flip r) (a :: l)
acc : Acc r a
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
induction acc generalizing l with
| intro a _ ih =>
  /- Bundle l with a proof that it is r-decreasing to form l' -/
  have hl' := (List.chain'_cons'.1 hl).2
  let l' : List.chains r := ⟨l, hl'⟩
  have : Acc (List.lex_chains r) l'
  · cases' l with b l
    · apply Acc.intro;
      rintro ⟨_⟩
        ⟨_⟩
            /- l' is accessible by induction hypothesis -/
    ·
      apply
        ih b
          (List.chain'_cons.1 hl).1
            /- make l' a free variable and induct on l' -/
  revert hl
  rw [(by rfl : l = l'.1)]
  clear_value l'
  induction this with
  | intro l _ ihl =>
    intro hl
    apply Acc.intro
    rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
    · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
    · apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
    · apply ih b hr
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl : List.Chain' (flip r) (a :: l)
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]

| intro a _ ih =>
  /- Bundle l with a proof that it is r-decreasing to form l' -/
  have hl' := (List.chain'_cons'.1 hl).2
  let l' : List.chains r := ⟨l, hl'⟩
  have : Acc (List.lex_chains r) l'
  · cases' l with b l
    · apply Acc.intro;
      rintro ⟨_⟩
        ⟨_⟩
            /- l' is accessible by induction hypothesis -/
    ·
      apply
        ih b
          (List.chain'_cons.1 hl).1
            /- make l' a free variable and induct on l' -/
  revert hl
  rw [(by rfl : l = l'.1)]
  clear_value l'
  induction this with
  | intro l _ ihl =>
    intro hl
    apply Acc.intro
    rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
    · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
    · apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
    · apply ih b hr
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl : List.Chain' (flip r) (a :: l)
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
have hl' := (List.chain'_cons'.1 hl).2
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl : List.Chain' (flip r) (a :: l)
hl' : List.Chain' (flip r) l
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
let l' : List.chains r := ⟨l, hl'⟩
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl : List.Chain' (flip r) (a :: l)
hl' : List.Chain' (flip r) l
l' : List.chains r := { val := l, property := hl' }
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
have : Acc (List.lex_chains r) l'
[GOAL]
case this
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl : List.Chain' (flip r) (a :: l)
hl' : List.Chain' (flip r) l
l' : List.chains r := { val := l, property := hl' }
⊢ Acc (List.lex_chains r) l'
[PROOFSTEP]
cases' l with b l
[GOAL]
case this.nil
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
hl : List.Chain' (flip r) [a]
hl' : List.Chain' (flip r) []
l' : List.chains r := { val := [], property := hl' }
⊢ Acc (List.lex_chains r) l'
[PROOFSTEP]
apply Acc.intro
[GOAL]
case this.nil.h
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
hl : List.Chain' (flip r) [a]
hl' : List.Chain' (flip r) []
l' : List.chains r := { val := [], property := hl' }
⊢ ∀ (y : List.chains r), List.lex_chains r y l' → Acc (List.lex_chains r) y
[PROOFSTEP]
rintro ⟨_⟩
  ⟨_⟩
      /- l' is accessible by induction hypothesis -/
[GOAL]
case this.cons
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
b : α
l : List α
hl : List.Chain' (flip r) (a :: b :: l)
hl' : List.Chain' (flip r) (b :: l)
l' : List.chains r := { val := b :: l, property := hl' }
⊢ Acc (List.lex_chains r) l'
[PROOFSTEP]
apply
  ih b
    (List.chain'_cons.1 hl).1
      /- make l' a free variable and induct on l' -/
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl : List.Chain' (flip r) (a :: l)
hl' : List.Chain' (flip r) l
l' : List.chains r := { val := l, property := hl' }
this : Acc (List.lex_chains r) l'
⊢ Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
revert hl
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl' : List.Chain' (flip r) l
l' : List.chains r := { val := l, property := hl' }
this : Acc (List.lex_chains r) l'
⊢ ∀ (hl : List.Chain' (flip r) (a :: l)), Acc (List.lex_chains r) { val := a :: l, property := hl }
[PROOFSTEP]
rw [(by rfl : l = l'.1)]
[GOAL]
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl' : List.Chain' (flip r) l
l' : List.chains r := { val := l, property := hl' }
this : Acc (List.lex_chains r) l'
⊢ l = ↑l'
[PROOFSTEP]
rfl
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl' : List.Chain' (flip r) l
l' : List.chains r := { val := l, property := hl' }
this : Acc (List.lex_chains r) l'
⊢ ∀ (hl : List.Chain' (flip r) (a :: ↑l')), Acc (List.lex_chains r) { val := a :: ↑l', property := hl }
[PROOFSTEP]
clear_value l'
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl' : List.Chain' (flip r) l
l' : List.chains r
this : Acc (List.lex_chains r) l'
⊢ ∀ (hl : List.Chain' (flip r) (a :: ↑l')), Acc (List.lex_chains r) { val := a :: ↑l', property := hl }
[PROOFSTEP]
induction this with
| intro l _ ihl =>
  intro hl
  apply Acc.intro
  rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
  · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
  · apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
  · apply ih b hr
[GOAL]
case mk.cons.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l : List α
hl' : List.Chain' (flip r) l
l' : List.chains r
this : Acc (List.lex_chains r) l'
⊢ ∀ (hl : List.Chain' (flip r) (a :: ↑l')), Acc (List.lex_chains r) { val := a :: ↑l', property := hl }
[PROOFSTEP]
induction this with
| intro l _ ihl =>
  intro hl
  apply Acc.intro
  rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
  · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
  · apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
  · apply ih b hr
[GOAL]
case mk.cons.intro.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
⊢ ∀ (hl : List.Chain' (flip r) (a :: ↑l)), Acc (List.lex_chains r) { val := a :: ↑l, property := hl }
[PROOFSTEP]

| intro l _ ihl =>
  intro hl
  apply Acc.intro
  rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
  · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
  · apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
  · apply ih b hr
[GOAL]
case mk.cons.intro.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
⊢ ∀ (hl : List.Chain' (flip r) (a :: ↑l)), Acc (List.lex_chains r) { val := a :: ↑l, property := hl }
[PROOFSTEP]
intro hl
[GOAL]
case mk.cons.intro.intro
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
hl : List.Chain' (flip r) (a :: ↑l)
⊢ Acc (List.lex_chains r) { val := a :: ↑l, property := hl }
[PROOFSTEP]
apply Acc.intro
[GOAL]
case mk.cons.intro.intro.h
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
hl : List.Chain' (flip r) (a :: ↑l)
⊢ ∀ (y : List.chains r), List.lex_chains r y { val := a :: ↑l, property := hl } → Acc (List.lex_chains r) y
[PROOFSTEP]
rintro ⟨_ | ⟨b, m⟩, hm⟩ (_ | hr | hr)
[GOAL]
case mk.cons.intro.intro.h.mk.nil.nil
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
hl : List.Chain' (flip r) (a :: ↑l)
hm : List.Chain' (flip r) []
⊢ Acc (List.lex_chains r) { val := [], property := hm }
[PROOFSTEP]
apply Acc.intro
[GOAL]
case mk.cons.intro.intro.h.mk.nil.nil.h
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
hl : List.Chain' (flip r) (a :: ↑l)
hm : List.Chain' (flip r) []
⊢ ∀ (y : List.chains r), List.lex_chains r y { val := [], property := hm } → Acc (List.lex_chains r) y
[PROOFSTEP]
rintro ⟨_⟩ ⟨_⟩
[GOAL]
case mk.cons.intro.intro.h.mk.cons.cons
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
hl : List.Chain' (flip r) (a :: ↑l)
m : List α
hm : List.Chain' (flip r) (a :: m)
hr : List.Lex r m ↑l
⊢ Acc (List.lex_chains r) { val := a :: m, property := hm }
[PROOFSTEP]
apply ihl ⟨m, (List.chain'_cons'.1 hm).2⟩ hr
[GOAL]
case mk.cons.intro.intro.h.mk.cons.rel
α : Type u_1
r : α → α → Prop
a✝ a : α
h✝¹ : ∀ (y : α), r y a → Acc r y
ih :
  ∀ (y : α),
    r y a →
      ∀ (l : List α) (hl : List.Chain' (flip r) (y :: l)), Acc (List.lex_chains r) { val := y :: l, property := hl }
l✝ : List α
hl' : List.Chain' (flip r) l✝
l' l : List.chains r
h✝ : ∀ (y : List.chains r), List.lex_chains r y l → Acc (List.lex_chains r) y
ihl :
  ∀ (y : List.chains r),
    List.lex_chains r y l →
      ∀ (hl : List.Chain' (flip r) (a :: ↑y)), Acc (List.lex_chains r) { val := a :: ↑y, property := hl }
hl : List.Chain' (flip r) (a :: ↑l)
b : α
m : List α
hm : List.Chain' (flip r) (b :: m)
hr : r b a
⊢ Acc (List.lex_chains r) { val := b :: m, property := hm }
[PROOFSTEP]
apply ih b hr
