mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -87,7 +87,7 @@ theorem chain_singleton {a b : α} : Chain R a [b] ↔ R a b := by
 theorem chain_split {a b : α} {l₁ l₂ : List α} :
     Chain R a (l₁ ++ b :: l₂) ↔ Chain R a (l₁ ++ [b]) ∧ Chain R b l₂ := by
   induction' l₁ with x l₁ IH generalizing a <;>
-    simp only [*, nil_append, cons_append, chain.nil, chain_cons, and_true_iff, and_assoc']
+    simp only [*, nil_append, cons_append, chain.nil, chain_cons, and_true_iff, and_assoc]
 #align list.chain_split List.chain_split
 -/
 
@@ -380,7 +380,7 @@ theorem chain'_append :
     ∀ {l₁ l₂ : List α},
       Chain' R (l₁ ++ l₂) ↔ Chain' R l₁ ∧ Chain' R l₂ ∧ ∀ x ∈ l₁.getLast?, ∀ y ∈ l₂.head?, R x y
   | [], l => by simp
-  | [a], l => by simp [chain'_cons', and_comm']
+  | [a], l => by simp [chain'_cons', and_comm]
   | a :: b :: l₁, l₂ => by
     rw [cons_append, cons_append, chain'_cons, chain'_cons, ← cons_append, chain'_append, last',
       and_assoc]
@@ -461,7 +461,7 @@ theorem chain'_reverse : ∀ {l}, Chain' R (reverse l) ↔ Chain' (flip R) l
   | [a] => by simp only [chain'_singleton, reverse_singleton]
   | a :: b :: l => by
     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]
+      chain'_split, ← reverse_cons, @chain'_reverse (b :: l), and_comm, chain'_pair, flip]
 #align list.chain'_reverse List.chain'_reverse
 -/
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -162,7 +162,7 @@ protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l :=
   by
   cases' pairwise_cons.1 p with r p'; clear p
   induction' p' with b l r' p IH generalizing a; · exact chain.nil
-  simp only [chain_cons, forall_mem_cons] at r 
+  simp only [chain_cons, forall_mem_cons] at r
   exact chain_cons.2 ⟨r.1, IH r'⟩
 #align list.pairwise.chain List.Pairwise.chain
 -/
@@ -193,7 +193,7 @@ protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <
 
 #print List.Chain.rel /-
 protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b := by
-  rw [chain_iff_pairwise] at hl ; exact rel_of_pairwise_cons hl hb
+  rw [chain_iff_pairwise] at hl; exact rel_of_pairwise_cons hl hb
 #align list.chain.rel List.Chain.rel
 -/
 
@@ -215,7 +215,7 @@ theorem chain_iff_nthLe {R} :
       cases i
       · apply h0
       convert h i _ using 1
-      simp only [succ_eq_add_one, add_succ_sub_one, add_zero, length, add_lt_add_iff_right] at w 
+      simp only [succ_eq_add_one, add_succ_sub_one, add_zero, length, add_lt_add_iff_right] at w
       exact lt_pred_iff.mpr w
     rintro ⟨h0, h⟩; constructor
     · apply h0; simp
@@ -358,7 +358,7 @@ theorem Chain'.rel_head {x y l} (h : Chain' R (x :: y :: l)) : R x y :=
 
 #print List.Chain'.rel_head? /-
 theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y := by
-  rw [← cons_head'_tail hy] at h ; exact h.rel_head
+  rw [← cons_head'_tail hy] at h; exact h.rel_head
 #align list.chain'.rel_head' List.Chain'.rel_head?
 -/
 
@@ -520,7 +520,7 @@ theorem Chain.induction (p : α → Prop) (l : List α) (h : Chain r a l)
   induction l generalizing a
   · cases hb
     simp [final]
-  · rw [chain_cons] at h 
+  · rw [chain_cons] at h
     rintro _ (rfl | _)
     apply carries h.1 (l_ih h.2 hb _ (Or.inl rfl))
     apply l_ih h.2 hb _ H

mathlib commit https://github.com/leanprover-community/mathlib/commit/19c869efa56bbb8b500f2724c0b77261edbfa28c

@@ -414,13 +414,13 @@ theorem Chain'.infix (h : Chain' R l) (h' : l₁ <:+: l) : Chain' R l₁ := by
 
 #print List.Chain'.suffix /-
 theorem Chain'.suffix (h : Chain' R l) (h' : l₁ <:+ l) : Chain' R l₁ :=
-  h.infix h'.isInfix
+  h.infix h'.IsInfix
 #align list.chain'.suffix List.Chain'.suffix
 -/
 
 #print List.Chain'.prefix /-
 theorem Chain'.prefix (h : Chain' R l) (h' : l₁ <+: l) : Chain' R l₁ :=
-  h.infix h'.isInfix
+  h.infix h'.IsInfix
 #align list.chain'.prefix List.Chain'.prefix
 -/
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

@@ -3,8 +3,8 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
 -/
-import Mathbin.Data.List.Pairwise
-import Mathbin.Logic.Relation
+import Data.List.Pairwise
+import Logic.Relation
 
 #align_import data.list.chain from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

@@ -2,15 +2,12 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
-
-! This file was ported from Lean 3 source module data.list.chain
-! leanprover-community/mathlib commit be24ec5de6701447e5df5ca75400ffee19d65659
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.List.Pairwise
 import Mathbin.Logic.Relation
 
+#align_import data.list.chain from "leanprover-community/mathlib"@"be24ec5de6701447e5df5ca75400ffee19d65659"
+
 /-!
 # Relation chain
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

@@ -160,6 +160,7 @@ theorem chain_of_chain_pmap {S : β → β → Prop} {p : α → Prop} (f : ∀
 #align list.chain_of_chain_pmap List.chain_of_chain_pmap
 -/
 
+#print List.Pairwise.chain /-
 protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l :=
   by
   cases' pairwise_cons.1 p with r p'; clear p
@@ -167,6 +168,7 @@ protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l :=
   simp only [chain_cons, forall_mem_cons] at r 
   exact chain_cons.2 ⟨r.1, IH r'⟩
 #align list.pairwise.chain List.Pairwise.chain
+-/
 
 #print List.Chain.pairwise /-
 protected theorem Chain.pairwise [IsTrans α R] :

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

@@ -50,8 +50,8 @@ theorem chain_of_chain_cons {a b : α} {l : List α} (p : Chain R a (b :: l)) :
 #print List.Chain.imp' /-
 theorem Chain.imp' {S : α → α → Prop} (HRS : ∀ ⦃a b⦄, R a b → S a b) {a b : α}
     (Hab : ∀ ⦃c⦄, R a c → S b c) {l : List α} (p : Chain R a l) : Chain S b l := by
-  induction' p with _ a c l r p IH generalizing b <;> constructor <;>
-    [exact Hab r;exact IH (@HRS _)]
+  induction' p with _ a c l r p IH generalizing b <;> constructor <;> [exact Hab r;
+    exact IH (@HRS _)]
 #align list.chain.imp' List.Chain.imp'
 -/
 
@@ -74,9 +74,8 @@ theorem Chain.iff_mem {a : α} {l : List α} :
     Chain R a l ↔ Chain (fun x y => x ∈ a :: l ∧ y ∈ l ∧ R x y) a l :=
   ⟨fun p => by
     induction' p with _ a b l r p 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⟩],
+      [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⟩],
     Chain.imp fun a b h => h.2.2⟩
 #align list.chain.iff_mem List.Chain.iff_mem
 -/
@@ -161,15 +160,13 @@ theorem chain_of_chain_pmap {S : β → β → Prop} {p : α → Prop} (f : ∀
 #align list.chain_of_chain_pmap List.chain_of_chain_pmap
 -/
 
-#print List.Pairwise.chain /-
 protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l :=
   by
   cases' pairwise_cons.1 p with r p'; clear p
   induction' p' with b l r' p IH generalizing a; · exact chain.nil
-  simp only [chain_cons, forall_mem_cons] at r
+  simp only [chain_cons, forall_mem_cons] at r 
   exact chain_cons.2 ⟨r.1, IH r'⟩
 #align list.pairwise.chain List.Pairwise.chain
--/
 
 #print List.Chain.pairwise /-
 protected theorem Chain.pairwise [IsTrans α R] :
@@ -191,13 +188,13 @@ theorem chain_iff_pairwise [IsTrans α R] {a : α} {l : List α} : Chain R a l 
 
 #print List.Chain.sublist /-
 protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <+ l₂) : l₁.Chain R a :=
-  by rw [chain_iff_pairwise] at hl⊢; exact hl.sublist (h.cons_cons a)
+  by rw [chain_iff_pairwise] at hl ⊢; exact hl.sublist (h.cons_cons a)
 #align list.chain.sublist List.Chain.sublist
 -/
 
 #print List.Chain.rel /-
 protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b := by
-  rw [chain_iff_pairwise] at hl; exact rel_of_pairwise_cons hl hb
+  rw [chain_iff_pairwise] at hl ; exact rel_of_pairwise_cons hl hb
 #align list.chain.rel List.Chain.rel
 -/
 
@@ -219,7 +216,7 @@ theorem chain_iff_nthLe {R} :
       cases i
       · apply h0
       convert h i _ using 1
-      simp only [succ_eq_add_one, add_succ_sub_one, add_zero, length, add_lt_add_iff_right] at w
+      simp only [succ_eq_add_one, add_succ_sub_one, add_zero, length, add_lt_add_iff_right] at w 
       exact lt_pred_iff.mpr w
     rintro ⟨h0, h⟩; constructor
     · apply h0; simp
@@ -232,7 +229,7 @@ theorem chain_iff_nthLe {R} :
 
 #print List.Chain'.imp /-
 theorem Chain'.imp {S : α → α → Prop} (H : ∀ a b, R a b → S a b) {l : List α} (p : Chain' R l) :
-    Chain' S l := by cases l <;> [trivial;exact p.imp H]
+    Chain' S l := by cases l <;> [trivial; exact p.imp H]
 #align list.chain'.imp List.Chain'.imp
 -/
 
@@ -302,7 +299,7 @@ theorem chain'_append_cons_cons {b c : α} {l₁ l₂ : List α} :
 #print List.chain'_map /-
 theorem chain'_map (f : β → α) {l : List β} :
     Chain' R (map f l) ↔ Chain' (fun a b : β => R (f a) (f b)) l := by
-  cases l <;> [rfl;exact chain_map _]
+  cases l <;> [rfl; exact chain_map _]
 #align list.chain'_map List.chain'_map
 -/
 
@@ -336,7 +333,7 @@ theorem chain'_iff_pairwise [IsTrans α R] : ∀ {l : List α}, Chain' R l ↔ P
 
 #print List.Chain'.sublist /-
 protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R := by
-  rw [chain'_iff_pairwise] at hl⊢; exact hl.sublist h
+  rw [chain'_iff_pairwise] at hl ⊢; exact hl.sublist h
 #align list.chain'.sublist List.Chain'.sublist
 -/
 
@@ -362,7 +359,7 @@ theorem Chain'.rel_head {x y l} (h : Chain' R (x :: y :: l)) : R x y :=
 
 #print List.Chain'.rel_head? /-
 theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y := by
-  rw [← cons_head'_tail hy] at h; exact h.rel_head
+  rw [← cons_head'_tail hy] at h ; exact h.rel_head
 #align list.chain'.rel_head' List.Chain'.rel_head?
 -/
 
@@ -524,7 +521,7 @@ theorem Chain.induction (p : α → Prop) (l : List α) (h : Chain r a l)
   induction l generalizing a
   · cases hb
     simp [final]
-  · rw [chain_cons] at h
+  · rw [chain_cons] at h 
     rintro _ (rfl | _)
     apply carries h.1 (l_ih h.2 hb _ (Or.inl rfl))
     apply l_ih h.2 hb _ H

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -191,17 +191,13 @@ theorem chain_iff_pairwise [IsTrans α R] {a : α} {l : List α} : Chain R a l 
 
 #print List.Chain.sublist /-
 protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <+ l₂) : l₁.Chain R a :=
-  by
-  rw [chain_iff_pairwise] at hl⊢
-  exact hl.sublist (h.cons_cons a)
+  by rw [chain_iff_pairwise] at hl⊢; exact hl.sublist (h.cons_cons a)
 #align list.chain.sublist List.Chain.sublist
 -/
 
 #print List.Chain.rel /-
-protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b :=
-  by
-  rw [chain_iff_pairwise] at hl
-  exact rel_of_pairwise_cons hl hb
+protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b := by
+  rw [chain_iff_pairwise] at hl; exact rel_of_pairwise_cons hl hb
 #align list.chain.rel List.Chain.rel
 -/
 
@@ -218,8 +214,7 @@ theorem chain_iff_nthLe {R} :
     constructor
     · rintro ⟨R, ⟨h0, h⟩⟩
       constructor
-      · intro w
-        exact R
+      · intro w; exact R
       intro i w
       cases i
       · apply h0
@@ -227,8 +222,7 @@ theorem chain_iff_nthLe {R} :
       simp only [succ_eq_add_one, add_succ_sub_one, add_zero, length, add_lt_add_iff_right] at w
       exact lt_pred_iff.mpr w
     rintro ⟨h0, h⟩; constructor
-    · apply h0
-      simp
+    · apply h0; simp
     constructor
     · apply h 0
     intro i w; convert h (i + 1) _ using 1
@@ -341,10 +335,8 @@ theorem chain'_iff_pairwise [IsTrans α R] : ∀ {l : List α}, Chain' R l ↔ P
 -/
 
 #print List.Chain'.sublist /-
-protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R :=
-  by
-  rw [chain'_iff_pairwise] at hl⊢
-  exact hl.sublist h
+protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R := by
+  rw [chain'_iff_pairwise] at hl⊢; exact hl.sublist h
 #align list.chain'.sublist List.Chain'.sublist
 -/
 
@@ -369,10 +361,8 @@ theorem Chain'.rel_head {x y l} (h : Chain' R (x :: y :: l)) : R x y :=
 -/
 
 #print List.Chain'.rel_head? /-
-theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y :=
-  by
-  rw [← cons_head'_tail hy] at h
-  exact h.rel_head
+theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y := by
+  rw [← cons_head'_tail hy] at h; exact h.rel_head
 #align list.chain'.rel_head' List.Chain'.rel_head?
 -/
 
@@ -421,10 +411,8 @@ theorem Chain'.right_of_append (h : Chain' R (l₁ ++ l₂)) : Chain' R l₂ :=
 -/
 
 #print List.Chain'.infix /-
-theorem Chain'.infix (h : Chain' R l) (h' : l₁ <:+: l) : Chain' R l₁ :=
-  by
-  rcases h' with ⟨l₂, l₃, rfl⟩
-  exact h.left_of_append.right_of_append
+theorem Chain'.infix (h : Chain' R l) (h' : l₁ <:+: l) : Chain' R l₁ := by
+  rcases h' with ⟨l₂, l₃, rfl⟩; exact h.left_of_append.right_of_append
 #align list.chain'.infix List.Chain'.infix
 -/
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b

@@ -50,8 +50,8 @@ theorem chain_of_chain_cons {a b : α} {l : List α} (p : Chain R a (b :: l)) :
 #print List.Chain.imp' /-
 theorem Chain.imp' {S : α → α → Prop} (HRS : ∀ ⦃a b⦄, R a b → S a b) {a b : α}
     (Hab : ∀ ⦃c⦄, R a c → S b c) {l : List α} (p : Chain R a l) : Chain S b l := by
-  induction' p with _ a c l r p IH generalizing b <;> constructor <;> [exact Hab r,
-    exact IH (@HRS _)]
+  induction' p with _ a c l r p IH generalizing b <;> constructor <;>
+    [exact Hab r;exact IH (@HRS _)]
 #align list.chain.imp' List.Chain.imp'
 -/
 
@@ -74,8 +74,9 @@ theorem Chain.iff_mem {a : α} {l : List α} :
     Chain R a l ↔ Chain (fun x y => x ∈ a :: l ∧ y ∈ l ∧ R x y) a l :=
   ⟨fun p => by
     induction' p with _ a b l r p 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⟩],
+      [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⟩],
     Chain.imp fun a b h => h.2.2⟩
 #align list.chain.iff_mem List.Chain.iff_mem
 -/
@@ -237,7 +238,7 @@ theorem chain_iff_nthLe {R} :
 
 #print List.Chain'.imp /-
 theorem Chain'.imp {S : α → α → Prop} (H : ∀ a b, R a b → S a b) {l : List α} (p : Chain' R l) :
-    Chain' S l := by cases l <;> [trivial, exact p.imp H]
+    Chain' S l := by cases l <;> [trivial;exact p.imp H]
 #align list.chain'.imp List.Chain'.imp
 -/
 
@@ -307,7 +308,7 @@ theorem chain'_append_cons_cons {b c : α} {l₁ l₂ : List α} :
 #print List.chain'_map /-
 theorem chain'_map (f : β → α) {l : List β} :
     Chain' R (map f l) ↔ Chain' (fun a b : β => R (f a) (f b)) l := by
-  cases l <;> [rfl, exact chain_map _]
+  cases l <;> [rfl;exact chain_map _]
 #align list.chain'_map List.chain'_map
 -/
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

A PR accompanying #12339.

Zulip discussion

@@ -420,8 +420,8 @@ theorem Chain.induction (p : α → Prop) (l : List α) (h : Chain r a l)
   · rw [chain_cons] at h
     simp only [mem_cons]
     rintro _ (rfl | H)
-    apply carries h.1 (l_ih h.2 hb _ (mem_cons.2 (Or.inl rfl)))
-    apply l_ih h.2 hb _ (mem_cons.2 H)
+    · apply carries h.1 (l_ih h.2 hb _ (mem_cons.2 (Or.inl rfl)))
+    · apply l_ih h.2 hb _ (mem_cons.2 H)
 #align list.chain.induction List.Chain.induction
 
 /-- Given a chain from `a` to `b`, and a predicate true at `b`, if `r x y → p y → p x` then

• Move tail_sublist to Basic
• Rename sublist_of_cons_sublist_cons to Sublist.of_cons_cos
• Rename cons_sublist_cons_iff to cons_sublist_cons
• Add Sublist.tail, drop_sublist_drop_left, Sublist.drop
• Protect some lemmas

@@ -6,6 +6,7 @@ Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
 import Mathlib.Logic.Relation
 import Mathlib.Data.List.Forall2
 import Mathlib.Data.List.Lex
+import Mathlib.Data.List.Infix
 
 #align_import data.list.chain from "leanprover-community/mathlib"@"dd71334db81d0bd444af1ee339a29298bef40734"
 

Most of them go back to the port.

@@ -165,7 +165,7 @@ theorem chain_iff_get {R} : ∀ {a : α} {l : List α}, Chain R a l ↔
     exact h (i+1) (by simp only [length_cons]; omega)
 
 set_option linter.deprecated false in
-@[deprecated chain_iff_get]
+@[deprecated chain_iff_get] -- 2023-01-10
 theorem chain_iff_nthLe {R} {a : α} {l : List α} : Chain R a l ↔
     (∀ h : 0 < length l, R a (nthLe l 0 h)) ∧
     ∀ (i) (h : i < length l - 1),
@@ -364,7 +364,7 @@ theorem chain'_iff_get {R} : ∀ {l : List α}, Chain' R l ↔
                     fun h i hi => h i (Nat.succ_lt_succ hi)⟩
 
 set_option linter.deprecated false in
-@[deprecated chain'_iff_get]
+@[deprecated chain'_iff_get] -- 2023-01-10
 theorem chain'_iff_nthLe {R} {l : List α} : Chain' R l ↔
     ∀ (i) (h : i < length l - 1),
       R (nthLe l i (by omega)) (nthLe l (i + 1) (by omega)) :=

• Make Algebra.BigOperators.List.Basic, Data.List.Chain not depend on Data.Nat.Order.Basic by using Nat-specific Std lemmas rather than general mathlib ones. I leave the Data.Nat.Basic import since Algebra.BigOperators.List.Basic is algebra territory.
• Make Algebra.BigOperators.List.Basic not depend on Algebra.Divisibility.Basic. I'm not too sure about that one since they already are algebra. My motivation is that they involve ring-like objects while big operators are about group-like objects, but this is in some sense a second order refactor.
• As a consequence, move the divisibility and MonoidWithZero lemmas from Algebra.BigOperators.List.Basic to Algebra.BigOperators.List.Lemmas.
• Move the content of Algebra.BigOperators.List.Defs to Algebra.BigOperators.List.Basic since no file imported the former without the latter and their imports are becoming very close after this PR.
• Make Data.List.Count, Data.List.Dedup, Data.List.ProdSigma, Data.List.Zip not depend on Algebra.BigOperators.List.Basic.
• As a consequence, move the big operators lemmas that were in there to Algebra.BigOperators.List.Basic. For the lemmas that were Nat -specific, keep a version of them stated using Nat.sum.
• To help with this, add Nat.sum_eq_listSum (l : List Nat) : Nat.sum l = l.sum.

@@ -6,7 +6,6 @@ Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
 import Mathlib.Logic.Relation
 import Mathlib.Data.List.Forall2
 import Mathlib.Data.List.Lex
-import Mathlib.Data.Nat.Order.Basic
 
 #align_import data.list.chain from "leanprover-community/mathlib"@"dd71334db81d0bd444af1ee339a29298bef40734"
 
@@ -20,6 +19,8 @@ A graph-specialized version is in development and will hopefully be added under
 sometime soon.
 -/
 
+-- Make sure we haven't imported `Data.Nat.Order.Basic`
+assert_not_exists OrderedSub
 
 universe u v
 
@@ -354,9 +355,10 @@ theorem chain'_iff_get {R} : ∀ {l : List α}, Chain' R l ↔
   | [a] => iff_of_true (by simp) (fun _ h => by simp at h)
   | a :: b :: t => by
     rw [← and_forall_succ, chain'_cons, chain'_iff_get]
-    simp only [length_cons, get_cons_succ, Fin.zero_eta, get_cons_zero, zero_add, Fin.mk_one,
-      get_cons_cons_one, succ_sub_succ_eq_sub, nonpos_iff_eq_zero, add_eq_zero_iff, and_false,
-      tsub_zero, add_pos_iff, zero_lt_one, or_true, forall_true_left, and_congr_right_iff]
+    simp only [length_cons, get_cons_succ, Fin.zero_eta, get_cons_zero, Nat.zero_add, Fin.mk_one,
+      get_cons_cons_one, succ_sub_succ_eq_sub, Nat.le_zero, Nat.add_eq_zero_iff, and_false,
+      Nat.sub_zero, Nat.add_pos_iff_pos_or_pos, Nat.zero_lt_one, or_true, forall_true_left,
+      and_congr_right_iff]
     dsimp [succ_sub_one]
     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)⟩

@@ -384,9 +384,9 @@ lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
 | [], _ => by simp
 | [l], _ => by simp [join]
 | (l₁ :: l₂ :: L), hL => by
-    rw [mem_cons, not_or, ← Ne.def] at hL
+    rw [mem_cons, not_or, ← Ne] at hL
     rw [join, chain'_append, chain'_join hL.2, forall_mem_cons, chain'_cons]
-    rw [mem_cons, not_or, ← Ne.def] at hL
+    rw [mem_cons, not_or, ← Ne] at hL
     simp only [forall_mem_cons, and_assoc, join, head?_append_of_ne_nil _ hL.2.1.symm]
     exact Iff.rfl.and (Iff.rfl.and <| Iff.rfl.and and_comm)
 

Use Nat specialized theorems, and omega, where necessary to avoid needing to import the abstract ordered algebra hierarchy for basic results about List.

Import graph between Mathlib.Order.Basic and Mathlib.Data.List.Basic:

• before.pdf
• after.pdf

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -6,6 +6,7 @@ Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
 import Mathlib.Logic.Relation
 import Mathlib.Data.List.Forall2
 import Mathlib.Data.List.Lex
+import Mathlib.Data.Nat.Order.Basic
 
 #align_import data.list.chain from "leanprover-community/mathlib"@"dd71334db81d0bd444af1ee339a29298bef40734"
 
@@ -141,7 +142,7 @@ protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R
 theorem chain_iff_get {R} : ∀ {a : α} {l : List α}, Chain R a l ↔
     (∀ h : 0 < length l, R a (get l ⟨0, h⟩)) ∧
       ∀ (i : ℕ) (h : i < l.length - 1),
-        R (get l ⟨i, lt_of_lt_pred h⟩) (get l ⟨i+1, lt_pred_iff.mp h⟩)
+        R (get l ⟨i, by omega⟩) (get l ⟨i+1, by omega⟩)
   | a, [] => iff_of_true (by simp) ⟨fun h => by simp at h, fun _ h => by simp at h⟩
   | a, b :: t => by
     rw [chain_cons, @chain_iff_get _ _ t]
@@ -153,21 +154,21 @@ theorem chain_iff_get {R} : ∀ {a : α} {l : List α}, Chain R a l ↔
       intro i w
       cases' i with i
       · apply h0
-      · exact h i (lt_pred_iff.2 <| by simpa using w)
+      · exact h i (by simp only [length_cons] at w; omega)
     rintro ⟨h0, h⟩; constructor
     · apply h0
       simp
     constructor
     · apply h 0
     intro i w
-    exact h (i+1) (lt_pred_iff.mp w)
+    exact h (i+1) (by simp only [length_cons]; omega)
 
 set_option linter.deprecated false in
 @[deprecated chain_iff_get]
 theorem chain_iff_nthLe {R} {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 (lt_of_lt_pred h)) (nthLe l (i + 1) (lt_pred_iff.mp h)) :=
+    R (nthLe l i (by omega)) (nthLe l (i + 1) (by omega)) :=
   by rw [chain_iff_get]; simp [nthLe]
 #align list.chain_iff_nth_le List.chain_iff_nthLe
 
@@ -348,7 +349,7 @@ theorem chain'_reverse : ∀ {l}, Chain' R (reverse l) ↔ Chain' (flip R) l
 
 theorem chain'_iff_get {R} : ∀ {l : List α}, Chain' R l ↔
     ∀ (i : ℕ) (h : i < length l - 1),
-      R (get l ⟨i, lt_of_lt_pred h⟩) (get l ⟨i + 1, lt_pred_iff.mp h⟩)
+      R (get l ⟨i, by omega⟩) (get l ⟨i + 1, by omega⟩)
   | [] => iff_of_true (by simp) (fun _ h => by simp at h)
   | [a] => iff_of_true (by simp) (fun _ h => by simp at h)
   | a :: b :: t => by
@@ -364,7 +365,7 @@ set_option linter.deprecated false in
 @[deprecated chain'_iff_get]
 theorem chain'_iff_nthLe {R} {l : List α} : Chain' R l ↔
     ∀ (i) (h : i < length l - 1),
-      R (nthLe l i (lt_of_lt_pred h)) (nthLe l (i + 1) (lt_pred_iff.mp h)) :=
+      R (nthLe l i (by omega)) (nthLe l (i + 1) (by omega)) :=
   chain'_iff_get.trans <| by simp [nthLe]
 #align list.chain'_iff_nth_le List.chain'_iff_nthLe
 

Classifies by adding issue number #10756 to porting notes claiming anything equivalent to:

• "added theorem"
• "added theorems"
• "new theorem"
• "new theorems"
• "added lemma"
• "new lemma"
• "new lemmas"

@@ -376,7 +376,7 @@ theorem Chain'.append_overlap {l₁ l₂ l₃ : List α} (h₁ : Chain' R (l₁
     simpa only [getLast?_append_of_ne_nil _ hn] using (chain'_append.1 h₂).2.2
 #align list.chain'.append_overlap List.Chain'.append_overlap
 
--- Porting note: new
+-- Porting note (#10756): new lemma
 lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
     (Chain' R L.join ↔ (∀ l ∈ L, Chain' R l) ∧
     L.Chain' (fun l₁ l₂ => ∀ᵉ (x ∈ l₁.getLast?) (y ∈ l₂.head?), R x y))

Homogenises porting notes via capitalisation and addition of whitespace.

It makes the following changes:

• converts "--porting note" into "-- Porting note";
• converts "porting note" into "Porting note".

@@ -376,7 +376,7 @@ theorem Chain'.append_overlap {l₁ l₂ l₃ : List α} (h₁ : Chain' R (l₁
     simpa only [getLast?_append_of_ne_nil _ hn] using (chain'_append.1 h₂).2.2
 #align list.chain'.append_overlap List.Chain'.append_overlap
 
--- porting note: new
+-- Porting note: new
 lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
     (Chain' R L.join ↔ (∀ l ∈ L, Chain' R l) ∧
     L.Chain' (fun l₁ l₂ => ∀ᵉ (x ∈ l₁.getLast?) (y ∈ l₂.head?), R x y))
@@ -437,7 +437,7 @@ reflexive transitive closure of `r`. The converse of `exists_chain_of_relationRe
 -/
 theorem relationReflTransGen_of_exists_chain (l : List α) (hl₁ : Chain r a l)
     (hl₂ : getLast (a :: l) (cons_ne_nil _ _) = b) : Relation.ReflTransGen r a b :=
---Porting note: `p` behaves like an implicit argument to `Chain.induction_head` but it is explicit.
+-- Porting note: `p` behaves like an implicit argument to `Chain.induction_head` but it is explicit.
   Chain.induction_head l hl₁ hl₂ (fun _ _ => Relation.ReflTransGen.head)
     Relation.ReflTransGen.refl
 #align list.relation_refl_trans_gen_of_exists_chain List.relationReflTransGen_of_exists_chain

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

@@ -3,8 +3,9 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
 -/
-import Mathlib.Data.List.Pairwise
 import Mathlib.Logic.Relation
+import Mathlib.Data.List.Forall2
+import Mathlib.Data.List.Lex
 
 #align_import data.list.chain from "leanprover-community/mathlib"@"dd71334db81d0bd444af1ee339a29298bef40734"
 

See Zulip thread for the discussion.

@@ -386,7 +386,7 @@ lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
     rw [join, chain'_append, chain'_join hL.2, forall_mem_cons, chain'_cons]
     rw [mem_cons, not_or, ← Ne.def] at hL
     simp only [forall_mem_cons, and_assoc, join, head?_append_of_ne_nil _ hL.2.1.symm]
-    exact Iff.rfl.and (Iff.rfl.and $ Iff.rfl.and and_comm)
+    exact Iff.rfl.and (Iff.rfl.and <| Iff.rfl.and and_comm)
 
 /-- If `a` and `b` are related by the reflexive transitive closure of `r`, then there is an
 `r`-chain starting from `a` and ending on `b`.

Search for [∀∃].*(_ and manually replace some occurrences with more readable versions. In case of ∀, the new expressions are defeq to the old ones. In case of ∃, they differ by exists_prop.

In some rare cases, golf proofs that needed fixing.

@@ -255,7 +255,7 @@ theorem Chain'.cons {x y l} (h₁ : R x y) (h₂ : Chain' R (y :: l)) : Chain' R
   chain'_cons.2 ⟨h₁, h₂⟩
 #align list.chain'.cons List.Chain'.cons
 
-theorem Chain'.tail : ∀ {l} (_ : Chain' R l), Chain' R l.tail
+theorem Chain'.tail : ∀ {l}, Chain' R l → Chain' R l.tail
   | [], _ => trivial
   | [_], _ => trivial
   | _ :: _ :: _, h => (chain'_cons.mp h).right

To fit with the "please try harder" convention of ! tactics.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -457,7 +457,7 @@ theorem Chain'.cons_of_le [LinearOrder α] {a : α} {as m : List α}
       refine gt_of_gt_of_ge ha.1 ?_
       rw [le_iff_lt_or_eq] at hmas
       cases' hmas with hmas hmas
-      · by_contra' hh
+      · by_contra! hh
         rw [← not_le] at hmas
         apply hmas
         apply le_of_lt

PR contents

This is the supremum of

• #8284
• #8056
• #8023
• #8332
• #8226 (already approved)
• #7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

• leanprover/lean4#2778
• leanprover/lean4#2790
• leanprover/lean4#2783
• leanprover/lean4#2825
• leanprover/lean4#2722

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

• switching to using explicit lemmas that have the intended level of application
• (config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
• Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

@@ -354,7 +354,7 @@ theorem chain'_iff_get {R} : ∀ {l : List α}, Chain' R l ↔
     rw [← and_forall_succ, chain'_cons, chain'_iff_get]
     simp only [length_cons, get_cons_succ, Fin.zero_eta, get_cons_zero, zero_add, Fin.mk_one,
       get_cons_cons_one, succ_sub_succ_eq_sub, nonpos_iff_eq_zero, add_eq_zero_iff, and_false,
-      tsub_zero, add_pos_iff, or_true, forall_true_left, and_congr_right_iff]
+      tsub_zero, add_pos_iff, zero_lt_one, or_true, forall_true_left, and_congr_right_iff]
     dsimp [succ_sub_one]
     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)⟩

@@ -441,6 +441,31 @@ theorem relationReflTransGen_of_exists_chain (l : List α) (hl₁ : Chain r a l)
     Relation.ReflTransGen.refl
 #align list.relation_refl_trans_gen_of_exists_chain List.relationReflTransGen_of_exists_chain
 
+theorem Chain'.cons_of_le [LinearOrder α] {a : α} {as m : List α}
+    (ha : List.Chain' (· > ·) (a :: as)) (hm : List.Chain' (· > ·) m) (hmas : m ≤ as) :
+    List.Chain' (· > ·) (a :: m) := by
+  cases m with
+  | nil => simp only [List.chain'_singleton]
+  | cons b bs =>
+    apply hm.cons
+    cases as with
+    | nil =>
+      simp only [le_iff_lt_or_eq, or_false] at hmas
+      exact (List.Lex.not_nil_right (·<·) _ hmas).elim
+    | cons a' as =>
+      rw [List.chain'_cons] at ha
+      refine gt_of_gt_of_ge ha.1 ?_
+      rw [le_iff_lt_or_eq] at hmas
+      cases' hmas with hmas hmas
+      · by_contra' hh
+        rw [← not_le] at hmas
+        apply hmas
+        apply le_of_lt
+        exact (List.lt_iff_lex_lt _ _).mp (List.lt.head _ _ hh)
+      · simp only [List.cons.injEq] at hmas
+        rw [ge_iff_le, le_iff_lt_or_eq]
+        exact Or.inr hmas.1
+
 end List
 
 

Fixes the nonterminal simps identified by #7496

@@ -352,7 +352,9 @@ theorem chain'_iff_get {R} : ∀ {l : List α}, Chain' R l ↔
   | [a] => iff_of_true (by simp) (fun _ h => by simp at h)
   | a :: b :: t => by
     rw [← and_forall_succ, chain'_cons, chain'_iff_get]
-    simp
+    simp only [length_cons, get_cons_succ, Fin.zero_eta, get_cons_zero, zero_add, Fin.mk_one,
+      get_cons_cons_one, succ_sub_succ_eq_sub, nonpos_iff_eq_zero, add_eq_zero_iff, and_false,
+      tsub_zero, add_pos_iff, or_true, forall_true_left, and_congr_right_iff]
     dsimp [succ_sub_one]
     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)⟩

Co-authored-by: Moritz Firsching <firsching@google.com>

@@ -164,9 +164,9 @@ theorem chain_iff_get {R} : ∀ {a : α} {l : List α}, Chain R a l ↔
 set_option linter.deprecated false in
 @[deprecated chain_iff_get]
 theorem chain_iff_nthLe {R} {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 (lt_of_lt_pred h)) (nthLe l (i + 1) (lt_pred_iff.mp h)) :=
+    (∀ h : 0 < length l, R a (nthLe l 0 h)) ∧
+    ∀ (i) (h : i < length l - 1),
+    R (nthLe l i (lt_of_lt_pred h)) (nthLe l (i + 1) (lt_pred_iff.mp h)) :=
   by rw [chain_iff_get]; simp [nthLe]
 #align list.chain_iff_nth_le List.chain_iff_nthLe
 
@@ -375,7 +375,7 @@ theorem Chain'.append_overlap {l₁ l₂ l₃ : List α} (h₁ : Chain' R (l₁
 
 -- porting note: new
 lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
-  (Chain' R L.join ↔ (∀ l ∈ L, Chain' R l) ∧
+    (Chain' R L.join ↔ (∀ l ∈ L, Chain' R l) ∧
     L.Chain' (fun l₁ l₂ => ∀ᵉ (x ∈ l₁.getLast?) (y ∈ l₂.head?), R x y))
 | [], _ => by simp
 | [l], _ => by simp [join]

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Alex Keizer <alex@keizer.dev>

@@ -72,7 +72,7 @@ theorem chain_iff_forall₂ :
   | a, [] => by simp
   | a, b :: l => by
     by_cases h : l = [] <;>
-    simp [@chain_iff_forall₂ b l, *]
+    simp [@chain_iff_forall₂ b l, dropLast, *]
 #align list.chain_iff_forall₂ List.chain_iff_forall₂
 
 theorem chain_append_singleton_iff_forall₂ : Chain R a (l ++ [b]) ↔ Forall₂ R (a :: l) (l ++ [b]) :=

Many proofs use the "stream of consciousness" style from Lean 3, rather than have ... := or suffices ... from/by.

This PR updates a fraction of these to the preferred Lean 4 style.

I think a good goal would be to delete the "deferred" versions of have, suffices, and let at the bottom of Mathlib.Tactic.Have

(Anyone who would like to contribute more cleanup is welcome to push directly to this branch.)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -469,8 +469,8 @@ theorem Acc.list_chain' {l : List.chains r} (acc : ∀ a ∈ l.val.head?, Acc r
     /- 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
+    have : Acc (List.lex_chains r) l' := by
+      cases' l with b l
       · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
       /- l' is accessible by induction hypothesis -/
       · apply ih b (List.chain'_cons.1 hl).1

shorter proof of the main result of #6361

Zulip: https://leanprover.zulipchat.com/#narrow/stream/217875-Is-there-code-for-X.3F/topic/List.2ELex.20is.20well.20founded.20on.20decreasing.20lists/near/382708025

Co-authored-by: Junyan Xu <junyanxu.math@gmail.com>

@@ -440,3 +440,58 @@ theorem relationReflTransGen_of_exists_chain (l : List α) (hl₁ : Chain r a l)
 #align list.relation_refl_trans_gen_of_exists_chain List.relationReflTransGen_of_exists_chain
 
 end List
+
+
+/-! In this section, we consider the type of `r`-decreasing chains (`List.Chain' (flip r)`)
+  equipped with lexicographic order `List.Lex r`. -/
+
+variable {α : Type*} (r : α → α → Prop)
+
+/-- The type of `r`-decreasing chains -/
+abbrev List.chains := { l : List α // l.Chain' (flip r) }
+
+/-- The lexicographic order on the `r`-decreasing chains -/
+abbrev List.lex_chains (l m : List.chains r) : Prop := List.Lex r l.val m.val
+
+variable {r}
+
+/-- If an `r`-decreasing chain `l` is empty or its head is accessible by `r`, then
+  `l` is accessible by the lexicographic order `List.Lex r`. -/
+theorem Acc.list_chain' {l : List.chains r} (acc : ∀ a ∈ l.val.head?, Acc r a) :
+    Acc (List.lex_chains r) l := by
+  obtain ⟨_ | ⟨a, l⟩, hl⟩ := l
+  · apply Acc.intro; rintro ⟨_⟩ ⟨_⟩
+  specialize acc a _
+  · rw [List.head?_cons, Option.mem_some_iff]
+  /- For an r-decreasing chain of the form a :: l, apply induction on a -/
+  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
+
+/-- If `r` is well-founded, the lexicographic order on `r`-decreasing chains is also. -/
+theorem WellFounded.list_chain' (hwf : WellFounded r) :
+    WellFounded (List.lex_chains r) :=
+  ⟨fun _ ↦ Acc.list_chain' (fun _ _ => hwf.apply _)⟩
+
+instance [hwf : IsWellFounded α r] :
+    IsWellFounded (List.chains r) (List.lex_chains r) :=
+  ⟨hwf.wf.list_chain'⟩

• depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -2,15 +2,12 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
-
-! This file was ported from Lean 3 source module data.list.chain
-! leanprover-community/mathlib commit dd71334db81d0bd444af1ee339a29298bef40734
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.List.Pairwise
 import Mathlib.Logic.Relation
 
+#align_import data.list.chain from "leanprover-community/mathlib"@"dd71334db81d0bd444af1ee339a29298bef40734"
+
 /-!
 # Relation chain
 

This PR is the result of running

find . -type f -name "*.lean" -exec sed -i -E 's/^( +)\. /\1· /' {} \;
find . -type f -name "*.lean" -exec sed -i -E 'N;s/^( +·)\n +(.*)$/\1 \2/;P;D' {} \;

which firstly replaces . focusing dots with · and secondly removes isolated instances of such dots, unifying them with the following line. A new rule is placed in the style linter to verify this.

@@ -155,7 +155,7 @@ theorem chain_iff_get {R} : ∀ {a : α} {l : List α}, Chain R a l ↔
       intro i w
       cases' i with i
       · apply h0
-      . exact h i (lt_pred_iff.2 <| by simpa using w)
+      · exact h i (lt_pred_iff.2 <| by simpa using w)
     rintro ⟨h0, h⟩; constructor
     · apply h0
       simp

Changes are of the form

• some_tactic at h⊢ -> some_tactic at h ⊢
• some_tactic at h -> some_tactic at h

@@ -131,7 +131,7 @@ theorem chain_iff_pairwise [IsTrans α R] {a : α} {l : List α} : Chain R a l 
 
 protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <+ l₂) :
     l₁.Chain R a := by
-  rw [chain_iff_pairwise] at hl⊢
+  rw [chain_iff_pairwise] at hl ⊢
   exact hl.sublist (h.cons_cons a)
 #align list.chain.sublist List.Chain.sublist
 
@@ -250,7 +250,7 @@ theorem chain'_iff_pairwise [IsTrans α R] : ∀ {l : List α}, Chain' R l ↔ P
 #align list.chain'_iff_pairwise List.chain'_iff_pairwise
 
 protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R := by
-  rw [chain'_iff_pairwise] at hl⊢
+  rw [chain'_iff_pairwise] at hl ⊢
   exact hl.sublist h
 #align list.chain'.sublist List.Chain'.sublist
 

Part 2 of #5001

@@ -389,8 +389,8 @@ lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
     simp only [forall_mem_cons, and_assoc, join, head?_append_of_ne_nil _ hL.2.1.symm]
     exact Iff.rfl.and (Iff.rfl.and $ Iff.rfl.and and_comm)
 
-/-- If `a` and `b` are related by the reflexive transitive closure of `r`, then there is a `r`-chain
-starting from `a` and ending on `b`.
+/-- If `a` and `b` are related by the reflexive transitive closure of `r`, then there is an
+`r`-chain starting from `a` and ending on `b`.
 The converse of `relationReflTransGen_of_exists_chain`.
 -/
 theorem exists_chain_of_relationReflTransGen (h : Relation.ReflTransGen r a b) :

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Floris van Doorn <fpvdoorn@gmail.com> Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com> Co-authored-by: Alex J Best <alex.j.best@gmail.com>

@@ -33,33 +33,11 @@ variable {α : Type u} {β : Type v} {R r : α → α → Prop} {l l₁ l₂ : L
 mk_iff_of_inductive_prop List.Chain List.chain_iff
 #align list.chain_iff List.chain_iff
 
---Porting note: attribute in Lean3, but not in Lean4 Std so added here instead
-attribute [simp] Chain.nil
-
 #align list.chain.nil List.Chain.nil
 #align list.chain.cons List.Chain.cons
-
-theorem rel_of_chain_cons {a b : α} {l : List α} (p : Chain R a (b :: l)) : R a b :=
-  (chain_cons.1 p).1
 #align list.rel_of_chain_cons List.rel_of_chain_cons
-
-theorem chain_of_chain_cons {a b : α} {l : List α} (p : Chain R a (b :: l)) : Chain R b l :=
-  (chain_cons.1 p).2
 #align list.chain_of_chain_cons List.chain_of_chain_cons
-
-theorem Chain.imp' {R S : α → α → Prop} (HRS : ∀ ⦃a b⦄, R a b → S a b) {a b : α}
-    (Hab : ∀ ⦃c⦄, R a c → S b c) {l : List α} (p : Chain R a l) : Chain S b l := by
-  induction p generalizing b with
-  | nil => constructor
-  | cons r _ ih =>
-    constructor
-    · exact Hab r
-    · exact ih (@HRS _)
 #align list.chain.imp' List.Chain.imp'
-
-theorem Chain.imp {R S : α → α → Prop} (H : ∀ a b, R a b → S a b) {a : α} {l : List α}
-    (p : Chain R a l) : Chain S a l :=
-  p.imp' H (H a)
 #align list.chain.imp List.Chain.imp
 
 theorem Chain.iff {S : α → α → Prop} (H : ∀ a b, R a b ↔ S a b) {a : α} {l : List α} :
@@ -135,11 +113,6 @@ theorem chain_of_chain_pmap {S : β → β → Prop} {p : α → Prop} (f : ∀
   · simp [H _ _ _ _ (rel_of_chain_cons hl₂), l_ih _ _ (chain_of_chain_cons hl₂)]
 #align list.chain_of_chain_pmap List.chain_of_chain_pmap
 
-protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l := by
-  cases' pairwise_cons.1 p with r p'; clear p
-  induction' p' with b l r' _ IH generalizing a; · exact Chain.nil
-  simp only [chain_cons, forall_mem_cons] at r
-  exact chain_cons.2 ⟨r.1, IH r'⟩
 #align list.pairwise.chain List.Pairwise.chain
 
 protected theorem Chain.pairwise [IsTrans α R] :

The main breaking change is that tac <;> [t1, t2] is now written tac <;> [t1; t2], to avoid clashing with tactics like cases and use that take comma-separated lists.

@@ -71,7 +71,7 @@ theorem Chain.iff_mem {a : α} {l : List α} :
     Chain R a l ↔ Chain (fun x y => x ∈ a :: l ∧ y ∈ l ∧ R x y) a l :=
   ⟨fun p => by
     induction' p with _ a b l r _ IH <;> constructor <;>
-      [exact ⟨mem_cons_self _ _, mem_cons_self _ _, r⟩,
+      [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⟩],
     Chain.imp fun a b h => h.2.2⟩
 #align list.chain.iff_mem List.Chain.iff_mem
@@ -201,7 +201,7 @@ theorem chain_iff_nthLe {R} {a : α} {l : List α} : Chain R a l ↔
 #align list.chain_iff_nth_le List.chain_iff_nthLe
 
 theorem Chain'.imp {S : α → α → Prop} (H : ∀ a b, R a b → S a b) {l : List α} (p : Chain' R l) :
-    Chain' S l := by cases l <;> [trivial, exact Chain.imp H p]
+    Chain' S l := by cases l <;> [trivial; exact Chain.imp H p]
 #align list.chain'.imp List.Chain'.imp
 
 theorem Chain'.iff {S : α → α → Prop} (H : ∀ a b, R a b ↔ S a b) {l : List α} :
@@ -253,7 +253,7 @@ theorem chain'_append_cons_cons {b c : α} {l₁ l₂ : List α} :
 
 theorem chain'_map (f : β → α) {l : List β} :
     Chain' R (map f l) ↔ Chain' (fun a b : β => R (f a) (f b)) l := by
-  cases l <;> [rfl, exact chain_map _]
+  cases l <;> [rfl; exact chain_map _]
 #align list.chain'_map List.chain'_map
 
 theorem chain'_of_chain'_map {S : β → β → Prop} (f : α → β) (H : ∀ a b : α, S (f a) (f b) → R a b)

@@ -403,6 +403,19 @@ theorem Chain'.append_overlap {l₁ l₂ l₃ : List α} (h₁ : Chain' R (l₁
     simpa only [getLast?_append_of_ne_nil _ hn] using (chain'_append.1 h₂).2.2
 #align list.chain'.append_overlap List.Chain'.append_overlap
 
+-- porting note: new
+lemma chain'_join : ∀ {L : List (List α)}, [] ∉ L →
+  (Chain' R L.join ↔ (∀ l ∈ L, Chain' R l) ∧
+    L.Chain' (fun l₁ l₂ => ∀ᵉ (x ∈ l₁.getLast?) (y ∈ l₂.head?), R x y))
+| [], _ => by simp
+| [l], _ => by simp [join]
+| (l₁ :: l₂ :: L), hL => by
+    rw [mem_cons, not_or, ← Ne.def] at hL
+    rw [join, chain'_append, chain'_join hL.2, forall_mem_cons, chain'_cons]
+    rw [mem_cons, not_or, ← Ne.def] at hL
+    simp only [forall_mem_cons, and_assoc, join, head?_append_of_ne_nil _ hL.2.1.symm]
+    exact Iff.rfl.and (Iff.rfl.and $ Iff.rfl.and and_comm)
+
 /-- If `a` and `b` are related by the reflexive transitive closure of `r`, then there is a `r`-chain
 starting from `a` and ending on `b`.
 The converse of `relationReflTransGen_of_exists_chain`.

This PR is the result of a slight variant on the following "algorithm"

• take all mathlib 3 names, remove _ and make all uppercase letters into lowercase
• take all mathlib 4 names, remove _ and make all uppercase letters into lowercase
• look for matches, and create pairs (original_lean3_name, OriginalLean4Name)
• for pairs that do not have an align statement:
  • use Lean 4 to lookup the file + position of the Lean 4 name
  • add an #align statement just before the next empty line
• manually fix some tiny mistakes (e.g., empty lines in proofs might cause the #align statement to have been inserted too early)

@@ -31,6 +31,7 @@ namespace List
 variable {α : Type u} {β : Type v} {R r : α → α → Prop} {l l₁ l₂ : List α} {a b : α}
 
 mk_iff_of_inductive_prop List.Chain List.chain_iff
+#align list.chain_iff List.chain_iff
 
 --Porting note: attribute in Lean3, but not in Lean4 Std so added here instead
 attribute [simp] Chain.nil

Now Trans.trans conflicts with _root_.trans.

@@ -148,7 +148,7 @@ protected theorem Chain.pairwise [IsTrans α R] :
     hb.pairwise.cons
       (by
         simp only [mem_cons, forall_eq_or_imp, h, true_and_iff]
-        exact fun c hc => trans h (rel_of_pairwise_cons hb.pairwise hc))
+        exact fun c hc => _root_.trans h (rel_of_pairwise_cons hb.pairwise hc))
 #align list.chain.pairwise List.Chain.pairwise
 
 theorem chain_iff_pairwise [IsTrans α R] {a : α} {l : List α} : Chain R a l ↔ Pairwise R (a :: l) :=

This was done semi-automatically with some regular expressions in vim in contrast to the fully automatic https://github.com/leanprover-community/mathlib4/pull/1523.

Co-authored-by: Moritz Firsching <firsching@google.com>

@@ -155,8 +155,8 @@ theorem chain_iff_pairwise [IsTrans α R] {a : α} {l : List α} : Chain R a l 
   ⟨Chain.pairwise, Pairwise.chain⟩
 #align list.chain_iff_pairwise List.chain_iff_pairwise
 
-protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <+ l₂) : l₁.Chain R a :=
-  by
+protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <+ l₂) :
+    l₁.Chain R a := by
   rw [chain_iff_pairwise] at hl⊢
   exact hl.sublist (h.cons_cons a)
 #align list.chain.sublist List.Chain.sublist

During porting, I usually fix the desired format we seem to want for the line breaks around by with

awk '{do {{if (match($0, "^  by$") && length(p) < 98) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}' Mathlib/File/Im/Working/On.lean

I noticed there are some more files that slipped through.

This pull request is the result of running this command:

grep -lr "^  by\$" Mathlib | xargs -n 1 awk -i inplace '{do {{if (match($0, "^  by$") && length(p) < 98 && not (match(p, "^[ \t]*--"))) {p=p " by";} else {if (NR!=1) {print p}; p=$0}}} while (getline == 1) if (getline==0) print p}'

Co-authored-by: Moritz Firsching <firsching@google.com>

@@ -120,8 +120,7 @@ theorem chain_map_of_chain {S : β → β → Prop} (f : α → β) (H : ∀ a b
 
 theorem chain_pmap_of_chain {S : β → β → Prop} {p : α → Prop} {f : ∀ a, p a → β}
     (H : ∀ a b ha hb, R a b → S (f a ha) (f b hb)) {a : α} {l : List α} (hl₁ : Chain R a l)
-    (ha : p a) (hl₂ : ∀ a ∈ l, p a) : Chain S (f a ha) (List.pmap f l hl₂) :=
-  by
+    (ha : p a) (hl₂ : ∀ a ∈ l, p a) : Chain S (f a ha) (List.pmap f l hl₂) := by
   induction' l with lh lt l_ih generalizing a
   · simp
   · simp [H _ _ _ _ (rel_of_chain_cons hl₁), l_ih (chain_of_chain_cons hl₁)]
@@ -129,15 +128,13 @@ theorem chain_pmap_of_chain {S : β → β → Prop} {p : α → Prop} {f : ∀
 
 theorem chain_of_chain_pmap {S : β → β → Prop} {p : α → Prop} (f : ∀ a, p a → β) {l : List α}
     (hl₁ : ∀ a ∈ l, p a) {a : α} (ha : p a) (hl₂ : Chain S (f a ha) (List.pmap f l hl₁))
-    (H : ∀ a b ha hb, S (f a ha) (f b hb) → R a b) : Chain R a l :=
-  by
+    (H : ∀ a b ha hb, S (f a ha) (f b hb) → R a b) : Chain R a l := by
   induction' l with lh lt l_ih generalizing a
   · simp
   · simp [H _ _ _ _ (rel_of_chain_cons hl₂), l_ih _ _ (chain_of_chain_cons hl₂)]
 #align list.chain_of_chain_pmap List.chain_of_chain_pmap
 
-protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l :=
-  by
+protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l := by
   cases' pairwise_cons.1 p with r p'; clear p
   induction' p' with b l r' _ IH generalizing a; · exact Chain.nil
   simp only [chain_cons, forall_mem_cons] at r
@@ -164,8 +161,7 @@ protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <
   exact hl.sublist (h.cons_cons a)
 #align list.chain.sublist List.Chain.sublist
 
-protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b :=
-  by
+protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b := by
   rw [chain_iff_pairwise] at hl
   exact rel_of_pairwise_cons hl hb
 #align list.chain.rel List.Chain.rel
@@ -279,8 +275,7 @@ theorem chain'_iff_pairwise [IsTrans α R] : ∀ {l : List α}, Chain' R l ↔ P
   | _ :: _ => chain_iff_pairwise
 #align list.chain'_iff_pairwise List.chain'_iff_pairwise
 
-protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R :=
-  by
+protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R := by
   rw [chain'_iff_pairwise] at hl⊢
   exact hl.sublist h
 #align list.chain'.sublist List.Chain'.sublist
@@ -299,8 +294,7 @@ theorem Chain'.rel_head {x y l} (h : Chain' R (x :: y :: l)) : R x y :=
   rel_of_chain_cons h
 #align list.chain'.rel_head List.Chain'.rel_head
 
-theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y :=
-  by
+theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y := by
   rw [← cons_head?_tail hy] at h
   exact h.rel_head
 #align list.chain'.rel_head' List.Chain'.rel_head?
@@ -338,8 +332,7 @@ theorem Chain'.right_of_append (h : Chain' R (l₁ ++ l₂)) : Chain' R l₂ :=
   (chain'_append.1 h).2.1
 #align list.chain'.right_of_append List.Chain'.right_of_append
 
-theorem Chain'.infix (h : Chain' R l) (h' : l₁ <:+: l) : Chain' R l₁ :=
-  by
+theorem Chain'.infix (h : Chain' R l) (h' : l₁ <:+: l) : Chain' R l₁ := by
   rcases h' with ⟨l₂, l₃, rfl⟩
   exact h.left_of_append.right_of_append
 #align list.chain'.infix List.Chain'.infix
@@ -429,8 +422,7 @@ That is, we can propagate the predicate up the chain.
 -/
 theorem Chain.induction (p : α → Prop) (l : List α) (h : Chain r a l)
     (hb : getLast (a :: l) (cons_ne_nil _ _) = b) (carries : ∀ ⦃x y : α⦄, r x y → p y → p x)
-    (final : p b) : ∀ i ∈ a :: l, p i :=
-  by
+    (final : p b) : ∀ i ∈ a :: l, p i := by
   induction' l with _ _ l_ih generalizing a
   · cases hb
     simpa using final

@@ -2,24 +2,50 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro, Kenny Lau, Yury Kudryashov
+
+! This file was ported from Lean 3 source module data.list.chain
+! leanprover-community/mathlib commit dd71334db81d0bd444af1ee339a29298bef40734
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
 -/
-import Std.Data.List.Basic
-import Mathlib.Init.Logic
-import Mathlib.Data.List.Defs
 import Mathlib.Data.List.Pairwise
+import Mathlib.Logic.Relation
 
 /-!
 # Relation chain
 
-This file provides basic results about `List.Chain` (definition in `Std.Data.List.Defs`).
+This file provides basic results about `List.Chain` (definition in `Data.List.Defs`).
 A list `[a₂, ..., aₙ]` is a `Chain` starting at `a₁` with respect to the relation `r` if `r a₁ a₂`
 and `r a₂ a₃` and ... and `r aₙ₋₁ aₙ`. We write it `Chain r a₁ [a₂, ..., aₙ]`.
 A graph-specialized version is in development and will hopefully be added under `combinatorics.`
 sometime soon.
 -/
 
+
+universe u v
+
+open Nat
+
 namespace List
 
+variable {α : Type u} {β : Type v} {R r : α → α → Prop} {l l₁ l₂ : List α} {a b : α}
+
+mk_iff_of_inductive_prop List.Chain List.chain_iff
+
+--Porting note: attribute in Lean3, but not in Lean4 Std so added here instead
+attribute [simp] Chain.nil
+
+#align list.chain.nil List.Chain.nil
+#align list.chain.cons List.Chain.cons
+
+theorem rel_of_chain_cons {a b : α} {l : List α} (p : Chain R a (b :: l)) : R a b :=
+  (chain_cons.1 p).1
+#align list.rel_of_chain_cons List.rel_of_chain_cons
+
+theorem chain_of_chain_cons {a b : α} {l : List α} (p : Chain R a (b :: l)) : Chain R b l :=
+  (chain_cons.1 p).2
+#align list.chain_of_chain_cons List.chain_of_chain_cons
+
 theorem Chain.imp' {R S : α → α → Prop} (HRS : ∀ ⦃a b⦄, R a b → S a b) {a b : α}
     (Hab : ∀ ⦃c⦄, R a c → S b c) {l : List α} (p : Chain R a l) : Chain S b l := by
   induction p generalizing b with
@@ -28,28 +54,413 @@ theorem Chain.imp' {R S : α → α → Prop} (HRS : ∀ ⦃a b⦄, R a b → S
     constructor
     · exact Hab r
     · exact ih (@HRS _)
+#align list.chain.imp' List.Chain.imp'
 
 theorem Chain.imp {R S : α → α → Prop} (H : ∀ a b, R a b → S a b) {a : α} {l : List α}
     (p : Chain R a l) : Chain S a l :=
   p.imp' H (H a)
+#align list.chain.imp List.Chain.imp
+
+theorem Chain.iff {S : α → α → Prop} (H : ∀ a b, R a b ↔ S a b) {a : α} {l : List α} :
+    Chain R a l ↔ Chain S a l :=
+  ⟨Chain.imp fun a b => (H a b).1, Chain.imp fun a b => (H a b).2⟩
+#align list.chain.iff List.Chain.iff
+
+theorem Chain.iff_mem {a : α} {l : List α} :
+    Chain R a l ↔ Chain (fun x y => x ∈ a :: l ∧ y ∈ l ∧ R x y) a l :=
+  ⟨fun p => by
+    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⟩],
+    Chain.imp fun a b h => h.2.2⟩
+#align list.chain.iff_mem List.Chain.iff_mem
+
+theorem chain_singleton {a b : α} : Chain R a [b] ↔ R a b := by
+  simp only [chain_cons, Chain.nil, and_true_iff]
+#align list.chain_singleton List.chain_singleton
+
+theorem chain_split {a b : α} {l₁ l₂ : List α} :
+    Chain R a (l₁ ++ b :: l₂) ↔ Chain R a (l₁ ++ [b]) ∧ Chain R b l₂ := by
+  induction' l₁ with x l₁ IH generalizing a <;>
+    simp only [*, nil_append, cons_append, Chain.nil, chain_cons, and_true_iff, and_assoc]
+#align list.chain_split List.chain_split
+
+@[simp]
+theorem chain_append_cons_cons {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₂ := by
+  rw [chain_split, chain_cons]
+#align list.chain_append_cons_cons List.chain_append_cons_cons
+
+theorem chain_iff_forall₂ :
+    ∀ {a : α} {l : List α}, Chain R a l ↔ l = [] ∨ Forall₂ R (a :: dropLast l) l
+  | a, [] => by simp
+  | a, b :: l => by
+    by_cases h : l = [] <;>
+    simp [@chain_iff_forall₂ b l, *]
+#align list.chain_iff_forall₂ List.chain_iff_forall₂
+
+theorem chain_append_singleton_iff_forall₂ : Chain R a (l ++ [b]) ↔ Forall₂ R (a :: l) (l ++ [b]) :=
+  by simp [chain_iff_forall₂]
+#align list.chain_append_singleton_iff_forall₂ List.chain_append_singleton_iff_forall₂
+
+theorem chain_map (f : β → α) {b : β} {l : List β} :
+    Chain R (f b) (map f l) ↔ Chain (fun a b : β => R (f a) (f b)) b l := by
+  induction l generalizing b <;> simp only [map, Chain.nil, chain_cons, *]
+#align list.chain_map List.chain_map
+
+theorem chain_of_chain_map {S : β → β → Prop} (f : α → β) (H : ∀ a b : α, S (f a) (f b) → R a b)
+    {a : α} {l : List α} (p : Chain S (f a) (map f l)) : Chain R a l :=
+  ((chain_map f).1 p).imp H
+#align list.chain_of_chain_map List.chain_of_chain_map
 
-protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l := by
-  rcases pairwise_cons.1 p with ⟨r,p'⟩
-  clear p
-  induction p' generalizing a with
-  | nil => exact Chain.nil
-  | cons r' _ ih =>
-    simp only [chain_cons, forall_mem_cons] at r
-    exact chain_cons.2 ⟨r.1, ih r'⟩
+theorem chain_map_of_chain {S : β → β → Prop} (f : α → β) (H : ∀ a b : α, R a b → S (f a) (f b))
+    {a : α} {l : List α} (p : Chain R a l) : Chain S (f a) (map f l) :=
+  (chain_map f).2 <| p.imp H
+#align list.chain_map_of_chain List.chain_map_of_chain
 
-protected theorem Chain.pairwise {R : α → α → Prop} [Trans R R R] :
+theorem chain_pmap_of_chain {S : β → β → Prop} {p : α → Prop} {f : ∀ a, p a → β}
+    (H : ∀ a b ha hb, R a b → S (f a ha) (f b hb)) {a : α} {l : List α} (hl₁ : Chain R a l)
+    (ha : p a) (hl₂ : ∀ a ∈ l, p a) : Chain S (f a ha) (List.pmap f l hl₂) :=
+  by
+  induction' l with lh lt l_ih generalizing a
+  · simp
+  · simp [H _ _ _ _ (rel_of_chain_cons hl₁), l_ih (chain_of_chain_cons hl₁)]
+#align list.chain_pmap_of_chain List.chain_pmap_of_chain
+
+theorem chain_of_chain_pmap {S : β → β → Prop} {p : α → Prop} (f : ∀ a, p a → β) {l : List α}
+    (hl₁ : ∀ a ∈ l, p a) {a : α} (ha : p a) (hl₂ : Chain S (f a ha) (List.pmap f l hl₁))
+    (H : ∀ a b ha hb, S (f a ha) (f b hb) → R a b) : Chain R a l :=
+  by
+  induction' l with lh lt l_ih generalizing a
+  · simp
+  · simp [H _ _ _ _ (rel_of_chain_cons hl₂), l_ih _ _ (chain_of_chain_cons hl₂)]
+#align list.chain_of_chain_pmap List.chain_of_chain_pmap
+
+protected theorem Pairwise.chain (p : Pairwise R (a :: l)) : Chain R a l :=
+  by
+  cases' pairwise_cons.1 p with r p'; clear p
+  induction' p' with b l r' _ IH generalizing a; · exact Chain.nil
+  simp only [chain_cons, forall_mem_cons] at r
+  exact chain_cons.2 ⟨r.1, IH r'⟩
+#align list.pairwise.chain List.Pairwise.chain
+
+protected theorem Chain.pairwise [IsTrans α R] :
     ∀ {a : α} {l : List α}, Chain R a l → Pairwise R (a :: l)
-  | a, [], .nil => pairwise_singleton _ _
-  | a, _, .cons h hb =>
-    hb.pairwise.cons (by
-      simp only [mem_cons, forall_eq_or_imp, h, true_and]
-      exact fun c hc ↦ trans h (rel_of_pairwise_cons hb.pairwise hc))
-
-theorem chain_iff_pairwise {R : α → α → Prop} [Trans R R R] {a : α} {l : List α} :
-    Chain R a l ↔ Pairwise R (a :: l) :=
+  | a, [], Chain.nil => pairwise_singleton _ _
+  | a, _, @Chain.cons _ _ _ b l h hb =>
+    hb.pairwise.cons
+      (by
+        simp only [mem_cons, forall_eq_or_imp, h, true_and_iff]
+        exact fun c hc => trans h (rel_of_pairwise_cons hb.pairwise hc))
+#align list.chain.pairwise List.Chain.pairwise
+
+theorem chain_iff_pairwise [IsTrans α R] {a : α} {l : List α} : Chain R a l ↔ Pairwise R (a :: l) :=
   ⟨Chain.pairwise, Pairwise.chain⟩
+#align list.chain_iff_pairwise List.chain_iff_pairwise
+
+protected theorem Chain.sublist [IsTrans α R] (hl : l₂.Chain R a) (h : l₁ <+ l₂) : l₁.Chain R a :=
+  by
+  rw [chain_iff_pairwise] at hl⊢
+  exact hl.sublist (h.cons_cons a)
+#align list.chain.sublist List.Chain.sublist
+
+protected theorem Chain.rel [IsTrans α R] (hl : l.Chain R a) (hb : b ∈ l) : R a b :=
+  by
+  rw [chain_iff_pairwise] at hl
+  exact rel_of_pairwise_cons hl hb
+#align list.chain.rel List.Chain.rel
+
+theorem chain_iff_get {R} : ∀ {a : α} {l : List α}, Chain R a l ↔
+    (∀ h : 0 < length l, R a (get l ⟨0, h⟩)) ∧
+      ∀ (i : ℕ) (h : i < l.length - 1),
+        R (get l ⟨i, lt_of_lt_pred h⟩) (get l ⟨i+1, lt_pred_iff.mp h⟩)
+  | a, [] => iff_of_true (by simp) ⟨fun h => by simp at h, fun _ h => by simp at h⟩
+  | a, b :: t => by
+    rw [chain_cons, @chain_iff_get _ _ t]
+    constructor
+    · rintro ⟨R, ⟨h0, h⟩⟩
+      constructor
+      · intro _
+        exact R
+      intro i w
+      cases' i with i
+      · apply h0
+      . exact h i (lt_pred_iff.2 <| by simpa using w)
+    rintro ⟨h0, h⟩; constructor
+    · apply h0
+      simp
+    constructor
+    · apply h 0
+    intro i w
+    exact h (i+1) (lt_pred_iff.mp w)
+
+set_option linter.deprecated false in
+@[deprecated chain_iff_get]
+theorem chain_iff_nthLe {R} {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 (lt_of_lt_pred h)) (nthLe l (i + 1) (lt_pred_iff.mp h)) :=
+  by rw [chain_iff_get]; simp [nthLe]
+#align list.chain_iff_nth_le List.chain_iff_nthLe
+
+theorem Chain'.imp {S : α → α → Prop} (H : ∀ a b, R a b → S a b) {l : List α} (p : Chain' R l) :
+    Chain' S l := by cases l <;> [trivial, exact Chain.imp H p]
+#align list.chain'.imp List.Chain'.imp
+
+theorem Chain'.iff {S : α → α → Prop} (H : ∀ a b, R a b ↔ S a b) {l : List α} :
+    Chain' R l ↔ Chain' S l :=
+  ⟨Chain'.imp fun a b => (H a b).1, Chain'.imp fun a b => (H a b).2⟩
+#align list.chain'.iff List.Chain'.iff
+
+theorem Chain'.iff_mem : ∀ {l : List α}, Chain' R l ↔ Chain' (fun x y => x ∈ l ∧ y ∈ l ∧ R x y) l
+  | [] => Iff.rfl
+  | _ :: _ =>
+    ⟨fun h => (Chain.iff_mem.1 h).imp fun _ _ ⟨h₁, h₂, h₃⟩ => ⟨h₁, mem_cons.2 (Or.inr h₂), h₃⟩,
+      Chain'.imp fun _ _ h => h.2.2⟩
+#align list.chain'.iff_mem List.Chain'.iff_mem
+
+@[simp]
+theorem chain'_nil : Chain' R [] :=
+  trivial
+#align list.chain'_nil List.chain'_nil
+
+@[simp]
+theorem chain'_singleton (a : α) : Chain' R [a] :=
+  Chain.nil
+#align list.chain'_singleton List.chain'_singleton
+
+@[simp]
+theorem chain'_cons {x y l} : Chain' R (x :: y :: l) ↔ R x y ∧ Chain' R (y :: l) :=
+  chain_cons
+#align list.chain'_cons List.chain'_cons
+
+theorem chain'_isInfix : ∀ l : List α, Chain' (fun x y => [x, y] <:+: l) l
+  | [] => chain'_nil
+  | [a] => chain'_singleton _
+  | a :: b :: l =>
+    chain'_cons.2
+      ⟨⟨[], l, by simp⟩, (chain'_isInfix (b :: l)).imp fun x y h => h.trans ⟨[a], [], by simp⟩⟩
+#align list.chain'_is_infix List.chain'_isInfix
+
+theorem chain'_split {a : α} :
+    ∀ {l₁ l₂ : List α}, Chain' R (l₁ ++ a :: l₂) ↔ Chain' R (l₁ ++ [a]) ∧ Chain' R (a :: l₂)
+  | [], _ => (and_iff_right (chain'_singleton a)).symm
+  | _ :: _, _ => chain_split
+#align list.chain'_split List.chain'_split
+
+@[simp]
+theorem chain'_append_cons_cons {b c : α} {l₁ l₂ : List α} :
+    Chain' R (l₁ ++ b :: c :: l₂) ↔ Chain' R (l₁ ++ [b]) ∧ R b c ∧ Chain' R (c :: l₂) := by
+  rw [chain'_split, chain'_cons]
+#align list.chain'_append_cons_cons List.chain'_append_cons_cons
+
+theorem chain'_map (f : β → α) {l : List β} :
+    Chain' R (map f l) ↔ Chain' (fun a b : β => R (f a) (f b)) l := by
+  cases l <;> [rfl, exact chain_map _]
+#align list.chain'_map List.chain'_map
+
+theorem chain'_of_chain'_map {S : β → β → Prop} (f : α → β) (H : ∀ a b : α, S (f a) (f b) → R a b)
+    {l : List α} (p : Chain' S (map f l)) : Chain' R l :=
+  ((chain'_map f).1 p).imp H
+#align list.chain'_of_chain'_map List.chain'_of_chain'_map
+
+theorem chain'_map_of_chain' {S : β → β → Prop} (f : α → β) (H : ∀ a b : α, R a b → S (f a) (f b))
+    {l : List α} (p : Chain' R l) : Chain' S (map f l) :=
+  (chain'_map f).2 <| p.imp H
+#align list.chain'_map_of_chain' List.chain'_map_of_chain'
+
+theorem Pairwise.chain' : ∀ {l : List α}, Pairwise R l → Chain' R l
+  | [], _ => trivial
+  | _ :: _, h => Pairwise.chain h
+#align list.pairwise.chain' List.Pairwise.chain'
+
+theorem chain'_iff_pairwise [IsTrans α R] : ∀ {l : List α}, Chain' R l ↔ Pairwise R l
+  | [] => (iff_true_intro Pairwise.nil).symm
+  | _ :: _ => chain_iff_pairwise
+#align list.chain'_iff_pairwise List.chain'_iff_pairwise
+
+protected theorem Chain'.sublist [IsTrans α R] (hl : l₂.Chain' R) (h : l₁ <+ l₂) : l₁.Chain' R :=
+  by
+  rw [chain'_iff_pairwise] at hl⊢
+  exact hl.sublist h
+#align list.chain'.sublist List.Chain'.sublist
+
+theorem Chain'.cons {x y l} (h₁ : R x y) (h₂ : Chain' R (y :: l)) : Chain' R (x :: y :: l) :=
+  chain'_cons.2 ⟨h₁, h₂⟩
+#align list.chain'.cons List.Chain'.cons
+
+theorem Chain'.tail : ∀ {l} (_ : Chain' R l), Chain' R l.tail
+  | [], _ => trivial
+  | [_], _ => trivial
+  | _ :: _ :: _, h => (chain'_cons.mp h).right
+#align list.chain'.tail List.Chain'.tail
+
+theorem Chain'.rel_head {x y l} (h : Chain' R (x :: y :: l)) : R x y :=
+  rel_of_chain_cons h
+#align list.chain'.rel_head List.Chain'.rel_head
+
+theorem Chain'.rel_head? {x l} (h : Chain' R (x :: l)) ⦃y⦄ (hy : y ∈ head? l) : R x y :=
+  by
+  rw [← cons_head?_tail hy] at h
+  exact h.rel_head
+#align list.chain'.rel_head' List.Chain'.rel_head?
+
+theorem Chain'.cons' {x} : ∀ {l : List α}, Chain' R l → (∀ y ∈ l.head?, R x y) → Chain' R (x :: l)
+  | [], _, _ => chain'_singleton x
+  | _ :: _, hl, H => hl.cons <| H _ rfl
+#align list.chain'.cons' List.Chain'.cons'
+
+theorem chain'_cons' {x l} : Chain' R (x :: l) ↔ (∀ y ∈ head? l, R x y) ∧ Chain' R l :=
+  ⟨fun h => ⟨h.rel_head?, h.tail⟩, fun ⟨h₁, h₂⟩ => h₂.cons' h₁⟩
+#align list.chain'_cons' List.chain'_cons'
+
+theorem chain'_append :
+    ∀ {l₁ l₂ : List α},
+      Chain' R (l₁ ++ l₂) ↔ Chain' R l₁ ∧ Chain' R l₂ ∧ ∀ x ∈ l₁.getLast?, ∀ y ∈ l₂.head?, R x y
+  | [], l => by simp
+  | [a], l => by simp [chain'_cons', and_comm]
+  | a :: b :: l₁, l₂ => by
+    rw [cons_append, cons_append, chain'_cons, chain'_cons, ← cons_append, chain'_append,
+      and_assoc]
+    simp
+#align list.chain'_append List.chain'_append
+
+theorem Chain'.append (h₁ : Chain' R l₁) (h₂ : Chain' R l₂)
+    (h : ∀ x ∈ l₁.getLast?, ∀ y ∈ l₂.head?, R x y) : Chain' R (l₁ ++ l₂) :=
+  chain'_append.2 ⟨h₁, h₂, h⟩
+#align list.chain'.append List.Chain'.append
+
+theorem Chain'.left_of_append (h : Chain' R (l₁ ++ l₂)) : Chain' R l₁ :=
+  (chain'_append.1 h).1
+#align list.chain'.left_of_append List.Chain'.left_of_append
+
+theorem Chain'.right_of_append (h : Chain' R (l₁ ++ l₂)) : Chain' R l₂ :=
+  (chain'_append.1 h).2.1
+#align list.chain'.right_of_append List.Chain'.right_of_append
+
+theorem Chain'.infix (h : Chain' R l) (h' : l₁ <:+: l) : Chain' R l₁ :=
+  by
+  rcases h' with ⟨l₂, l₃, rfl⟩
+  exact h.left_of_append.right_of_append
+#align list.chain'.infix List.Chain'.infix
+
+theorem Chain'.suffix (h : Chain' R l) (h' : l₁ <:+ l) : Chain' R l₁ :=
+  h.infix h'.isInfix
+#align list.chain'.suffix List.Chain'.suffix
+
+theorem Chain'.prefix (h : Chain' R l) (h' : l₁ <+: l) : Chain' R l₁ :=
+  h.infix h'.isInfix
+#align list.chain'.prefix List.Chain'.prefix
+
+theorem Chain'.drop (h : Chain' R l) (n : ℕ) : Chain' R (drop n l) :=
+  h.suffix (drop_suffix _ _)
+#align list.chain'.drop List.Chain'.drop
+
+theorem Chain'.init (h : Chain' R l) : Chain' R l.dropLast :=
+  h.prefix l.dropLast_prefix
+#align list.chain'.init List.Chain'.init
+
+theorem Chain'.take (h : Chain' R l) (n : ℕ) : Chain' R (take n l) :=
+  h.prefix (take_prefix _ _)
+#align list.chain'.take List.Chain'.take
+
+theorem chain'_pair {x y} : Chain' R [x, y] ↔ R x y := by
+  simp only [chain'_singleton, chain'_cons, and_true_iff]
+#align list.chain'_pair List.chain'_pair
+
+theorem Chain'.imp_head {x y} (h : ∀ {z}, R x z → R y z) {l} (hl : Chain' R (x :: l)) :
+    Chain' R (y :: l) :=
+  hl.tail.cons' fun _ hz => h <| hl.rel_head? hz
+#align list.chain'.imp_head List.Chain'.imp_head
+
+theorem chain'_reverse : ∀ {l}, Chain' R (reverse l) ↔ Chain' (flip R) l
+  | [] => Iff.rfl
+  | [a] => by simp only [chain'_singleton, reverse_singleton]
+  | a :: b :: l => by
+    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]
+#align list.chain'_reverse List.chain'_reverse
+
+theorem chain'_iff_get {R} : ∀ {l : List α}, Chain' R l ↔
+    ∀ (i : ℕ) (h : i < length l - 1),
+      R (get l ⟨i, lt_of_lt_pred h⟩) (get l ⟨i + 1, lt_pred_iff.mp h⟩)
+  | [] => iff_of_true (by simp) (fun _ h => by simp at h)
+  | [a] => iff_of_true (by simp) (fun _ h => by simp at h)
+  | a :: b :: t => by
+    rw [← and_forall_succ, chain'_cons, chain'_iff_get]
+    simp
+    dsimp [succ_sub_one]
+    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)⟩
+
+set_option linter.deprecated false in
+@[deprecated chain'_iff_get]
+theorem chain'_iff_nthLe {R} {l : List α} : Chain' R l ↔
+    ∀ (i) (h : i < length l - 1),
+      R (nthLe l i (lt_of_lt_pred h)) (nthLe l (i + 1) (lt_pred_iff.mp h)) :=
+  chain'_iff_get.trans <| by simp [nthLe]
+#align list.chain'_iff_nth_le List.chain'_iff_nthLe
+
+/-- If `l₁ l₂` and `l₃` are lists and `l₁ ++ l₂` and `l₂ ++ l₃` both satisfy
+  `Chain' R`, then so does `l₁ ++ l₂ ++ l₃` provided `l₂ ≠ []` -/
+theorem Chain'.append_overlap {l₁ l₂ l₃ : List α} (h₁ : Chain' R (l₁ ++ l₂))
+    (h₂ : Chain' R (l₂ ++ l₃)) (hn : l₂ ≠ []) : Chain' R (l₁ ++ l₂ ++ l₃) :=
+  h₁.append h₂.right_of_append <| by
+    simpa only [getLast?_append_of_ne_nil _ hn] using (chain'_append.1 h₂).2.2
+#align list.chain'.append_overlap List.Chain'.append_overlap
+
+/-- If `a` and `b` are related by the reflexive transitive closure of `r`, then there is a `r`-chain
+starting from `a` and ending on `b`.
+The converse of `relationReflTransGen_of_exists_chain`.
+-/
+theorem exists_chain_of_relationReflTransGen (h : Relation.ReflTransGen r a b) :
+    ∃ l, Chain r a l ∧ getLast (a :: l) (cons_ne_nil _ _) = b := by
+  refine' Relation.ReflTransGen.head_induction_on h _ _
+  · exact ⟨[], Chain.nil, rfl⟩
+  · intro c d e _ ih
+    obtain ⟨l, hl₁, hl₂⟩ := ih
+    refine' ⟨d :: l, Chain.cons e hl₁, _⟩
+    rwa [getLast_cons_cons]
+#align list.exists_chain_of_relation_refl_trans_gen List.exists_chain_of_relationReflTransGen
+
+/-- Given a chain from `a` to `b`, and a predicate true at `b`, if `r x y → p y → p x` then
+the predicate is true everywhere in the chain and at `a`.
+That is, we can propagate the predicate up the chain.
+-/
+theorem Chain.induction (p : α → Prop) (l : List α) (h : Chain r a l)
+    (hb : getLast (a :: l) (cons_ne_nil _ _) = b) (carries : ∀ ⦃x y : α⦄, r x y → p y → p x)
+    (final : p b) : ∀ i ∈ a :: l, p i :=
+  by
+  induction' l with _ _ l_ih generalizing a
+  · cases hb
+    simpa using final
+  · rw [chain_cons] at h
+    simp only [mem_cons]
+    rintro _ (rfl | H)
+    apply carries h.1 (l_ih h.2 hb _ (mem_cons.2 (Or.inl rfl)))
+    apply l_ih h.2 hb _ (mem_cons.2 H)
+#align list.chain.induction List.Chain.induction
+
+/-- Given a chain from `a` to `b`, and a predicate true at `b`, if `r x y → p y → p x` then
+the predicate is true at `a`.
+That is, we can propagate the predicate all the way up the chain.
+-/
+@[elab_as_elim]
+theorem Chain.induction_head (p : α → Prop) (l : List α) (h : Chain r a l)
+    (hb : getLast (a :: l) (cons_ne_nil _ _) = b) (carries : ∀ ⦃x y : α⦄, r x y → p y → p x)
+    (final : p b) : p a :=
+  (Chain.induction p l h hb carries final) _ (mem_cons_self _ _)
+#align list.chain.induction_head List.Chain.induction_head
+
+/--
+If there is an `r`-chain starting from `a` and ending at `b`, then `a` and `b` are related by the
+reflexive transitive closure of `r`. The converse of `exists_chain_of_relationReflTransGen`.
+-/
+theorem relationReflTransGen_of_exists_chain (l : List α) (hl₁ : Chain r a l)
+    (hl₂ : getLast (a :: l) (cons_ne_nil _ _) = b) : Relation.ReflTransGen r a b :=
+--Porting note: `p` behaves like an implicit argument to `Chain.induction_head` but it is explicit.
+  Chain.induction_head l hl₁ hl₂ (fun _ _ => Relation.ReflTransGen.head)
+    Relation.ReflTransGen.refl
+#align list.relation_refl_trans_gen_of_exists_chain List.relationReflTransGen_of_exists_chain
+
+end List