combinatorics.simple_graph.regularity.equitabilise
⟷
Mathlib.Combinatorics.SimpleGraph.Regularity.Equitabilise
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.
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(last sync)
Define the increment partition and prove its two crucial properties:
This is all internal to the proof of SRL, so I made most lemmas private
.
Co-authored-by: Bhavik Mehta <bhavikmehta8@gmail.com>
@@ -22,6 +22,10 @@ This file allows to blow partitions up into parts of controlled size. Given a pa
* `finpartition.equitabilise`: `P.equitabilise h` where `h : a * m + b * (m + 1)` is a partition
with `a` parts of size `m` and `b` parts of size `m + 1` which almost refines `P`.
* `finpartition.exists_equipartition_card_eq`: We can find equipartitions of arbitrary size.
+
+## References
+
+[Yaël Dillies, Bhavik Mehta, *Formalising Szemerédi’s Regularity Lemma in Lean*][srl_itp]
-/
open finset nat
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(first ported)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -52,7 +52,7 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
-- Get rid of the easy case `m = 0`
obtain rfl | m_pos := m.eq_zero_or_pos
· refine' ⟨⊥, by simp, _, by simpa using hs.symm⟩
- simp only [le_zero_iff, card_eq_zero, mem_bUnion, exists_prop, mem_filter, id.def, and_assoc',
+ simp only [le_zero_iff, card_eq_zero, mem_bUnion, exists_prop, mem_filter, id.def, and_assoc,
sdiff_eq_empty_iff_subset, subset_iff]
exact fun x hx a ha =>
⟨{a}, mem_map_of_mem _ (P.le hx ha), singleton_subset_iff.2 ha, mem_singleton_self _⟩
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -60,10 +60,10 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
induction' s using Finset.strongInduction with s ih generalizing P a b
-- If `a = b = 0`, then `s = ∅` and we can partition into zero parts
by_cases hab : a = 0 ∧ b = 0
- · simp only [hab.1, hab.2, add_zero, MulZeroClass.zero_mul, eq_comm, card_eq_zero] at hs
+ · simp only [hab.1, hab.2, add_zero, MulZeroClass.zero_mul, eq_comm, card_eq_zero] at hs
subst hs
exact ⟨Finpartition.empty _, by simp, by simp [Unique.eq_default P], by simp [hab.2]⟩
- simp_rw [not_and_or, ← Ne.def, ← pos_iff_ne_zero] at hab
+ simp_rw [not_and_or, ← Ne.def, ← pos_iff_ne_zero] at hab
-- `n` will be the size of the smallest part
set n := if 0 < a then m else m + 1 with hn
-- Some easy facts about it
@@ -103,7 +103,7 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
rw [card_insert_of_not_mem fun H => _, hR₃, if_neg ha, tsub_add_cancel_of_le]
· exact hab.resolve_left ha
· exact ht.ne_empty (le_sdiff_iff.1 <| R.le <| filter_subset _ _ H)
- push_neg at h
+ push_neg at h
obtain ⟨u, hu₁, hu₂⟩ := h
obtain ⟨t, htu, htn⟩ := exists_smaller_set _ _ (hn₁.trans hu₂)
have ht : t.nonempty := by rwa [← card_pos, htn]
@@ -227,7 +227,7 @@ variable (s)
theorem exists_equipartition_card_eq (hn : n ≠ 0) (hs : n ≤ s.card) :
∃ P : Finpartition s, P.IsEquipartition ∧ P.parts.card = n :=
by
- rw [← pos_iff_ne_zero] at hn
+ rw [← pos_iff_ne_zero] at hn
have : (n - s.card % n) * (s.card / n) + s.card % n * (s.card / n + 1) = s.card := by
rw [tsub_mul, mul_add, ← add_assoc,
tsub_add_cancel_of_le (Nat.mul_le_mul_right _ (mod_lt _ hn).le), mul_one, add_comm,
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,7 +3,7 @@ Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-/
-import Mathbin.Order.Partition.Equipartition
+import Order.Partition.Equipartition
#align_import combinatorics.simple_graph.regularity.equitabilise from "leanprover-community/mathlib"@"bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,14 +2,11 @@
Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.equitabilise
-! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Order.Partition.Equipartition
+#align_import combinatorics.simple_graph.regularity.equitabilise from "leanprover-community/mathlib"@"bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d"
+
/-!
# Equitabilising a partition
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -40,6 +40,7 @@ namespace Finpartition
variable {α : Type _} [DecidableEq α] {s t : Finset α} {m n a b : ℕ} {P : Finpartition s}
+#print Finpartition.equitabilise_aux /-
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, we can
find a new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the
union of parts of `Q` plus at most `m` extra elements, there are `b` parts of size `m + 1` and
@@ -143,9 +144,11 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
· rw [card_insert_of_not_mem fun H => _, hR₃, if_neg h, Nat.sub_add_cancel (hab.resolve_left h)]
exact ht.ne_empty (le_sdiff_iff.1 <| R.le <| filter_subset _ _ H)
#align finpartition.equitabilise_aux Finpartition.equitabilise_aux
+-/
variable (P) (h : a * m + b * (m + 1) = s.card)
+#print Finpartition.equitabilise /-
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, build a
new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the union of
parts of `Q` plus at most `m` extra elements, there are `b` parts of size `m + 1` and (provided
@@ -154,25 +157,33 @@ hence `a + b` parts in total. -/
noncomputable def equitabilise : Finpartition s :=
(P.equitabilise_aux h).some
#align finpartition.equitabilise Finpartition.equitabilise
+-/
variable {P h}
+#print Finpartition.card_eq_of_mem_parts_equitabilise /-
theorem card_eq_of_mem_parts_equitabilise :
t ∈ (P.equitabilise h).parts → t.card = m ∨ t.card = m + 1 :=
(P.equitabilise_aux h).choose_spec.1 _
#align finpartition.card_eq_of_mem_parts_equitabilise Finpartition.card_eq_of_mem_parts_equitabilise
+-/
+#print Finpartition.equitabilise_isEquipartition /-
theorem equitabilise_isEquipartition : (P.equitabilise h).IsEquipartition :=
Set.equitableOn_iff_exists_eq_eq_add_one.2 ⟨m, fun u => card_eq_of_mem_parts_equitabilise⟩
#align finpartition.equitabilise_is_equipartition Finpartition.equitabilise_isEquipartition
+-/
variable (P h)
+#print Finpartition.card_filter_equitabilise_big /-
theorem card_filter_equitabilise_big :
((P.equitabilise h).parts.filterₓ fun u : Finset α => u.card = m + 1).card = b :=
(P.equitabilise_aux h).choose_spec.2.2
#align finpartition.card_filter_equitabilise_big Finpartition.card_filter_equitabilise_big
+-/
+#print Finpartition.card_filter_equitabilise_small /-
theorem card_filter_equitabilise_small (hm : m ≠ 0) :
((P.equitabilise h).parts.filterₓ fun u : Finset α => u.card = m).card = a :=
by
@@ -193,7 +204,9 @@ theorem card_filter_equitabilise_small (hm : m ≠ 0) :
apply succ_ne_self m _
exact (hb i h).symm.trans (ha i h)
#align finpartition.card_filter_equitabilise_small Finpartition.card_filter_equitabilise_small
+-/
+#print Finpartition.card_parts_equitabilise /-
theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card = a + b :=
by
rw [← filter_true_of_mem fun x => card_eq_of_mem_parts_equitabilise, filter_or, card_union_eq,
@@ -201,14 +214,18 @@ theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card =
exact disjoint_filter.2 fun x _ h₀ h₁ => Nat.succ_ne_self m <| h₁.symm.trans h₀
infer_instance
#align finpartition.card_parts_equitabilise Finpartition.card_parts_equitabilise
+-/
+#print Finpartition.card_parts_equitabilise_subset_le /-
theorem card_parts_equitabilise_subset_le :
t ∈ P.parts → (t \ ((P.equitabilise h).parts.filterₓ fun u => u ⊆ t).biUnion id).card ≤ m :=
(Classical.choose_spec <| P.equitabilise_aux h).2.1 t
#align finpartition.card_parts_equitabilise_subset_le Finpartition.card_parts_equitabilise_subset_le
+-/
variable (s)
+#print Finpartition.exists_equipartition_card_eq /-
/-- We can find equipartitions of arbitrary size. -/
theorem exists_equipartition_card_eq (hn : n ≠ 0) (hs : n ≤ s.card) :
∃ P : Finpartition s, P.IsEquipartition ∧ P.parts.card = n :=
@@ -223,6 +240,7 @@ theorem exists_equipartition_card_eq (hn : n ≠ 0) (hs : n ≤ s.card) :
equitabilise_is_equipartition, _⟩
rw [card_parts_equitabilise _ _ (Nat.div_pos hs hn).ne', tsub_add_cancel_of_le (mod_lt _ hn).le]
#align finpartition.exists_equipartition_card_eq Finpartition.exists_equipartition_card_eq
+-/
end Finpartition
mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297
@@ -105,7 +105,7 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
rw [card_insert_of_not_mem fun H => _, hR₃, if_neg ha, tsub_add_cancel_of_le]
· exact hab.resolve_left ha
· exact ht.ne_empty (le_sdiff_iff.1 <| R.le <| filter_subset _ _ H)
- push_neg at h
+ push_neg at h
obtain ⟨u, hu₁, hu₂⟩ := h
obtain ⟨t, htu, htn⟩ := exists_smaller_set _ _ (hn₁.trans hu₂)
have ht : t.nonempty := by rwa [← card_pos, htn]
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -62,10 +62,10 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
induction' s using Finset.strongInduction with s ih generalizing P a b
-- If `a = b = 0`, then `s = ∅` and we can partition into zero parts
by_cases hab : a = 0 ∧ b = 0
- · simp only [hab.1, hab.2, add_zero, MulZeroClass.zero_mul, eq_comm, card_eq_zero] at hs
+ · simp only [hab.1, hab.2, add_zero, MulZeroClass.zero_mul, eq_comm, card_eq_zero] at hs
subst hs
exact ⟨Finpartition.empty _, by simp, by simp [Unique.eq_default P], by simp [hab.2]⟩
- simp_rw [not_and_or, ← Ne.def, ← pos_iff_ne_zero] at hab
+ simp_rw [not_and_or, ← Ne.def, ← pos_iff_ne_zero] at hab
-- `n` will be the size of the smallest part
set n := if 0 < a then m else m + 1 with hn
-- Some easy facts about it
@@ -105,7 +105,7 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
rw [card_insert_of_not_mem fun H => _, hR₃, if_neg ha, tsub_add_cancel_of_le]
· exact hab.resolve_left ha
· exact ht.ne_empty (le_sdiff_iff.1 <| R.le <| filter_subset _ _ H)
- push_neg at h
+ push_neg at h
obtain ⟨u, hu₁, hu₂⟩ := h
obtain ⟨t, htu, htn⟩ := exists_smaller_set _ _ (hn₁.trans hu₂)
have ht : t.nonempty := by rwa [← card_pos, htn]
@@ -213,7 +213,7 @@ variable (s)
theorem exists_equipartition_card_eq (hn : n ≠ 0) (hs : n ≤ s.card) :
∃ P : Finpartition s, P.IsEquipartition ∧ P.parts.card = n :=
by
- rw [← pos_iff_ne_zero] at hn
+ rw [← pos_iff_ne_zero] at hn
have : (n - s.card % n) * (s.card / n) + s.card % n * (s.card / n + 1) = s.card := by
rw [tsub_mul, mul_add, ← add_assoc,
tsub_add_cancel_of_le (Nat.mul_le_mul_right _ (mod_lt _ hn).le), mul_one, add_comm,
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -40,9 +40,6 @@ namespace Finpartition
variable {α : Type _} [DecidableEq α] {s t : Finset α} {m n a b : ℕ} {P : Finpartition s}
-/- warning: finpartition.equitabilise_aux -> Finpartition.equitabilise_aux is a dubious translation:
-<too large>
-Case conversion may be inaccurate. Consider using '#align finpartition.equitabilise_aux Finpartition.equitabilise_auxₓ'. -/
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, we can
find a new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the
union of parts of `Q` plus at most `m` extra elements, there are `b` parts of size `m + 1` and
@@ -149,12 +146,6 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
variable (P) (h : a * m + b * (m + 1) = s.card)
-/- warning: finpartition.equitabilise -> Finpartition.equitabilise is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat}, (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) -> (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)) -> (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s}, (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)) -> (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s)
-Case conversion may be inaccurate. Consider using '#align finpartition.equitabilise Finpartition.equitabiliseₓ'. -/
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, build a
new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the union of
parts of `Q` plus at most `m` extra elements, there are `b` parts of size `m + 1` and (provided
@@ -166,46 +157,22 @@ noncomputable def equitabilise : Finpartition s :=
variable {P h}
-/- warning: finpartition.card_eq_of_mem_parts_equitabilise -> Finpartition.card_eq_of_mem_parts_equitabilise is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s} {h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)}, (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) -> (Or (Eq.{1} Nat (Finset.card.{u1} α t) m) (Eq.{1} Nat (Finset.card.{u1} α t) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s} {h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)}, (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) -> (Or (Eq.{1} Nat (Finset.card.{u1} α t) m) (Eq.{1} Nat (Finset.card.{u1} α t) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))))
-Case conversion may be inaccurate. Consider using '#align finpartition.card_eq_of_mem_parts_equitabilise Finpartition.card_eq_of_mem_parts_equitabiliseₓ'. -/
theorem card_eq_of_mem_parts_equitabilise :
t ∈ (P.equitabilise h).parts → t.card = m ∨ t.card = m + 1 :=
(P.equitabilise_aux h).choose_spec.1 _
#align finpartition.card_eq_of_mem_parts_equitabilise Finpartition.card_eq_of_mem_parts_equitabilise
-/- warning: finpartition.equitabilise_is_equipartition -> Finpartition.equitabilise_isEquipartition is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s} {h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)}, Finpartition.IsEquipartition.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s} {h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)}, Finpartition.IsEquipartition.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h)
-Case conversion may be inaccurate. Consider using '#align finpartition.equitabilise_is_equipartition Finpartition.equitabilise_isEquipartitionₓ'. -/
theorem equitabilise_isEquipartition : (P.equitabilise h).IsEquipartition :=
Set.equitableOn_iff_exists_eq_eq_add_one.2 ⟨m, fun u => card_eq_of_mem_parts_equitabilise⟩
#align finpartition.equitabilise_is_equipartition Finpartition.equitabilise_isEquipartition
variable (P h)
-/- warning: finpartition.card_filter_equitabilise_big -> Finpartition.card_filter_equitabilise_big is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)), Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α u) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (a : Finset.{u1} α) => Nat.decidableEq (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h)))) b
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)), Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α u) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (a : Finset.{u1} α) => instDecidableEqNat (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h)))) b
-Case conversion may be inaccurate. Consider using '#align finpartition.card_filter_equitabilise_big Finpartition.card_filter_equitabilise_bigₓ'. -/
theorem card_filter_equitabilise_big :
((P.equitabilise h).parts.filterₓ fun u : Finset α => u.card = m + 1).card = b :=
(P.equitabilise_aux h).choose_spec.2.2
#align finpartition.card_filter_equitabilise_big Finpartition.card_filter_equitabilise_big
-/- warning: finpartition.card_filter_equitabilise_small -> Finpartition.card_filter_equitabilise_small is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)), (Ne.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α u) m) (fun (a : Finset.{u1} α) => Nat.decidableEq (Finset.card.{u1} α a) m) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h)))) a)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)), (Ne.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α u) m) (fun (a : Finset.{u1} α) => instDecidableEqNat (Finset.card.{u1} α a) m) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h)))) a)
-Case conversion may be inaccurate. Consider using '#align finpartition.card_filter_equitabilise_small Finpartition.card_filter_equitabilise_smallₓ'. -/
theorem card_filter_equitabilise_small (hm : m ≠ 0) :
((P.equitabilise h).parts.filterₓ fun u : Finset α => u.card = m).card = a :=
by
@@ -227,12 +194,6 @@ theorem card_filter_equitabilise_small (hm : m ≠ 0) :
exact (hb i h).symm.trans (ha i h)
#align finpartition.card_filter_equitabilise_small Finpartition.card_filter_equitabilise_small
-/- warning: finpartition.card_parts_equitabilise -> Finpartition.card_parts_equitabilise is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)), (Ne.{1} Nat m (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) a b))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)), (Ne.{1} Nat m (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) a b))
-Case conversion may be inaccurate. Consider using '#align finpartition.card_parts_equitabilise Finpartition.card_parts_equitabiliseₓ'. -/
theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card = a + b :=
by
rw [← filter_true_of_mem fun x => card_eq_of_mem_parts_equitabilise, filter_or, card_union_eq,
@@ -241,12 +202,6 @@ theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card =
infer_instance
#align finpartition.card_parts_equitabilise Finpartition.card_parts_equitabilise
-/- warning: finpartition.card_parts_equitabilise_subset_le -> Finpartition.card_parts_equitabilise_subset_le is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.hasSdiff.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) t (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) u t) (fun (a : Finset.{u1} α) => Finset.decidableDforallFinset.{u1} α a (fun (a_1 : α) (ᾰ : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 t) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Finset.decidableMem.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a_1 t)) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (id.{succ u1} (Finset.{u1} α))))) m)
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.instSDiffFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) t (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) u t) (fun (a : Finset.{u1} α) => Finset.decidableSubsetFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a t) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (id.{succ u1} (Finset.{u1} α))))) m)
-Case conversion may be inaccurate. Consider using '#align finpartition.card_parts_equitabilise_subset_le Finpartition.card_parts_equitabilise_subset_leₓ'. -/
theorem card_parts_equitabilise_subset_le :
t ∈ P.parts → (t \ ((P.equitabilise h).parts.filterₓ fun u => u ⊆ t).biUnion id).card ≤ m :=
(Classical.choose_spec <| P.equitabilise_aux h).2.1 t
@@ -254,12 +209,6 @@ theorem card_parts_equitabilise_subset_le :
variable (s)
-/- warning: finpartition.exists_equipartition_card_eq -> Finpartition.exists_equipartition_card_eq is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Finset.{u1} α) {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (OfNat.mk.{0} Nat 0 (Zero.zero.{0} Nat Nat.hasZero)))) -> (LE.le.{0} Nat Nat.hasLe n (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (fun (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) => And (Finpartition.IsEquipartition.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) n)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] (s : Finset.{u1} α) {n : Nat}, (Ne.{1} Nat n (OfNat.ofNat.{0} Nat 0 (instOfNatNat 0))) -> (LE.le.{0} Nat instLENat n (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (fun (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) => And (Finpartition.IsEquipartition.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s P) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) n)))
-Case conversion may be inaccurate. Consider using '#align finpartition.exists_equipartition_card_eq Finpartition.exists_equipartition_card_eqₓ'. -/
/-- We can find equipartitions of arbitrary size. -/
theorem exists_equipartition_card_eq (hn : n ≠ 0) (hs : n ≤ s.card) :
∃ P : Finpartition s, P.IsEquipartition ∧ P.parts.card = n :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -41,10 +41,7 @@ namespace Finpartition
variable {α : Type _} [DecidableEq α] {s t : Finset α} {m n a b : ℕ} {P : Finpartition s}
/- warning: finpartition.equitabilise_aux -> Finpartition.equitabilise_aux is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s), (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (fun (Q : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) => And (forall (x : Finset.{u1} α), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q)) -> (Or (Eq.{1} Nat (Finset.card.{u1} α x) m) (Eq.{1} Nat (Finset.card.{u1} α x) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))))) (And (forall (x : Finset.{u1} α), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.hasSdiff.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) x (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (y : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) y x) (fun (a : Finset.{u1} α) => Finset.decidableDforallFinset.{u1} α a (fun (a_1 : α) (ᾰ : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 x) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Finset.decidableMem.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a_1 x)) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q)) (id.{succ u1} (Finset.{u1} α))))) m)) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (i : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α i) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (a : Finset.{u1} α) => Nat.decidableEq (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q))) b))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s}, (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (fun (Q : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) => And (forall (x : Finset.{u1} α), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q)) -> (Or (Eq.{1} Nat (Finset.card.{u1} α x) m) (Eq.{1} Nat (Finset.card.{u1} α x) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))))) (And (forall (x : Finset.{u1} α), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.instSDiffFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) x (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (y : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) y x) (fun (a : Finset.{u1} α) => Finset.decidableSubsetFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a x) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q)) (id.{succ u1} (Finset.{u1} α))))) m)) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (i : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α i) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (a : Finset.{u1} α) => instDecidableEqNat (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q))) b))))
+<too large>
Case conversion may be inaccurate. Consider using '#align finpartition.equitabilise_aux Finpartition.equitabilise_auxₓ'. -/
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, we can
find a new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the
mathlib commit https://github.com/leanprover-community/mathlib/commit/33c67ae661dd8988516ff7f247b0be3018cdd952
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.equitabilise
-! leanprover-community/mathlib commit b6da1a0b3e7cd83b1f744c49ce48ef8c6307d2f6
+! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -27,6 +27,10 @@ This file allows to blow partitions up into parts of controlled size. Given a pa
* `finpartition.equitabilise`: `P.equitabilise h` where `h : a * m + b * (m + 1)` is a partition
with `a` parts of size `m` and `b` parts of size `m + 1` which almost refines `P`.
* `finpartition.exists_equipartition_card_eq`: We can find equipartitions of arbitrary size.
+
+## References
+
+[Yaël Dillies, Bhavik Mehta, *Formalising Szemerédi’s Regularity Lemma in Lean*][srl_itp]
-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/e3fb84046afd187b710170887195d50bada934ee
@@ -38,9 +38,9 @@ variable {α : Type _} [DecidableEq α] {s t : Finset α} {m n a b : ℕ} {P : F
/- warning: finpartition.equitabilise_aux -> Finpartition.equitabilise_aux is a dubious translation:
lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s), (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (fun (Q : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) => And (forall (x : Finset.{u1} α), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q)) -> (Or (Eq.{1} Nat (Finset.card.{u1} α x) m) (Eq.{1} Nat (Finset.card.{u1} α x) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))))) (And (forall (x : Finset.{u1} α), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.hasSdiff.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) x (Finset.bunionᵢ.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (y : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) y x) (fun (a : Finset.{u1} α) => Finset.decidableDforallFinset.{u1} α a (fun (a_1 : α) (ᾰ : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 x) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Finset.decidableMem.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a_1 x)) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q)) (id.{succ u1} (Finset.{u1} α))))) m)) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (i : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α i) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (a : Finset.{u1} α) => Nat.decidableEq (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q))) b))))
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s), (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (fun (Q : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) => And (forall (x : Finset.{u1} α), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q)) -> (Or (Eq.{1} Nat (Finset.card.{u1} α x) m) (Eq.{1} Nat (Finset.card.{u1} α x) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))))) (And (forall (x : Finset.{u1} α), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.hasSdiff.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) x (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (y : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) y x) (fun (a : Finset.{u1} α) => Finset.decidableDforallFinset.{u1} α a (fun (a_1 : α) (ᾰ : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 x) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Finset.decidableMem.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a_1 x)) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q)) (id.{succ u1} (Finset.{u1} α))))) m)) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (i : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α i) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (fun (a : Finset.{u1} α) => Nat.decidableEq (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne))))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s Q))) b))))
but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s}, (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (fun (Q : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) => And (forall (x : Finset.{u1} α), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q)) -> (Or (Eq.{1} Nat (Finset.card.{u1} α x) m) (Eq.{1} Nat (Finset.card.{u1} α x) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))))) (And (forall (x : Finset.{u1} α), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.instSDiffFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) x (Finset.bunionᵢ.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (y : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) y x) (fun (a : Finset.{u1} α) => Finset.decidableSubsetFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a x) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q)) (id.{succ u1} (Finset.{u1} α))))) m)) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (i : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α i) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (a : Finset.{u1} α) => instDecidableEqNat (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q))) b))))
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} {P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s}, (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)) -> (Exists.{succ u1} (Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (fun (Q : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) => And (forall (x : Finset.{u1} α), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q)) -> (Or (Eq.{1} Nat (Finset.card.{u1} α x) m) (Eq.{1} Nat (Finset.card.{u1} α x) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))))) (And (forall (x : Finset.{u1} α), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) x (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.instSDiffFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) x (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (y : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) y x) (fun (a : Finset.{u1} α) => Finset.decidableSubsetFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a x) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q)) (id.{succ u1} (Finset.{u1} α))))) m)) (Eq.{1} Nat (Finset.card.{u1} (Finset.{u1} α) (Finset.filter.{u1} (Finset.{u1} α) (fun (i : Finset.{u1} α) => Eq.{1} Nat (Finset.card.{u1} α i) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (fun (a : Finset.{u1} α) => instDecidableEqNat (Finset.card.{u1} α a) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s Q))) b))))
Case conversion may be inaccurate. Consider using '#align finpartition.equitabilise_aux Finpartition.equitabilise_auxₓ'. -/
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, we can
find a new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the
@@ -50,7 +50,7 @@ union of parts of `Q` plus at most `m` extra elements, there are `b` parts of si
theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card) :
∃ Q : Finpartition s,
(∀ x : Finset α, x ∈ Q.parts → x.card = m ∨ x.card = m + 1) ∧
- (∀ x, x ∈ P.parts → (x \ (Q.parts.filterₓ fun y => y ⊆ x).bunionᵢ id).card ≤ m) ∧
+ (∀ x, x ∈ P.parts → (x \ (Q.parts.filterₓ fun y => y ⊆ x).biUnion id).card ≤ m) ∧
(Q.parts.filterₓ fun i => card i = m + 1).card = b :=
by
-- Get rid of the easy case `m = 0`
@@ -242,12 +242,12 @@ theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card =
/- warning: finpartition.card_parts_equitabilise_subset_le -> Finpartition.card_parts_equitabilise_subset_le is a dubious translation:
lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.hasSdiff.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) t (Finset.bunionᵢ.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) u t) (fun (a : Finset.{u1} α) => Finset.decidableDforallFinset.{u1} α a (fun (a_1 : α) (ᾰ : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 t) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Finset.decidableMem.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a_1 t)) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (id.{succ u1} (Finset.{u1} α))))) m)
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) m (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))))) (Finset.card.{u1} α s)), (Membership.Mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.hasMem.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s P)) -> (LE.le.{0} Nat Nat.hasLe (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.hasSdiff.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) t (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.hasSubset.{u1} α) u t) (fun (a : Finset.{u1} α) => Finset.decidableDforallFinset.{u1} α a (fun (a_1 : α) (ᾰ : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 t) (fun (a_1 : α) (h : Membership.Mem.{u1, u1} α (Finset.{u1} α) (Finset.hasMem.{u1} α) a_1 a) => Finset.decidableMem.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a_1 t)) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.lattice.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.orderBot.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (id.{succ u1} (Finset.{u1} α))))) m)
but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.instSDiffFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) t (Finset.bunionᵢ.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) u t) (fun (a : Finset.{u1} α) => Finset.decidableSubsetFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a t) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (id.{succ u1} (Finset.{u1} α))))) m)
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {s : Finset.{u1} α} {t : Finset.{u1} α} {m : Nat} {a : Nat} {b : Nat} (P : Finpartition.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s) (h : Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) a m) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) b (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) m (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))))) (Finset.card.{u1} α s)), (Membership.mem.{u1, u1} (Finset.{u1} α) (Finset.{u1} (Finset.{u1} α)) (Finset.instMembershipFinset.{u1} (Finset.{u1} α)) t (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s P)) -> (LE.le.{0} Nat instLENat (Finset.card.{u1} α (SDiff.sdiff.{u1} (Finset.{u1} α) (Finset.instSDiffFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) t (Finset.biUnion.{u1, u1} (Finset.{u1} α) α (fun (a : α) (b : α) => _inst_1 a b) (Finset.filter.{u1} (Finset.{u1} α) (fun (u : Finset.{u1} α) => HasSubset.Subset.{u1} (Finset.{u1} α) (Finset.instHasSubsetFinset.{u1} α) u t) (fun (a : Finset.{u1} α) => Finset.decidableSubsetFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a t) (Finpartition.parts.{u1} (Finset.{u1} α) (Finset.instLatticeFinset.{u1} α (fun (a : α) (b : α) => _inst_1 a b)) (Finset.instOrderBotFinsetToLEToPreorderPartialOrder.{u1} α) s (Finpartition.equitabilise.{u1} α (fun (a : α) (b : α) => _inst_1 a b) s m a b P h))) (id.{succ u1} (Finset.{u1} α))))) m)
Case conversion may be inaccurate. Consider using '#align finpartition.card_parts_equitabilise_subset_le Finpartition.card_parts_equitabilise_subset_leₓ'. -/
theorem card_parts_equitabilise_subset_le :
- t ∈ P.parts → (t \ ((P.equitabilise h).parts.filterₓ fun u => u ⊆ t).bunionᵢ id).card ≤ m :=
+ t ∈ P.parts → (t \ ((P.equitabilise h).parts.filterₓ fun u => u ⊆ t).biUnion id).card ≤ m :=
(Classical.choose_spec <| P.equitabilise_aux h).2.1 t
#align finpartition.card_parts_equitabilise_subset_le Finpartition.card_parts_equitabilise_subset_le
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -64,7 +64,7 @@ theorem equitabilise_aux (P : Finpartition s) (hs : a * m + b * (m + 1) = s.card
induction' s using Finset.strongInduction with s ih generalizing P a b
-- If `a = b = 0`, then `s = ∅` and we can partition into zero parts
by_cases hab : a = 0 ∧ b = 0
- · simp only [hab.1, hab.2, add_zero, zero_mul, eq_comm, card_eq_zero] at hs
+ · simp only [hab.1, hab.2, add_zero, MulZeroClass.zero_mul, eq_comm, card_eq_zero] at hs
subst hs
exact ⟨Finpartition.empty _, by simp, by simp [Unique.eq_default P], by simp [hab.2]⟩
simp_rw [not_and_or, ← Ne.def, ← pos_iff_ne_zero] at hab
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
These are changes from #11997, the latest adaptation PR for nightly-2024-04-07, which can be made directly on master.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Ruben Van de Velde <65514131+Ruben-VandeVelde@users.noreply.github.com>
@@ -47,7 +47,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
-- Get rid of the easy case `m = 0`
obtain rfl | m_pos := m.eq_zero_or_pos
· refine' ⟨⊥, by simp, _, by simpa using hs.symm⟩
- simp only [Nat.le_zero, card_eq_zero, mem_biUnion, exists_prop, mem_filter, id.def, and_assoc,
+ simp only [le_zero_iff, card_eq_zero, mem_biUnion, exists_prop, mem_filter, id, and_assoc,
sdiff_eq_empty_iff_subset, subset_iff]
exact fun x hx a ha =>
⟨{a}, mem_map_of_mem _ (P.le hx ha), singleton_subset_iff.2 ha, mem_singleton_self _⟩
@@ -110,9 +110,9 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
· simp only [mem_insert, forall_eq_or_imp, extend_parts, and_iff_left hR₁, htn, hn]
exact ite_eq_or_eq _ _ _
· conv in _ ∈ _ => rw [← insert_erase hu₁]
- simp only [and_imp, mem_insert, forall_eq_or_imp, Ne.def, extend_parts]
+ simp only [and_imp, mem_insert, forall_eq_or_imp, Ne, extend_parts]
refine' ⟨_, fun x hx => (card_le_card _).trans <| hR₂ x _⟩
- · simp only [filter_insert, if_pos htu, biUnion_insert, mem_erase, id.def]
+ · simp only [filter_insert, if_pos htu, biUnion_insert, mem_erase, id]
obtain rfl | hut := eq_or_ne u t
· rw [sdiff_eq_empty_iff_subset.2 (subset_union_left _ _)]
exact bot_le
@@ -121,7 +121,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
(hR₂ (u \ t) <| P.mem_avoid.2 ⟨u, hu₁, fun i => hut <| i.antisymm htu, rfl⟩)
-- Porting note: `not_and` required because `∃ x ∈ s, p x` is defined differently
simp only [not_exists, not_and, mem_biUnion, and_imp, mem_union, mem_filter, mem_sdiff,
- id.def, not_or]
+ id, not_or]
exact fun hi₁ hi₂ hi₃ =>
⟨⟨hi₁, hi₂⟩, fun x hx hx' => hi₃ _ hx <| hx'.trans <| sdiff_subset _ _⟩
· apply sdiff_subset_sdiff Subset.rfl (biUnion_subset_biUnion_of_subset_left _ _)
LinearOrderedCommGroupWithZero
(#11716)
Reconstitute the file Algebra.Order.Monoid.WithZero
from three files:
Algebra.Order.Monoid.WithZero.Defs
Algebra.Order.Monoid.WithZero.Basic
Algebra.Order.WithZero
Avoid importing it in many files. Most uses were just to get le_zero_iff
to work on Nat
.
Before
After
@@ -47,7 +47,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
-- Get rid of the easy case `m = 0`
obtain rfl | m_pos := m.eq_zero_or_pos
· refine' ⟨⊥, by simp, _, by simpa using hs.symm⟩
- simp only [le_zero_iff, card_eq_zero, mem_biUnion, exists_prop, mem_filter, id.def, and_assoc,
+ simp only [Nat.le_zero, card_eq_zero, mem_biUnion, exists_prop, mem_filter, id.def, and_assoc,
sdiff_eq_empty_iff_subset, subset_iff]
exact fun x hx a ha =>
⟨{a}, mem_map_of_mem _ (P.le hx ha), singleton_subset_iff.2 ha, mem_singleton_self _⟩
@@ -189,7 +189,7 @@ theorem card_filter_equitabilise_small (hm : m ≠ 0) :
theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card = a + b := by
rw [← filter_true_of_mem fun x => card_eq_of_mem_parts_equitabilise, filter_or,
card_union_of_disjoint, P.card_filter_equitabilise_small _ hm, P.card_filter_equitabilise_big]
- -- Porting note: was `infer_instance`
+ -- Porting note (#11187): was `infer_instance`
exact disjoint_filter.2 fun x _ h₀ h₁ => Nat.succ_ne_self m <| h₁.symm.trans h₀
#align finpartition.card_parts_equitabilise Finpartition.card_parts_equitabilise
(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
@@ -187,8 +187,8 @@ theorem card_filter_equitabilise_small (hm : m ≠ 0) :
#align finpartition.card_filter_equitabilise_small Finpartition.card_filter_equitabilise_small
theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card = a + b := by
- rw [← filter_true_of_mem fun x => card_eq_of_mem_parts_equitabilise, filter_or, card_union_eq,
- P.card_filter_equitabilise_small _ hm, P.card_filter_equitabilise_big]
+ rw [← filter_true_of_mem fun x => card_eq_of_mem_parts_equitabilise, filter_or,
+ card_union_of_disjoint, P.card_filter_equitabilise_small _ hm, P.card_filter_equitabilise_big]
-- Porting note: was `infer_instance`
exact disjoint_filter.2 fun x _ h₀ h₁ => Nat.succ_ne_self m <| h₁.symm.trans h₀
#align finpartition.card_parts_equitabilise Finpartition.card_parts_equitabilise
@@ -90,7 +90,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
refine' ⟨R.extend ht.ne_empty sdiff_disjoint (sdiff_sup_cancel hts), _, _, _⟩
· simp only [extend_parts, mem_insert, forall_eq_or_imp, and_iff_left hR₁, htn, hn]
exact ite_eq_or_eq _ _ _
- · exact fun x hx => (card_le_card <| sdiff_subset _ _).trans (lt_succ_iff.1 <| h _ hx)
+ · exact fun x hx => (card_le_card <| sdiff_subset _ _).trans (Nat.lt_succ_iff.1 <| h _ hx)
simp_rw [extend_parts, filter_insert, htn, m.succ_ne_self.symm.ite_eq_right_iff]
split_ifs with ha
· rw [hR₃, if_pos ha]
@@ -68,10 +68,11 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
ite (0 < a) (a - 1) a * m + ite (0 < a) b (b - 1) * (m + 1) = s.card - n := by
rw [hn, ← hs]
split_ifs with h <;> rw [tsub_mul, one_mul]
- · refine' ⟨m_pos, le_succ _, le_add_right (le_mul_of_pos_left ‹0 < a›), _⟩
- rw [tsub_add_eq_add_tsub (le_mul_of_pos_left h)]
- · refine' ⟨succ_pos', le_rfl, le_add_left (le_mul_of_pos_left <| hab.resolve_left ‹¬0 < a›), _⟩
- rw [← add_tsub_assoc_of_le (le_mul_of_pos_left <| hab.resolve_left ‹¬0 < a›)]
+ · refine' ⟨m_pos, le_succ _, le_add_right (Nat.le_mul_of_pos_left _ ‹0 < a›), _⟩
+ rw [tsub_add_eq_add_tsub (Nat.le_mul_of_pos_left _ h)]
+ · refine' ⟨succ_pos', le_rfl,
+ le_add_left (Nat.le_mul_of_pos_left _ <| hab.resolve_left ‹¬0 < a›), _⟩
+ rw [← add_tsub_assoc_of_le (Nat.le_mul_of_pos_left _ <| hab.resolve_left ‹¬0 < a›)]
/- We will call the inductive hypothesis on a partition of `s \ t` for a carefully chosen `t ⊆ s`.
To decide which, however, we must distinguish the case where all parts of `P` have size `m` (in
which case we take `t` to be an arbitrary subset of `s` of size `n`) from the case where at
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
@@ -89,7 +89,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
refine' ⟨R.extend ht.ne_empty sdiff_disjoint (sdiff_sup_cancel hts), _, _, _⟩
· simp only [extend_parts, mem_insert, forall_eq_or_imp, and_iff_left hR₁, htn, hn]
exact ite_eq_or_eq _ _ _
- · exact fun x hx => (card_le_of_subset <| sdiff_subset _ _).trans (lt_succ_iff.1 <| h _ hx)
+ · exact fun x hx => (card_le_card <| sdiff_subset _ _).trans (lt_succ_iff.1 <| h _ hx)
simp_rw [extend_parts, filter_insert, htn, m.succ_ne_self.symm.ite_eq_right_iff]
split_ifs with ha
· rw [hR₃, if_pos ha]
@@ -110,13 +110,13 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
exact ite_eq_or_eq _ _ _
· conv in _ ∈ _ => rw [← insert_erase hu₁]
simp only [and_imp, mem_insert, forall_eq_or_imp, Ne.def, extend_parts]
- refine' ⟨_, fun x hx => (card_le_of_subset _).trans <| hR₂ x _⟩
+ refine' ⟨_, fun x hx => (card_le_card _).trans <| hR₂ x _⟩
· simp only [filter_insert, if_pos htu, biUnion_insert, mem_erase, id.def]
obtain rfl | hut := eq_or_ne u t
· rw [sdiff_eq_empty_iff_subset.2 (subset_union_left _ _)]
exact bot_le
refine'
- (card_le_of_subset fun i => _).trans
+ (card_le_card fun i => _).trans
(hR₂ (u \ t) <| P.mem_avoid.2 ⟨u, hu₁, fun i => hut <| i.antisymm htu, rfl⟩)
-- Porting note: `not_and` required because `∃ x ∈ s, p x` is defined differently
simp only [not_exists, not_and, mem_biUnion, and_imp, mem_union, mem_filter, mem_sdiff,
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -32,7 +32,7 @@ open Finset Nat
namespace Finpartition
-variable {α : Type _} [DecidableEq α] {s t : Finset α} {m n a b : ℕ} {P : Finpartition s}
+variable {α : Type*} [DecidableEq α] {s t : Finset α} {m n a b : ℕ} {P : Finpartition s}
/-- Given a partition `P` of `s`, as well as a proof that `a * m + b * (m + 1) = s.card`, we can
find a new partition `Q` of `s` where each part has size `m` or `m + 1`, every part of `P` is the
@@ -2,14 +2,11 @@
Copyright (c) 2022 Yaël Dillies, Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.equitabilise
-! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Order.Partition.Equipartition
+#align_import combinatorics.simple_graph.regularity.equitabilise from "leanprover-community/mathlib"@"bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d"
+
/-!
# Equitabilising a partition
at
and goals (#5387)
Changes are of the form
some_tactic at h⊢
-> some_tactic at h ⊢
some_tactic at h
-> some_tactic at h
@@ -99,7 +99,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
rw [card_insert_of_not_mem, hR₃, if_neg ha, tsub_add_cancel_of_le]
· exact hab.resolve_left ha
· intro H; exact ht.ne_empty (le_sdiff_iff.1 <| R.le <| filter_subset _ _ H)
- push_neg at h
+ push_neg at h
obtain ⟨u, hu₁, hu₂⟩ := h
obtain ⟨t, htu, htn⟩ := exists_smaller_set _ _ (hn₁.trans hu₂)
have ht : t.Nonempty := by rwa [← card_pos, htn]
I ran codespell Mathlib
and got tired halfway through the suggestions.
@@ -121,7 +121,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
refine'
(card_le_of_subset fun i => _).trans
(hR₂ (u \ t) <| P.mem_avoid.2 ⟨u, hu₁, fun i => hut <| i.antisymm htu, rfl⟩)
- -- Porting note: `not_and` required because `∃ x ∈ s, p x` is defined diferently
+ -- Porting note: `not_and` required because `∃ x ∈ s, p x` is defined differently
simp only [not_exists, not_and, mem_biUnion, and_imp, mem_union, mem_filter, mem_sdiff,
id.def, not_or]
exact fun hi₁ hi₂ hi₃ =>
Match https://github.com/leanprover-community/mathlib/pull/19051 (and one line of https://github.com/leanprover-community/mathlib/pull/18371)
combinatorics.simple_graph.regularity.energy
@f7707875544ef1f81b32cb68c79e0e24e45a0e76
..bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
combinatorics.simple_graph.regularity.equitabilise
@4c19a16e4b705bf135cf9a80ac18fcc99c438514
..bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
combinatorics.simple_graph.regularity.uniform
@32b08ef840dd25ca2e47e035c5da03ce16d2dc3c
..bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies, Bhavik Mehta
! This file was ported from Lean 3 source module combinatorics.simple_graph.regularity.equitabilise
-! leanprover-community/mathlib commit 4c19a16e4b705bf135cf9a80ac18fcc99c438514
+! leanprover-community/mathlib commit bf7ef0e83e5b7e6c1169e97f055e58a2e4e9d52d
! Please do not edit these lines, except to modify the commit id
! if you have ported upstream changes.
-/
@@ -24,6 +24,10 @@ This file allows to blow partitions up into parts of controlled size. Given a pa
* `Finpartition.equitabilise`: `P.equitabilise h` where `h : a * m + b * (m + 1)` is a partition
with `a` parts of size `m` and `b` parts of size `m + 1` which almost refines `P`.
* `Finpartition.exists_equipartition_card_eq`: We can find equipartitions of arbitrary size.
+
+## References
+
+[Yaël Dillies, Bhavik Mehta, *Formalising Szemerédi’s Regularity Lemma in Lean*][srl_itp]
-/
sSup
/iSup
(#3938)
As discussed on Zulip
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>
@@ -41,12 +41,12 @@ union of parts of `Q` plus at most `m` extra elements, there are `b` parts of si
theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
∃ Q : Finpartition s,
(∀ x : Finset α, x ∈ Q.parts → x.card = m ∨ x.card = m + 1) ∧
- (∀ x, x ∈ P.parts → (x \ (Q.parts.filter fun y => y ⊆ x).bunionᵢ id).card ≤ m) ∧
+ (∀ x, x ∈ P.parts → (x \ (Q.parts.filter fun y => y ⊆ x).biUnion id).card ≤ m) ∧
(Q.parts.filter fun i => card i = m + 1).card = b := by
-- Get rid of the easy case `m = 0`
obtain rfl | m_pos := m.eq_zero_or_pos
· refine' ⟨⊥, by simp, _, by simpa using hs.symm⟩
- simp only [le_zero_iff, card_eq_zero, mem_bunionᵢ, exists_prop, mem_filter, id.def, and_assoc,
+ simp only [le_zero_iff, card_eq_zero, mem_biUnion, exists_prop, mem_filter, id.def, and_assoc,
sdiff_eq_empty_iff_subset, subset_iff]
exact fun x hx a ha =>
⟨{a}, mem_map_of_mem _ (P.le hx ha), singleton_subset_iff.2 ha, mem_singleton_self _⟩
@@ -110,7 +110,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
· conv in _ ∈ _ => rw [← insert_erase hu₁]
simp only [and_imp, mem_insert, forall_eq_or_imp, Ne.def, extend_parts]
refine' ⟨_, fun x hx => (card_le_of_subset _).trans <| hR₂ x _⟩
- · simp only [filter_insert, if_pos htu, bunionᵢ_insert, mem_erase, id.def]
+ · simp only [filter_insert, if_pos htu, biUnion_insert, mem_erase, id.def]
obtain rfl | hut := eq_or_ne u t
· rw [sdiff_eq_empty_iff_subset.2 (subset_union_left _ _)]
exact bot_le
@@ -118,11 +118,11 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
(card_le_of_subset fun i => _).trans
(hR₂ (u \ t) <| P.mem_avoid.2 ⟨u, hu₁, fun i => hut <| i.antisymm htu, rfl⟩)
-- Porting note: `not_and` required because `∃ x ∈ s, p x` is defined diferently
- simp only [not_exists, not_and, mem_bunionᵢ, and_imp, mem_union, mem_filter, mem_sdiff,
+ simp only [not_exists, not_and, mem_biUnion, and_imp, mem_union, mem_filter, mem_sdiff,
id.def, not_or]
exact fun hi₁ hi₂ hi₃ =>
⟨⟨hi₁, hi₂⟩, fun x hx hx' => hi₃ _ hx <| hx'.trans <| sdiff_subset _ _⟩
- · apply sdiff_subset_sdiff Subset.rfl (bunionᵢ_subset_bunionᵢ_of_subset_left _ _)
+ · apply sdiff_subset_sdiff Subset.rfl (biUnion_subset_biUnion_of_subset_left _ _)
exact filter_subset_filter _ (subset_insert _ _)
simp only [avoid, ofErase, mem_erase, mem_image, bot_eq_empty]
exact
@@ -192,7 +192,7 @@ theorem card_parts_equitabilise (hm : m ≠ 0) : (P.equitabilise h).parts.card =
#align finpartition.card_parts_equitabilise Finpartition.card_parts_equitabilise
theorem card_parts_equitabilise_subset_le :
- t ∈ P.parts → (t \ ((P.equitabilise h).parts.filter fun u => u ⊆ t).bunionᵢ id).card ≤ m :=
+ t ∈ P.parts → (t \ ((P.equitabilise h).parts.filter fun u => u ⊆ t).biUnion id).card ≤ m :=
(Classical.choose_spec <| P.equitabilise_aux h).2.1 t
#align finpartition.card_parts_equitabilise_subset_le Finpartition.card_parts_equitabilise_subset_le
by
s! (#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 by
s".
@@ -63,10 +63,8 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
-- `n` will be the size of the smallest part
set n := if 0 < a then m else m + 1 with hn
-- Some easy facts about it
- obtain ⟨hn₀, hn₁, hn₂, hn₃⟩ :
- 0 < n ∧ n ≤ m + 1 ∧ n ≤ a * m + b * (m + 1) ∧
- ite (0 < a) (a - 1) a * m + ite (0 < a) b (b - 1) * (m + 1) = s.card - n :=
- by
+ obtain ⟨hn₀, hn₁, hn₂, hn₃⟩ : 0 < n ∧ n ≤ m + 1 ∧ n ≤ a * m + b * (m + 1) ∧
+ ite (0 < a) (a - 1) a * m + ite (0 < a) b (b - 1) * (m + 1) = s.card - n := by
rw [hn, ← hs]
split_ifs with h <;> rw [tsub_mul, one_mul]
· refine' ⟨m_pos, le_succ _, le_add_right (le_mul_of_pos_left ‹0 < a›), _⟩
closes #3680, see https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Stepping.20through.20simp_rw/near/326712986
@@ -91,7 +91,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
· simp only [extend_parts, mem_insert, forall_eq_or_imp, and_iff_left hR₁, htn, hn]
exact ite_eq_or_eq _ _ _
· exact fun x hx => (card_le_of_subset <| sdiff_subset _ _).trans (lt_succ_iff.1 <| h _ hx)
- simp_rw [extend_parts, filter_insert, htn, hn, m.succ_ne_self.symm.ite_eq_right_iff]
+ simp_rw [extend_parts, filter_insert, htn, m.succ_ne_self.symm.ite_eq_right_iff]
split_ifs with ha
· rw [hR₃, if_pos ha]
rw [card_insert_of_not_mem, hR₃, if_neg ha, tsub_add_cancel_of_le]
@@ -79,7 +79,7 @@ theorem equitabilise_aux (hs : a * m + b * (m + 1) = s.card) :
least one part `u` of `P` has size `m + 1` (in which case we take `t` to be an arbitrary subset
of `u` of size `n`). The rest of each branch is just tedious calculations to satisfy the
induction hypothesis. -/
- by_cases ∀ u ∈ P.parts, card u < m + 1
+ by_cases h : ∀ u ∈ P.parts, card u < m + 1
· obtain ⟨t, hts, htn⟩ := exists_smaller_set s n (hn₂.trans_eq hs)
have ht : t.Nonempty := by rwa [← card_pos, htn]
have hcard : ite (0 < a) (a - 1) a * m + ite (0 < a) b (b - 1) * (m + 1) = (s \ t).card := by
The unported dependencies are