data.list.lex | Mathlib porting status

Changes since the initial port

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.

Changes in mathlib3

d6aae1bc

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

448144f7

bump to nightly-2024-02-01-06

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

5433bded

Diff

@@ -184,7 +184,7 @@ theorem Decidable.List.Lex.ne_iff [DecidableEq α] {l₁ l₂ : List α} (H : le
 
 #print List.Lex.ne_iff /-
 theorem ne_iff {l₁ l₂ : List α} (H : length l₁ ≤ length l₂) : Lex (· ≠ ·) l₁ l₂ ↔ l₁ ≠ l₂ := by
-  classical
+  classical exact Decidable.List.Lex.ne_iff H
 #align list.lex.ne_iff List.Lex.ne_iff
 -/

448144f7

bump to nightly-2024-01-31-06

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

61100fe9

Diff

@@ -184,7 +184,7 @@ theorem Decidable.List.Lex.ne_iff [DecidableEq α] {l₁ l₂ : List α} (H : le
 
 #print List.Lex.ne_iff /-
 theorem ne_iff {l₁ l₂ : List α} (H : length l₁ ≤ length l₂) : Lex (· ≠ ·) l₁ l₂ ↔ l₁ ≠ l₂ := by
-  classical exact Decidable.List.Lex.ne_iff H
+  classical
 #align list.lex.ne_iff List.Lex.ne_iff
 -/

448144f7

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
-import Mathbin.Order.RelClasses
+import Order.RelClasses
 
 #align_import data.list.lex from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"

448144f7

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.list.lex
-! leanprover-community/mathlib commit 448144f7ae193a8990cb7473c9e9a01990f64ac7
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Order.RelClasses
 
+#align_import data.list.lex from "leanprover-community/mathlib"@"448144f7ae193a8990cb7473c9e9a01990f64ac7"
+
 /-!
 # Lexicographic ordering of lists.

448144f7

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -59,7 +59,7 @@ namespace Lex
 #print List.Lex.cons_iff /-
 theorem cons_iff {r : α → α → Prop} [IsIrrefl α r] {a l₁ l₂} :
     Lex r (a :: l₁) (a :: l₂) ↔ Lex r l₁ l₂ :=
-  ⟨fun h => by cases' h with _ _ _ _ _ h _ _ _ _ h <;> [exact h;exact (irrefl_of r a h).elim],
+  ⟨fun h => by cases' h with _ _ _ _ _ h _ _ _ _ h <;> [exact h; exact (irrefl_of r a h).elim],
     Lex.cons⟩
 #align list.lex.cons_iff List.Lex.cons_iff
 -/

448144f7

bump to nightly-2023-05-28-18

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

8d353152

Diff

@@ -212,7 +212,7 @@ instance [LinearOrder α] : LinearOrder (List α) :=
 #print List.LE' /-
 --Note: this overrides an instance in core lean
 instance LE' [LinearOrder α] : LE (List α) :=
-  Preorder.toHasLe _
+  Preorder.toLE _
 #align list.has_le' List.LE'
 -/

448144f7

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -179,8 +179,7 @@ theorem Decidable.List.Lex.ne_iff [DecidableEq α] {l₁ l₂ : List α} (H : le
     · apply nil
     · exact (not_lt_of_ge H).elim (succ_pos _)
     · by_cases ab : a = b
-      · subst b
-        apply cons
+      · subst b; apply cons
         exact IH (le_of_succ_le_succ H) (mt (congr_arg _) h)
       · exact Rel ab⟩
 #align decidable.list.lex.ne_iff Decidable.List.Lex.ne_iff

448144f7

bump to nightly-2023-05-24-06

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

fbc7b476

Diff

@@ -59,7 +59,7 @@ namespace Lex
 #print List.Lex.cons_iff /-
 theorem cons_iff {r : α → α → Prop} [IsIrrefl α r] {a l₁ l₂} :
     Lex r (a :: l₁) (a :: l₂) ↔ Lex r l₁ l₂ :=
-  ⟨fun h => by cases' h with _ _ _ _ _ h _ _ _ _ h <;> [exact h, exact (irrefl_of r a h).elim],
+  ⟨fun h => by cases' h with _ _ _ _ _ h _ _ _ _ h <;> [exact h;exact (irrefl_of r a h).elim],
     Lex.cons⟩
 #align list.lex.cons_iff List.Lex.cons_iff
 -/

448144f7

bump to nightly-2023-05-16-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8

9cb92e8c

Diff

@@ -213,7 +213,7 @@ instance [LinearOrder α] : LinearOrder (List α) :=
 #print List.LE' /-
 --Note: this overrides an instance in core lean
 instance LE' [LinearOrder α] : LE (List α) :=
-  Preorder.toLE _
+  Preorder.toHasLe _
 #align list.has_le' List.LE'
 -/

448144f7

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

d6aae1bc

chore: reduce proof dependencies for Nat.factors_count_eq (#12105)

This is a bit longer, partially duplicating the argument from UniqueFactorizationMonoid.multiplicity_eq_count_normalizedFactors, but it means we no longer need to depend on RingTheory.Int.Basic at this point.

The other added lemmas seem useful regardless.

51a6e529

Diff

@@ -212,6 +212,12 @@ theorem lt_iff_lex_lt [LinearOrder α] (l l' : List α) : lt l l' ↔ Lex (· <
     | @cons a as bs _ ih => apply lt.tail <;> simp [ih]
     | @rel a as b bs h => apply lt.head; assumption
 
+@[simp]
+theorem nil_le {α} [LinearOrder α] {l : List α} : [] ≤ l :=
+  match l with
+  | [] => le_rfl
+  | _ :: _ => le_of_lt <| nil_lt_cons _ _
+
 theorem head_le_of_lt [LinearOrder α] {a a' : α} {l l' : List α} (h : (a' :: l') < (a :: l)) :
     a' ≤ a := by
   by_contra hh

d6aae1bc

chore: move Mathlib to v4.7.0-rc1 (#11162)

This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0 branch as we update to intermediate nightlies.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>

fa48894a

Diff

@@ -59,7 +59,7 @@ theorem cons_iff {r : α → α → Prop} [IsIrrefl α r] {a l₁ l₂} :
 
 @[simp]
 theorem not_nil_right (r : α → α → Prop) (l : List α) : ¬Lex r l [] :=
-  fun.
+  nofun
 #align list.lex.not_nil_right List.Lex.not_nil_right
 
 theorem nil_left_or_eq_nil {r : α → α → Prop} (l : List α) : List.Lex r [] l ∨ l = [] :=

d6aae1bc

chore: tidy various files (#8175)

11572f18

Diff

@@ -231,7 +231,7 @@ theorem cons_le_cons [LinearOrder α] (a : α) {l l' : List α} (h : l' ≤ l) :
   rw [le_iff_lt_or_eq] at h ⊢
   refine h.imp ?_ (congr_arg _)
   intro h
-  have haa : ¬(a < a) := gt_irrefl a
+  have haa := lt_irrefl a
   exact (List.lt_iff_lex_lt _ _).mp
     (List.lt.tail haa haa ((List.lt_iff_lex_lt _ _).mpr h))

d6aae1bc

feat: condition for being < an ordinal in a decreasing list (#7899)

c6cb8b61

Diff

@@ -212,15 +212,19 @@ theorem lt_iff_lex_lt [LinearOrder α] (l l' : List α) : lt l l' ↔ Lex (· <
     | @cons a as bs _ ih => apply lt.tail <;> simp [ih]
     | @rel a as b bs h => apply lt.head; assumption
 
-theorem head!_le_of_lt [LinearOrder α] [Inhabited α] (l l' : List α) (h : lt l' l) (hl' : l' ≠ []) :
+theorem head_le_of_lt [LinearOrder α] {a a' : α} {l l' : List α} (h : (a' :: l') < (a :: l)) :
+    a' ≤ a := by
+  by_contra hh
+  simp only [not_le] at hh
+  exact List.Lex.isAsymm.aux _ _ _ (List.Lex.rel hh) h
+
+theorem head!_le_of_lt [LinearOrder α] [Inhabited α] (l l' : List α) (h : l' < l) (hl' : l' ≠ []) :
     l'.head! ≤ l.head! := by
-  rw [lt_iff_lex_lt l' l] at h
+  replace h : List.Lex (· < ·) l' l := h
   by_cases hl : l = []
-  · simp only [hl, List.Lex.not_nil_right] at h
-  · by_contra hh
-    have := List.Lex.rel (r := (·<·)) (l₁ := l.tail) (l₂ := l'.tail) (not_le.mp hh)
-    rw [List.cons_head!_tail hl', List.cons_head!_tail hl] at this
-    exact asymm h this
+  · simp [hl] at h
+  · rw [← List.cons_head!_tail hl', ← List.cons_head!_tail hl] at h
+    exact head_le_of_lt h
 
 theorem cons_le_cons [LinearOrder α] (a : α) {l l' : List α} (h : l' ≤ l) :
     a :: l' ≤ a :: l := by

d6aae1bc

feat: adding an element at the head of lists preserves non-strict lexicographic inequality (#7897)

840db663

Diff

@@ -222,4 +222,13 @@ theorem head!_le_of_lt [LinearOrder α] [Inhabited α] (l l' : List α) (h : lt
     rw [List.cons_head!_tail hl', List.cons_head!_tail hl] at this
     exact asymm h this
 
+theorem cons_le_cons [LinearOrder α] (a : α) {l l' : List α} (h : l' ≤ l) :
+    a :: l' ≤ a :: l := by
+  rw [le_iff_lt_or_eq] at h ⊢
+  refine h.imp ?_ (congr_arg _)
+  intro h
+  have haa : ¬(a < a) := gt_irrefl a
+  exact (List.lt_iff_lex_lt _ _).mp
+    (List.lt.tail haa haa ((List.lt_iff_lex_lt _ _).mpr h))
+
 end List

d6aae1bc

feat: two small lemmas about ordered lists (#7829)

We prove that in a sorted list, the head! is the smallest element, and that if a list is lexicographically smaller than another list, then its head! is smaller than or equal to that of the other.

7db2b0a8

Diff

@@ -4,6 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
 -/
 import Mathlib.Order.RelClasses
+import Mathlib.Data.List.Basic
 
 #align_import data.list.lex from "leanprover-community/mathlib"@"d6aae1bcbd04b8de2022b9b83a5b5b10e10c777d"
 
@@ -211,4 +212,14 @@ theorem lt_iff_lex_lt [LinearOrder α] (l l' : List α) : lt l l' ↔ Lex (· <
     | @cons a as bs _ ih => apply lt.tail <;> simp [ih]
     | @rel a as b bs h => apply lt.head; assumption
 
+theorem head!_le_of_lt [LinearOrder α] [Inhabited α] (l l' : List α) (h : lt l' l) (hl' : l' ≠ []) :
+    l'.head! ≤ l.head! := by
+  rw [lt_iff_lex_lt l' l] at h
+  by_cases hl : l = []
+  · simp only [hl, List.Lex.not_nil_right] at h
+  · by_contra hh
+    have := List.Lex.rel (r := (·<·)) (l₁ := l.tail) (l₂ := l'.tail) (not_le.mp hh)
+    rw [List.cons_head!_tail hl', List.cons_head!_tail hl] at this
+    exact asymm h this
+
 end List

d6aae1bc

feat: two easy lemmas about List.Lex (#6395)

Proves that [] is the "bottom element" for List.Lex r for any relation r and that List.Lex r [a] [b] iff r a b

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

5759caed

Diff

@@ -61,6 +61,15 @@ theorem not_nil_right (r : α → α → Prop) (l : List α) : ¬Lex r l [] :=
   fun.
 #align list.lex.not_nil_right List.Lex.not_nil_right
 
+theorem nil_left_or_eq_nil {r : α → α → Prop} (l : List α) : List.Lex r [] l ∨ l = [] :=
+  match l with
+  | [] => Or.inr rfl
+  | (_ :: _) => Or.inl nil
+
+@[simp]
+theorem singleton_iff {r : α → α → Prop} (a b : α) : List.Lex r [a] [b] ↔ r a b :=
+  ⟨fun | rel h => h, List.Lex.rel⟩
+
 instance isOrderConnected (r : α → α → Prop) [IsOrderConnected α r] [IsTrichotomous α r] :
     IsOrderConnected (List α) (Lex r) where
   conn := aux where

d6aae1bc

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

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

89aa3a3b

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
-
-! This file was ported from Lean 3 source module data.list.lex
-! leanprover-community/mathlib commit d6aae1bcbd04b8de2022b9b83a5b5b10e10c777d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Order.RelClasses
 
+#align_import data.list.lex from "leanprover-community/mathlib"@"d6aae1bcbd04b8de2022b9b83a5b5b10e10c777d"
+
 /-!
 # Lexicographic ordering of lists.

d6aae1bc

feat: add Mathlib.Tactic.Common, and import (#4056)

This makes a mathlib4 version of mathlib3's tactic.basic, now called Mathlib.Tactic.Common, which imports all tactics which do not have significant theory requirements, and then is imported all across the base of the hierarchy.

This ensures that all common tactics are available nearly everywhere in the library, rather than having to be imported one-by-one as you need them.

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

a4eaf1c4

Diff

@@ -9,7 +9,6 @@ Authors: Mario Carneiro
 ! if you have ported upstream changes.
 -/
 import Mathlib.Order.RelClasses
-import Mathlib.Tactic.Classical
 
 /-!
 # Lexicographic ordering of lists.

d6aae1bc

chore: move List.lt_iff_lex_lt to a more logical location (#3403)

85a0b4ca

Diff

@@ -192,4 +192,18 @@ instance LE' [LinearOrder α] : LE (List α) :=
   Preorder.toLE
 #align list.has_le' List.LE'
 
+theorem lt_iff_lex_lt [LinearOrder α] (l l' : List α) : lt l l' ↔ Lex (· < ·) l l' := by
+  constructor <;>
+  intro h
+  · induction h with
+    | nil b bs => exact Lex.nil
+    | @head a as b bs hab => apply Lex.rel; assumption
+    | @tail a as b bs hab hba _ ih =>
+      have heq : a = b := _root_.le_antisymm (le_of_not_lt hba) (le_of_not_lt hab)
+      subst b; apply Lex.cons; assumption
+  · induction h with
+    | @nil a as => apply lt.nil
+    | @cons a as bs _ ih => apply lt.tail <;> simp [ih]
+    | @rel a as b bs h => apply lt.head; assumption
+
 end List

d6aae1bc

chore: add source headers to ported theory files (#1094)

The script used to do this is included. The yaml file was obtained from https://raw.githubusercontent.com/wiki/leanprover-community/mathlib/mathlib4-port-status.md

f168625e

Diff

@@ -2,6 +2,11 @@
 Copyright (c) 2018 Mario Carneiro. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Mario Carneiro
+
+! This file was ported from Lean 3 source module data.list.lex
+! leanprover-community/mathlib commit d6aae1bcbd04b8de2022b9b83a5b5b10e10c777d
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
 -/
 import Mathlib.Order.RelClasses
 import Mathlib.Tactic.Classical

`data.list.lex` ⟷ `Mathlib.Data.List.Lex`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 10

data.list.lex ⟷ Mathlib.Data.List.Lex

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 10

`data.list.lex` ⟷ `Mathlib.Data.List.Lex`