data.list.lemmas | Mathlib porting status

(last sync)

feat(data/list/lemmas): add lemmas about set.range list.nth* (#18647)

Add versions for list.nth_le, list.nth, list.nthd, and list.inth. Also move lemmas from list to set namespace.

Diff

@@ -20,29 +20,6 @@ variables {α β γ : Type*}
 
 namespace list
 
-lemma range_map (f : α → β) : set.range (map f) = {l | ∀ x ∈ l, x ∈ set.range f} :=
-begin
-  refine set.subset.antisymm (set.range_subset_iff.2 $
-    λ l, forall_mem_map_iff.2 $ λ y _, set.mem_range_self _) (λ l hl, _),
-  induction l with a l ihl, { exact ⟨[], rfl⟩ },
-  rcases ihl (λ x hx, hl x $ subset_cons _ _ hx) with ⟨l, rfl⟩,
-  rcases hl a (mem_cons_self _ _) with ⟨a, rfl⟩,
-  exact ⟨a :: l, map_cons _ _ _⟩
-end
-
-lemma range_map_coe (s : set α) : set.range (map (coe : s → α)) = {l | ∀ x ∈ l, x ∈ s} :=
-by rw [range_map, subtype.range_coe]
-
-/-- If each element of a list can be lifted to some type, then the whole list can be lifted to this
-type. -/
-instance can_lift (c) (p) [can_lift α β c p] :
-  can_lift (list α) (list β) (list.map c) (λ l, ∀ x ∈ l, p x) :=
-{ prf  := λ l H,
-    begin
-      rw [← set.mem_range, range_map],
-      exact λ a ha, can_lift.prf a (H a ha),
-    end}
-
 lemma inj_on_insert_nth_index_of_not_mem (l : list α) (x : α) (hx : x ∉ l) :
   set.inj_on (λ k, insert_nth k x l) {n | n ≤ l.length} :=
 begin

feat(data/list/lemmas): Range of foldr (#13328)

Mathlib4 pair: https://github.com/leanprover-community/mathlib4/pull/1870

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

Diff

@@ -16,7 +16,7 @@ Split out from `data.list.basic` to reduce its dependencies.
 
 open list
 
-variables {α β : Type*}
+variables {α β γ : Type*}
 
 namespace list
 
@@ -66,4 +66,38 @@ begin
       { simpa [nat.succ_le_succ_iff] using hm } } }
 end
 
+lemma foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α → α}
+  (hfg : set.range f ⊆ set.range g) (a : α) :
+  set.range (foldr f a) ⊆ set.range (foldr g a) :=
+begin
+  rintro _ ⟨l, rfl⟩,
+  induction l with b l H,
+  { exact ⟨[], rfl⟩ },
+  { cases hfg (set.mem_range_self b) with c hgf,
+    cases H with m hgf',
+    rw [foldr_cons, ←hgf, ←hgf'],
+    exact ⟨c :: m, rfl⟩ }
+end
+
+lemma foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ → α}
+  (hfg : set.range (λ a c, f c a) ⊆ set.range (λ b c, g c b)) (a : α) :
+  set.range (foldl f a) ⊆ set.range (foldl g a) :=
+begin
+  change set.range (λ l, _) ⊆ set.range (λ l, _),
+  simp_rw ←foldr_reverse at hfg ⊢,
+  simp_rw [set.range_comp _ list.reverse, reverse_involutive.bijective.surjective.range_eq,
+    set.image_univ],
+  exact foldr_range_subset_of_range_subset hfg a,
+end
+
+lemma foldr_range_eq_of_range_eq {f : β → α → α} {g : γ → α → α} (hfg : set.range f = set.range g)
+  (a : α) :
+  set.range (foldr f a) = set.range (foldr g a) :=
+(foldr_range_subset_of_range_subset hfg.le a).antisymm (foldr_range_subset_of_range_subset hfg.ge a)
+
+lemma foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
+  (hfg : set.range (λ a c, f c a) = set.range (λ b c, g c b)) (a : α) :
+  set.range (foldl f a) = set.range (foldl g a) :=
+(foldl_range_subset_of_range_subset hfg.le a).antisymm (foldl_range_subset_of_range_subset hfg.ge a)
+
 end list

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -30,16 +30,16 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
   induction' l with hd tl IH
   · intro n hn m hm h
     simp only [Set.mem_singleton_iff, Set.setOf_eq_eq_singleton, length, nonpos_iff_eq_zero] at hn
-      hm 
+      hm
     simp [hn, hm]
   · intro n hn m hm h
-    simp only [length, Set.mem_setOf_eq] at hn hm 
-    simp only [mem_cons_iff, not_or] at hx 
+    simp only [length, Set.mem_setOf_eq] at hn hm
+    simp only [mem_cons_iff, not_or] at hx
     cases n <;> cases m
     · rfl
     · simpa [hx.left] using h
     · simpa [Ne.symm hx.left] using h
-    · simp only [true_and_iff, eq_self_iff_true, insert_nth_succ_cons] at h 
+    · simp only [true_and_iff, eq_self_iff_true, insert_nth_succ_cons] at h
       rw [Nat.succ_inj]
       refine' IH hx.right _ _ h
       · simpa [Nat.succ_le_succ_iff] using hn

bump to nightly-2024-01-13-06

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

31733180

Diff

@@ -40,7 +40,7 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
     · simpa [hx.left] using h
     · simpa [Ne.symm hx.left] using h
     · simp only [true_and_iff, eq_self_iff_true, insert_nth_succ_cons] at h 
-      rw [Nat.succ_inj']
+      rw [Nat.succ_inj]
       refine' IH hx.right _ _ h
       · simpa [Nat.succ_le_succ_iff] using hn
       · simpa [Nat.succ_le_succ_iff] using hm

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2021 Yakov Pechersky. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
 -/
-import Mathbin.Data.Set.Function
-import Mathbin.Data.List.Basic
+import Data.Set.Function
+import Data.List.Basic
 
 #align_import data.list.lemmas from "leanprover-community/mathlib"@"2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4"

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2021 Yakov Pechersky. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
-
-! This file was ported from Lean 3 source module data.list.lemmas
-! leanprover-community/mathlib commit 2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Set.Function
 import Mathbin.Data.List.Basic
 
+#align_import data.list.lemmas from "leanprover-community/mathlib"@"2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4"
+
 /-! # Some lemmas about lists involving sets
 
 > THIS FILE IS SYNCHRONIZED WITH MATHLIB4.

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -50,6 +50,7 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
 #align list.inj_on_insert_nth_index_of_not_mem List.injOn_insertNth_index_of_not_mem
 -/
 
+#print List.foldr_range_subset_of_range_subset /-
 theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α → α}
     (hfg : Set.range f ⊆ Set.range g) (a : α) : Set.range (foldr f a) ⊆ Set.range (foldr g a) :=
   by
@@ -61,7 +62,9 @@ theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α
     rw [foldr_cons, ← hgf, ← hgf']
     exact ⟨c :: m, rfl⟩
 #align list.foldr_range_subset_of_range_subset List.foldr_range_subset_of_range_subset
+-/
 
+#print List.foldl_range_subset_of_range_subset /-
 theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ → α}
     (hfg : (Set.range fun a c => f c a) ⊆ Set.range fun b c => g c b) (a : α) :
     Set.range (foldl f a) ⊆ Set.range (foldl g a) :=
@@ -72,19 +75,24 @@ theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ
     Set.image_univ]
   exact foldr_range_subset_of_range_subset hfg a
 #align list.foldl_range_subset_of_range_subset List.foldl_range_subset_of_range_subset
+-/
 
+#print List.foldr_range_eq_of_range_eq /-
 theorem foldr_range_eq_of_range_eq {f : β → α → α} {g : γ → α → α} (hfg : Set.range f = Set.range g)
     (a : α) : Set.range (foldr f a) = Set.range (foldr g a) :=
   (foldr_range_subset_of_range_subset hfg.le a).antisymm
     (foldr_range_subset_of_range_subset hfg.ge a)
 #align list.foldr_range_eq_of_range_eq List.foldr_range_eq_of_range_eq
+-/
 
+#print List.foldl_range_eq_of_range_eq /-
 theorem foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
     (hfg : (Set.range fun a c => f c a) = Set.range fun b c => g c b) (a : α) :
     Set.range (foldl f a) = Set.range (foldl g a) :=
   (foldl_range_subset_of_range_subset hfg.le a).antisymm
     (foldl_range_subset_of_range_subset hfg.ge a)
 #align list.foldl_range_eq_of_range_eq List.foldl_range_eq_of_range_eq
+-/
 
 end List

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -28,7 +28,7 @@ namespace List
 
 #print List.injOn_insertNth_index_of_not_mem /-
 theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
-    Set.InjOn (fun k => insertNth k x l) { n | n ≤ l.length } :=
+    Set.InjOn (fun k => insertNth k x l) {n | n ≤ l.length} :=
   by
   induction' l with hd tl IH
   · intro n hn m hm h

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -32,17 +32,17 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
   by
   induction' l with hd tl IH
   · intro n hn m hm h
-    simp only [Set.mem_singleton_iff, Set.setOf_eq_eq_singleton, length, nonpos_iff_eq_zero] at
-      hn hm
+    simp only [Set.mem_singleton_iff, Set.setOf_eq_eq_singleton, length, nonpos_iff_eq_zero] at hn
+      hm 
     simp [hn, hm]
   · intro n hn m hm h
-    simp only [length, Set.mem_setOf_eq] at hn hm
-    simp only [mem_cons_iff, not_or] at hx
+    simp only [length, Set.mem_setOf_eq] at hn hm 
+    simp only [mem_cons_iff, not_or] at hx 
     cases n <;> cases m
     · rfl
     · simpa [hx.left] using h
     · simpa [Ne.symm hx.left] using h
-    · simp only [true_and_iff, eq_self_iff_true, insert_nth_succ_cons] at h
+    · simp only [true_and_iff, eq_self_iff_true, insert_nth_succ_cons] at h 
       rw [Nat.succ_inj']
       refine' IH hx.right _ _ h
       · simpa [Nat.succ_le_succ_iff] using hn
@@ -67,7 +67,7 @@ theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ
     Set.range (foldl f a) ⊆ Set.range (foldl g a) :=
   by
   change (Set.range fun l => _) ⊆ Set.range fun l => _
-  simp_rw [← foldr_reverse] at hfg⊢
+  simp_rw [← foldr_reverse] at hfg ⊢
   simp_rw [Set.range_comp _ List.reverse, reverse_involutive.bijective.surjective.range_eq,
     Set.image_univ]
   exact foldr_range_subset_of_range_subset hfg a

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -50,12 +50,6 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
 #align list.inj_on_insert_nth_index_of_not_mem List.injOn_insertNth_index_of_not_mem
 -/
 
-/- warning: list.foldr_range_subset_of_range_subset -> List.foldr_range_subset_of_range_subset is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : β -> α -> α} {g : γ -> α -> α}, (HasSubset.Subset.{u1} (Set.{u1} (α -> α)) (Set.hasSubset.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β f) (Set.range.{u1, succ u3} (α -> α) γ g)) -> (forall (a : α), HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldr.{u2, u1} β α f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldr.{u3, u1} γ α g a)))
-but is expected to have type
-  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : β -> α -> α} {g : γ -> α -> α}, (HasSubset.Subset.{u3} (Set.{u3} (α -> α)) (Set.instHasSubsetSet.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β f) (Set.range.{u3, succ u1} (α -> α) γ g)) -> (forall (a : α), HasSubset.Subset.{u3} (Set.{u3} α) (Set.instHasSubsetSet.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldr.{u2, u3} β α f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldr.{u1, u3} γ α g a)))
-Case conversion may be inaccurate. Consider using '#align list.foldr_range_subset_of_range_subset List.foldr_range_subset_of_range_subsetₓ'. -/
 theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α → α}
     (hfg : Set.range f ⊆ Set.range g) (a : α) : Set.range (foldr f a) ⊆ Set.range (foldr g a) :=
   by
@@ -68,12 +62,6 @@ theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α
     exact ⟨c :: m, rfl⟩
 #align list.foldr_range_subset_of_range_subset List.foldr_range_subset_of_range_subset
 
-/- warning: list.foldl_range_subset_of_range_subset -> List.foldl_range_subset_of_range_subset is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : α -> β -> α} {g : α -> γ -> α}, (HasSubset.Subset.{u1} (Set.{u1} (α -> α)) (Set.hasSubset.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u1, succ u3} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldl.{u1, u2} α β f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldl.{u1, u3} α γ g a)))
-but is expected to have type
-  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : α -> β -> α} {g : α -> γ -> α}, (HasSubset.Subset.{u3} (Set.{u3} (α -> α)) (Set.instHasSubsetSet.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u3, succ u1} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), HasSubset.Subset.{u3} (Set.{u3} α) (Set.instHasSubsetSet.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldl.{u3, u2} α β f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldl.{u3, u1} α γ g a)))
-Case conversion may be inaccurate. Consider using '#align list.foldl_range_subset_of_range_subset List.foldl_range_subset_of_range_subsetₓ'. -/
 theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ → α}
     (hfg : (Set.range fun a c => f c a) ⊆ Set.range fun b c => g c b) (a : α) :
     Set.range (foldl f a) ⊆ Set.range (foldl g a) :=
@@ -85,24 +73,12 @@ theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ
   exact foldr_range_subset_of_range_subset hfg a
 #align list.foldl_range_subset_of_range_subset List.foldl_range_subset_of_range_subset
 
-/- warning: list.foldr_range_eq_of_range_eq -> List.foldr_range_eq_of_range_eq is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : β -> α -> α} {g : γ -> α -> α}, (Eq.{succ u1} (Set.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β f) (Set.range.{u1, succ u3} (α -> α) γ g)) -> (forall (a : α), Eq.{succ u1} (Set.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldr.{u2, u1} β α f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldr.{u3, u1} γ α g a)))
-but is expected to have type
-  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : β -> α -> α} {g : γ -> α -> α}, (Eq.{succ u3} (Set.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β f) (Set.range.{u3, succ u1} (α -> α) γ g)) -> (forall (a : α), Eq.{succ u3} (Set.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldr.{u2, u3} β α f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldr.{u1, u3} γ α g a)))
-Case conversion may be inaccurate. Consider using '#align list.foldr_range_eq_of_range_eq List.foldr_range_eq_of_range_eqₓ'. -/
 theorem foldr_range_eq_of_range_eq {f : β → α → α} {g : γ → α → α} (hfg : Set.range f = Set.range g)
     (a : α) : Set.range (foldr f a) = Set.range (foldr g a) :=
   (foldr_range_subset_of_range_subset hfg.le a).antisymm
     (foldr_range_subset_of_range_subset hfg.ge a)
 #align list.foldr_range_eq_of_range_eq List.foldr_range_eq_of_range_eq
 
-/- warning: list.foldl_range_eq_of_range_eq -> List.foldl_range_eq_of_range_eq is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : α -> β -> α} {g : α -> γ -> α}, (Eq.{succ u1} (Set.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u1, succ u3} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), Eq.{succ u1} (Set.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldl.{u1, u2} α β f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldl.{u1, u3} α γ g a)))
-but is expected to have type
-  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : α -> β -> α} {g : α -> γ -> α}, (Eq.{succ u3} (Set.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u3, succ u1} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), Eq.{succ u3} (Set.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldl.{u3, u2} α β f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldl.{u3, u1} α γ g a)))
-Case conversion may be inaccurate. Consider using '#align list.foldl_range_eq_of_range_eq List.foldl_range_eq_of_range_eqₓ'. -/
 theorem foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
     (hfg : (Set.range fun a c => f c a) = Set.range fun b c => g c b) (a : α) :
     Set.range (foldl f a) = Set.range (foldl g a) :=

bump to nightly-2023-03-31-02

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

c3ffa91f

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
 
 ! This file was ported from Lean 3 source module data.list.lemmas
-! leanprover-community/mathlib commit 975c8c329887c50db6f3556a5f382292ee152ff9
+! leanprover-community/mathlib commit 2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -26,37 +26,6 @@ variable {α β γ : Type _}
 
 namespace List
 
-#print List.range_map /-
-theorem range_map (f : α → β) : Set.range (map f) = { l | ∀ x ∈ l, x ∈ Set.range f } :=
-  by
-  refine'
-    Set.Subset.antisymm
-      (Set.range_subset_iff.2 fun l => forall_mem_map_iff.2 fun y _ => Set.mem_range_self _)
-      fun l hl => _
-  induction' l with a l ihl; · exact ⟨[], rfl⟩
-  rcases ihl fun x hx => hl x <| subset_cons _ _ hx with ⟨l, rfl⟩
-  rcases hl a (mem_cons_self _ _) with ⟨a, rfl⟩
-  exact ⟨a :: l, map_cons _ _ _⟩
-#align list.range_map List.range_map
--/
-
-#print List.range_map_coe /-
-theorem range_map_coe (s : Set α) : Set.range (map (coe : s → α)) = { l | ∀ x ∈ l, x ∈ s } := by
-  rw [range_map, Subtype.range_coe]
-#align list.range_map_coe List.range_map_coe
--/
-
-#print List.canLift /-
-/-- If each element of a list can be lifted to some type, then the whole list can be lifted to this
-type. -/
-instance canLift (c) (p) [CanLift α β c p] :
-    CanLift (List α) (List β) (List.map c) fun l => ∀ x ∈ l, p x
-    where prf l H := by
-    rw [← Set.mem_range, range_map]
-    exact fun a ha => CanLift.prf a (H a ha)
-#align list.can_lift List.canLift
--/
-
 #print List.injOn_insertNth_index_of_not_mem /-
 theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
     Set.InjOn (fun k => insertNth k x l) { n | n ≤ l.length } :=

bump to nightly-2023-03-17-20

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

4420e8a1

Diff

@@ -81,6 +81,12 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
 #align list.inj_on_insert_nth_index_of_not_mem List.injOn_insertNth_index_of_not_mem
 -/
 
+/- warning: list.foldr_range_subset_of_range_subset -> List.foldr_range_subset_of_range_subset is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : β -> α -> α} {g : γ -> α -> α}, (HasSubset.Subset.{u1} (Set.{u1} (α -> α)) (Set.hasSubset.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β f) (Set.range.{u1, succ u3} (α -> α) γ g)) -> (forall (a : α), HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldr.{u2, u1} β α f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldr.{u3, u1} γ α g a)))
+but is expected to have type
+  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : β -> α -> α} {g : γ -> α -> α}, (HasSubset.Subset.{u3} (Set.{u3} (α -> α)) (Set.instHasSubsetSet.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β f) (Set.range.{u3, succ u1} (α -> α) γ g)) -> (forall (a : α), HasSubset.Subset.{u3} (Set.{u3} α) (Set.instHasSubsetSet.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldr.{u2, u3} β α f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldr.{u1, u3} γ α g a)))
+Case conversion may be inaccurate. Consider using '#align list.foldr_range_subset_of_range_subset List.foldr_range_subset_of_range_subsetₓ'. -/
 theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α → α}
     (hfg : Set.range f ⊆ Set.range g) (a : α) : Set.range (foldr f a) ⊆ Set.range (foldr g a) :=
   by
@@ -93,6 +99,12 @@ theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α
     exact ⟨c :: m, rfl⟩
 #align list.foldr_range_subset_of_range_subset List.foldr_range_subset_of_range_subset
 
+/- warning: list.foldl_range_subset_of_range_subset -> List.foldl_range_subset_of_range_subset is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : α -> β -> α} {g : α -> γ -> α}, (HasSubset.Subset.{u1} (Set.{u1} (α -> α)) (Set.hasSubset.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u1, succ u3} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), HasSubset.Subset.{u1} (Set.{u1} α) (Set.hasSubset.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldl.{u1, u2} α β f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldl.{u1, u3} α γ g a)))
+but is expected to have type
+  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : α -> β -> α} {g : α -> γ -> α}, (HasSubset.Subset.{u3} (Set.{u3} (α -> α)) (Set.instHasSubsetSet.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u3, succ u1} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), HasSubset.Subset.{u3} (Set.{u3} α) (Set.instHasSubsetSet.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldl.{u3, u2} α β f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldl.{u3, u1} α γ g a)))
+Case conversion may be inaccurate. Consider using '#align list.foldl_range_subset_of_range_subset List.foldl_range_subset_of_range_subsetₓ'. -/
 theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ → α}
     (hfg : (Set.range fun a c => f c a) ⊆ Set.range fun b c => g c b) (a : α) :
     Set.range (foldl f a) ⊆ Set.range (foldl g a) :=
@@ -104,12 +116,24 @@ theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ
   exact foldr_range_subset_of_range_subset hfg a
 #align list.foldl_range_subset_of_range_subset List.foldl_range_subset_of_range_subset
 
+/- warning: list.foldr_range_eq_of_range_eq -> List.foldr_range_eq_of_range_eq is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : β -> α -> α} {g : γ -> α -> α}, (Eq.{succ u1} (Set.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β f) (Set.range.{u1, succ u3} (α -> α) γ g)) -> (forall (a : α), Eq.{succ u1} (Set.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldr.{u2, u1} β α f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldr.{u3, u1} γ α g a)))
+but is expected to have type
+  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : β -> α -> α} {g : γ -> α -> α}, (Eq.{succ u3} (Set.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β f) (Set.range.{u3, succ u1} (α -> α) γ g)) -> (forall (a : α), Eq.{succ u3} (Set.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldr.{u2, u3} β α f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldr.{u1, u3} γ α g a)))
+Case conversion may be inaccurate. Consider using '#align list.foldr_range_eq_of_range_eq List.foldr_range_eq_of_range_eqₓ'. -/
 theorem foldr_range_eq_of_range_eq {f : β → α → α} {g : γ → α → α} (hfg : Set.range f = Set.range g)
     (a : α) : Set.range (foldr f a) = Set.range (foldr g a) :=
   (foldr_range_subset_of_range_subset hfg.le a).antisymm
     (foldr_range_subset_of_range_subset hfg.ge a)
 #align list.foldr_range_eq_of_range_eq List.foldr_range_eq_of_range_eq
 
+/- warning: list.foldl_range_eq_of_range_eq -> List.foldl_range_eq_of_range_eq is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} {γ : Type.{u3}} {f : α -> β -> α} {g : α -> γ -> α}, (Eq.{succ u1} (Set.{u1} (α -> α)) (Set.range.{u1, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u1, succ u3} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), Eq.{succ u1} (Set.{u1} α) (Set.range.{u1, succ u2} α (List.{u2} β) (List.foldl.{u1, u2} α β f a)) (Set.range.{u1, succ u3} α (List.{u3} γ) (List.foldl.{u1, u3} α γ g a)))
+but is expected to have type
+  forall {α : Type.{u3}} {β : Type.{u2}} {γ : Type.{u1}} {f : α -> β -> α} {g : α -> γ -> α}, (Eq.{succ u3} (Set.{u3} (α -> α)) (Set.range.{u3, succ u2} (α -> α) β (fun (a : β) (c : α) => f c a)) (Set.range.{u3, succ u1} (α -> α) γ (fun (b : γ) (c : α) => g c b))) -> (forall (a : α), Eq.{succ u3} (Set.{u3} α) (Set.range.{u3, succ u2} α (List.{u2} β) (List.foldl.{u3, u2} α β f a)) (Set.range.{u3, succ u1} α (List.{u1} γ) (List.foldl.{u3, u1} α γ g a)))
+Case conversion may be inaccurate. Consider using '#align list.foldl_range_eq_of_range_eq List.foldl_range_eq_of_range_eqₓ'. -/
 theorem foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
     (hfg : (Set.range fun a c => f c a) = Set.range fun b c => g c b) (a : α) :
     Set.range (foldl f a) = Set.range (foldl g a) :=

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

chore: remove autoImplicit from more files (#11798)

and reduce its scope in a few other instances. Mostly in CategoryTheory and Data this time; some Combinatorics also.

Co-authored-by: Richard Osborn <richardosborn@mac.com>

3bb1d613

Diff

@@ -14,9 +14,6 @@ import Mathlib.Init.Data.List.Lemmas
 Split out from `Data.List.Basic` to reduce its dependencies.
 -/
 
-set_option autoImplicit true
-
-
 open List
 
 variable {α β γ : Type*}
@@ -90,7 +87,7 @@ theorem foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
 -/
 section MapAccumr
 
-theorem mapAccumr_eq_foldr (f : α → σ → σ × β) : ∀ (as : List α) (s : σ),
+theorem mapAccumr_eq_foldr {σ : Type*} (f : α → σ → σ × β) : ∀ (as : List α) (s : σ),
     mapAccumr f as s = List.foldr (fun a s =>
                                     let r := f a s.1
                                     (r.1, r.2 :: s.2)
@@ -99,7 +96,7 @@ theorem mapAccumr_eq_foldr (f : α → σ → σ × β) : ∀ (as : List α) (s
   | a :: as, s => by
     simp only [mapAccumr, foldr, mapAccumr_eq_foldr f as]
 
-theorem mapAccumr₂_eq_foldr (f : α → β → σ → σ × φ) :
+theorem mapAccumr₂_eq_foldr {σ φ : Type*} (f : α → β → σ → σ × φ) :
     ∀ (as : List α) (bs : List β) (s : σ),
     mapAccumr₂ f as bs s = foldr (fun ab s =>
                               let r := f ab.1 ab.2 s.1

chore: split insertNth lemmas from List.Basic (#11542)

Removes the insertNth section of this long file to its own new file. This section seems to be completely independent of the rest of the file, so this is a fairly easy split to make.

bf26b9c5

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
 -/
 import Mathlib.Data.Set.Image
-import Mathlib.Data.List.Basic
+import Mathlib.Data.List.InsertNth
 import Mathlib.Init.Data.List.Lemmas
 
 #align_import data.list.lemmas from "leanprover-community/mathlib"@"2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4"

chore(Mathlib/Data/List/Basic): minimize imports (#11497)

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>

4bf0be48

Diff

@@ -28,8 +28,8 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
   induction' l with hd tl IH
   · intro n hn m hm _
     simp only [Set.mem_singleton_iff, Set.setOf_eq_eq_singleton,
-      length, nonpos_iff_eq_zero] at hn hm
-    simp [hn, hm]
+      length] at hn hm
+    simp_all [hn, hm]
   · intro n hn m hm h
     simp only [length, Set.mem_setOf_eq] at hn hm
     simp only [mem_cons, not_or] at hx

chore: reduce imports (#9830)

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

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

f4c4ca61

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2021 Yakov Pechersky. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
 -/
-import Mathlib.Data.Set.Function
+import Mathlib.Data.Set.Image
 import Mathlib.Data.List.Basic
 import Mathlib.Init.Data.List.Lemmas

fix: disable autoImplicit globally (#6528)

Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.

The intent of this PR is to make autoImplicit opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true in the few files that rely on it.

That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.

I claim that many of the uses of autoImplicit in these files are accidental; situations such as:

Assuming variables are in scope, but pasting the lemma in the wrong section
Pasting in a lemma from a scratch file without checking to see if the variable names are consistent with the rest of the file
Making a copy-paste error between lemmas and forgetting to add an explicit arguments.

Having set_option autoImplicit false as the default prevents these types of mistake being made in the 90% of files where autoImplicits are not used at all, and causes them to be caught by CI during review.

I think there were various points during the port where we encouraged porters to delete the universes u v lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.

A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18 as the no:dontcare:yes vote ratio.

While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true has been placed locally within a section, rather than at the top of the file.

0c24f831

Diff

@@ -14,6 +14,8 @@ import Mathlib.Init.Data.List.Lemmas
 Split out from `Data.List.Basic` to reduce its dependencies.
 -/
 
+set_option autoImplicit true
+
 
 open List

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -17,7 +17,7 @@ Split out from `Data.List.Basic` to reduce its dependencies.
 
 open List
 
-variable {α β γ : Type _}
+variable {α β γ : Type*}
 
 namespace List

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,16 +2,13 @@
 Copyright (c) 2021 Yakov Pechersky. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
-
-! This file was ported from Lean 3 source module data.list.lemmas
-! leanprover-community/mathlib commit 2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Set.Function
 import Mathlib.Data.List.Basic
 import Mathlib.Init.Data.List.Lemmas
 
+#align_import data.list.lemmas from "leanprover-community/mathlib"@"2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4"
+
 /-! # Some lemmas about lists involving sets
 
 Split out from `Data.List.Basic` to reduce its dependencies.

feat: relate List.mapAccumr to List.foldr (#5390)

Add lemmas that rewrite an application of List.mapAccumr or List.mapAccumr_2 into an application of List.foldr

Co-authored-by: Chris Hughes <chrishughes24@gmail.com>

177ae4e9

Diff

@@ -10,6 +10,7 @@ Authors: Yakov Pechersky, Yury Kudryashov
 -/
 import Mathlib.Data.Set.Function
 import Mathlib.Data.List.Basic
+import Mathlib.Init.Data.List.Lemmas
 
 /-! # Some lemmas about lists involving sets
 
@@ -82,4 +83,36 @@ theorem foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
     (foldl_range_subset_of_range_subset hfg.ge a)
 #align list.foldl_range_eq_of_range_eq List.foldl_range_eq_of_range_eq
 
+
+
+/-!
+  ### MapAccumr and Foldr
+  Some lemmas relation `mapAccumr` and `foldr`
+-/
+section MapAccumr
+
+theorem mapAccumr_eq_foldr (f : α → σ → σ × β) : ∀ (as : List α) (s : σ),
+    mapAccumr f as s = List.foldr (fun a s =>
+                                    let r := f a s.1
+                                    (r.1, r.2 :: s.2)
+                                  ) (s, []) as
+  | [], s => rfl
+  | a :: as, s => by
+    simp only [mapAccumr, foldr, mapAccumr_eq_foldr f as]
+
+theorem mapAccumr₂_eq_foldr (f : α → β → σ → σ × φ) :
+    ∀ (as : List α) (bs : List β) (s : σ),
+    mapAccumr₂ f as bs s = foldr (fun ab s =>
+                              let r := f ab.1 ab.2 s.1
+                              (r.1, r.2 :: s.2)
+                            ) (s, []) (as.zip bs)
+  | [], [], s => rfl
+  | a :: as, [], s => rfl
+  | [], b :: bs, s => rfl
+  | a :: as, b :: bs, s => by
+    simp only [mapAccumr₂, foldr, mapAccumr₂_eq_foldr f as]
+    rfl
+
+end MapAccumr
+
 end List

feat: port Data.Set.List + leanprover-community/mathlib#18647 (#3203)

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

dcbcc203

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
 
 ! This file was ported from Lean 3 source module data.list.lemmas
-! leanprover-community/mathlib commit 975c8c329887c50db6f3556a5f382292ee152ff9
+! leanprover-community/mathlib commit 2ec920d35348cb2d13ac0e1a2ad9df0fdf1a76b4
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -23,30 +23,6 @@ variable {α β γ : Type _}
 
 namespace List
 
-theorem range_map (f : α → β) : Set.range (map f) = { l | ∀ x ∈ l, x ∈ Set.range f } := by
-  refine'
-    Set.Subset.antisymm
-      (Set.range_subset_iff.2 fun l => forall_mem_map_iff.2 fun y _ => Set.mem_range_self _)
-      fun l hl => _
-  induction' l with a l ihl; · exact ⟨[], rfl⟩
-  rcases ihl fun x hx => hl x <| subset_cons _ _ hx with ⟨l, rfl⟩
-  rcases hl a (mem_cons_self _ _) with ⟨a, rfl⟩
-  exact ⟨a :: l, map_cons _ _ _⟩
-#align list.range_map List.range_map
-
-theorem range_map_coe (s : Set α) : Set.range (map ((↑) : s → α)) = { l | ∀ x ∈ l, x ∈ s } := by
-  rw [range_map, Subtype.range_coe]
-#align list.range_map_coe List.range_map_coe
-
-/-- If each element of a list can be lifted to some type, then the whole list can be
-lifted to this type. -/
-instance canLift (c) (p) [CanLift α β c p] :
-    CanLift (List α) (List β) (List.map c) fun l => ∀ x ∈ l, p x where
-  prf l H := by
-    rw [← Set.mem_range, range_map]
-    exact fun a ha => CanLift.prf a (H a ha)
-#align list.can_lift List.canLift
-
 theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
     Set.InjOn (fun k => insertNth k x l) { n | n ≤ l.length } := by
   induction' l with hd tl IH

feat: port range of foldr PR (#1870)

Mathlib3 pair: https://github.com/leanprover-community/mathlib/pull/13328

Co-authored-by: Jon Eugster <eugster.jon@gmail.com>

36809c40

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yakov Pechersky, Yury Kudryashov
 
 ! This file was ported from Lean 3 source module data.list.lemmas
-! leanprover-community/mathlib commit 6d0adfa76594f304b4650d098273d4366edeb61b
+! leanprover-community/mathlib commit 975c8c329887c50db6f3556a5f382292ee152ff9
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -19,7 +19,7 @@ Split out from `Data.List.Basic` to reduce its dependencies.
 
 open List
 
-variable {α β : Type _}
+variable {α β γ : Type _}
 
 namespace List
 
@@ -68,4 +68,42 @@ theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
       · simpa [Nat.succ_le_succ_iff] using hm
 #align list.inj_on_insert_nth_index_of_not_mem List.injOn_insertNth_index_of_not_mem
 
+theorem foldr_range_subset_of_range_subset {f : β → α → α} {g : γ → α → α}
+    (hfg : Set.range f ⊆ Set.range g) (a : α) : Set.range (foldr f a) ⊆ Set.range (foldr g a) := by
+  rintro _ ⟨l, rfl⟩
+  induction' l with b l H
+  · exact ⟨[], rfl⟩
+  · cases' hfg (Set.mem_range_self b) with c hgf
+    cases' H with m hgf'
+    rw [foldr_cons, ← hgf, ← hgf']
+    exact ⟨c :: m, rfl⟩
+#align list.foldr_range_subset_of_range_subset List.foldr_range_subset_of_range_subset
+
+theorem foldl_range_subset_of_range_subset {f : α → β → α} {g : α → γ → α}
+    (hfg : (Set.range fun a c => f c a) ⊆ Set.range fun b c => g c b) (a : α) :
+    Set.range (foldl f a) ⊆ Set.range (foldl g a) := by
+  change (Set.range fun l => _) ⊆ Set.range fun l => _
+  -- Porting note: This was simply `simp_rw [← foldr_reverse]`
+  simp_rw [← foldr_reverse _ (fun z w => g w z), ← foldr_reverse _ (fun z w => f w z)]
+  -- Porting note: This `change` was not necessary in mathlib3
+  change (Set.range (foldr (fun z w => f w z) a ∘ reverse)) ⊆
+    Set.range (foldr (fun z w => g w z) a ∘ reverse)
+  simp_rw [Set.range_comp _ reverse, reverse_involutive.bijective.surjective.range_eq,
+    Set.image_univ]
+  exact foldr_range_subset_of_range_subset hfg a
+#align list.foldl_range_subset_of_range_subset List.foldl_range_subset_of_range_subset
+
+theorem foldr_range_eq_of_range_eq {f : β → α → α} {g : γ → α → α} (hfg : Set.range f = Set.range g)
+    (a : α) : Set.range (foldr f a) = Set.range (foldr g a) :=
+  (foldr_range_subset_of_range_subset hfg.le a).antisymm
+    (foldr_range_subset_of_range_subset hfg.ge a)
+#align list.foldr_range_eq_of_range_eq List.foldr_range_eq_of_range_eq
+
+theorem foldl_range_eq_of_range_eq {f : α → β → α} {g : α → γ → α}
+    (hfg : (Set.range fun a c => f c a) = Set.range fun b c => g c b) (a : α) :
+    Set.range (foldl f a) = Set.range (foldl g a) :=
+  (foldl_range_subset_of_range_subset hfg.le a).antisymm
+    (foldl_range_subset_of_range_subset hfg.ge a)
+#align list.foldl_range_eq_of_range_eq List.foldl_range_eq_of_range_eq
+
 end List

chore: format 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>

d6d859a7

Diff

@@ -23,8 +23,7 @@ variable {α β : Type _}
 
 namespace List
 
-theorem range_map (f : α → β) : Set.range (map f) = { l | ∀ x ∈ l, x ∈ Set.range f } :=
-  by
+theorem range_map (f : α → β) : Set.range (map f) = { l | ∀ x ∈ l, x ∈ Set.range f } := by
   refine'
     Set.Subset.antisymm
       (Set.range_subset_iff.2 fun l => forall_mem_map_iff.2 fun y _ => Set.mem_range_self _)

feat: port some CanLift instances, restore lift tactic usage (#1425)

93812b0f

Diff

@@ -39,16 +39,14 @@ theorem range_map_coe (s : Set α) : Set.range (map ((↑) : s → α)) = { l |
   rw [range_map, Subtype.range_coe]
 #align list.range_map_coe List.range_map_coe
 
---Porting note: Waiting for `lift` tactic
--- /-- If each element of a list can be lifted to some type, then the whole list can be
--- lifted to this type. -/
--- instance canLift (c) (p) [CanLift α β c p] :
---     CanLift (List α) (List β) (List.map c) fun l => ∀ x ∈ l, p x
---     where
---     prf l H := by
---       rw [← Set.mem_range, range_map]
---       exact fun a ha => CanLift.prf a (H a ha)
--- #align list.can_lift List.canLift
+/-- If each element of a list can be lifted to some type, then the whole list can be
+lifted to this type. -/
+instance canLift (c) (p) [CanLift α β c p] :
+    CanLift (List α) (List β) (List.map c) fun l => ∀ x ∈ l, p x where
+  prf l H := by
+    rw [← Set.mem_range, range_map]
+    exact fun a ha => CanLift.prf a (H a ha)
+#align list.can_lift List.canLift
 
 theorem injOn_insertNth_index_of_not_mem (l : List α) (x : α) (hx : x ∉ l) :
     Set.InjOn (fun k => insertNth k x l) { n | n ≤ l.length } := by