Skip to main content
fpvandoorn/carleson
Source indexedlemma ยท leanprover/lean4:v4.32.0

eq_biUnion_iteratedMaximalSubfamily

Carleson.TileStructure ยท Carleson/TileStructure.lean:569 to 626

Source documentation

Any set of tiles can be written as the union of disjoint subfamilies, their number being controlled by the maximal stack size.

Exact Lean statement

lemma eq_biUnion_iteratedMaximalSubfamily (A : Set (๐”“ X)) {N : โ„•} (hN : โˆ€ x, stackSize A x โ‰ค N) :
    A = โ‹ƒ n < N, iteratedMaximalSubfamily A n

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
lemma eq_biUnion_iteratedMaximalSubfamily (A : Set (๐”“ X)) {N : โ„•} (hN : โˆ€ x, stackSize A x โ‰ค N) :    A = โ‹ƒ n < N, iteratedMaximalSubfamily A n := by  apply Subset.antisymm; swap  ยท simp [iUnion_subset_iff, iteratedMaximalSubfamily_subset]  -- we show that after `N` steps the maximal subfamilies cover everything. Otherwise, say some  -- `p` is left. Then `๐“˜ p` is contained in an element of each of the previous subfamilies.  -- This gives `N+1` different elements containing any element of `๐“˜ p`, a contradiction with  -- the maximal stack size.  intro p hp  contrapose! hN  simp only [mem_iUnion, exists_prop, not_exists, not_and] at hN  have E n (hn : n < N) : โˆƒ u โˆˆ iteratedMaximalSubfamily A n, (๐“˜ p : Set X) โІ (๐“˜ u : Set X) := by    rw [iteratedMaximalSubfamily]    apply (exists_maximal_disjoint_covering_subfamily _).choose_spec.2.2    simp only [coe_setOf, mem_setOf_eq, mem_sdiff, hp,      mem_iUnion, Subtype.exists, exists_prop, not_exists, not_and, true_and]    intro i hi    exact hN i (hi.trans hn)  choose! u hu h'u using E  obtain โŸจx, hxpโŸฉ : โˆƒ x, x โˆˆ (๐“˜ p : Set X) := โŸจ_, Grid.c_mem_GridโŸฉ  use x  have : stackSize {q โˆˆ A | q = p} x + stackSize {q โˆˆ A | q โ‰  p} x = stackSize A x :=    stackSize_setOf_add_stackSize_setOf_not  have : 1 = stackSize {q โˆˆ A | q = p} x := by    have : 1 = โˆ‘ q โˆˆ {p}, (๐“˜ q : Set X).indicator 1 x := by simp [hxp]    rw [this]    congr    ext    simp (config := {contextual := true}) [hp]  classical  have : โˆ‘ p with p โˆˆ u '' (Iio N), (๐“˜ p : Set X).indicator 1 x      โ‰ค stackSize {q | q โˆˆ A โˆง q โ‰  p} x := by    apply Finset.sum_le_sum_of_subset    rintro p hp    simp only [Finset.mem_filter_univ, mem_image, mem_Iio] at hp    rcases hp with โŸจn, hn, rflโŸฉ    simp only [ne_eq, mem_setOf_eq, Finset.mem_filter,      Finset.mem_univ, iteratedMaximalSubfamily_subset _ _ (hu n hn), true_and]    rintro rfl    exact hN n hn (hu n hn)  have : โˆ‘ p with p โˆˆ u '' (Iio N), (๐“˜ p : Set X).indicator 1 x      = โˆ‘ p with p โˆˆ u '' (Iio N), 1 := by    apply Finset.sum_congr rfl (fun p hp โ†ฆ ?_)    simp only [Finset.mem_filter_univ, mem_image, mem_Iio] at hp    rcases hp with โŸจn, hn, rflโŸฉ    have : x โˆˆ (๐“˜ (u n) : Set X) := h'u n hn hxp    simp [this]  have : โˆ‘ p with p โˆˆ u '' (Iio N), 1 = N := by    have : Finset.filter (fun p โ†ฆ p โˆˆ u '' Iio N) Finset.univ = Finset.image u (Finset.Iio N) := by      ext p; simp    simp only [Finset.sum_const, smul_eq_mul, mul_one, this]    rw [Finset.card_image_of_injOn, Nat.card_Iio N]    intro a ha b hb hab    contrapose! hab    simp only [Finset.coe_Iio, mem_Iio] at ha hb    have := pairwiseDisjoint_iteratedMaximalSubfamily A (mem_univ a) (mem_univ b) hab    exact disjoint_iff_forall_ne.1 this (hu a ha) (hu b hb)  lia