combinatorics.set_family.compression.down

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

9003f287

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

cc70d914

bump to nightly-2024-04-25-08

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

ad7a2212

Diff

@@ -189,7 +189,7 @@ scoped[FinsetFamily] notation "𝓓 " => Down.compression
 original, or it's not in the original but it's the compression of something in the original. -/
 theorem mem_compression : s ∈ 𝓓 a 𝒜 ↔ s ∈ 𝒜 ∧ s.eraseₓ a ∈ 𝒜 ∨ s ∉ 𝒜 ∧ insert a s ∈ 𝒜 :=
   by
-  simp_rw [compression, mem_disj_union, mem_filter, mem_image, and_comm' (s ∉ 𝒜)]
+  simp_rw [compression, mem_disj_union, mem_filter, mem_image, and_comm (s ∉ 𝒜)]
   refine'
     or_congr_right
       (and_congr_left fun hs =>

cc70d914

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -222,7 +222,7 @@ theorem erase_mem_compression_of_mem_compression : s ∈ 𝓓 a 𝒜 → s.erase
 theorem mem_compression_of_insert_mem_compression (h : insert a s ∈ 𝓓 a 𝒜) : s ∈ 𝓓 a 𝒜 :=
   by
   by_cases ha : a ∈ s
-  · rwa [insert_eq_of_mem ha] at h 
+  · rwa [insert_eq_of_mem ha] at h
   · rw [← erase_insert ha]
     exact erase_mem_compression_of_mem_compression h
 #align down.mem_compression_of_insert_mem_compression Down.mem_compression_of_insert_mem_compression
@@ -250,7 +250,7 @@ theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).ca
     card_image_of_inj_on ((erase_inj_on' _).mono fun s hs => _), ← card_disjoint_union,
     filter_union_filter_neg_eq]
   · exact disjoint_filter_filter_neg _ _ _
-  rw [mem_coe, mem_filter] at hs 
+  rw [mem_coe, mem_filter] at hs
   exact not_imp_comm.1 erase_eq_of_not_mem (ne_of_mem_of_not_mem hs.1 hs.2).symm
 #align down.card_compression Down.card_compression
 -/

cc70d914

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) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
 -/
-import Mathbin.Data.Finset.Card
+import Data.Finset.Card
 
 #align_import combinatorics.set_family.compression.down from "leanprover-community/mathlib"@"cc70d9141824ea8982d1562ce009952f2c3ece30"

cc70d914

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) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module combinatorics.set_family.compression.down
-! leanprover-community/mathlib commit cc70d9141824ea8982d1562ce009952f2c3ece30
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Finset.Card
 
+#align_import combinatorics.set_family.compression.down from "leanprover-community/mathlib"@"cc70d9141824ea8982d1562ce009952f2c3ece30"
+
 /-!
 # Down-compressions

cc70d914

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -185,7 +185,6 @@ def compression (a : α) (𝒜 : Finset (Finset α)) : Finset (Finset α) :=
 #align down.compression Down.compression
 -/
 
--- mathport name: down.compression
 scoped[FinsetFamily] notation "𝓓 " => Down.compression
 
 #print Down.mem_compression /-

cc70d914

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -226,7 +226,7 @@ theorem erase_mem_compression_of_mem_compression : s ∈ 𝓓 a 𝒜 → s.erase
 theorem mem_compression_of_insert_mem_compression (h : insert a s ∈ 𝓓 a 𝒜) : s ∈ 𝓓 a 𝒜 :=
   by
   by_cases ha : a ∈ s
-  · rwa [insert_eq_of_mem ha] at h
+  · rwa [insert_eq_of_mem ha] at h 
   · rw [← erase_insert ha]
     exact erase_mem_compression_of_mem_compression h
 #align down.mem_compression_of_insert_mem_compression Down.mem_compression_of_insert_mem_compression
@@ -254,7 +254,7 @@ theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).ca
     card_image_of_inj_on ((erase_inj_on' _).mono fun s hs => _), ← card_disjoint_union,
     filter_union_filter_neg_eq]
   · exact disjoint_filter_filter_neg _ _ _
-  rw [mem_coe, mem_filter] at hs
+  rw [mem_coe, mem_filter] at hs 
   exact not_imp_comm.1 erase_eq_of_not_mem (ne_of_mem_of_not_mem hs.1 hs.2).symm
 #align down.card_compression Down.card_compression
 -/

cc70d914

bump to nightly-2023-05-28-04

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

6797a637

Diff

@@ -142,39 +142,29 @@ theorem memberSubfamily_union_nonMemberSubfamily (a : α) (𝒜 : Finset (Finset
 
 #print Finset.memberSubfamily_memberSubfamily /-
 @[simp]
-theorem memberSubfamily_memberSubfamily : (𝒜.memberSubfamily a).memberSubfamily a = ∅ :=
-  by
-  ext
+theorem memberSubfamily_memberSubfamily : (𝒜.memberSubfamily a).memberSubfamily a = ∅ := by ext;
   simp
 #align finset.member_subfamily_member_subfamily Finset.memberSubfamily_memberSubfamily
 -/
 
 #print Finset.memberSubfamily_nonMemberSubfamily /-
 @[simp]
-theorem memberSubfamily_nonMemberSubfamily : (𝒜.nonMemberSubfamily a).memberSubfamily a = ∅ :=
-  by
-  ext
-  simp
+theorem memberSubfamily_nonMemberSubfamily : (𝒜.nonMemberSubfamily a).memberSubfamily a = ∅ := by
+  ext; simp
 #align finset.member_subfamily_non_member_subfamily Finset.memberSubfamily_nonMemberSubfamily
 -/
 
 #print Finset.nonMemberSubfamily_memberSubfamily /-
 @[simp]
 theorem nonMemberSubfamily_memberSubfamily :
-    (𝒜.memberSubfamily a).nonMemberSubfamily a = 𝒜.memberSubfamily a :=
-  by
-  ext
-  simp
+    (𝒜.memberSubfamily a).nonMemberSubfamily a = 𝒜.memberSubfamily a := by ext; simp
 #align finset.non_member_subfamily_member_subfamily Finset.nonMemberSubfamily_memberSubfamily
 -/
 
 #print Finset.nonMemberSubfamily_nonMemberSubfamily /-
 @[simp]
 theorem nonMemberSubfamily_nonMemberSubfamily :
-    (𝒜.nonMemberSubfamily a).nonMemberSubfamily a = 𝒜.nonMemberSubfamily a :=
-  by
-  ext
-  simp
+    (𝒜.nonMemberSubfamily a).nonMemberSubfamily a = 𝒜.nonMemberSubfamily a := by ext; simp
 #align finset.non_member_subfamily_non_member_subfamily Finset.nonMemberSubfamily_nonMemberSubfamily
 -/

cc70d914

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

9003f287

chore: remove mathport name: <expression> lines (#11928)

Quoting [@digama0](https://github.com/digama0):

These were actually never meant to go in the file, they are basically debugging information and only useful on significantly broken mathport files. You can safely remove all of them.

11431c65

Diff

@@ -231,7 +231,6 @@ def compression (a : α) (𝒜 : Finset (Finset α)) : Finset (Finset α) :=
       exact this (mem_filter.1 h₁).1
 #align down.compression Down.compression
 
--- mathport name: down.compression
 @[inherit_doc]
 scoped[FinsetFamily] notation "𝓓 " => Down.compression
 -- Porting note: had to open this

9003f287

feat: (s ∩ t).card = s.card + t.card - (s ∪ t).card (#10224)

once coerced to an AddGroupWithOne. Also unify Finset.card_disjoint_union and Finset.card_union_eq

From LeanAPAP

80bf34f1

Diff

@@ -283,7 +283,7 @@ theorem compression_idem (a : α) (𝒜 : Finset (Finset α)) : 𝓓 a (𝓓 a 
 @[simp]
 theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).card = 𝒜.card := by
   rw [compression, card_disjUnion, filter_image,
-    card_image_of_injOn ((erase_injOn' _).mono fun s hs => _), ← card_disjoint_union]
+    card_image_of_injOn ((erase_injOn' _).mono fun s hs => _), ← card_union_of_disjoint]
   · conv_rhs => rw [← filter_union_filter_neg_eq (fun s => (erase s a ∈ 𝒜)) 𝒜]
   · exact disjoint_filter_filter_neg 𝒜 𝒜 (fun s => (erase s a ∈ 𝒜))
   intro s hs

9003f287

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

@@ -282,7 +282,7 @@ theorem compression_idem (a : α) (𝒜 : Finset (Finset α)) : 𝓓 a (𝓓 a 
 /-- Down-compressing a family doesn't change its size. -/
 @[simp]
 theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).card = 𝒜.card := by
-  rw [compression, card_disjUnion, image_filter,
+  rw [compression, card_disjUnion, filter_image,
     card_image_of_injOn ((erase_injOn' _).mono fun s hs => _), ← card_disjoint_union]
   · conv_rhs => rw [← filter_union_filter_neg_eq (fun s => (erase s a ∈ 𝒜)) 𝒜]
   · exact disjoint_filter_filter_neg 𝒜 𝒜 (fun s => (erase s a ∈ 𝒜))

9003f287

chore: space after ← (#8178)

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

5fb9beab

Diff

@@ -142,7 +142,7 @@ lemma memberSubfamily_image_insert (h𝒜 : ∀ s ∈ 𝒜, a ∉ s) :
   simp only [mem_memberSubfamily, mem_image]
   refine ⟨?_, fun hs ↦ ⟨⟨s, hs, rfl⟩, h𝒜 _ hs⟩⟩
   rintro ⟨⟨t, ht, hts⟩, hs⟩
-  rwa [←insert_erase_invOn.2.injOn (h𝒜 _ ht) hs hts]
+  rwa [← insert_erase_invOn.2.injOn (h𝒜 _ ht) hs hts]
 
 @[simp] lemma nonMemberSubfamily_image_insert : (𝒜.image <| insert a).nonMemberSubfamily a = ∅ := by
   simp [eq_empty_iff_forall_not_mem]
@@ -182,7 +182,7 @@ lemma memberFamily_induction_on {p : Finset (Finset α) → Prop}
   clear_value u
   induction' u using Finset.induction with a u _ ih generalizing 𝒜
   · simp_rw [subset_empty] at hu
-    rw [←subset_singleton_iff', subset_singleton_iff] at hu
+    rw [← subset_singleton_iff', subset_singleton_iff] at hu
     obtain rfl | rfl := hu <;> assumption
   refine subfamily a (ih _ ?_) (ih _ ?_)
   · simp only [mem_nonMemberSubfamily, and_imp]
@@ -211,7 +211,7 @@ protected lemma family_induction_on {p : Finset (Finset α) → Prop}
     (subfamily : ∀ (a : α) ⦃𝒜 : Finset (Finset α)⦄,
       p (𝒜.filter (a ∉ ·)) → p (𝒜.filter (a ∈ ·)) → p 𝒜) : p 𝒜 := by
   refine memberFamily_induction_on 𝒜 empty singleton_empty fun a 𝒜 h𝒜₀ h𝒜₁ ↦ subfamily a h𝒜₀ ?_
-  rw [←image_insert_memberSubfamily]
+  rw [← image_insert_memberSubfamily]
   exact image_insert _ (by simp) h𝒜₁
 
 end Finset

9003f287

feat: Finset family induction (#7522)

Provide an induction principle for finset families: One can increase the support of a finset family one by one.

c98e6b7f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
 -/
-import Mathlib.Data.Finset.Card
+import Mathlib.Data.Finset.Lattice
 
 #align_import combinatorics.set_family.compression.down from "leanprover-community/mathlib"@"9003f28797c0664a49e4179487267c494477d853"
 
@@ -136,6 +136,84 @@ theorem nonMemberSubfamily_nonMemberSubfamily :
   simp
 #align finset.non_member_subfamily_non_member_subfamily Finset.nonMemberSubfamily_nonMemberSubfamily
 
+lemma memberSubfamily_image_insert (h𝒜 : ∀ s ∈ 𝒜, a ∉ s) :
+    (𝒜.image <| insert a).memberSubfamily a = 𝒜 := by
+  ext s
+  simp only [mem_memberSubfamily, mem_image]
+  refine ⟨?_, fun hs ↦ ⟨⟨s, hs, rfl⟩, h𝒜 _ hs⟩⟩
+  rintro ⟨⟨t, ht, hts⟩, hs⟩
+  rwa [←insert_erase_invOn.2.injOn (h𝒜 _ ht) hs hts]
+
+@[simp] lemma nonMemberSubfamily_image_insert : (𝒜.image <| insert a).nonMemberSubfamily a = ∅ := by
+  simp [eq_empty_iff_forall_not_mem]
+
+@[simp] lemma memberSubfamily_image_erase : (𝒜.image (erase · a)).memberSubfamily a = ∅ := by
+  simp [eq_empty_iff_forall_not_mem,
+    (ne_of_mem_of_not_mem' (mem_insert_self _ _) (not_mem_erase _ _)).symm]
+
+lemma image_insert_memberSubfamily (𝒜 : Finset (Finset α)) (a : α) :
+    (𝒜.memberSubfamily a).image (insert a) = 𝒜.filter (a ∈ ·) := by
+  ext s
+  simp only [mem_memberSubfamily, mem_image, mem_filter]
+  refine ⟨?_, fun ⟨hs, ha⟩ ↦ ⟨erase s a, ⟨?_, not_mem_erase _ _⟩, insert_erase ha⟩⟩
+  · rintro ⟨s, ⟨hs, -⟩, rfl⟩
+    exact ⟨hs, mem_insert_self _ _⟩
+  · rwa [insert_erase ha]
+
+/-- Induction principle for finset families. To prove a statement for every finset family,
+it suffices to prove it for
+* the empty finset family.
+* the finset family which only contains the empty finset.
+* `ℬ ∪ {s ∪ {a} | s ∈ 𝒞}` assuming the property for `ℬ` and `𝒞`, where `a` is an element of the
+  ground type and `𝒜` and `ℬ` are families of finsets not containing `a`.
+  Note that instead of giving `ℬ` and `𝒞`, the `subfamily` case gives you
+  `𝒜 = ℬ ∪ {s ∪ {a} | s ∈ 𝒞}`, so that `ℬ = 𝒜.nonMemberSubfamily` and `𝒞 = 𝒜.memberSubfamily`.
+
+This is a way of formalising induction on `n` where `𝒜` is a finset family on `n` elements.
+
+See also `Finset.family_induction_on.`-/
+@[elab_as_elim]
+lemma memberFamily_induction_on {p : Finset (Finset α) → Prop}
+    (𝒜 : Finset (Finset α)) (empty : p ∅) (singleton_empty : p {∅})
+    (subfamily : ∀ (a : α) ⦃𝒜 : Finset (Finset α)⦄,
+      p (𝒜.nonMemberSubfamily a) → p (𝒜.memberSubfamily a) → p 𝒜) : p 𝒜 := by
+  set u := 𝒜.sup id
+  have hu : ∀ s ∈ 𝒜, s ⊆ u := fun s ↦ le_sup (f := id)
+  clear_value u
+  induction' u using Finset.induction with a u _ ih generalizing 𝒜
+  · simp_rw [subset_empty] at hu
+    rw [←subset_singleton_iff', subset_singleton_iff] at hu
+    obtain rfl | rfl := hu <;> assumption
+  refine subfamily a (ih _ ?_) (ih _ ?_)
+  · simp only [mem_nonMemberSubfamily, and_imp]
+    exact fun s hs has ↦ (subset_insert_iff_of_not_mem has).1 <| hu _ hs
+  · simp only [mem_memberSubfamily, and_imp]
+    exact fun s hs ha ↦ (insert_subset_insert_iff ha).1 <| hu _ hs
+
+/-- Induction principle for finset families. To prove a statement for every finset family,
+it suffices to prove it for
+* the empty finset family.
+* the finset family which only contains the empty finset.
+* `{s ∪ {a} | s ∈ 𝒜}` assuming the property for `𝒜` a family of finsets not containing `a`.
+* `ℬ ∪ 𝒞` assuming the property for `ℬ` and `𝒞`, where `a` is an element of the ground type and
+  `ℬ`is a family of finsets not containing `a` and `𝒞` a family of finsets containing `a`.
+  Note that instead of giving `ℬ` and `𝒞`, the `subfamily` case gives you `𝒜 = ℬ ∪ 𝒞`, so that
+  `ℬ = 𝒜.filter (a ∉ ·)` and `𝒞 = 𝒜.filter (a ∈ ·)`.
+
+This is a way of formalising induction on `n` where `𝒜` is a finset family on `n` elements.
+
+See also `Finset.memberFamily_induction_on.`-/
+@[elab_as_elim]
+protected lemma family_induction_on {p : Finset (Finset α) → Prop}
+    (𝒜 : Finset (Finset α)) (empty : p ∅) (singleton_empty : p {∅})
+    (image_insert : ∀ (a : α) ⦃𝒜 : Finset (Finset α)⦄,
+      (∀ s ∈ 𝒜, a ∉ s) → p 𝒜 → p (𝒜.image <| insert a))
+    (subfamily : ∀ (a : α) ⦃𝒜 : Finset (Finset α)⦄,
+      p (𝒜.filter (a ∉ ·)) → p (𝒜.filter (a ∈ ·)) → p 𝒜) : p 𝒜 := by
+  refine memberFamily_induction_on 𝒜 empty singleton_empty fun a 𝒜 h𝒜₀ h𝒜₁ ↦ subfamily a h𝒜₀ ?_
+  rw [←image_insert_memberSubfamily]
+  exact image_insert _ (by simp) h𝒜₁
+
 end Finset
 
 open Finset

9003f287

feat: Miscellaneous Finset lemmas (#7379)

3ac819de

Diff

@@ -209,7 +209,7 @@ theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).ca
   · conv_rhs => rw [← filter_union_filter_neg_eq (fun s => (erase s a ∈ 𝒜)) 𝒜]
   · exact disjoint_filter_filter_neg 𝒜 𝒜 (fun s => (erase s a ∈ 𝒜))
   intro s hs
-  rw [mem_coe, mem_filter, Function.comp_apply] at hs
+  rw [mem_coe, mem_filter] at hs
   exact not_imp_comm.1 erase_eq_of_not_mem (ne_of_mem_of_not_mem hs.1 hs.2).symm
 #align down.card_compression Down.card_compression

9003f287

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

@@ -37,7 +37,7 @@ compression, down-compression
 -/
 
 
-variable {α : Type _} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
+variable {α : Type*} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
 
 namespace Finset

9003f287

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) 2022 Yaël Dillies. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module combinatorics.set_family.compression.down
-! leanprover-community/mathlib commit 9003f28797c0664a49e4179487267c494477d853
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Finset.Card
 
+#align_import combinatorics.set_family.compression.down from "leanprover-community/mathlib"@"9003f28797c0664a49e4179487267c494477d853"
+
 /-!
 # Down-compressions

9003f287

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: Yaël Dillies
 ! if you have ported upstream changes.
 -/
 import Mathlib.Data.Finset.Card
-import Mathlib.Tactic.ScopedNS
 
 /-!
 # Down-compressions

9003f287

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -62,8 +62,7 @@ theorem mem_nonMemberSubfamily : s ∈ 𝒜.nonMemberSubfamily a ↔ s ∈ 𝒜
 #align finset.mem_non_member_subfamily Finset.mem_nonMemberSubfamily
 
 @[simp]
-theorem mem_memberSubfamily : s ∈ 𝒜.memberSubfamily a ↔ insert a s ∈ 𝒜 ∧ a ∉ s :=
-  by
+theorem mem_memberSubfamily : s ∈ 𝒜.memberSubfamily a ↔ insert a s ∈ 𝒜 ∧ a ∉ s := by
   simp_rw [memberSubfamily, mem_image, mem_filter]
   refine' ⟨_, fun h => ⟨insert a s, ⟨h.1, by simp⟩, erase_insert h.2⟩⟩
   rintro ⟨s, ⟨hs1, hs2⟩, rfl⟩
@@ -77,8 +76,7 @@ theorem nonMemberSubfamily_inter (a : α) (𝒜 ℬ : Finset (Finset α)) :
 #align finset.non_member_subfamily_inter Finset.nonMemberSubfamily_inter
 
 theorem memberSubfamily_inter (a : α) (𝒜 ℬ : Finset (Finset α)) :
-    (𝒜 ∩ ℬ).memberSubfamily a = 𝒜.memberSubfamily a ∩ ℬ.memberSubfamily a :=
-  by
+    (𝒜 ∩ ℬ).memberSubfamily a = 𝒜.memberSubfamily a ∩ ℬ.memberSubfamily a := by
   unfold memberSubfamily
   rw [filter_inter_distrib, image_inter_of_injOn _ _ ((erase_injOn' _).mono _)]
   simp
@@ -95,8 +93,7 @@ theorem memberSubfamily_union (a : α) (𝒜 ℬ : Finset (Finset α)) :
 #align finset.member_subfamily_union Finset.memberSubfamily_union
 
 theorem card_memberSubfamily_add_card_nonMemberSubfamily (a : α) (𝒜 : Finset (Finset α)) :
-    (𝒜.memberSubfamily a).card + (𝒜.nonMemberSubfamily a).card = 𝒜.card :=
-  by
+    (𝒜.memberSubfamily a).card + (𝒜.nonMemberSubfamily a).card = 𝒜.card := by
   rw [memberSubfamily, nonMemberSubfamily, card_image_of_injOn]
   · conv_rhs => rw [← filter_card_add_filter_neg_card_eq_card (fun s => (a ∈ s))]
   · apply (erase_injOn' _).mono
@@ -104,8 +101,7 @@ theorem card_memberSubfamily_add_card_nonMemberSubfamily (a : α) (𝒜 : Finset
 #align finset.card_member_subfamily_add_card_non_member_subfamily Finset.card_memberSubfamily_add_card_nonMemberSubfamily
 
 theorem memberSubfamily_union_nonMemberSubfamily (a : α) (𝒜 : Finset (Finset α)) :
-    𝒜.memberSubfamily a ∪ 𝒜.nonMemberSubfamily a = 𝒜.image fun s => s.erase a :=
-  by
+    𝒜.memberSubfamily a ∪ 𝒜.nonMemberSubfamily a = 𝒜.image fun s => s.erase a := by
   ext s
   simp only [mem_union, mem_memberSubfamily, mem_nonMemberSubfamily, mem_image, exists_prop]
   constructor
@@ -119,31 +115,27 @@ theorem memberSubfamily_union_nonMemberSubfamily (a : α) (𝒜 : Finset (Finset
 #align finset.member_subfamily_union_non_member_subfamily Finset.memberSubfamily_union_nonMemberSubfamily
 
 @[simp]
-theorem memberSubfamily_memberSubfamily : (𝒜.memberSubfamily a).memberSubfamily a = ∅ :=
-  by
+theorem memberSubfamily_memberSubfamily : (𝒜.memberSubfamily a).memberSubfamily a = ∅ := by
   ext
   simp
 #align finset.member_subfamily_member_subfamily Finset.memberSubfamily_memberSubfamily
 
 @[simp]
-theorem memberSubfamily_nonMemberSubfamily : (𝒜.nonMemberSubfamily a).memberSubfamily a = ∅ :=
-  by
+theorem memberSubfamily_nonMemberSubfamily : (𝒜.nonMemberSubfamily a).memberSubfamily a = ∅ := by
   ext
   simp
 #align finset.member_subfamily_non_member_subfamily Finset.memberSubfamily_nonMemberSubfamily
 
 @[simp]
 theorem nonMemberSubfamily_memberSubfamily :
-    (𝒜.memberSubfamily a).nonMemberSubfamily a = 𝒜.memberSubfamily a :=
-  by
+    (𝒜.memberSubfamily a).nonMemberSubfamily a = 𝒜.memberSubfamily a := by
   ext
   simp
 #align finset.non_member_subfamily_member_subfamily Finset.nonMemberSubfamily_memberSubfamily
 
 @[simp]
 theorem nonMemberSubfamily_nonMemberSubfamily :
-    (𝒜.nonMemberSubfamily a).nonMemberSubfamily a = 𝒜.nonMemberSubfamily a :=
-  by
+    (𝒜.nonMemberSubfamily a).nonMemberSubfamily a = 𝒜.nonMemberSubfamily a := by
   ext
   simp
 #align finset.non_member_subfamily_non_member_subfamily Finset.nonMemberSubfamily_nonMemberSubfamily
@@ -173,8 +165,7 @@ open FinsetFamily
 
 /-- `a` is in the down-compressed family iff it's in the original and its compression is in the
 original, or it's not in the original but it's the compression of something in the original. -/
-theorem mem_compression : s ∈ 𝓓 a 𝒜 ↔ s ∈ 𝒜 ∧ s.erase a ∈ 𝒜 ∨ s ∉ 𝒜 ∧ insert a s ∈ 𝒜 :=
-  by
+theorem mem_compression : s ∈ 𝓓 a 𝒜 ↔ s ∈ 𝒜 ∧ s.erase a ∈ 𝒜 ∨ s ∉ 𝒜 ∧ insert a s ∈ 𝒜 := by
   simp_rw [compression, mem_disjUnion, mem_filter, mem_image, and_comm (a := (¬ s ∈ 𝒜))]
   refine'
     or_congr_right
@@ -184,23 +175,20 @@ theorem mem_compression : s ∈ 𝓓 a 𝒜 ↔ s ∈ 𝒜 ∧ s.erase a ∈ 
   rwa [insert_erase (erase_ne_self.1 (ne_of_mem_of_not_mem ht hs).symm)]
 #align down.mem_compression Down.mem_compression
 
-theorem erase_mem_compression (hs : s ∈ 𝒜) : s.erase a ∈ 𝓓 a 𝒜 :=
-  by
+theorem erase_mem_compression (hs : s ∈ 𝒜) : s.erase a ∈ 𝓓 a 𝒜 := by
   simp_rw [mem_compression, erase_idem, and_self_iff]
   refine' (em _).imp_right fun h => ⟨h, _⟩
   rwa [insert_erase (erase_ne_self.1 (ne_of_mem_of_not_mem hs h).symm)]
 #align down.erase_mem_compression Down.erase_mem_compression
 
 -- This is a special case of `erase_mem_compression` once we have `compression_idem`.
-theorem erase_mem_compression_of_mem_compression : s ∈ 𝓓 a 𝒜 → s.erase a ∈ 𝓓 a 𝒜 :=
-  by
+theorem erase_mem_compression_of_mem_compression : s ∈ 𝓓 a 𝒜 → s.erase a ∈ 𝓓 a 𝒜 := by
   simp_rw [mem_compression, erase_idem]
   refine' Or.imp (fun h => ⟨h.2, h.2⟩) fun h => _
   rwa [erase_eq_of_not_mem (insert_ne_self.1 <| ne_of_mem_of_not_mem h.2 h.1)]
 #align down.erase_mem_compression_of_mem_compression Down.erase_mem_compression_of_mem_compression
 
-theorem mem_compression_of_insert_mem_compression (h : insert a s ∈ 𝓓 a 𝒜) : s ∈ 𝓓 a 𝒜 :=
-  by
+theorem mem_compression_of_insert_mem_compression (h : insert a s ∈ 𝓓 a 𝒜) : s ∈ 𝓓 a 𝒜 := by
   by_cases ha : a ∈ s
   · rwa [insert_eq_of_mem ha] at h
   · rw [← erase_insert ha]
@@ -209,8 +197,7 @@ theorem mem_compression_of_insert_mem_compression (h : insert a s ∈ 𝓓 a 
 
 /-- Down-compressing a family is idempotent. -/
 @[simp]
-theorem compression_idem (a : α) (𝒜 : Finset (Finset α)) : 𝓓 a (𝓓 a 𝒜) = 𝓓 a 𝒜 :=
-  by
+theorem compression_idem (a : α) (𝒜 : Finset (Finset α)) : 𝓓 a (𝓓 a 𝒜) = 𝓓 a 𝒜 := by
   ext s
   refine' mem_compression.trans ⟨_, fun h => Or.inl ⟨h, erase_mem_compression_of_mem_compression h⟩⟩
   rintro (h | h)
@@ -220,8 +207,7 @@ theorem compression_idem (a : α) (𝒜 : Finset (Finset α)) : 𝓓 a (𝓓 a 
 
 /-- Down-compressing a family doesn't change its size. -/
 @[simp]
-theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).card = 𝒜.card :=
-  by
+theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).card = 𝒜.card := by
   rw [compression, card_disjUnion, image_filter,
     card_image_of_injOn ((erase_injOn' _).mono fun s hs => _), ← card_disjoint_union]
   · conv_rhs => rw [← filter_union_filter_neg_eq (fun s => (erase s a ∈ 𝒜)) 𝒜]

9003f287

feat: implement intermediate state for simp_rw (#3738)

closes #3680, see https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Stepping.20through.20simp_rw/near/326712986

ff334843

Diff

@@ -175,8 +175,7 @@ open FinsetFamily
 original, or it's not in the original but it's the compression of something in the original. -/
 theorem mem_compression : s ∈ 𝓓 a 𝒜 ↔ s ∈ 𝒜 ∧ s.erase a ∈ 𝒜 ∨ s ∉ 𝒜 ∧ insert a s ∈ 𝒜 :=
   by
-  simp_rw [compression, mem_disjUnion, mem_filter, mem_image,
-    decide_eq_true_eq, and_comm (a := (¬ s ∈ 𝒜))]
+  simp_rw [compression, mem_disjUnion, mem_filter, mem_image, and_comm (a := (¬ s ∈ 𝒜))]
   refine'
     or_congr_right
       (and_congr_left fun hs =>

9003f287

feat: improvements to congr! and convert (#2606)

There is now configuration for congr!, convert, and convert_to to control parts of the congruence algorithm, in particular transparency settings when applying congruence lemmas.
congr! now applies congruence lemmas with reducible transparency by default. This prevents it from unfolding definitions when applying congruence lemmas. It also now tries both the LHS-biased and RHS-biased simp congruence lemmas, with a configuration option to set which it should try first.
There is now a new HEq congruence lemma generator that gives each hypothesis access to the proofs of previous hypotheses. This means that if you have an equality ⊢ ⟨a, x⟩ = ⟨b, y⟩ of sigma types, congr! turns this into goals ⊢ a = b and ⊢ a = b → HEq x y (note that congr! will also auto-introduce a = b for you in the second goal). This congruence lemma generator applies to more cases than the simp congruence lemma generator does.
congr! (and hence convert) are more careful about applying lemmas that don't force definitions to unfold. There were a number of cases in mathlib where the implementation of congr was being abused to unfold definitions.
With set_option trace.congr! true you can see what congr! sees when it is deciding on congruence lemmas.
There is also a bug fix in convert_to to do using 1 when there is no using clause, to match its documentation.

Note that congr! is more capable than congr at finding a way to equate left-hand sides and right-hand sides, so you will frequently need to limit its depth with a using clause. However, there is also a new heuristic to prevent considering unlikely-to-be-provable type equalities (controlled by the typeEqs option), which can help limit the depth automatically.

There is also a predefined configuration that you can invoke with, for example, convert (config := .unfoldSameFun) h, that causes it to behave more like congr, including using default transparency when unfolding.

61ca0ea8

Diff

@@ -226,10 +226,10 @@ theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).ca
   rw [compression, card_disjUnion, image_filter,
     card_image_of_injOn ((erase_injOn' _).mono fun s hs => _), ← card_disjoint_union]
   · conv_rhs => rw [← filter_union_filter_neg_eq (fun s => (erase s a ∈ 𝒜)) 𝒜]
-  · convert disjoint_filter_filter_neg 𝒜 𝒜 (fun s => (erase s a ∈ 𝒜))
+  · exact disjoint_filter_filter_neg 𝒜 𝒜 (fun s => (erase s a ∈ 𝒜))
   intro s hs
   rw [mem_coe, mem_filter, Function.comp_apply] at hs
-  convert not_imp_comm.1 erase_eq_of_not_mem (ne_of_mem_of_not_mem hs.1 hs.2).symm
+  exact not_imp_comm.1 erase_eq_of_not_mem (ne_of_mem_of_not_mem hs.1 hs.2).symm
 #align down.card_compression Down.card_compression
 
 end Down

9003f287

chore: the style linter shouldn't complain about long #align lines (#1643)

54af0498

Diff

@@ -101,9 +101,7 @@ theorem card_memberSubfamily_add_card_nonMemberSubfamily (a : α) (𝒜 : Finset
   · conv_rhs => rw [← filter_card_add_filter_neg_card_eq_card (fun s => (a ∈ s))]
   · apply (erase_injOn' _).mono
     simp
-#align
-  finset.card_member_subfamily_add_card_non_member_subfamily
-  Finset.card_memberSubfamily_add_card_nonMemberSubfamily
+#align finset.card_member_subfamily_add_card_non_member_subfamily Finset.card_memberSubfamily_add_card_nonMemberSubfamily
 
 theorem memberSubfamily_union_nonMemberSubfamily (a : α) (𝒜 : Finset (Finset α)) :
     𝒜.memberSubfamily a ∪ 𝒜.nonMemberSubfamily a = 𝒜.image fun s => s.erase a :=
@@ -118,9 +116,7 @@ theorem memberSubfamily_union_nonMemberSubfamily (a : α) (𝒜 : Finset (Finset
     by_cases ha : a ∈ s
     · exact Or.inl ⟨by rwa [insert_erase ha], not_mem_erase _ _⟩
     · exact Or.inr ⟨by rwa [erase_eq_of_not_mem ha], not_mem_erase _ _⟩
-#align
-  finset.member_subfamily_union_non_member_subfamily
-  Finset.memberSubfamily_union_nonMemberSubfamily
+#align finset.member_subfamily_union_non_member_subfamily Finset.memberSubfamily_union_nonMemberSubfamily
 
 @[simp]
 theorem memberSubfamily_memberSubfamily : (𝒜.memberSubfamily a).memberSubfamily a = ∅ :=
@@ -150,8 +146,7 @@ theorem nonMemberSubfamily_nonMemberSubfamily :
   by
   ext
   simp
-#align
-  finset.non_member_subfamily_non_member_subfamily Finset.nonMemberSubfamily_nonMemberSubfamily
+#align finset.non_member_subfamily_non_member_subfamily Finset.nonMemberSubfamily_nonMemberSubfamily
 
 end Finset

9003f287

chore: revert Multiset and Finset API to use Prop instead of Bool (#1652)

Co-authored-by: Reid Barton <rwbarton@gmail.com>

bc61efff

Diff

@@ -67,7 +67,6 @@ theorem mem_memberSubfamily : s ∈ 𝒜.memberSubfamily a ↔ insert a s ∈ 
   simp_rw [memberSubfamily, mem_image, mem_filter]
   refine' ⟨_, fun h => ⟨insert a s, ⟨h.1, by simp⟩, erase_insert h.2⟩⟩
   rintro ⟨s, ⟨hs1, hs2⟩, rfl⟩
-  rw [decide_eq_true_eq] at hs2
   rw [insert_erase hs2]
   exact ⟨hs1, not_mem_erase _ _⟩
 #align finset.mem_member_subfamily Finset.mem_memberSubfamily
@@ -100,7 +99,6 @@ theorem card_memberSubfamily_add_card_nonMemberSubfamily (a : α) (𝒜 : Finset
   by
   rw [memberSubfamily, nonMemberSubfamily, card_image_of_injOn]
   · conv_rhs => rw [← filter_card_add_filter_neg_card_eq_card (fun s => (a ∈ s))]
-    simp
   · apply (erase_injOn' _).mono
     simp
 #align
@@ -169,7 +167,6 @@ def compression (a : α) (𝒜 : Finset (Finset α)) : Finset (Finset α) :=
       ((𝒜.image fun s => erase s a).filter fun s => s ∉ 𝒜) <|
     disjoint_left.2 fun s h₁ h₂ => by
       have := (mem_filter.1 h₂).2
-      rw [decide_eq_true_iff] at this
       exact this (mem_filter.1 h₁).1
 #align down.compression Down.compression
 
@@ -234,14 +231,9 @@ theorem card_compression (a : α) (𝒜 : Finset (Finset α)) : (𝓓 a 𝒜).ca
   rw [compression, card_disjUnion, image_filter,
     card_image_of_injOn ((erase_injOn' _).mono fun s hs => _), ← card_disjoint_union]
   · conv_rhs => rw [← filter_union_filter_neg_eq (fun s => (erase s a ∈ 𝒜)) 𝒜]
-    congr
-    ext
-    simp
   · convert disjoint_filter_filter_neg 𝒜 𝒜 (fun s => (erase s a ∈ 𝒜))
-    ext
-    simp
   intro s hs
-  rw [mem_coe, mem_filter, Function.comp_apply, decide_eq_true_iff] at hs
+  rw [mem_coe, mem_filter, Function.comp_apply] at hs
   convert not_imp_comm.1 erase_eq_of_not_mem (ne_of_mem_of_not_mem hs.1 hs.2).symm
 #align down.card_compression Down.card_compression

9003f287

feat: port Combinatorics.SetFamily.Compression.Down (#1604)

Some proofs here needed rewriting mostly due to Finset.filter now taking bools and Function.comp not being seen through (see Zulip for what I think is a related discussion.)

c211d671

`combinatorics.set_family.compression.down` ⟷ `Mathlib.Combinatorics.SetFamily.Compression.Down`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 154

combinatorics.set_family.compression.down ⟷ Mathlib.Combinatorics.SetFamily.Compression.Down

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 154

`combinatorics.set_family.compression.down` ⟷ `Mathlib.Combinatorics.SetFamily.Compression.Down`