data.list.chain
⟷
Mathlib.Data.List.Chain
The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
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
@@ -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
Sublist
(#12326)
tail_sublist
to Basic
sublist_of_cons_sublist_cons
to Sublist.of_cons_cos
cons_sublist_cons_iff
to cons_sublist_cons
Sublist.tail
, drop_sublist_drop_left
, Sublist.drop
@@ -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)) :=
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.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.MonoidWithZero
lemmas from Algebra.BigOperators.List.Basic
to Algebra.BigOperators.List.Lemmas
.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.Data.List.Count
, Data.List.Dedup
, Data.List.ProdSigma
, Data.List.Zip
not depend on Algebra.BigOperators.List.Basic
.Algebra.BigOperators.List.Basic
. For the lemmas that were Nat
-specific, keep a version of them stated using Nat.sum
.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
:
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
@@ -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:
@@ -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
@@ -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"
$
with <|
(#9319)
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`.
∃ x ∈ s, _
instead of ∃ (x) (_ : x ∈ s), _
(#9184)
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
@@ -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
This is the supremum of
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.
In particular this includes adjustments for the Lean PRs
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).
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})
.
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:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[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
@@ -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)⟩
@@ -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]
@@ -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
@@ -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'⟩
@@ -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
at
and goals (#5387)
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
@@ -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"
_
and make all uppercase letters into lowercase_
and make all uppercase letters into lowercase(original_lean3_name, OriginalLean4Name)
#align
statement just before the next empty line#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
IsTrans α r → Trans r r r
and Trans r r r → IsTrans α r
(#1522)
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
by
line breaks (#1523)
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
The unported dependencies are