combinatorics.hall.basic | 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

8195826f

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

2ed2c631

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -120,7 +120,7 @@ instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset 
     exact ⟨i, i.property, f.property.2 i⟩
   apply Finite.of_injective g
   intro f f' h
-  simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h 
+  simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h
   ext a
   exact h a
 #align hall_matchings_on.finite hallMatchingsOn.finite

2ed2c631

bump to nightly-2024-02-01-06

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

5433bded

Diff

@@ -85,7 +85,14 @@ def hallMatchingsOn.restrict {ι : Type u} {α : Type v} (t : ι → Finset α)
 This is where `finset.all_card_le_bUnion_card_iff_exists_injective'` comes into the argument. -/
 theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t : ι → Finset α)
     (h : ∀ s : Finset ι, s.card ≤ (s.biUnion t).card) (ι' : Finset ι) :
-    Nonempty (hallMatchingsOn t ι') := by classical
+    Nonempty (hallMatchingsOn t ι') := by
+  classical
+  refine' ⟨Classical.indefiniteDescription _ _⟩
+  apply (all_card_le_bUnion_card_iff_exists_injective' fun i : ι' => t i).mp
+  intro s'
+  convert h (s'.image coe) using 1
+  simp only [card_image_of_injective s' Subtype.coe_injective]
+  rw [image_bUnion]
 #align hall_matchings_on.nonempty hallMatchingsOn.nonempty
 -/
 
@@ -102,7 +109,20 @@ def hallMatchingsFunctor {ι : Type u} {α : Type v} (t : ι → Finset α) : (F
 
 #print hallMatchingsOn.finite /-
 instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :
-    Finite (hallMatchingsOn t ι') := by classical
+    Finite (hallMatchingsOn t ι') := by
+  classical
+  rw [hallMatchingsOn]
+  let g : hallMatchingsOn t ι' → ι' → ι'.bUnion t :=
+    by
+    rintro f i
+    refine' ⟨f.val i, _⟩
+    rw [mem_bUnion]
+    exact ⟨i, i.property, f.property.2 i⟩
+  apply Finite.of_injective g
+  intro f f' h
+  simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h 
+  ext a
+  exact h a
 #align hall_matchings_on.finite hallMatchingsOn.finite
 -/
 
@@ -128,11 +148,29 @@ theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α :
     haveI : ∀ ι' : (Finset ι)ᵒᵖ, Nonempty ((hallMatchingsFunctor t).obj ι') := fun ι' =>
       hallMatchingsOn.nonempty t h ι'.unop
     classical
-  -- Apply the compactness argument 
-  -- Interpret the resulting section of the inverse limit 
-  -- Build the matching function from the section 
-  -- Show that it is injective 
-  -- Show that it maps each index to the corresponding finite set
+    haveI : ∀ ι' : (Finset ι)ᵒᵖ, Finite ((hallMatchingsFunctor t).obj ι') :=
+      by
+      intro ι'
+      rw [hallMatchingsFunctor]
+      infer_instance
+    -- Apply the compactness argument
+    obtain ⟨u, hu⟩ := nonempty_sections_of_finite_inverse_system (hallMatchingsFunctor t)
+    -- Interpret the resulting section of the inverse limit
+    refine' ⟨_, _, _⟩
+    ·-- Build the matching function from the section
+      exact fun i =>
+        (u (Opposite.op ({i} : Finset ι))).val ⟨i, by simp only [Opposite.unop_op, mem_singleton]⟩
+    · -- Show that it is injective
+      intro i i'
+      have subi : ({i} : Finset ι) ⊆ {i, i'} := by simp
+      have subi' : ({i'} : Finset ι) ⊆ {i, i'} := by simp
+      have le : ∀ {s t : Finset ι}, s ⊆ t → s ≤ t := fun _ _ h => h
+      rw [← hu (CategoryTheory.homOfLE (le subi)).op, ← hu (CategoryTheory.homOfLE (le subi')).op]
+      let uii' := u (Opposite.op ({i, i'} : Finset ι))
+      exact fun h => subtype.mk_eq_mk.mp (uii'.property.1 h)
+    · -- Show that it maps each index to the corresponding finite set
+      intro i
+      apply (u (Opposite.op ({i} : Finset ι))).property.2
   · -- The reverse direction is a straightforward cardinality argument
     rintro ⟨f, hf₁, hf₂⟩ s
     rw [← Finset.card_image_of_injective s hf₁]

2ed2c631

bump to nightly-2024-01-31-06

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

61100fe9

Diff

@@ -85,14 +85,7 @@ def hallMatchingsOn.restrict {ι : Type u} {α : Type v} (t : ι → Finset α)
 This is where `finset.all_card_le_bUnion_card_iff_exists_injective'` comes into the argument. -/
 theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t : ι → Finset α)
     (h : ∀ s : Finset ι, s.card ≤ (s.biUnion t).card) (ι' : Finset ι) :
-    Nonempty (hallMatchingsOn t ι') := by
-  classical
-  refine' ⟨Classical.indefiniteDescription _ _⟩
-  apply (all_card_le_bUnion_card_iff_exists_injective' fun i : ι' => t i).mp
-  intro s'
-  convert h (s'.image coe) using 1
-  simp only [card_image_of_injective s' Subtype.coe_injective]
-  rw [image_bUnion]
+    Nonempty (hallMatchingsOn t ι') := by classical
 #align hall_matchings_on.nonempty hallMatchingsOn.nonempty
 -/
 
@@ -109,20 +102,7 @@ def hallMatchingsFunctor {ι : Type u} {α : Type v} (t : ι → Finset α) : (F
 
 #print hallMatchingsOn.finite /-
 instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :
-    Finite (hallMatchingsOn t ι') := by
-  classical
-  rw [hallMatchingsOn]
-  let g : hallMatchingsOn t ι' → ι' → ι'.bUnion t :=
-    by
-    rintro f i
-    refine' ⟨f.val i, _⟩
-    rw [mem_bUnion]
-    exact ⟨i, i.property, f.property.2 i⟩
-  apply Finite.of_injective g
-  intro f f' h
-  simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h 
-  ext a
-  exact h a
+    Finite (hallMatchingsOn t ι') := by classical
 #align hall_matchings_on.finite hallMatchingsOn.finite
 -/
 
@@ -148,29 +128,11 @@ theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α :
     haveI : ∀ ι' : (Finset ι)ᵒᵖ, Nonempty ((hallMatchingsFunctor t).obj ι') := fun ι' =>
       hallMatchingsOn.nonempty t h ι'.unop
     classical
-    haveI : ∀ ι' : (Finset ι)ᵒᵖ, Finite ((hallMatchingsFunctor t).obj ι') :=
-      by
-      intro ι'
-      rw [hallMatchingsFunctor]
-      infer_instance
-    -- Apply the compactness argument
-    obtain ⟨u, hu⟩ := nonempty_sections_of_finite_inverse_system (hallMatchingsFunctor t)
-    -- Interpret the resulting section of the inverse limit
-    refine' ⟨_, _, _⟩
-    ·-- Build the matching function from the section
-      exact fun i =>
-        (u (Opposite.op ({i} : Finset ι))).val ⟨i, by simp only [Opposite.unop_op, mem_singleton]⟩
-    · -- Show that it is injective
-      intro i i'
-      have subi : ({i} : Finset ι) ⊆ {i, i'} := by simp
-      have subi' : ({i'} : Finset ι) ⊆ {i, i'} := by simp
-      have le : ∀ {s t : Finset ι}, s ⊆ t → s ≤ t := fun _ _ h => h
-      rw [← hu (CategoryTheory.homOfLE (le subi)).op, ← hu (CategoryTheory.homOfLE (le subi')).op]
-      let uii' := u (Opposite.op ({i, i'} : Finset ι))
-      exact fun h => subtype.mk_eq_mk.mp (uii'.property.1 h)
-    · -- Show that it maps each index to the corresponding finite set
-      intro i
-      apply (u (Opposite.op ({i} : Finset ι))).property.2
+  -- Apply the compactness argument 
+  -- Interpret the resulting section of the inverse limit 
+  -- Build the matching function from the section 
+  -- Show that it is injective 
+  -- Show that it maps each index to the corresponding finite set
   · -- The reverse direction is a straightforward cardinality argument
     rintro ⟨f, hf₁, hf₂⟩ s
     rw [← Finset.card_image_of_injective s hf₁]

2ed2c631

bump to nightly-2023-12-28-06

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

c30f5587

Diff

@@ -174,7 +174,7 @@ theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α :
   · -- The reverse direction is a straightforward cardinality argument
     rintro ⟨f, hf₁, hf₂⟩ s
     rw [← Finset.card_image_of_injective s hf₁]
-    apply Finset.card_le_of_subset
+    apply Finset.card_le_card
     intro
     rw [Finset.mem_image, Finset.mem_biUnion]
     rintro ⟨x, hx, rfl⟩

2ed2c631

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,9 +3,9 @@ Copyright (c) 2021 Alena Gusakov, Bhavik Mehta, Kyle Miller. All rights reserved
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Bhavik Mehta, Kyle Miller
 -/
-import Mathbin.Combinatorics.Hall.Finite
-import Mathbin.CategoryTheory.CofilteredSystem
-import Mathbin.Data.Rel
+import Combinatorics.Hall.Finite
+import CategoryTheory.CofilteredSystem
+import Data.Rel
 
 #align_import combinatorics.hall.basic from "leanprover-community/mathlib"@"2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe"

2ed2c631

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,16 +2,13 @@
 Copyright (c) 2021 Alena Gusakov, Bhavik Mehta, Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Bhavik Mehta, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.hall.basic
-! leanprover-community/mathlib commit 2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.Hall.Finite
 import Mathbin.CategoryTheory.CofilteredSystem
 import Mathbin.Data.Rel
 
+#align_import combinatorics.hall.basic from "leanprover-community/mathlib"@"2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe"
+
 /-!
 # Hall's Marriage Theorem

2ed2c631

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -225,6 +225,7 @@ theorem Fintype.all_card_le_rel_image_card_iff_exists_injective {α : Type u} {
 #align fintype.all_card_le_rel_image_card_iff_exists_injective Fintype.all_card_le_rel_image_card_iff_exists_injective
 -/
 
+#print Fintype.all_card_le_filter_rel_iff_exists_injective /-
 -- TODO: decidable_pred makes Yael sad. When an appropriate decidable_rel-like exists, fix it.
 /-- This is a version of **Hall's Marriage Theorem** in terms of a relation to a finite type.
 There is a transversal of the relation (an injective function `α → β` whose graph is a subrelation
@@ -249,4 +250,5 @@ theorem Fintype.all_card_le_filter_rel_iff_exists_injective {α : Type u} {β :
   simp_rw [h, h']
   apply Finset.all_card_le_biUnion_card_iff_exists_injective
 #align fintype.all_card_le_filter_rel_iff_exists_injective Fintype.all_card_le_filter_rel_iff_exists_injective
+-/

2ed2c631

bump to nightly-2023-06-04-18

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

3fb4268b

Diff

@@ -66,7 +66,7 @@ universe u v
 #print hallMatchingsOn /-
 /-- The set of matchings for `t` when restricted to a `finset` of `ι`. -/
 def hallMatchingsOn {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :=
-  { f : ι' → α | Function.Injective f ∧ ∀ x, f x ∈ t x }
+  {f : ι' → α | Function.Injective f ∧ ∀ x, f x ∈ t x}
 #align hall_matchings_on hallMatchingsOn
 -/
 
@@ -90,12 +90,12 @@ theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t
     (h : ∀ s : Finset ι, s.card ≤ (s.biUnion t).card) (ι' : Finset ι) :
     Nonempty (hallMatchingsOn t ι') := by
   classical
-    refine' ⟨Classical.indefiniteDescription _ _⟩
-    apply (all_card_le_bUnion_card_iff_exists_injective' fun i : ι' => t i).mp
-    intro s'
-    convert h (s'.image coe) using 1
-    simp only [card_image_of_injective s' Subtype.coe_injective]
-    rw [image_bUnion]
+  refine' ⟨Classical.indefiniteDescription _ _⟩
+  apply (all_card_le_bUnion_card_iff_exists_injective' fun i : ι' => t i).mp
+  intro s'
+  convert h (s'.image coe) using 1
+  simp only [card_image_of_injective s' Subtype.coe_injective]
+  rw [image_bUnion]
 #align hall_matchings_on.nonempty hallMatchingsOn.nonempty
 -/
 
@@ -114,18 +114,18 @@ def hallMatchingsFunctor {ι : Type u} {α : Type v} (t : ι → Finset α) : (F
 instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :
     Finite (hallMatchingsOn t ι') := by
   classical
-    rw [hallMatchingsOn]
-    let g : hallMatchingsOn t ι' → ι' → ι'.bUnion t :=
-      by
-      rintro f i
-      refine' ⟨f.val i, _⟩
-      rw [mem_bUnion]
-      exact ⟨i, i.property, f.property.2 i⟩
-    apply Finite.of_injective g
-    intro f f' h
-    simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h 
-    ext a
-    exact h a
+  rw [hallMatchingsOn]
+  let g : hallMatchingsOn t ι' → ι' → ι'.bUnion t :=
+    by
+    rintro f i
+    refine' ⟨f.val i, _⟩
+    rw [mem_bUnion]
+    exact ⟨i, i.property, f.property.2 i⟩
+  apply Finite.of_injective g
+  intro f f' h
+  simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h 
+  ext a
+  exact h a
 #align hall_matchings_on.finite hallMatchingsOn.finite
 -/
 
@@ -151,29 +151,29 @@ theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α :
     haveI : ∀ ι' : (Finset ι)ᵒᵖ, Nonempty ((hallMatchingsFunctor t).obj ι') := fun ι' =>
       hallMatchingsOn.nonempty t h ι'.unop
     classical
-      haveI : ∀ ι' : (Finset ι)ᵒᵖ, Finite ((hallMatchingsFunctor t).obj ι') :=
-        by
-        intro ι'
-        rw [hallMatchingsFunctor]
-        infer_instance
-      -- Apply the compactness argument
-      obtain ⟨u, hu⟩ := nonempty_sections_of_finite_inverse_system (hallMatchingsFunctor t)
-      -- Interpret the resulting section of the inverse limit
-      refine' ⟨_, _, _⟩
-      ·-- Build the matching function from the section
-        exact fun i =>
-          (u (Opposite.op ({i} : Finset ι))).val ⟨i, by simp only [Opposite.unop_op, mem_singleton]⟩
-      · -- Show that it is injective
-        intro i i'
-        have subi : ({i} : Finset ι) ⊆ {i, i'} := by simp
-        have subi' : ({i'} : Finset ι) ⊆ {i, i'} := by simp
-        have le : ∀ {s t : Finset ι}, s ⊆ t → s ≤ t := fun _ _ h => h
-        rw [← hu (CategoryTheory.homOfLE (le subi)).op, ← hu (CategoryTheory.homOfLE (le subi')).op]
-        let uii' := u (Opposite.op ({i, i'} : Finset ι))
-        exact fun h => subtype.mk_eq_mk.mp (uii'.property.1 h)
-      · -- Show that it maps each index to the corresponding finite set
-        intro i
-        apply (u (Opposite.op ({i} : Finset ι))).property.2
+    haveI : ∀ ι' : (Finset ι)ᵒᵖ, Finite ((hallMatchingsFunctor t).obj ι') :=
+      by
+      intro ι'
+      rw [hallMatchingsFunctor]
+      infer_instance
+    -- Apply the compactness argument
+    obtain ⟨u, hu⟩ := nonempty_sections_of_finite_inverse_system (hallMatchingsFunctor t)
+    -- Interpret the resulting section of the inverse limit
+    refine' ⟨_, _, _⟩
+    ·-- Build the matching function from the section
+      exact fun i =>
+        (u (Opposite.op ({i} : Finset ι))).val ⟨i, by simp only [Opposite.unop_op, mem_singleton]⟩
+    · -- Show that it is injective
+      intro i i'
+      have subi : ({i} : Finset ι) ⊆ {i, i'} := by simp
+      have subi' : ({i'} : Finset ι) ⊆ {i, i'} := by simp
+      have le : ∀ {s t : Finset ι}, s ⊆ t → s ≤ t := fun _ _ h => h
+      rw [← hu (CategoryTheory.homOfLE (le subi)).op, ← hu (CategoryTheory.homOfLE (le subi')).op]
+      let uii' := u (Opposite.op ({i, i'} : Finset ι))
+      exact fun h => subtype.mk_eq_mk.mp (uii'.property.1 h)
+    · -- Show that it maps each index to the corresponding finite set
+      intro i
+      apply (u (Opposite.op ({i} : Finset ι))).property.2
   · -- The reverse direction is a straightforward cardinality argument
     rintro ⟨f, hf₁, hf₂⟩ s
     rw [← Finset.card_image_of_injective s hf₁]

2ed2c631

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -123,7 +123,7 @@ instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset 
       exact ⟨i, i.property, f.property.2 i⟩
     apply Finite.of_injective g
     intro f f' h
-    simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h
+    simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h 
     ext a
     exact h a
 #align hall_matchings_on.finite hallMatchingsOn.finite

2ed2c631

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -225,12 +225,6 @@ theorem Fintype.all_card_le_rel_image_card_iff_exists_injective {α : Type u} {
 #align fintype.all_card_le_rel_image_card_iff_exists_injective Fintype.all_card_le_rel_image_card_iff_exists_injective
 -/
 
-/- warning: fintype.all_card_le_filter_rel_iff_exists_injective -> Fintype.all_card_le_filter_rel_iff_exists_injective is a dubious translation:
-lean 3 declaration is
-  forall {α : Type.{u1}} {β : Type.{u2}} [_inst_1 : Fintype.{u2} β] (r : α -> β -> Prop) [_inst_2 : forall (a : α), DecidablePred.{succ u2} β (r a)], Iff (forall (A : Finset.{u1} α), LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α A) (Finset.card.{u2} β (Finset.filter.{u2} β (fun (b : β) => Exists.{succ u1} α (fun (a : α) => Exists.{0} (Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a A) (fun (H : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a A) => r a b))) (fun (a : β) => Finset.decidableDexistsFinset.{u1} α A (fun (a_1 : α) (H : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 A) => r a_1 a) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 A) => _inst_2 a_1 a)) (Finset.univ.{u2} β _inst_1)))) (Exists.{max (succ u1) (succ u2)} (α -> β) (fun (f : α -> β) => And (Function.Injective.{succ u1, succ u2} α β f) (forall (x : α), r x (f x))))
-but is expected to have type
-  forall {α : Type.{u1}} {β : Type.{u2}} [_inst_1 : Fintype.{u2} β] (r : α -> β -> Prop) [_inst_2 : forall (a : α), DecidablePred.{succ u2} β (r a)], Iff (forall (A : Finset.{u1} α), LE.le.{0} Nat instLENat (Finset.card.{u1} α A) (Finset.card.{u2} β (Finset.filter.{u2} β (fun (b : β) => Exists.{succ u1} α (fun (a : α) => And (Membership.mem.{u1, u1} α (Finset.{u1} α) (Finset.instMembershipFinset.{u1} α) a A) (r a b))) (fun (a : β) => Finset.decidableExistsAndFinset.{u1} α A (fun (a_1 : α) => r a_1 a) (fun (a_1 : α) => _inst_2 a_1 a)) (Finset.univ.{u2} β _inst_1)))) (Exists.{max (succ u1) (succ u2)} (α -> β) (fun (f : α -> β) => And (Function.Injective.{succ u1, succ u2} α β f) (forall (x : α), r x (f x))))
-Case conversion may be inaccurate. Consider using '#align fintype.all_card_le_filter_rel_iff_exists_injective Fintype.all_card_le_filter_rel_iff_exists_injectiveₓ'. -/
 -- TODO: decidable_pred makes Yael sad. When an appropriate decidable_rel-like exists, fix it.
 /-- This is a version of **Hall's Marriage Theorem** in terms of a relation to a finite type.
 There is a transversal of the relation (an injective function `α → β` whose graph is a subrelation

2ed2c631

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -190,9 +190,7 @@ finite set is finite. -/
 instance {α : Type u} {β : Type v} [DecidableEq β] (r : α → β → Prop)
     [∀ a : α, Fintype (Rel.image r {a})] (A : Finset α) : Fintype (Rel.image r A) :=
   by
-  have h : Rel.image r A = (A.bUnion fun a => (Rel.image r {a}).toFinset : Set β) :=
-    by
-    ext
+  have h : Rel.image r A = (A.bUnion fun a => (Rel.image r {a}).toFinset : Set β) := by ext;
     simp [Rel.image]
   rw [h]
   apply FinsetCoe.fintype

2ed2c631

bump to nightly-2023-05-18-03

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

b46e9d53

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Bhavik Mehta, Kyle Miller
 
 ! This file was ported from Lean 3 source module combinatorics.hall.basic
-! leanprover-community/mathlib commit 8195826f5c428fc283510bc67303dd4472d78498
+! leanprover-community/mathlib commit 2ed2c6310e6f1c5562bdf6bfbda55ebbf6891abe
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -15,6 +15,9 @@ import Mathbin.Data.Rel
 /-!
 # Hall's Marriage Theorem
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 Given a list of finite subsets $X_1, X_2, \dots, X_n$ of some given set
 $S$, P. Hall in [Hall1935] gave a necessary and sufficient condition for
 there to be a list of distinct elements $x_1, x_2, \dots, x_n$ with

8195826f

bump to nightly-2023-05-16-10

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

7f411d29

Diff

@@ -60,11 +60,14 @@ open Finset
 
 universe u v
 
+#print hallMatchingsOn /-
 /-- The set of matchings for `t` when restricted to a `finset` of `ι`. -/
 def hallMatchingsOn {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :=
   { f : ι' → α | Function.Injective f ∧ ∀ x, f x ∈ t x }
 #align hall_matchings_on hallMatchingsOn
+-/
 
+#print hallMatchingsOn.restrict /-
 /-- Given a matching on a finset, construct the restriction of that matching to a subset. -/
 def hallMatchingsOn.restrict {ι : Type u} {α : Type v} (t : ι → Finset α) {ι' ι'' : Finset ι}
     (h : ι' ⊆ ι'') (f : hallMatchingsOn t ι'') : hallMatchingsOn t ι' :=
@@ -75,7 +78,9 @@ def hallMatchingsOn.restrict {ι : Type u} {α : Type v} (t : ι → Finset α)
   rintro ⟨i, hi⟩ ⟨j, hj⟩ hh
   simpa only [Subtype.mk_eq_mk] using hinj hh
 #align hall_matchings_on.restrict hallMatchingsOn.restrict
+-/
 
+#print hallMatchingsOn.nonempty /-
 /-- When the Hall condition is satisfied, the set of matchings on a finite set is nonempty.
 This is where `finset.all_card_le_bUnion_card_iff_exists_injective'` comes into the argument. -/
 theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t : ι → Finset α)
@@ -89,7 +94,9 @@ theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t
     simp only [card_image_of_injective s' Subtype.coe_injective]
     rw [image_bUnion]
 #align hall_matchings_on.nonempty hallMatchingsOn.nonempty
+-/
 
+#print hallMatchingsFunctor /-
 -- TODO: This takes a long time to elaborate for an unknown reason.
 /-- This is the `hall_matchings_on` sets assembled into a directed system.
 -/
@@ -98,7 +105,9 @@ def hallMatchingsFunctor {ι : Type u} {α : Type v} (t : ι → Finset α) : (F
   obj ι' := hallMatchingsOn t ι'.unop
   map ι' ι'' g f := hallMatchingsOn.restrict t (CategoryTheory.leOfHom g.unop) f
 #align hall_matchings_functor hallMatchingsFunctor
+-/
 
+#print hallMatchingsOn.finite /-
 instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :
     Finite (hallMatchingsOn t ι') := by
   classical
@@ -115,7 +124,9 @@ instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset 
     ext a
     exact h a
 #align hall_matchings_on.finite hallMatchingsOn.finite
+-/
 
+#print Finset.all_card_le_biUnion_card_iff_exists_injective /-
 /-- This is the version of **Hall's Marriage Theorem** in terms of indexed
 families of finite sets `t : ι → finset α`.  It states that there is a
 set of distinct representatives if and only if every union of `k` of the
@@ -169,6 +180,7 @@ theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α :
     rintro ⟨x, hx, rfl⟩
     exact ⟨x, hx, hf₂ x⟩
 #align finset.all_card_le_bUnion_card_iff_exists_injective Finset.all_card_le_biUnion_card_iff_exists_injective
+-/
 
 /-- Given a relation such that the image of every singleton set is finite, then the image of every
 finite set is finite. -/
@@ -182,6 +194,7 @@ instance {α : Type u} {β : Type v} [DecidableEq β] (r : α → β → Prop)
   rw [h]
   apply FinsetCoe.fintype
 
+#print Fintype.all_card_le_rel_image_card_iff_exists_injective /-
 /-- This is a version of **Hall's Marriage Theorem** in terms of a relation
 between types `α` and `β` such that `α` is finite and the image of
 each `x : α` is finite (it suffices for `β` to be finite; see
@@ -209,7 +222,14 @@ theorem Fintype.all_card_le_rel_image_card_iff_exists_injective {α : Type u} {
   simp only [h, h']
   apply Finset.all_card_le_biUnion_card_iff_exists_injective
 #align fintype.all_card_le_rel_image_card_iff_exists_injective Fintype.all_card_le_rel_image_card_iff_exists_injective
+-/
 
+/- warning: fintype.all_card_le_filter_rel_iff_exists_injective -> Fintype.all_card_le_filter_rel_iff_exists_injective is a dubious translation:
+lean 3 declaration is
+  forall {α : Type.{u1}} {β : Type.{u2}} [_inst_1 : Fintype.{u2} β] (r : α -> β -> Prop) [_inst_2 : forall (a : α), DecidablePred.{succ u2} β (r a)], Iff (forall (A : Finset.{u1} α), LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α A) (Finset.card.{u2} β (Finset.filter.{u2} β (fun (b : β) => Exists.{succ u1} α (fun (a : α) => Exists.{0} (Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a A) (fun (H : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a A) => r a b))) (fun (a : β) => Finset.decidableDexistsFinset.{u1} α A (fun (a_1 : α) (H : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 A) => r a_1 a) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 A) => _inst_2 a_1 a)) (Finset.univ.{u2} β _inst_1)))) (Exists.{max (succ u1) (succ u2)} (α -> β) (fun (f : α -> β) => And (Function.Injective.{succ u1, succ u2} α β f) (forall (x : α), r x (f x))))
+but is expected to have type
+  forall {α : Type.{u1}} {β : Type.{u2}} [_inst_1 : Fintype.{u2} β] (r : α -> β -> Prop) [_inst_2 : forall (a : α), DecidablePred.{succ u2} β (r a)], Iff (forall (A : Finset.{u1} α), LE.le.{0} Nat instLENat (Finset.card.{u1} α A) (Finset.card.{u2} β (Finset.filter.{u2} β (fun (b : β) => Exists.{succ u1} α (fun (a : α) => And (Membership.mem.{u1, u1} α (Finset.{u1} α) (Finset.instMembershipFinset.{u1} α) a A) (r a b))) (fun (a : β) => Finset.decidableExistsAndFinset.{u1} α A (fun (a_1 : α) => r a_1 a) (fun (a_1 : α) => _inst_2 a_1 a)) (Finset.univ.{u2} β _inst_1)))) (Exists.{max (succ u1) (succ u2)} (α -> β) (fun (f : α -> β) => And (Function.Injective.{succ u1, succ u2} α β f) (forall (x : α), r x (f x))))
+Case conversion may be inaccurate. Consider using '#align fintype.all_card_le_filter_rel_iff_exists_injective Fintype.all_card_le_filter_rel_iff_exists_injectiveₓ'. -/
 -- TODO: decidable_pred makes Yael sad. When an appropriate decidable_rel-like exists, fix it.
 /-- This is a version of **Hall's Marriage Theorem** in terms of a relation to a finite type.
 There is a transversal of the relation (an injective function `α → β` whose graph is a subrelation

8195826f

bump to nightly-2023-05-14-08

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

d31da313

Diff

@@ -79,7 +79,7 @@ def hallMatchingsOn.restrict {ι : Type u} {α : Type v} (t : ι → Finset α)
 /-- When the Hall condition is satisfied, the set of matchings on a finite set is nonempty.
 This is where `finset.all_card_le_bUnion_card_iff_exists_injective'` comes into the argument. -/
 theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t : ι → Finset α)
-    (h : ∀ s : Finset ι, s.card ≤ (s.bunionᵢ t).card) (ι' : Finset ι) :
+    (h : ∀ s : Finset ι, s.card ≤ (s.biUnion t).card) (ι' : Finset ι) :
     Nonempty (hallMatchingsOn t ι') := by
   classical
     refine' ⟨Classical.indefiniteDescription _ _⟩
@@ -126,9 +126,9 @@ Recall that `s.bUnion t` is the union of all the sets `t i` for `i ∈ s`.
 This theorem is bootstrapped from `finset.all_card_le_bUnion_card_iff_exists_injective'`,
 which has the additional constraint that `ι` is a `fintype`.
 -/
-theorem Finset.all_card_le_bunionᵢ_card_iff_exists_injective {ι : Type u} {α : Type v}
+theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α : Type v}
     [DecidableEq α] (t : ι → Finset α) :
-    (∀ s : Finset ι, s.card ≤ (s.bunionᵢ t).card) ↔
+    (∀ s : Finset ι, s.card ≤ (s.biUnion t).card) ↔
       ∃ f : ι → α, Function.Injective f ∧ ∀ x, f x ∈ t x :=
   by
   constructor
@@ -165,10 +165,10 @@ theorem Finset.all_card_le_bunionᵢ_card_iff_exists_injective {ι : Type u} {α
     rw [← Finset.card_image_of_injective s hf₁]
     apply Finset.card_le_of_subset
     intro
-    rw [Finset.mem_image, Finset.mem_bunionᵢ]
+    rw [Finset.mem_image, Finset.mem_biUnion]
     rintro ⟨x, hx, rfl⟩
     exact ⟨x, hx, hf₂ x⟩
-#align finset.all_card_le_bUnion_card_iff_exists_injective Finset.all_card_le_bunionᵢ_card_iff_exists_injective
+#align finset.all_card_le_bUnion_card_iff_exists_injective Finset.all_card_le_biUnion_card_iff_exists_injective
 
 /-- Given a relation such that the image of every singleton set is finite, then the image of every
 finite set is finite. -/
@@ -198,7 +198,7 @@ theorem Fintype.all_card_le_rel_image_card_iff_exists_injective {α : Type u} {
       ∃ f : α → β, Function.Injective f ∧ ∀ x, r x (f x) :=
   by
   let r' a := (Rel.image r {a}).toFinset
-  have h : ∀ A : Finset α, Fintype.card (Rel.image r A) = (A.bunionᵢ r').card :=
+  have h : ∀ A : Finset α, Fintype.card (Rel.image r A) = (A.biUnion r').card :=
     by
     intro A
     rw [← Set.toFinset_card]
@@ -207,7 +207,7 @@ theorem Fintype.all_card_le_rel_image_card_iff_exists_injective {α : Type u} {
     simp [Rel.image]
   have h' : ∀ (f : α → β) (x), r x (f x) ↔ f x ∈ r' x := by simp [Rel.image]
   simp only [h, h']
-  apply Finset.all_card_le_bunionᵢ_card_iff_exists_injective
+  apply Finset.all_card_le_biUnion_card_iff_exists_injective
 #align fintype.all_card_le_rel_image_card_iff_exists_injective Fintype.all_card_le_rel_image_card_iff_exists_injective
 
 -- TODO: decidable_pred makes Yael sad. When an appropriate decidable_rel-like exists, fix it.
@@ -225,13 +225,13 @@ theorem Fintype.all_card_le_filter_rel_iff_exists_injective {α : Type u} {β :
   by
   haveI := Classical.decEq β
   let r' a := univ.filter fun b => r a b
-  have h : ∀ A : Finset α, (univ.filter fun b : β => ∃ a ∈ A, r a b) = A.bunionᵢ r' :=
+  have h : ∀ A : Finset α, (univ.filter fun b : β => ∃ a ∈ A, r a b) = A.biUnion r' :=
     by
     intro A
     ext b
     simp
   have h' : ∀ (f : α → β) (x), r x (f x) ↔ f x ∈ r' x := by simp
   simp_rw [h, h']
-  apply Finset.all_card_le_bunionᵢ_card_iff_exists_injective
+  apply Finset.all_card_le_biUnion_card_iff_exists_injective
 #align fintype.all_card_le_filter_rel_iff_exists_injective Fintype.all_card_le_filter_rel_iff_exists_injective

8195826f

bump to nightly-2023-03-02-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c

db7421c3

Diff

@@ -4,12 +4,12 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Bhavik Mehta, Kyle Miller
 
 ! This file was ported from Lean 3 source module combinatorics.hall.basic
-! leanprover-community/mathlib commit 2987594a0b88ccb096b11b0f4b17923a9e11df02
+! leanprover-community/mathlib commit 8195826f5c428fc283510bc67303dd4472d78498
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.Hall.Finite
-import Mathbin.Topology.Category.Top.Limits
+import Mathbin.CategoryTheory.CofilteredSystem
 import Mathbin.Data.Rel
 
 /-!
@@ -32,7 +32,7 @@ The theorem can be generalized to remove the constraint that `ι` be a `fintype`
 As observed in [Halpern1966], one may use the constrained version of the theorem
 in a compactness argument to remove this constraint.
 The formulation of compactness we use is that inverse limits of nonempty finite sets
-are nonempty (`nonempty_sections_of_fintype_inverse_system`), which uses the
+are nonempty (`nonempty_sections_of_finite_inverse_system`), which uses the
 Tychonoff theorem.
 The core of this module is constructing the inverse system: for every finite subset `ι'` of
 `ι`, we can consider the matchings on the restriction of the indexed family `t` to `ι'`.
@@ -99,8 +99,8 @@ def hallMatchingsFunctor {ι : Type u} {α : Type v} (t : ι → Finset α) : (F
   map ι' ι'' g f := hallMatchingsOn.restrict t (CategoryTheory.leOfHom g.unop) f
 #align hall_matchings_functor hallMatchingsFunctor
 
-noncomputable instance hallMatchingsOn.fintype {ι : Type u} {α : Type v} (t : ι → Finset α)
-    (ι' : Finset ι) : Fintype (hallMatchingsOn t ι') := by
+instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset α) (ι' : Finset ι) :
+    Finite (hallMatchingsOn t ι') := by
   classical
     rw [hallMatchingsOn]
     let g : hallMatchingsOn t ι' → ι' → ι'.bUnion t :=
@@ -109,12 +109,12 @@ noncomputable instance hallMatchingsOn.fintype {ι : Type u} {α : Type v} (t :
       refine' ⟨f.val i, _⟩
       rw [mem_bUnion]
       exact ⟨i, i.property, f.property.2 i⟩
-    apply Fintype.ofInjective g
+    apply Finite.of_injective g
     intro f f' h
     simp only [g, Function.funext_iff, Subtype.val_eq_coe] at h
     ext a
     exact h a
-#align hall_matchings_on.fintype hallMatchingsOn.fintype
+#align hall_matchings_on.finite hallMatchingsOn.finite
 
 /-- This is the version of **Hall's Marriage Theorem** in terms of indexed
 families of finite sets `t : ι → finset α`.  It states that there is a
@@ -137,13 +137,13 @@ theorem Finset.all_card_le_bunionᵢ_card_iff_exists_injective {ι : Type u} {α
     haveI : ∀ ι' : (Finset ι)ᵒᵖ, Nonempty ((hallMatchingsFunctor t).obj ι') := fun ι' =>
       hallMatchingsOn.nonempty t h ι'.unop
     classical
-      haveI : ∀ ι' : (Finset ι)ᵒᵖ, Fintype ((hallMatchingsFunctor t).obj ι') :=
+      haveI : ∀ ι' : (Finset ι)ᵒᵖ, Finite ((hallMatchingsFunctor t).obj ι') :=
         by
         intro ι'
         rw [hallMatchingsFunctor]
         infer_instance
       -- Apply the compactness argument
-      obtain ⟨u, hu⟩ := nonempty_sections_of_fintype_inverse_system (hallMatchingsFunctor t)
+      obtain ⟨u, hu⟩ := nonempty_sections_of_finite_inverse_system (hallMatchingsFunctor t)
       -- Interpret the resulting section of the inverse limit
       refine' ⟨_, _, _⟩
       ·-- Build the matching function from the section

2987594a

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

8195826f

chore: adapt to multiple goal linter 3 (#12372)

A PR analogous to #12338 and #12361: reformatting proofs following the multiple goals linter of #12339.

d29b3780

Diff

@@ -82,8 +82,8 @@ theorem hallMatchingsOn.nonempty {ι : Type u} {α : Type v} [DecidableEq α] (t
     apply (all_card_le_biUnion_card_iff_existsInjective' fun i : ι' => t i).mp
     intro s'
     convert h (s'.image (↑)) using 1
-    simp only [card_image_of_injective s' Subtype.coe_injective]
-    rw [image_biUnion]
+    · simp only [card_image_of_injective s' Subtype.coe_injective]
+    · rw [image_biUnion]
 #align hall_matchings_on.nonempty hallMatchingsOn.nonempty
 
 /-- This is the `hallMatchingsOn` sets assembled into a directed system.

8195826f

chore: prepare Lean version bump with explicit simp (#10999)

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

38bce757

Diff

@@ -107,7 +107,7 @@ instance hallMatchingsOn.finite {ι : Type u} {α : Type v} (t : ι → Finset 
     intro f f' h
     ext a
     rw [Function.funext_iff] at h
-    simpa using h a
+    simpa [g] using h a
 #align hall_matchings_on.finite hallMatchingsOn.finite
 
 /-- This is the version of **Hall's Marriage Theorem** in terms of indexed
@@ -219,8 +219,8 @@ theorem Fintype.all_card_le_filter_rel_iff_exists_injective {α : Type u} {β :
   have h : ∀ A : Finset α, (univ.filter fun b : β => ∃ a ∈ A, r a b) = A.biUnion r' := by
     intro A
     ext b
-    simp
-  have h' : ∀ (f : α → β) (x), r x (f x) ↔ f x ∈ r' x := by simp
+    simp [r']
+  have h' : ∀ (f : α → β) (x), r x (f x) ↔ f x ∈ r' x := by simp [r']
   simp_rw [h, h']
   apply Finset.all_card_le_biUnion_card_iff_exists_injective
 #align fintype.all_card_le_filter_rel_iff_exists_injective Fintype.all_card_le_filter_rel_iff_exists_injective

8195826f

chore: Improve Finset lemma names (#8894)

Change a few lemma names that have historically bothered me.

Finset.card_le_of_subset → Finset.card_le_card
Multiset.card_le_of_le → Multiset.card_le_card
Multiset.card_lt_of_lt → Multiset.card_lt_card
Set.ncard_le_of_subset → Set.ncard_le_ncard
Finset.image_filter → Finset.filter_image
CompleteLattice.finset_sup_compact_of_compact → CompleteLattice.isCompactElement_finset_sup

7d3d6e43

Diff

@@ -156,7 +156,7 @@ theorem Finset.all_card_le_biUnion_card_iff_exists_injective {ι : Type u} {α :
   · -- The reverse direction is a straightforward cardinality argument
     rintro ⟨f, hf₁, hf₂⟩ s
     rw [← Finset.card_image_of_injective s hf₁]
-    apply Finset.card_le_of_subset
+    apply Finset.card_le_card
     intro
     rw [Finset.mem_image, Finset.mem_biUnion]
     rintro ⟨x, hx, rfl⟩

8195826f

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 Alena Gusakov, Bhavik Mehta, Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Bhavik Mehta, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.hall.basic
-! leanprover-community/mathlib commit 8195826f5c428fc283510bc67303dd4472d78498
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.Hall.Finite
 import Mathlib.CategoryTheory.CofilteredSystem
 import Mathlib.Data.Rel
 
+#align_import combinatorics.hall.basic from "leanprover-community/mathlib"@"8195826f5c428fc283510bc67303dd4472d78498"
+
 /-!
 # Hall's Marriage Theorem

8195826f

chore: scope notations from category theory. (#5685)

Make sure in particular one can import Mathlib.Tactic for teaching without getting category theory notations in scope. Note that only two files needed an extra open.

5c108f1c

Diff

@@ -56,7 +56,7 @@ Hall's Marriage Theorem, indexed families
 -/
 
 
-open Finset
+open Finset CategoryTheory
 
 universe u v

8195826f

feat: port Combinatorics.Hall.Basic (#3999)

6c44e6ae

`combinatorics.hall.basic` ⟷ `Mathlib.Combinatorics.Hall.Basic`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 8 + 401

combinatorics.hall.basic ⟷ Mathlib.Combinatorics.Hall.Basic

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 8 + 401

`combinatorics.hall.basic` ⟷ `Mathlib.Combinatorics.Hall.Basic`