combinatorics.set_family.kleitman | 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

4c19a16e

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

50832dae

bump to nightly-2024-04-06-08

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

e34029c9

Diff

@@ -74,7 +74,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
   rw [union_sdiff_left, sdiff_eq_inter_compl]
   refine' le_of_mul_le_mul_left _ (pow_pos zero_lt_two <| card α + 1)
-  rw [pow_succ', mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
+  rw [pow_succ, mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
   refine'
     (add_le_add
             ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
@@ -95,7 +95,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
             (hf₁ _ <| subset_cons _ hi).2.2)
           _).trans
       _
-  rw [mul_tsub, two_mul, ← pow_succ, ←
+  rw [mul_tsub, two_mul, ← pow_succ', ←
     add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting

50832dae

bump to nightly-2024-02-01-06

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

5433bded

Diff

@@ -53,6 +53,51 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   induction' s using Finset.cons_induction with i s hi ih generalizing f
   · simp
   classical
+  set f' : ι → Finset (Finset α) := fun j =>
+    if hj : j ∈ cons i s hi then (hf j hj).exists_card_eq.some else ∅ with hf'
+  have hf₁ :
+    ∀ j,
+      j ∈ cons i s hi →
+        f j ⊆ f' j ∧ 2 * (f' j).card = 2 ^ card α ∧ (f' j : Set (Finset α)).Intersecting :=
+    by
+    rintro j hj
+    simp_rw [hf', dif_pos hj, ← Fintype.card_finset]
+    exact Classical.choose_spec (hf j hj).exists_card_eq
+  have hf₂ : ∀ j, j ∈ cons i s hi → IsUpperSet (f' j : Set (Finset α)) :=
+    by
+    refine' fun j hj => (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)
+    rw [Fintype.card_finset]
+    exact (hf₁ _ hj).2.1
+  refine' (card_le_of_subset <| bUnion_mono fun j hj => (hf₁ _ hj).1).trans _
+  nth_rw 1 [cons_eq_insert i]
+  rw [bUnion_insert]
+  refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
+  rw [union_sdiff_left, sdiff_eq_inter_compl]
+  refine' le_of_mul_le_mul_left _ (pow_pos zero_lt_two <| card α + 1)
+  rw [pow_succ', mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
+  refine'
+    (add_le_add
+            ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
+              (hf₁ _ <| mem_cons_self _ _).2.2.card_le) <|
+          (mul_le_mul_left <| zero_lt_two' ℕ).2 <| IsUpperSet.card_inter_le_finset _ _).trans
+      _
+  · rw [coe_bUnion]
+    exact isUpperSet_iUnion₂ fun i hi => hf₂ _ <| subset_cons _ hi
+  · rw [coe_compl]
+    exact (hf₂ _ <| mem_cons_self _ _).compl
+  rw [mul_tsub, card_compl, Fintype.card_finset, mul_left_comm, mul_tsub,
+    (hf₁ _ <| mem_cons_self _ _).2.1, two_mul, add_tsub_cancel_left, ← mul_tsub, ← mul_two,
+    mul_assoc, ← add_mul, mul_comm]
+  refine' mul_le_mul_left' _ _
+  refine'
+    (add_le_add_left
+          (ih ((card_le_of_subset <| subset_cons _).trans hs) _ fun i hi =>
+            (hf₁ _ <| subset_cons _ hi).2.2)
+          _).trans
+      _
+  rw [mul_tsub, two_mul, ← pow_succ, ←
+    add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
+    tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting
 -/

50832dae

bump to nightly-2024-01-31-06

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

61100fe9

Diff

@@ -53,51 +53,6 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   induction' s using Finset.cons_induction with i s hi ih generalizing f
   · simp
   classical
-  set f' : ι → Finset (Finset α) := fun j =>
-    if hj : j ∈ cons i s hi then (hf j hj).exists_card_eq.some else ∅ with hf'
-  have hf₁ :
-    ∀ j,
-      j ∈ cons i s hi →
-        f j ⊆ f' j ∧ 2 * (f' j).card = 2 ^ card α ∧ (f' j : Set (Finset α)).Intersecting :=
-    by
-    rintro j hj
-    simp_rw [hf', dif_pos hj, ← Fintype.card_finset]
-    exact Classical.choose_spec (hf j hj).exists_card_eq
-  have hf₂ : ∀ j, j ∈ cons i s hi → IsUpperSet (f' j : Set (Finset α)) :=
-    by
-    refine' fun j hj => (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)
-    rw [Fintype.card_finset]
-    exact (hf₁ _ hj).2.1
-  refine' (card_le_of_subset <| bUnion_mono fun j hj => (hf₁ _ hj).1).trans _
-  nth_rw 1 [cons_eq_insert i]
-  rw [bUnion_insert]
-  refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
-  rw [union_sdiff_left, sdiff_eq_inter_compl]
-  refine' le_of_mul_le_mul_left _ (pow_pos zero_lt_two <| card α + 1)
-  rw [pow_succ', mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
-  refine'
-    (add_le_add
-            ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
-              (hf₁ _ <| mem_cons_self _ _).2.2.card_le) <|
-          (mul_le_mul_left <| zero_lt_two' ℕ).2 <| IsUpperSet.card_inter_le_finset _ _).trans
-      _
-  · rw [coe_bUnion]
-    exact isUpperSet_iUnion₂ fun i hi => hf₂ _ <| subset_cons _ hi
-  · rw [coe_compl]
-    exact (hf₂ _ <| mem_cons_self _ _).compl
-  rw [mul_tsub, card_compl, Fintype.card_finset, mul_left_comm, mul_tsub,
-    (hf₁ _ <| mem_cons_self _ _).2.1, two_mul, add_tsub_cancel_left, ← mul_tsub, ← mul_two,
-    mul_assoc, ← add_mul, mul_comm]
-  refine' mul_le_mul_left' _ _
-  refine'
-    (add_le_add_left
-          (ih ((card_le_of_subset <| subset_cons _).trans hs) _ fun i hi =>
-            (hf₁ _ <| subset_cons _ hi).2.2)
-          _).trans
-      _
-  rw [mul_tsub, two_mul, ← pow_succ, ←
-    add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
-    tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting
 -/

50832dae

bump to nightly-2023-12-20-06

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

058cd493

Diff

@@ -96,7 +96,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
           _).trans
       _
   rw [mul_tsub, two_mul, ← pow_succ, ←
-    add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
+    add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting
 -/

50832dae

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) 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.Combinatorics.SetFamily.HarrisKleitman
-import Mathbin.Combinatorics.SetFamily.Intersecting
+import Combinatorics.SetFamily.HarrisKleitman
+import Combinatorics.SetFamily.Intersecting
 
 #align_import combinatorics.set_family.kleitman from "leanprover-community/mathlib"@"50832daea47b195a48b5b33b1c8b2162c48c3afc"

50832dae

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) 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.kleitman
-! leanprover-community/mathlib commit 50832daea47b195a48b5b33b1c8b2162c48c3afc
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.SetFamily.HarrisKleitman
 import Mathbin.Combinatorics.SetFamily.Intersecting
 
+#align_import combinatorics.set_family.kleitman from "leanprover-community/mathlib"@"50832daea47b195a48b5b33b1c8b2162c48c3afc"
+
 /-!
 # Kleitman's bound on the size of intersecting families

50832dae

bump to nightly-2023-06-13-21

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

829520ac

Diff

@@ -38,6 +38,7 @@ open Fintype (card)
 
 variable {ι α : Type _} [Fintype α] [DecidableEq α] [Nonempty α]
 
+#print Finset.card_biUnion_le_of_intersecting /-
 /-- **Kleitman's theorem**. An intersecting family on `n` elements contains at most `2ⁿ⁻¹` sets, and
 each further intersecting family takes at most half of the sets that are in no previous family. -/
 theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finset (Finset α))
@@ -101,4 +102,5 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
     add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting
+-/

50832dae

bump to nightly-2023-06-04-18

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

3fb4268b

Diff

@@ -55,50 +55,50 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   induction' s using Finset.cons_induction with i s hi ih generalizing f
   · simp
   classical
-    set f' : ι → Finset (Finset α) := fun j =>
-      if hj : j ∈ cons i s hi then (hf j hj).exists_card_eq.some else ∅ with hf'
-    have hf₁ :
-      ∀ j,
-        j ∈ cons i s hi →
-          f j ⊆ f' j ∧ 2 * (f' j).card = 2 ^ card α ∧ (f' j : Set (Finset α)).Intersecting :=
-      by
-      rintro j hj
-      simp_rw [hf', dif_pos hj, ← Fintype.card_finset]
-      exact Classical.choose_spec (hf j hj).exists_card_eq
-    have hf₂ : ∀ j, j ∈ cons i s hi → IsUpperSet (f' j : Set (Finset α)) :=
-      by
-      refine' fun j hj => (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)
-      rw [Fintype.card_finset]
-      exact (hf₁ _ hj).2.1
-    refine' (card_le_of_subset <| bUnion_mono fun j hj => (hf₁ _ hj).1).trans _
-    nth_rw 1 [cons_eq_insert i]
-    rw [bUnion_insert]
-    refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
-    rw [union_sdiff_left, sdiff_eq_inter_compl]
-    refine' le_of_mul_le_mul_left _ (pow_pos zero_lt_two <| card α + 1)
-    rw [pow_succ', mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
-    refine'
-      (add_le_add
-              ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
-                (hf₁ _ <| mem_cons_self _ _).2.2.card_le) <|
-            (mul_le_mul_left <| zero_lt_two' ℕ).2 <| IsUpperSet.card_inter_le_finset _ _).trans
-        _
-    · rw [coe_bUnion]
-      exact isUpperSet_iUnion₂ fun i hi => hf₂ _ <| subset_cons _ hi
-    · rw [coe_compl]
-      exact (hf₂ _ <| mem_cons_self _ _).compl
-    rw [mul_tsub, card_compl, Fintype.card_finset, mul_left_comm, mul_tsub,
-      (hf₁ _ <| mem_cons_self _ _).2.1, two_mul, add_tsub_cancel_left, ← mul_tsub, ← mul_two,
-      mul_assoc, ← add_mul, mul_comm]
-    refine' mul_le_mul_left' _ _
-    refine'
-      (add_le_add_left
-            (ih ((card_le_of_subset <| subset_cons _).trans hs) _ fun i hi =>
-              (hf₁ _ <| subset_cons _ hi).2.2)
-            _).trans
-        _
-    rw [mul_tsub, two_mul, ← pow_succ, ←
-      add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
-      tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
+  set f' : ι → Finset (Finset α) := fun j =>
+    if hj : j ∈ cons i s hi then (hf j hj).exists_card_eq.some else ∅ with hf'
+  have hf₁ :
+    ∀ j,
+      j ∈ cons i s hi →
+        f j ⊆ f' j ∧ 2 * (f' j).card = 2 ^ card α ∧ (f' j : Set (Finset α)).Intersecting :=
+    by
+    rintro j hj
+    simp_rw [hf', dif_pos hj, ← Fintype.card_finset]
+    exact Classical.choose_spec (hf j hj).exists_card_eq
+  have hf₂ : ∀ j, j ∈ cons i s hi → IsUpperSet (f' j : Set (Finset α)) :=
+    by
+    refine' fun j hj => (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)
+    rw [Fintype.card_finset]
+    exact (hf₁ _ hj).2.1
+  refine' (card_le_of_subset <| bUnion_mono fun j hj => (hf₁ _ hj).1).trans _
+  nth_rw 1 [cons_eq_insert i]
+  rw [bUnion_insert]
+  refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
+  rw [union_sdiff_left, sdiff_eq_inter_compl]
+  refine' le_of_mul_le_mul_left _ (pow_pos zero_lt_two <| card α + 1)
+  rw [pow_succ', mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
+  refine'
+    (add_le_add
+            ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
+              (hf₁ _ <| mem_cons_self _ _).2.2.card_le) <|
+          (mul_le_mul_left <| zero_lt_two' ℕ).2 <| IsUpperSet.card_inter_le_finset _ _).trans
+      _
+  · rw [coe_bUnion]
+    exact isUpperSet_iUnion₂ fun i hi => hf₂ _ <| subset_cons _ hi
+  · rw [coe_compl]
+    exact (hf₂ _ <| mem_cons_self _ _).compl
+  rw [mul_tsub, card_compl, Fintype.card_finset, mul_left_comm, mul_tsub,
+    (hf₁ _ <| mem_cons_self _ _).2.1, two_mul, add_tsub_cancel_left, ← mul_tsub, ← mul_two,
+    mul_assoc, ← add_mul, mul_comm]
+  refine' mul_le_mul_left' _ _
+  refine'
+    (add_le_add_left
+          (ih ((card_le_of_subset <| subset_cons _).trans hs) _ fun i hi =>
+            (hf₁ _ <| subset_cons _ hi).2.2)
+          _).trans
+      _
+  rw [mul_tsub, two_mul, ← pow_succ, ←
+    add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
+    tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting

50832dae

bump to nightly-2023-05-28-06

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

ba5d8b97

Diff

@@ -38,12 +38,6 @@ open Fintype (card)
 
 variable {ι α : Type _} [Fintype α] [DecidableEq α] [Nonempty α]
 
-/- warning: finset.card_bUnion_le_of_intersecting -> Finset.card_biUnion_le_of_intersecting is a dubious translation:
-lean 3 declaration is
-  forall {ι : Type.{u1}} {α : Type.{u2}} [_inst_1 : Fintype.{u2} α] [_inst_2 : DecidableEq.{succ u2} α] [_inst_3 : Nonempty.{succ u2} α] (s : Finset.{u1} ι) (f : ι -> (Finset.{u2} (Finset.{u2} α))), (forall (i : ι), (Membership.Mem.{u1, u1} ι (Finset.{u1} ι) (Finset.hasMem.{u1} ι) i s) -> (Set.Intersecting.{u2} (Finset.{u2} α) (Lattice.toSemilatticeInf.{u2} (Finset.{u2} α) (Finset.lattice.{u2} α (fun (a : α) (b : α) => _inst_2 a b))) (Finset.orderBot.{u2} α) ((fun (a : Type.{u2}) (b : Type.{u2}) [self : HasLiftT.{succ u2, succ u2} a b] => self.0) (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (HasLiftT.mk.{succ u2, succ u2} (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (CoeTCₓ.coe.{succ u2, succ u2} (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (Finset.Set.hasCoeT.{u2} (Finset.{u2} α)))) (f i)))) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u2} (Finset.{u2} α) (Finset.biUnion.{u1, u2} ι (Finset.{u2} α) (fun (a : Finset.{u2} α) (b : Finset.{u2} α) => Finset.decidableEq.{u2} α (fun (a : α) (b : α) => _inst_2 a b) a b) s f)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u2} α _inst_1)) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (Fintype.card.{u2} α _inst_1) (Finset.card.{u1} ι s)))))
-but is expected to have type
-  forall {ι : Type.{u2}} {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] [_inst_3 : Nonempty.{succ u1} α] (s : Finset.{u2} ι) (f : ι -> (Finset.{u1} (Finset.{u1} α))), (forall (i : ι), (Membership.mem.{u2, u2} ι (Finset.{u2} ι) (Finset.instMembershipFinset.{u2} ι) i s) -> (Set.Intersecting.{u1} (Finset.{u1} α) (Lattice.toSemilatticeInf.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_2 a b))) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) (Finset.toSet.{u1} (Finset.{u1} α) (f i)))) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} (Finset.{u1} α) (Finset.biUnion.{u2, u1} ι (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_2 a b) a b) s f)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_1)) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (Fintype.card.{u1} α _inst_1) (Finset.card.{u2} ι s)))))
-Case conversion may be inaccurate. Consider using '#align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersectingₓ'. -/
 /-- **Kleitman's theorem**. An intersecting family on `n` elements contains at most `2ⁿ⁻¹` sets, and
 each further intersecting family takes at most half of the sets that are in no previous family. -/
 theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finset (Finset α))

50832dae

bump to nightly-2023-05-14-08

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

d31da313

Diff

@@ -38,17 +38,17 @@ open Fintype (card)
 
 variable {ι α : Type _} [Fintype α] [DecidableEq α] [Nonempty α]
 
-/- warning: finset.card_bUnion_le_of_intersecting -> Finset.card_bunionᵢ_le_of_intersecting is a dubious translation:
+/- warning: finset.card_bUnion_le_of_intersecting -> Finset.card_biUnion_le_of_intersecting is a dubious translation:
 lean 3 declaration is
-  forall {ι : Type.{u1}} {α : Type.{u2}} [_inst_1 : Fintype.{u2} α] [_inst_2 : DecidableEq.{succ u2} α] [_inst_3 : Nonempty.{succ u2} α] (s : Finset.{u1} ι) (f : ι -> (Finset.{u2} (Finset.{u2} α))), (forall (i : ι), (Membership.Mem.{u1, u1} ι (Finset.{u1} ι) (Finset.hasMem.{u1} ι) i s) -> (Set.Intersecting.{u2} (Finset.{u2} α) (Lattice.toSemilatticeInf.{u2} (Finset.{u2} α) (Finset.lattice.{u2} α (fun (a : α) (b : α) => _inst_2 a b))) (Finset.orderBot.{u2} α) ((fun (a : Type.{u2}) (b : Type.{u2}) [self : HasLiftT.{succ u2, succ u2} a b] => self.0) (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (HasLiftT.mk.{succ u2, succ u2} (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (CoeTCₓ.coe.{succ u2, succ u2} (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (Finset.Set.hasCoeT.{u2} (Finset.{u2} α)))) (f i)))) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u2} (Finset.{u2} α) (Finset.bunionᵢ.{u1, u2} ι (Finset.{u2} α) (fun (a : Finset.{u2} α) (b : Finset.{u2} α) => Finset.decidableEq.{u2} α (fun (a : α) (b : α) => _inst_2 a b) a b) s f)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u2} α _inst_1)) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (Fintype.card.{u2} α _inst_1) (Finset.card.{u1} ι s)))))
+  forall {ι : Type.{u1}} {α : Type.{u2}} [_inst_1 : Fintype.{u2} α] [_inst_2 : DecidableEq.{succ u2} α] [_inst_3 : Nonempty.{succ u2} α] (s : Finset.{u1} ι) (f : ι -> (Finset.{u2} (Finset.{u2} α))), (forall (i : ι), (Membership.Mem.{u1, u1} ι (Finset.{u1} ι) (Finset.hasMem.{u1} ι) i s) -> (Set.Intersecting.{u2} (Finset.{u2} α) (Lattice.toSemilatticeInf.{u2} (Finset.{u2} α) (Finset.lattice.{u2} α (fun (a : α) (b : α) => _inst_2 a b))) (Finset.orderBot.{u2} α) ((fun (a : Type.{u2}) (b : Type.{u2}) [self : HasLiftT.{succ u2, succ u2} a b] => self.0) (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (HasLiftT.mk.{succ u2, succ u2} (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (CoeTCₓ.coe.{succ u2, succ u2} (Finset.{u2} (Finset.{u2} α)) (Set.{u2} (Finset.{u2} α)) (Finset.Set.hasCoeT.{u2} (Finset.{u2} α)))) (f i)))) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u2} (Finset.{u2} α) (Finset.biUnion.{u1, u2} ι (Finset.{u2} α) (fun (a : Finset.{u2} α) (b : Finset.{u2} α) => Finset.decidableEq.{u2} α (fun (a : α) (b : α) => _inst_2 a b) a b) s f)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u2} α _inst_1)) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat Nat.hasSub) (Fintype.card.{u2} α _inst_1) (Finset.card.{u1} ι s)))))
 but is expected to have type
-  forall {ι : Type.{u2}} {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] [_inst_3 : Nonempty.{succ u1} α] (s : Finset.{u2} ι) (f : ι -> (Finset.{u1} (Finset.{u1} α))), (forall (i : ι), (Membership.mem.{u2, u2} ι (Finset.{u2} ι) (Finset.instMembershipFinset.{u2} ι) i s) -> (Set.Intersecting.{u1} (Finset.{u1} α) (Lattice.toSemilatticeInf.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_2 a b))) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) (Finset.toSet.{u1} (Finset.{u1} α) (f i)))) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} (Finset.{u1} α) (Finset.bunionᵢ.{u2, u1} ι (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_2 a b) a b) s f)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_1)) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (Fintype.card.{u1} α _inst_1) (Finset.card.{u2} ι s)))))
-Case conversion may be inaccurate. Consider using '#align finset.card_bUnion_le_of_intersecting Finset.card_bunionᵢ_le_of_intersectingₓ'. -/
+  forall {ι : Type.{u2}} {α : Type.{u1}} [_inst_1 : Fintype.{u1} α] [_inst_2 : DecidableEq.{succ u1} α] [_inst_3 : Nonempty.{succ u1} α] (s : Finset.{u2} ι) (f : ι -> (Finset.{u1} (Finset.{u1} α))), (forall (i : ι), (Membership.mem.{u2, u2} ι (Finset.{u2} ι) (Finset.instMembershipFinset.{u2} ι) i s) -> (Set.Intersecting.{u1} (Finset.{u1} α) (Lattice.toSemilatticeInf.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_2 a b))) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) (Finset.toSet.{u1} (Finset.{u1} α) (f i)))) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} (Finset.{u1} α) (Finset.biUnion.{u2, u1} ι (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_2 a b) a b) s f)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_1)) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (HSub.hSub.{0, 0, 0} Nat Nat Nat (instHSub.{0} Nat instSubNat) (Fintype.card.{u1} α _inst_1) (Finset.card.{u2} ι s)))))
+Case conversion may be inaccurate. Consider using '#align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersectingₓ'. -/
 /-- **Kleitman's theorem**. An intersecting family on `n` elements contains at most `2ⁿ⁻¹` sets, and
 each further intersecting family takes at most half of the sets that are in no previous family. -/
-theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Finset (Finset α))
+theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finset (Finset α))
     (hf : ∀ i ∈ s, (f i : Set (Finset α)).Intersecting) :
-    (s.bunionᵢ f).card ≤ 2 ^ card α - 2 ^ (card α - s.card) :=
+    (s.biUnion f).card ≤ 2 ^ card α - 2 ^ (card α - s.card) :=
   by
   obtain hs | hs := le_total (card α) s.card
   · rw [tsub_eq_zero_of_le hs, pow_zero]
@@ -90,7 +90,7 @@ theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Fin
             (mul_le_mul_left <| zero_lt_two' ℕ).2 <| IsUpperSet.card_inter_le_finset _ _).trans
         _
     · rw [coe_bUnion]
-      exact isUpperSet_unionᵢ₂ fun i hi => hf₂ _ <| subset_cons _ hi
+      exact isUpperSet_iUnion₂ fun i hi => hf₂ _ <| subset_cons _ hi
     · rw [coe_compl]
       exact (hf₂ _ <| mem_cons_self _ _).compl
     rw [mul_tsub, card_compl, Fintype.card_finset, mul_left_comm, mul_tsub,
@@ -106,5 +106,5 @@ theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Fin
     rw [mul_tsub, two_mul, ← pow_succ, ←
       add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
       tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
-#align finset.card_bUnion_le_of_intersecting Finset.card_bunionᵢ_le_of_intersecting
+#align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting

50832dae

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

4c19a16e

change the order of operation in zsmulRec and nsmulRec (#11451)

We change the following field in the definition of an additive commutative monoid:

 nsmul_succ : ∀ (n : ℕ) (x : G),
-  AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+  AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x

where the latter is more natural

We adjust the definitions of ^ in monoids, groups, etc. Originally there was a warning comment about why this natural order was preferred

use x * npowRec n x and not npowRec n x * x in the definition to make sure that definitional unfolding of npowRec is blocked, to avoid deep recursion issues.

but it seems to no longer apply.

Remarks on the PR :

pow_succ and pow_succ' have switched their meanings.
Most of the time, the proofs were adjusted by priming/unpriming one lemma, or exchanging left and right; a few proofs were more complicated to adjust.
In particular, [Mathlib/NumberTheory/RamificationInertia.lean] used Ideal.IsPrime.mul_mem_pow which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul.
the docstring for Cauchy condensation test in [Mathlib/Analysis/PSeries.lean] was mathematically incorrect, I added the mention that the function is antitone.

9a3feeae

Diff

@@ -64,7 +64,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
   rw [union_sdiff_left, sdiff_eq_inter_compl]
   refine' le_of_mul_le_mul_left _ (pow_pos (zero_lt_two' ℕ) <| Fintype.card α + 1)
-  rw [pow_succ', mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
+  rw [pow_succ, mul_add, mul_assoc, mul_comm _ 2, mul_assoc]
   refine' (add_le_add
       ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
       (hf₁ _ <| mem_cons_self _ _).2.2.card_le) <|
@@ -80,7 +80,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   refine' (add_le_add_left
     (ih _ (fun i hi ↦ (hf₁ _ <| subset_cons _ hi).2.2)
     ((card_le_card <| subset_cons _).trans hs)) _).trans _
-  rw [mul_tsub, two_mul, ← pow_succ,
+  rw [mul_tsub, two_mul, ← pow_succ',
     ← add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting

4c19a16e

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

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

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

fa48894a

Diff

@@ -52,7 +52,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   have hf₁ : ∀ j, j ∈ cons i s hi → f j ⊆ f' j ∧ 2 * (f' j).card =
       2 ^ Fintype.card α ∧ (f' j : Set (Finset α)).Intersecting := by
     rintro j hj
-    simp_rw [dif_pos hj, ← Fintype.card_finset]
+    simp_rw [f', dif_pos hj, ← Fintype.card_finset]
     exact Classical.choose_spec (hf j hj).exists_card_eq
   have hf₂ : ∀ j, j ∈ cons i s hi → IsUpperSet (f' j : Set (Finset α)) := by
     refine' fun j hj ↦ (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)

4c19a16e

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

@@ -42,7 +42,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
     infer_instance
   obtain hs | hs := le_total (Fintype.card α) s.card
   · rw [tsub_eq_zero_of_le hs, pow_zero]
-    refine' (card_le_of_subset <| biUnion_subset.2 fun i hi a ha ↦
+    refine' (card_le_card <| biUnion_subset.2 fun i hi a ha ↦
       mem_compl.2 <| not_mem_singleton.2 <| (hf _ hi).ne_bot ha).trans_eq _
     rw [card_compl, Fintype.card_finset, card_singleton]
   induction' s using Finset.cons_induction with i s hi ih generalizing f
@@ -58,7 +58,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
     refine' fun j hj ↦ (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)
     rw [Fintype.card_finset]
     exact (hf₁ _ hj).2.1
-  refine' (card_le_of_subset <| biUnion_mono fun j hj ↦ (hf₁ _ hj).1).trans _
+  refine' (card_le_card <| biUnion_mono fun j hj ↦ (hf₁ _ hj).1).trans _
   nth_rw 1 [cons_eq_insert i]
   rw [biUnion_insert]
   refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
@@ -79,7 +79,7 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
   refine' mul_le_mul_left' _ _
   refine' (add_le_add_left
     (ih _ (fun i hi ↦ (hf₁ _ <| subset_cons _ hi).2.2)
-    ((card_le_of_subset <| subset_cons _).trans hs)) _).trans _
+    ((card_le_card <| subset_cons _).trans hs)) _).trans _
   rw [mul_tsub, two_mul, ← pow_succ,
     ← add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]

4c19a16e

chore: Rename pow monotonicity lemmas (#9095)

The names for lemmas about monotonicity of (a ^ ·) and (· ^ n) were a mess. This PR tidies up everything related by following the naming convention for (a * ·) and (· * b). Namely, (a ^ ·) is pow_right and (· ^ n) is pow_left in lemma names. All lemma renames follow the corresponding multiplication lemma names closely.

Renames

`Algebra.GroupPower.Order`

pow_mono → pow_right_mono
pow_le_pow → pow_le_pow_right
pow_le_pow_of_le_left → pow_le_pow_left
pow_lt_pow_of_lt_left → pow_lt_pow_left
strictMonoOn_pow → pow_left_strictMonoOn
pow_strictMono_right → pow_right_strictMono
pow_lt_pow → pow_lt_pow_right
pow_lt_pow_iff → pow_lt_pow_iff_right
pow_le_pow_iff → pow_le_pow_iff_right
self_lt_pow → lt_self_pow
strictAnti_pow → pow_right_strictAnti
pow_lt_pow_iff_of_lt_one → pow_lt_pow_iff_right_of_lt_one
pow_lt_pow_of_lt_one → pow_lt_pow_right_of_lt_one
lt_of_pow_lt_pow → lt_of_pow_lt_pow_left
le_of_pow_le_pow → le_of_pow_le_pow_left
pow_lt_pow₀ → pow_lt_pow_right₀

`Algebra.GroupPower.CovariantClass`

pow_le_pow_of_le_left' → pow_le_pow_left'
nsmul_le_nsmul_of_le_right → nsmul_le_nsmul_right
pow_lt_pow' → pow_lt_pow_right'
nsmul_lt_nsmul → nsmul_lt_nsmul_left
pow_strictMono_left → pow_right_strictMono'
nsmul_strictMono_right → nsmul_left_strictMono
StrictMono.pow_right' → StrictMono.pow_const
StrictMono.nsmul_left → StrictMono.const_nsmul
pow_strictMono_right' → pow_left_strictMono
nsmul_strictMono_left → nsmul_right_strictMono
Monotone.pow_right → Monotone.pow_const
Monotone.nsmul_left → Monotone.const_nsmul
lt_of_pow_lt_pow' → lt_of_pow_lt_pow_left'
lt_of_nsmul_lt_nsmul → lt_of_nsmul_lt_nsmul_right
pow_le_pow' → pow_le_pow_right'
nsmul_le_nsmul → nsmul_le_nsmul_left
pow_le_pow_of_le_one' → pow_le_pow_right_of_le_one'
nsmul_le_nsmul_of_nonpos → nsmul_le_nsmul_left_of_nonpos
le_of_pow_le_pow' → le_of_pow_le_pow_left'
le_of_nsmul_le_nsmul' → le_of_nsmul_le_nsmul_right'
pow_le_pow_iff' → pow_le_pow_iff_right'
nsmul_le_nsmul_iff → nsmul_le_nsmul_iff_left
pow_lt_pow_iff' → pow_lt_pow_iff_right'
nsmul_lt_nsmul_iff → nsmul_lt_nsmul_iff_left

`Data.Nat.Pow`

Nat.pow_lt_pow_of_lt_left → Nat.pow_lt_pow_left
Nat.pow_le_iff_le_left → Nat.pow_le_pow_iff_left
Nat.pow_lt_iff_lt_left → Nat.pow_lt_pow_iff_left

Lemmas added

pow_le_pow_iff_left
pow_lt_pow_iff_left
pow_right_injective
pow_right_inj
Nat.pow_le_pow_left to have the correct name since Nat.pow_le_pow_of_le_left is in Std.
Nat.pow_le_pow_right to have the correct name since Nat.pow_le_pow_of_le_right is in Std.

Lemmas removed

self_le_pow was a duplicate of le_self_pow.
Nat.pow_lt_pow_of_lt_right is defeq to pow_lt_pow_right.
Nat.pow_right_strictMono is defeq to pow_right_strictMono.
Nat.pow_le_iff_le_right is defeq to pow_le_pow_iff_right.
Nat.pow_lt_iff_lt_right is defeq to pow_lt_pow_iff_right.

Other changes

A bunch of proofs have been golfed.
Some lemma assumptions have been turned from 0 < n or 1 ≤ n to n ≠ 0.
A few Nat lemmas have been protected.
One docstring has been fixed.

d61c95e1

Diff

@@ -81,6 +81,6 @@ theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finse
     (ih _ (fun i hi ↦ (hf₁ _ <| subset_cons _ hi).2.2)
     ((card_le_of_subset <| subset_cons _).trans hs)) _).trans _
   rw [mul_tsub, two_mul, ← pow_succ,
-    ← add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
+    ← add_tsub_assoc_of_le (pow_le_pow_right' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
 #align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting

4c19a16e

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

@@ -30,7 +30,7 @@ open Finset
 
 open Fintype (card)
 
-variable {ι α : Type _} [Fintype α] [DecidableEq α] [Nonempty α]
+variable {ι α : Type*} [Fintype α] [DecidableEq α] [Nonempty α]
 
 /-- **Kleitman's theorem**. An intersecting family on `n` elements contains at most `2ⁿ⁻¹` sets, and
 each further intersecting family takes at most half of the sets that are in no previous family. -/

4c19a16e

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,15 +2,12 @@
 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.kleitman
-! leanprover-community/mathlib commit 4c19a16e4b705bf135cf9a80ac18fcc99c438514
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SetFamily.HarrisKleitman
 import Mathlib.Combinatorics.SetFamily.Intersecting
 
+#align_import combinatorics.set_family.kleitman from "leanprover-community/mathlib"@"4c19a16e4b705bf135cf9a80ac18fcc99c438514"
+
 /-!
 # Kleitman's bound on the size of intersecting families

4c19a16e

chore: Rename to sSup/iSup (#3938)

As discussed on Zulip

Renames

supₛ → sSup
infₛ → sInf
supᵢ → iSup
infᵢ → iInf
bsupₛ → bsSup
binfₛ → bsInf
bsupᵢ → biSup
binfᵢ → biInf
csupₛ → csSup
cinfₛ → csInf
csupᵢ → ciSup
cinfᵢ → ciInf
unionₛ → sUnion
interₛ → sInter
unionᵢ → iUnion
interᵢ → iInter
bunionₛ → bsUnion
binterₛ → bsInter
bunionᵢ → biUnion
binterᵢ → biInter

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

d1eb6264

Diff

@@ -21,7 +21,7 @@ Kleitman's bound stipulates that `k` intersecting families cover at most `2ⁿ -
 
 ## Main declarations
 
-* `Finset.card_bunionᵢ_le_of_intersecting`: Kleitman's theorem.
+* `Finset.card_biUnion_le_of_intersecting`: Kleitman's theorem.
 
 ## References
 
@@ -37,15 +37,15 @@ variable {ι α : Type _} [Fintype α] [DecidableEq α] [Nonempty α]
 
 /-- **Kleitman's theorem**. An intersecting family on `n` elements contains at most `2ⁿ⁻¹` sets, and
 each further intersecting family takes at most half of the sets that are in no previous family. -/
-theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Finset (Finset α))
+theorem Finset.card_biUnion_le_of_intersecting (s : Finset ι) (f : ι → Finset (Finset α))
     (hf : ∀ i ∈ s, (f i : Set (Finset α)).Intersecting) :
-    (s.bunionᵢ f).card ≤ 2 ^ Fintype.card α - 2 ^ (Fintype.card α - s.card) := by
+    (s.biUnion f).card ≤ 2 ^ Fintype.card α - 2 ^ (Fintype.card α - s.card) := by
   have : DecidableEq ι := by
     classical
     infer_instance
   obtain hs | hs := le_total (Fintype.card α) s.card
   · rw [tsub_eq_zero_of_le hs, pow_zero]
-    refine' (card_le_of_subset <| bunionᵢ_subset.2 fun i hi a ha ↦
+    refine' (card_le_of_subset <| biUnion_subset.2 fun i hi a ha ↦
       mem_compl.2 <| not_mem_singleton.2 <| (hf _ hi).ne_bot ha).trans_eq _
     rw [card_compl, Fintype.card_finset, card_singleton]
   induction' s using Finset.cons_induction with i s hi ih generalizing f
@@ -61,9 +61,9 @@ theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Fin
     refine' fun j hj ↦ (hf₁ _ hj).2.2.isUpperSet' ((hf₁ _ hj).2.2.is_max_iff_card_eq.2 _)
     rw [Fintype.card_finset]
     exact (hf₁ _ hj).2.1
-  refine' (card_le_of_subset <| bunionᵢ_mono fun j hj ↦ (hf₁ _ hj).1).trans _
+  refine' (card_le_of_subset <| biUnion_mono fun j hj ↦ (hf₁ _ hj).1).trans _
   nth_rw 1 [cons_eq_insert i]
-  rw [bunionᵢ_insert]
+  rw [biUnion_insert]
   refine' (card_mono <| @le_sup_sdiff _ _ _ <| f' i).trans ((card_union_le _ _).trans _)
   rw [union_sdiff_left, sdiff_eq_inter_compl]
   refine' le_of_mul_le_mul_left _ (pow_pos (zero_lt_two' ℕ) <| Fintype.card α + 1)
@@ -72,8 +72,8 @@ theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Fin
       ((mul_le_mul_left <| pow_pos (zero_lt_two' ℕ) _).2
       (hf₁ _ <| mem_cons_self _ _).2.2.card_le) <|
       (mul_le_mul_left <| zero_lt_two' ℕ).2 <| IsUpperSet.card_inter_le_finset _ _).trans _
-  · rw [coe_bunionᵢ]
-    exact isUpperSet_unionᵢ₂ fun i hi ↦ hf₂ _ <| subset_cons _ hi
+  · rw [coe_biUnion]
+    exact isUpperSet_iUnion₂ fun i hi ↦ hf₂ _ <| subset_cons _ hi
   · rw [coe_compl]
     exact (hf₂ _ <| mem_cons_self _ _).compl
   rw [mul_tsub, card_compl, Fintype.card_finset, mul_left_comm, mul_tsub,
@@ -86,4 +86,4 @@ theorem Finset.card_bunionᵢ_le_of_intersecting (s : Finset ι) (f : ι → Fin
   rw [mul_tsub, two_mul, ← pow_succ,
     ← add_tsub_assoc_of_le (pow_le_pow' (one_le_two : (1 : ℕ) ≤ 2) tsub_le_self),
     tsub_add_eq_add_tsub hs, card_cons, add_tsub_add_eq_tsub_right]
-#align finset.card_bUnion_le_of_intersecting Finset.card_bunionᵢ_le_of_intersecting
+#align finset.card_bUnion_le_of_intersecting Finset.card_biUnion_le_of_intersecting

4c19a16e

feat: port Combinatorics.SetFamily.Kleitman (#2071)

0716ef58

`combinatorics.set_family.kleitman` ⟷ `Mathlib.Combinatorics.SetFamily.Kleitman`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

`Algebra.GroupPower.Order`

`Algebra.GroupPower.CovariantClass`

`Data.Nat.Pow`

Lemmas added

Lemmas removed

Other changes

Renames

Dependencies 7 + 234

combinatorics.set_family.kleitman ⟷ Mathlib.Combinatorics.SetFamily.Kleitman

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Algebra.GroupPower.Order

Algebra.GroupPower.CovariantClass

Data.Nat.Pow

Lemmas added

Lemmas removed

Other changes

Renames

Dependencies 7 + 234

`combinatorics.set_family.kleitman` ⟷ `Mathlib.Combinatorics.SetFamily.Kleitman`

`Algebra.GroupPower.Order`

`Algebra.GroupPower.CovariantClass`

`Data.Nat.Pow`