combinatorics.set_family.shadow
β·
Mathlib.Combinatorics.SetFamily.Shadow
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)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(no changes)
(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)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -105,7 +105,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
#align finset.erase_mem_shadow Finset.erase_mem_shadow
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:641:2: warning: expanding binder collection (a Β«expr β Β» s) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:642:2: warning: expanding binder collection (a Β«expr β Β» s) -/
#print Finset.mem_shadow_iff_insert_mem /-
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
@@ -231,7 +231,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:641:2: warning: expanding binder collection (a Β«expr β Β» t) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:642:2: warning: expanding binder collection (a Β«expr β Β» t) -/
#print Finset.mem_upShadow_iff /-
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -189,7 +189,7 @@ theorem mem_shadow_iterate_iff_exists_mem_card_add :
Β· rintro β¨t, ht, hst, hcardβ©
obtain β¨u, hsu, hut, huβ© :=
Finset.exists_intermediate_set k (by rw [add_comm, hcard]; exact le_succ _) hst
- rw [add_comm] at hu
+ rw [add_comm] at hu
refine' β¨u, mem_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, hut, _β©, hsu, huβ©
rw [hcard, hu]
rfl
@@ -319,7 +319,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
obtain β¨u, htu, hus, huβ© :=
Finset.exists_intermediate_set 1
(by rw [add_comm, β hcard]; exact add_le_add_left (zero_lt_succ _) _) hts
- rw [add_comm] at hu
+ rw [add_comm] at hu
refine' β¨u, mem_up_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, htu, hu.symmβ©, hus, _β©
rw [hu, β hcard, add_right_comm]
rfl
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -120,6 +120,9 @@ theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _) (_ : a β
#align finset.mem_shadow_iff_insert_mem Finset.mem_shadow_iff_insert_mem
-/
+/- warning: set.sized.shadow clashes with finset.set.sized.shadow -> Set.Sized.shadow
+Case conversion may be inaccurate. Consider using '#align set.sized.shadow Set.Sized.shadowβ'. -/
+#print Set.Sized.shadow /-
/-- The shadow of a family of `r`-sets is a family of `r - 1`-sets. -/
protected theorem Set.Sized.shadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
((β ) π : Set (Finset Ξ±)).Sized (r - 1) :=
@@ -128,6 +131,7 @@ protected theorem Set.Sized.shadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
obtain β¨A, hA, i, hi, rflβ© := mem_shadow_iff.1 h
rw [card_erase_of_mem hi, hπ hA]
#align set.sized.shadow Set.Sized.shadow
+-/
#print Finset.sized_shadow_iff /-
theorem sized_shadow_iff (h : β
β π) :
@@ -164,9 +168,9 @@ theorem exists_subset_of_mem_shadow (hs : s β (β ) π) : β t β π, s
#align finset.exists_subset_of_mem_shadow Finset.exists_subset_of_mem_shadow
-/
-#print Finset.mem_shadow_iff_exists_mem_card_add /-
+#print Finset.mem_shadow_iterate_iff_exists_mem_card_add /-
/-- `t β β^k π` iff `t` is exactly `k` elements less than something in `π`. -/
-theorem mem_shadow_iff_exists_mem_card_add :
+theorem mem_shadow_iterate_iff_exists_mem_card_add :
s β (β ^[k]) π β β t β π, s β t β§ t.card = s.card + k :=
by
induction' k with k ih generalizing π s
@@ -189,7 +193,7 @@ theorem mem_shadow_iff_exists_mem_card_add :
refine' β¨u, mem_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, hut, _β©, hsu, huβ©
rw [hcard, hu]
rfl
-#align finset.mem_shadow_iff_exists_mem_card_add Finset.mem_shadow_iff_exists_mem_card_add
+#align finset.mem_shadow_iff_exists_mem_card_add Finset.mem_shadow_iterate_iff_exists_mem_card_add
-/
end Shadow
@@ -242,6 +246,9 @@ theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β (
#align finset.insert_mem_up_shadow Finset.insert_mem_upShadow
-/
+/- warning: set.sized.up_shadow clashes with finset.set.sized.up_shadow -> Set.Sized.upShadow
+Case conversion may be inaccurate. Consider using '#align set.sized.up_shadow Set.Sized.upShadowβ'. -/
+#print Set.Sized.upShadow /-
/-- The upper shadow of a family of `r`-sets is a family of `r + 1`-sets. -/
protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
((ββΊ ) π : Set (Finset Ξ±)).Sized (r + 1) :=
@@ -250,6 +257,7 @@ protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r)
obtain β¨A, hA, i, hi, rflβ© := mem_up_shadow_iff.1 h
rw [card_insert_of_not_mem hi, hπ hA]
#align set.sized.up_shadow Set.Sized.upShadow
+-/
#print Finset.mem_upShadow_iff_erase_mem /-
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
mathlib commit https://github.com/leanprover-community/mathlib/commit/3365b20c2ffa7c35e47e5209b89ba9abdddf3ffe
@@ -318,9 +318,9 @@ theorem mem_upShadow_iff_exists_mem_card_add :
#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_add
-/
-#print Finset.shadow_image_compl /-
+#print Finset.upShadow_compls /-
@[simp]
-theorem shadow_image_compl : ((β ) π).image compl = (ββΊ ) (π.image compl) :=
+theorem upShadow_compls : ((β ) π).image compl = (ββΊ ) (π.image compl) :=
by
ext s
simp only [mem_image, exists_prop, mem_shadow_iff, mem_up_shadow_iff]
@@ -329,12 +329,12 @@ theorem shadow_image_compl : ((β ) π).image compl = (ββΊ ) (π.image c
exact β¨sαΆ, β¨s, hs, rflβ©, a, not_mem_compl.2 ha, compl_erase.symmβ©
Β· rintro β¨_, β¨s, hs, rflβ©, a, ha, rflβ©
exact β¨s.erase a, β¨s, hs, a, not_mem_compl.1 ha, rflβ©, compl_eraseβ©
-#align finset.shadow_image_compl Finset.shadow_image_compl
+#align finset.shadow_image_compl Finset.upShadow_compls
-/
-#print Finset.upShadow_image_compl /-
+#print Finset.shadow_compls /-
@[simp]
-theorem upShadow_image_compl : ((ββΊ ) π).image compl = (β ) (π.image compl) :=
+theorem shadow_compls : ((ββΊ ) π).image compl = (β ) (π.image compl) :=
by
ext s
simp only [mem_image, exists_prop, mem_shadow_iff, mem_up_shadow_iff]
@@ -343,7 +343,7 @@ theorem upShadow_image_compl : ((ββΊ ) π).image compl = (β ) (π.image
exact β¨sαΆ, β¨s, hs, rflβ©, a, mem_compl.2 ha, compl_insert.symmβ©
Β· rintro β¨_, β¨s, hs, rflβ©, a, ha, rflβ©
exact β¨insert a s, β¨s, hs, a, mem_compl.1 ha, rflβ©, compl_insertβ©
-#align finset.up_shadow_image_compl Finset.upShadow_image_compl
+#align finset.up_shadow_image_compl Finset.shadow_compls
-/
end UpShadow
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,8 +3,8 @@ Copyright (c) 2021 Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Bhavik Mehta, Alena Gusakov, YaΓ«l Dillies
-/
-import Mathbin.Data.Finset.Slice
-import Mathbin.Logic.Function.Iterate
+import Data.Finset.Slice
+import Logic.Function.Iterate
#align_import combinatorics.set_family.shadow from "leanprover-community/mathlib"@"13a5329a8625701af92e9a96ffc90fa787fff24d"
@@ -105,7 +105,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
#align finset.erase_mem_shadow Finset.erase_mem_shadow
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» s) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:641:2: warning: expanding binder collection (a Β«expr β Β» s) -/
#print Finset.mem_shadow_iff_insert_mem /-
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
@@ -227,7 +227,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» t) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:641:2: warning: expanding binder collection (a Β«expr β Β» t) -/
#print Finset.mem_upShadow_iff /-
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,15 +2,12 @@
Copyright (c) 2021 Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Bhavik Mehta, Alena Gusakov, YaΓ«l Dillies
-
-! This file was ported from Lean 3 source module combinatorics.set_family.shadow
-! leanprover-community/mathlib commit 13a5329a8625701af92e9a96ffc90fa787fff24d
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Data.Finset.Slice
import Mathbin.Logic.Function.Iterate
+#align_import combinatorics.set_family.shadow from "leanprover-community/mathlib"@"13a5329a8625701af92e9a96ffc90fa787fff24d"
+
/-!
# Shadows
@@ -108,7 +105,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
#align finset.erase_mem_shadow Finset.erase_mem_shadow
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:638:2: warning: expanding binder collection (a Β«expr β Β» s) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» s) -/
#print Finset.mem_shadow_iff_insert_mem /-
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
@@ -230,7 +227,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:638:2: warning: expanding binder collection (a Β«expr β Β» t) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» t) -/
#print Finset.mem_upShadow_iff /-
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423
@@ -68,7 +68,6 @@ def shadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
#align finset.shadow Finset.shadow
-/
--- mathport name: finset.shadow
scoped[FinsetFamily] notation:90 "β " => Finset.shadow
#print Finset.shadow_empty /-
@@ -95,11 +94,13 @@ theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Fins
#align finset.shadow_monotone Finset.shadow_monotone
-/
+#print Finset.mem_shadow_iff /-
/-- `s` is in the shadow of `π` iff there is an `t β π` from which we can remove one element to
get `s`. -/
theorem mem_shadow_iff : s β (β ) π β β t β π, β a β t, erase t a = s := by
simp only [shadow, mem_sup, mem_image]
#align finset.mem_shadow_iff Finset.mem_shadow_iff
+-/
#print Finset.erase_mem_shadow /-
theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β ) π :=
@@ -141,6 +142,7 @@ theorem sized_shadow_iff (h : β
β π) :
#align finset.sized_shadow_iff Finset.sized_shadow_iff
-/
+#print Finset.mem_shadow_iff_exists_mem_card_add_one /-
/-- `s β β π` iff `s` is exactly one element less than something from `π` -/
theorem mem_shadow_iff_exists_mem_card_add_one :
s β (β ) π β β t β π, s β t β§ t.card = s.card + 1 :=
@@ -155,13 +157,17 @@ theorem mem_shadow_iff_exists_mem_card_add_one :
β¨a, fun hat => not_mem_sdiff_of_mem_right hat ((ha.ge : _ β _) <| mem_singleton_self a), by
rwa [insert_eq a s, β ha, sdiff_union_of_subset hst]β©
#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_one
+-/
+#print Finset.exists_subset_of_mem_shadow /-
/-- Being in the shadow of `π` means we have a superset in `π`. -/
theorem exists_subset_of_mem_shadow (hs : s β (β ) π) : β t β π, s β t :=
let β¨t, ht, hstβ© := mem_shadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, hst.1β©
#align finset.exists_subset_of_mem_shadow Finset.exists_subset_of_mem_shadow
+-/
+#print Finset.mem_shadow_iff_exists_mem_card_add /-
/-- `t β β^k π` iff `t` is exactly `k` elements less than something in `π`. -/
theorem mem_shadow_iff_exists_mem_card_add :
s β (β ^[k]) π β β t β π, s β t β§ t.card = s.card + k :=
@@ -187,6 +193,7 @@ theorem mem_shadow_iff_exists_mem_card_add :
rw [hcard, hu]
rfl
#align finset.mem_shadow_iff_exists_mem_card_add Finset.mem_shadow_iff_exists_mem_card_add
+-/
end Shadow
@@ -205,7 +212,6 @@ def upShadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
#align finset.up_shadow Finset.upShadow
-/
--- mathport name: finset.up_shadow
scoped[FinsetFamily] notation:90 "ββΊ " => Finset.upShadow
#print Finset.upShadow_empty /-
@@ -225,11 +231,13 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
-/
/- ./././Mathport/Syntax/Translate/Basic.lean:638:2: warning: expanding binder collection (a Β«expr β Β» t) -/
+#print Finset.mem_upShadow_iff /-
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
simp_rw [up_shadow, mem_sup, mem_image, exists_prop, mem_compl]
#align finset.mem_up_shadow_iff Finset.mem_upShadow_iff
+-/
#print Finset.insert_mem_upShadow /-
theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β (ββΊ ) π :=
@@ -246,6 +254,7 @@ protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r)
rw [card_insert_of_not_mem hi, hπ hA]
#align set.sized.up_shadow Set.Sized.upShadow
+#print Finset.mem_upShadow_iff_erase_mem /-
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
finset is in `π`. -/
theorem mem_upShadow_iff_erase_mem : s β (ββΊ ) π β β a β s, s.eraseβ a β π :=
@@ -257,7 +266,9 @@ theorem mem_upShadow_iff_erase_mem : s β (ββΊ ) π β β a β s, s.era
Β· rintro β¨a, ha, hsβ©
exact β¨s.erase a, hs, a, not_mem_erase _ _, insert_erase haβ©
#align finset.mem_up_shadow_iff_erase_mem Finset.mem_upShadow_iff_erase_mem
+-/
+#print Finset.mem_upShadow_iff_exists_mem_card_add_one /-
/-- `s β ββΊ π` iff `s` is exactly one element less than something from `π`. -/
theorem mem_upShadow_iff_exists_mem_card_add_one :
s β (ββΊ ) π β β t β π, t β s β§ t.card + 1 = s.card :=
@@ -271,13 +282,17 @@ theorem mem_upShadow_iff_exists_mem_card_add_one :
refine' β¨a, sdiff_subset _ _ ((ha.ge : _ β _) <| mem_singleton_self a), _β©
rwa [β sdiff_singleton_eq_erase, β ha, sdiff_sdiff_eq_self hts]
#align finset.mem_up_shadow_iff_exists_mem_card_add_one Finset.mem_upShadow_iff_exists_mem_card_add_one
+-/
+#print Finset.exists_subset_of_mem_upShadow /-
/-- Being in the upper shadow of `π` means we have a superset in `π`. -/
theorem exists_subset_of_mem_upShadow (hs : s β (ββΊ ) π) : β t β π, t β s :=
let β¨t, ht, hts, _β© := mem_upShadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, htsβ©
#align finset.exists_subset_of_mem_up_shadow Finset.exists_subset_of_mem_upShadow
+-/
+#print Finset.mem_upShadow_iff_exists_mem_card_add /-
/-- `t β β^k π` iff `t` is exactly `k` elements more than something in `π`. -/
theorem mem_upShadow_iff_exists_mem_card_add :
s β (ββΊ ^[k]) π β β t β π, t β s β§ t.card + k = s.card :=
@@ -304,6 +319,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
rw [hu, β hcard, add_right_comm]
rfl
#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_add
+-/
#print Finset.shadow_image_compl /-
@[simp]
mathlib commit https://github.com/leanprover-community/mathlib/commit/31c24aa72e7b3e5ed97a8412470e904f82b81004
@@ -107,7 +107,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
#align finset.erase_mem_shadow Finset.erase_mem_shadow
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» s) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:638:2: warning: expanding binder collection (a Β«expr β Β» s) -/
#print Finset.mem_shadow_iff_insert_mem /-
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
@@ -224,7 +224,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» t) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:638:2: warning: expanding binder collection (a Β«expr β Β» t) -/
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -111,7 +111,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
#print Finset.mem_shadow_iff_insert_mem /-
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
-theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _)(_ : a β s), insert a s β π :=
+theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _) (_ : a β s), insert a s β π :=
by
refine' mem_shadow_iff.trans β¨_, _β©
Β· rintro β¨s, hs, a, ha, rflβ©
@@ -182,7 +182,7 @@ theorem mem_shadow_iff_exists_mem_card_add :
Β· rintro β¨t, ht, hst, hcardβ©
obtain β¨u, hsu, hut, huβ© :=
Finset.exists_intermediate_set k (by rw [add_comm, hcard]; exact le_succ _) hst
- rw [add_comm] at hu
+ rw [add_comm] at hu
refine' β¨u, mem_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, hut, _β©, hsu, huβ©
rw [hcard, hu]
rfl
@@ -227,7 +227,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» t) -/
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
-theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _)(_ : a β t), insert a t = s := by
+theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
simp_rw [up_shadow, mem_sup, mem_image, exists_prop, mem_compl]
#align finset.mem_up_shadow_iff Finset.mem_upShadow_iff
@@ -299,7 +299,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
obtain β¨u, htu, hus, huβ© :=
Finset.exists_intermediate_set 1
(by rw [add_comm, β hcard]; exact add_le_add_left (zero_lt_succ _) _) hts
- rw [add_comm] at hu
+ rw [add_comm] at hu
refine' β¨u, mem_up_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, htu, hu.symmβ©, hus, _β©
rw [hu, β hcard, add_right_comm]
rfl
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -190,7 +190,7 @@ theorem mem_shadow_iff_exists_mem_card_add :
end Shadow
-open FinsetFamily
+open scoped FinsetFamily
section UpShadow
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -95,12 +95,6 @@ theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Fins
#align finset.shadow_monotone Finset.shadow_monotone
-/
-/- warning: finset.mem_shadow_iff -> Finset.mem_shadow_iff is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => Exists.{succ u1} Ξ± (fun (a : Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasMem.{u1} Ξ±) a t) (fun (H : Membership.Mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasMem.{u1} Ξ±) a t) => Eq.{succ u1} (Finset.{u1} Ξ±) (Finset.erase.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) t a) s)))))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (Exists.{succ u1} Ξ± (fun (a : Ξ±) => And (Membership.mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instMembershipFinset.{u1} Ξ±) a t) (Eq.{succ u1} (Finset.{u1} Ξ±) (Finset.erase.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) t a) s)))))
-Case conversion may be inaccurate. Consider using '#align finset.mem_shadow_iff Finset.mem_shadow_iffβ'. -/
/-- `s` is in the shadow of `π` iff there is an `t β π` from which we can remove one element to
get `s`. -/
theorem mem_shadow_iff : s β (β ) π β β t β π, β a β t, erase t a = s := by
@@ -147,12 +141,6 @@ theorem sized_shadow_iff (h : β
β π) :
#align finset.sized_shadow_iff Finset.sized_shadow_iff
-/
-/- warning: finset.mem_shadow_iff_exists_mem_card_add_one -> Finset.mem_shadow_iff_exists_mem_card_add_one is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.hasSubset.{u1} Ξ±) s t) (Eq.{1} Nat (Finset.card.{u1} Ξ± t) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (Finset.card.{u1} Ξ± s) (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} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.instHasSubsetFinset.{u1} Ξ±) s t) (Eq.{1} Nat (Finset.card.{u1} Ξ± t) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (Finset.card.{u1} Ξ± s) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1)))))))
-Case conversion may be inaccurate. Consider using '#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_oneβ'. -/
/-- `s β β π` iff `s` is exactly one element less than something from `π` -/
theorem mem_shadow_iff_exists_mem_card_add_one :
s β (β ) π β β t β π, s β t β§ t.card = s.card + 1 :=
@@ -168,24 +156,12 @@ theorem mem_shadow_iff_exists_mem_card_add_one :
rwa [insert_eq a s, β ha, sdiff_union_of_subset hst]β©
#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_one
-/- warning: finset.exists_subset_of_mem_shadow -> Finset.exists_subset_of_mem_shadow is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) -> (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.hasSubset.{u1} Ξ±) s t)))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) -> (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.instHasSubsetFinset.{u1} Ξ±) s t)))
-Case conversion may be inaccurate. Consider using '#align finset.exists_subset_of_mem_shadow Finset.exists_subset_of_mem_shadowβ'. -/
/-- Being in the shadow of `π` means we have a superset in `π`. -/
theorem exists_subset_of_mem_shadow (hs : s β (β ) π) : β t β π, s β t :=
let β¨t, ht, hstβ© := mem_shadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, hst.1β©
#align finset.exists_subset_of_mem_shadow Finset.exists_subset_of_mem_shadow
-/- warning: finset.mem_shadow_iff_exists_mem_card_add -> Finset.mem_shadow_iff_exists_mem_card_add is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±} {k : Nat}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Nat.iterate.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)) k π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.hasSubset.{u1} Ξ±) s t) (Eq.{1} Nat (Finset.card.{u1} Ξ± t) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (Finset.card.{u1} Ξ± s) k)))))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±} {k : Nat}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Nat.iterate.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)) k π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.instHasSubsetFinset.{u1} Ξ±) s t) (Eq.{1} Nat (Finset.card.{u1} Ξ± t) (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (Finset.card.{u1} Ξ± s) k)))))
-Case conversion may be inaccurate. Consider using '#align finset.mem_shadow_iff_exists_mem_card_add Finset.mem_shadow_iff_exists_mem_card_addβ'. -/
/-- `t β β^k π` iff `t` is exactly `k` elements less than something in `π`. -/
theorem mem_shadow_iff_exists_mem_card_add :
s β (β ^[k]) π β β t β π, s β t β§ t.card = s.card + k :=
@@ -248,12 +224,6 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/
-/- warning: finset.mem_up_shadow_iff -> Finset.mem_upShadow_iff is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => Exists.{succ u1} Ξ± (fun (a : Ξ±) => Exists.{0} (Not (Membership.Mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasMem.{u1} Ξ±) a t)) (fun (H : Not (Membership.Mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasMem.{u1} Ξ±) a t)) => Eq.{succ u1} (Finset.{u1} Ξ±) (Insert.insert.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasInsert.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)) a t) s)))))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (Exists.{succ u1} Ξ± (fun (a : Ξ±) => Exists.{0} (Not (Membership.mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instMembershipFinset.{u1} Ξ±) a t)) (fun (x._@.Mathlib.Combinatorics.SetFamily.Shadow._hyg.2641 : Not (Membership.mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instMembershipFinset.{u1} Ξ±) a t)) => Eq.{succ u1} (Finset.{u1} Ξ±) (Insert.insert.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instInsertFinset.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)) a t) s)))))
-Case conversion may be inaccurate. Consider using '#align finset.mem_up_shadow_iff Finset.mem_upShadow_iffβ'. -/
/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» t) -/
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
@@ -276,12 +246,6 @@ protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r)
rw [card_insert_of_not_mem hi, hπ hA]
#align set.sized.up_shadow Set.Sized.upShadow
-/- warning: finset.mem_up_shadow_iff_erase_mem -> Finset.mem_upShadow_iff_erase_mem is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} Ξ± (fun (a : Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasMem.{u1} Ξ±) a s) (fun (H : Membership.Mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.hasMem.{u1} Ξ±) a s) => Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) (Finset.erase.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) s a) π)))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} Ξ± (fun (a : Ξ±) => And (Membership.mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instMembershipFinset.{u1} Ξ±) a s) (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) (Finset.erase.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) s a) π)))
-Case conversion may be inaccurate. Consider using '#align finset.mem_up_shadow_iff_erase_mem Finset.mem_upShadow_iff_erase_memβ'. -/
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
finset is in `π`. -/
theorem mem_upShadow_iff_erase_mem : s β (ββΊ ) π β β a β s, s.eraseβ a β π :=
@@ -294,12 +258,6 @@ theorem mem_upShadow_iff_erase_mem : s β (ββΊ ) π β β a β s, s.era
exact β¨s.erase a, hs, a, not_mem_erase _ _, insert_erase haβ©
#align finset.mem_up_shadow_iff_erase_mem Finset.mem_upShadow_iff_erase_mem
-/- warning: finset.mem_up_shadow_iff_exists_mem_card_add_one -> Finset.mem_upShadow_iff_exists_mem_card_add_one is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.hasSubset.{u1} Ξ±) t s) (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (Finset.card.{u1} Ξ± t) (OfNat.ofNat.{0} Nat 1 (OfNat.mk.{0} Nat 1 (One.one.{0} Nat Nat.hasOne)))) (Finset.card.{u1} Ξ± s)))))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.instHasSubsetFinset.{u1} Ξ±) t s) (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (Finset.card.{u1} Ξ± t) (OfNat.ofNat.{0} Nat 1 (instOfNatNat 1))) (Finset.card.{u1} Ξ± s)))))
-Case conversion may be inaccurate. Consider using '#align finset.mem_up_shadow_iff_exists_mem_card_add_one Finset.mem_upShadow_iff_exists_mem_card_add_oneβ'. -/
/-- `s β ββΊ π` iff `s` is exactly one element less than something from `π`. -/
theorem mem_upShadow_iff_exists_mem_card_add_one :
s β (ββΊ ) π β β t β π, t β s β§ t.card + 1 = s.card :=
@@ -314,24 +272,12 @@ theorem mem_upShadow_iff_exists_mem_card_add_one :
rwa [β sdiff_singleton_eq_erase, β ha, sdiff_sdiff_eq_self hts]
#align finset.mem_up_shadow_iff_exists_mem_card_add_one Finset.mem_upShadow_iff_exists_mem_card_add_one
-/- warning: finset.exists_subset_of_mem_up_shadow -> Finset.exists_subset_of_mem_upShadow is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) -> (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.hasSubset.{u1} Ξ±) t s)))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) -> (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.instHasSubsetFinset.{u1} Ξ±) t s)))
-Case conversion may be inaccurate. Consider using '#align finset.exists_subset_of_mem_up_shadow Finset.exists_subset_of_mem_upShadowβ'. -/
/-- Being in the upper shadow of `π` means we have a superset in `π`. -/
theorem exists_subset_of_mem_upShadow (hs : s β (ββΊ ) π) : β t β π, t β s :=
let β¨t, ht, hts, _β© := mem_upShadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, htsβ©
#align finset.exists_subset_of_mem_up_shadow Finset.exists_subset_of_mem_upShadow
-/- warning: finset.mem_up_shadow_iff_exists_mem_card_add -> Finset.mem_upShadow_iff_exists_mem_card_add is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±} {k : Nat}, Iff (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) s (Nat.iterate.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2) k π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => Exists.{0} (Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) (fun (H : Membership.Mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.hasMem.{u1} (Finset.{u1} Ξ±)) t π) => And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.hasSubset.{u1} Ξ±) t s) (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat Nat.hasAdd) (Finset.card.{u1} Ξ± t) k) (Finset.card.{u1} Ξ± s)))))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±} {k : Nat}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Nat.iterate.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2) k π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (And (HasSubset.Subset.{u1} (Finset.{u1} Ξ±) (Finset.instHasSubsetFinset.{u1} Ξ±) t s) (Eq.{1} Nat (HAdd.hAdd.{0, 0, 0} Nat Nat Nat (instHAdd.{0} Nat instAddNat) (Finset.card.{u1} Ξ± t) k) (Finset.card.{u1} Ξ± s)))))
-Case conversion may be inaccurate. Consider using '#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_addβ'. -/
/-- `t β β^k π` iff `t` is exactly `k` elements more than something in `π`. -/
theorem mem_upShadow_iff_exists_mem_card_add :
s β (ββΊ ^[k]) π β β t β π, t β s β§ t.card + k = s.card :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -205,11 +205,7 @@ theorem mem_shadow_iff_exists_mem_card_add :
rfl
Β· rintro β¨t, ht, hst, hcardβ©
obtain β¨u, hsu, hut, huβ© :=
- Finset.exists_intermediate_set k
- (by
- rw [add_comm, hcard]
- exact le_succ _)
- hst
+ Finset.exists_intermediate_set k (by rw [add_comm, hcard]; exact le_succ _) hst
rw [add_comm] at hu
refine' β¨u, mem_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, hut, _β©, hsu, huβ©
rw [hcard, hu]
@@ -356,10 +352,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
Β· rintro β¨t, ht, hts, hcardβ©
obtain β¨u, htu, hus, huβ© :=
Finset.exists_intermediate_set 1
- (by
- rw [add_comm, β hcard]
- exact add_le_add_left (zero_lt_succ _) _)
- hts
+ (by rw [add_comm, β hcard]; exact add_le_add_left (zero_lt_succ _) _) hts
rw [add_comm] at hu
refine' β¨u, mem_up_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, htu, hu.symmβ©, hus, _β©
rw [hu, β hcard, add_right_comm]
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -366,12 +366,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
rfl
#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_add
-/- warning: finset.shadow_image_compl -> Finset.shadow_image_compl is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)}, Eq.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.booleanAlgebra.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.booleanAlgebra.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) π))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)}, Eq.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.instBooleanAlgebraFinset.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) π)) (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.instBooleanAlgebraFinset.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) π))
-Case conversion may be inaccurate. Consider using '#align finset.shadow_image_compl Finset.shadow_image_complβ'. -/
+#print Finset.shadow_image_compl /-
@[simp]
theorem shadow_image_compl : ((β ) π).image compl = (ββΊ ) (π.image compl) :=
by
@@ -383,13 +378,9 @@ theorem shadow_image_compl : ((β ) π).image compl = (ββΊ ) (π.image c
Β· rintro β¨_, β¨s, hs, rflβ©, a, ha, rflβ©
exact β¨s.erase a, β¨s, hs, a, not_mem_compl.1 ha, rflβ©, compl_eraseβ©
#align finset.shadow_image_compl Finset.shadow_image_compl
+-/
-/- warning: finset.up_shadow_image_compl -> Finset.upShadow_image_compl is a dubious translation:
-lean 3 declaration is
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)}, Eq.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.booleanAlgebra.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.booleanAlgebra.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) π))
-but is expected to have type
- forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)}, Eq.{succ u1} (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.instBooleanAlgebraFinset.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Finset.shadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) (Finset.image.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} Ξ±) (fun (a : Finset.{u1} Ξ±) (b : Finset.{u1} Ξ±) => Finset.decidableEq.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) a b) (HasCompl.compl.{u1} (Finset.{u1} Ξ±) (BooleanAlgebra.toHasCompl.{u1} (Finset.{u1} Ξ±) (Finset.instBooleanAlgebraFinset.{u1} Ξ± _inst_2 (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)))) π))
-Case conversion may be inaccurate. Consider using '#align finset.up_shadow_image_compl Finset.upShadow_image_complβ'. -/
+#print Finset.upShadow_image_compl /-
@[simp]
theorem upShadow_image_compl : ((ββΊ ) π).image compl = (β ) (π.image compl) :=
by
@@ -401,6 +392,7 @@ theorem upShadow_image_compl : ((ββΊ ) π).image compl = (β ) (π.image
Β· rintro β¨_, β¨s, hs, rflβ©, a, ha, rflβ©
exact β¨insert a s, β¨s, hs, a, mem_compl.1 ha, rflβ©, compl_insertβ©
#align finset.up_shadow_image_compl Finset.upShadow_image_compl
+-/
end UpShadow
mathlib commit https://github.com/leanprover-community/mathlib/commit/4c586d291f189eecb9d00581aeb3dd998ac34442
@@ -113,7 +113,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
#align finset.erase_mem_shadow Finset.erase_mem_shadow
-/
-/- ./././Mathport/Syntax/Translate/Basic.lean:628:2: warning: expanding binder collection (a Β«expr β Β» s) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» s) -/
#print Finset.mem_shadow_iff_insert_mem /-
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
@@ -258,7 +258,7 @@ lean 3 declaration is
but is expected to have type
forall {Ξ± : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} Ξ±] [_inst_2 : Fintype.{u1} Ξ±] {π : Finset.{u1} (Finset.{u1} Ξ±)} {s : Finset.{u1} Ξ±}, Iff (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) s (Finset.upShadow.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b) _inst_2 π)) (Exists.{succ u1} (Finset.{u1} Ξ±) (fun (t : Finset.{u1} Ξ±) => And (Membership.mem.{u1, u1} (Finset.{u1} Ξ±) (Finset.{u1} (Finset.{u1} Ξ±)) (Finset.instMembershipFinset.{u1} (Finset.{u1} Ξ±)) t π) (Exists.{succ u1} Ξ± (fun (a : Ξ±) => Exists.{0} (Not (Membership.mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instMembershipFinset.{u1} Ξ±) a t)) (fun (x._@.Mathlib.Combinatorics.SetFamily.Shadow._hyg.2641 : Not (Membership.mem.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instMembershipFinset.{u1} Ξ±) a t)) => Eq.{succ u1} (Finset.{u1} Ξ±) (Insert.insert.{u1, u1} Ξ± (Finset.{u1} Ξ±) (Finset.instInsertFinset.{u1} Ξ± (fun (a : Ξ±) (b : Ξ±) => _inst_1 a b)) a t) s)))))
Case conversion may be inaccurate. Consider using '#align finset.mem_up_shadow_iff Finset.mem_upShadow_iffβ'. -/
-/- ./././Mathport/Syntax/Translate/Basic.lean:628:2: warning: expanding binder collection (a Β«expr β Β» t) -/
+/- ./././Mathport/Syntax/Translate/Basic.lean:635:2: warning: expanding binder collection (a Β«expr β Β» t) -/
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _)(_ : a β t), insert a t = s := by
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
@@ -105,7 +105,7 @@ lemma mem_shadow_iff_exists_sdiff : t β β π β β s β π, t β s
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
-lemma mem_shadow_iff_insert_mem : t β β π β β a, a β t β§ insert a t β π := by
+lemma mem_shadow_iff_insert_mem : t β β π β β a β t, insert a t β π := by
simp_rw [mem_shadow_iff_exists_sdiff, β covBy_iff_card_sdiff_eq_one, covBy_iff_exists_insert]
aesop
#align finset.mem_shadow_iff_insert_mem Finset.mem_shadow_iff_insert_mem
This is a very large PR, but it has been reviewed piecemeal already in PRs to the bump/v4.7.0
branch as we update to intermediate nightlies.
Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com> Co-authored-by: damiano <adomani@gmail.com>
@@ -125,6 +125,7 @@ lemma mem_shadow_iterate_iff_exists_card :
t β β^[k] π β β u : Finset Ξ±, u.card = k β§ Disjoint t u β§ t βͺ u β π := by
induction' k with k ih generalizing t
Β· simp
+ set_option tactic.skipAssignedInstances false in
simp only [mem_shadow_iff_insert_mem, ih, Function.iterate_succ_apply', card_eq_succ]
aesop
Covby
to CovBy
(#9578)
Rename
Covby
β CovBy
, Wcovby
β WCovBy
*covby*
β *covBy*
wcovby.finset_val
β WCovBy.finset_val
, wcovby.finset_coe
β WCovBy.finset_coe
Covby.is_coatom
β CovBy.isCoatom
@@ -101,12 +101,12 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β β
See also `Finset.mem_shadow_iff_exists_mem_card_add_one`. -/
lemma mem_shadow_iff_exists_sdiff : t β β π β β s β π, t β s β§ (s \ t).card = 1 := by
- simp_rw [mem_shadow_iff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_erase]
+ simp_rw [mem_shadow_iff, β covBy_iff_card_sdiff_eq_one, covBy_iff_exists_erase]
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
lemma mem_shadow_iff_insert_mem : t β β π β β a, a β t β§ insert a t β π := by
- simp_rw [mem_shadow_iff_exists_sdiff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
+ simp_rw [mem_shadow_iff_exists_sdiff, β covBy_iff_card_sdiff_eq_one, covBy_iff_exists_insert]
aesop
#align finset.mem_shadow_iff_insert_mem Finset.mem_shadow_iff_insert_mem
@@ -223,12 +223,12 @@ theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β
See also `Finset.mem_upShadow_iff_exists_mem_card_add_one`. -/
lemma mem_upShadow_iff_exists_sdiff : t β ββΊ π β β s β π, s β t β§ (t \ s).card = 1 := by
- simp_rw [mem_upShadow_iff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
+ simp_rw [mem_upShadow_iff, β covBy_iff_card_sdiff_eq_one, covBy_iff_exists_insert]
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
finset is in `π`. -/
lemma mem_upShadow_iff_erase_mem : t β ββΊ π β β a, a β t β§ erase t a β π := by
- simp_rw [mem_upShadow_iff_exists_sdiff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_erase]
+ simp_rw [mem_upShadow_iff_exists_sdiff, β covBy_iff_card_sdiff_eq_one, covBy_iff_exists_erase]
aesop
#align finset.mem_up_shadow_iff_erase_mem Finset.mem_upShadow_iff_erase_mem
$
with <|
(#9319)
See Zulip thread for the discussion.
@@ -115,7 +115,7 @@ lemma mem_shadow_iff_insert_mem : t β β π β β a, a β t β§ insert a
See also `Finset.mem_shadow_iff_exists_sdiff`. -/
lemma mem_shadow_iff_exists_mem_card_add_one :
t β β π β β s β π, t β s β§ s.card = t.card + 1 := by
- refine mem_shadow_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ refine mem_shadow_iff_exists_sdiff.trans <| exists_congr fun t β¦ and_congr_right fun _ β¦
and_congr_right fun hst β¦ ?_
rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
exact card_mono hst
@@ -145,7 +145,7 @@ lemma mem_shadow_iterate_iff_exists_sdiff : t β β^[k] π β β s β
See also `Finset.mem_shadow_iterate_iff_exists_sdiff`. -/
lemma mem_shadow_iterate_iff_exists_mem_card_add :
t β β^[k] π β β s β π, t β s β§ s.card = t.card + k := by
- refine mem_shadow_iterate_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ refine mem_shadow_iterate_iff_exists_sdiff.trans <| exists_congr fun t β¦ and_congr_right fun _ β¦
and_congr_right fun hst β¦ ?_
rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
exact card_mono hst
@@ -237,7 +237,7 @@ lemma mem_upShadow_iff_erase_mem : t β ββΊ π β β a, a β t β§ eras
See also `Finset.mem_upShadow_iff_exists_sdiff`. -/
lemma mem_upShadow_iff_exists_mem_card_add_one :
t β ββΊ π β β s β π, s β t β§ t.card = s.card + 1 := by
- refine mem_upShadow_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ refine mem_upShadow_iff_exists_sdiff.trans <| exists_congr fun t β¦ and_congr_right fun _ β¦
and_congr_right fun hst β¦ ?_
rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
exact card_mono hst
@@ -273,7 +273,7 @@ lemma mem_upShadow_iterate_iff_exists_sdiff :
See also `Finset.mem_upShadow_iterate_iff_exists_sdiff`. -/
lemma mem_upShadow_iterate_iff_exists_mem_card_add :
t β ββΊ^[k] π β β s β π, s β t β§ t.card = s.card + k := by
- refine mem_upShadow_iterate_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ refine mem_upShadow_iterate_iff_exists_sdiff.trans <| exists_congr fun t β¦ and_congr_right fun _ β¦
and_congr_right fun hst β¦ ?_
rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
exact card_mono hst
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
@@ -164,7 +164,7 @@ lemma _root_.Set.Sized.shadow_iterate (hπ : (π : Set (Finset Ξ±)).Sized r)
(β^[k] π : Set (Finset Ξ±)).Sized (r - k) := by
simp_rw [Set.Sized, mem_coe, mem_shadow_iterate_iff_exists_sdiff]
rintro t β¨s, hs, hts, rflβ©
- rw [card_sdiff hts, β hπ hs, Nat.sub_sub_self (card_le_of_subset hts)]
+ rw [card_sdiff hts, β hπ hs, Nat.sub_sub_self (card_le_card hts)]
theorem sized_shadow_iff (h : β
β π) :
(β π : Set (Finset Ξ±)).Sized r β (π : Set (Finset Ξ±)).Sized (r + 1) := by
Co-authored-by: James <jamesgallicchio@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mario Carneiro <di.gama@gmail.com> Co-authored-by: Siddharth Bhat <siddu.druid@gmail.com>
@@ -211,7 +211,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
/-- `t` is in the upper shadow of `π` iff there is a `s β π` from which we can remove one element
to get `t`. -/
-lemma mem_upShadow_iff : t β ββΊ π β β s β π, β a, a β s β§ insert a s = t := by
+lemma mem_upShadow_iff : t β ββΊ π β β s β π, β a β s, insert a s = t := by
simp_rw [upShadow, mem_sup, mem_image, mem_compl]
#align finset.mem_up_shadow_iff Finset.mem_upShadow_iff
Characterise IsAtom
, IsCoatom
, Covby
in Set Ξ±
, Multiset Ξ±
, Finset Ξ±
and deduce that Multiset Ξ±
, Finset Ξ±
are graded orders.
Note I am moving some existing characterisations to here because it makes sense thematically, but I could be convinced otherwise.
@@ -3,6 +3,7 @@ Copyright (c) 2021 Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Bhavik Mehta, Alena Gusakov, YaΓ«l Dillies
-/
+import Mathlib.Data.Finset.Grade
import Mathlib.Data.Finset.Sups
import Mathlib.Logic.Function.Iterate
@@ -100,7 +101,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β β
See also `Finset.mem_shadow_iff_exists_mem_card_add_one`. -/
lemma mem_shadow_iff_exists_sdiff : t β β π β β s β π, t β s β§ (s \ t).card = 1 := by
- simp_rw [mem_shadow_iff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_erase, eq_comm]
+ simp_rw [mem_shadow_iff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_erase]
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
@@ -100,12 +100,12 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β β
See also `Finset.mem_shadow_iff_exists_mem_card_add_one`. -/
lemma mem_shadow_iff_exists_sdiff : t β β π β β s β π, t β s β§ (s \ t).card = 1 := by
- simp_rw [mem_shadow_iff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_erase, eq_comm]
+ simp_rw [mem_shadow_iff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_erase, eq_comm]
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
lemma mem_shadow_iff_insert_mem : t β β π β β a, a β t β§ insert a t β π := by
- simp_rw [mem_shadow_iff_exists_sdiff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
+ simp_rw [mem_shadow_iff_exists_sdiff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
aesop
#align finset.mem_shadow_iff_insert_mem Finset.mem_shadow_iff_insert_mem
@@ -163,7 +163,7 @@ lemma _root_.Set.Sized.shadow_iterate (hπ : (π : Set (Finset Ξ±)).Sized r)
(β^[k] π : Set (Finset Ξ±)).Sized (r - k) := by
simp_rw [Set.Sized, mem_coe, mem_shadow_iterate_iff_exists_sdiff]
rintro t β¨s, hs, hts, rflβ©
- rw [card_sdiff hts, βhπ hs, Nat.sub_sub_self (card_le_of_subset hts)]
+ rw [card_sdiff hts, β hπ hs, Nat.sub_sub_self (card_le_of_subset hts)]
theorem sized_shadow_iff (h : β
β π) :
(β π : Set (Finset Ξ±)).Sized r β (π : Set (Finset Ξ±)).Sized (r + 1) := by
@@ -222,12 +222,12 @@ theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β
See also `Finset.mem_upShadow_iff_exists_mem_card_add_one`. -/
lemma mem_upShadow_iff_exists_sdiff : t β ββΊ π β β s β π, s β t β§ (t \ s).card = 1 := by
- simp_rw [mem_upShadow_iff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
+ simp_rw [mem_upShadow_iff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
finset is in `π`. -/
lemma mem_upShadow_iff_erase_mem : t β ββΊ π β β a, a β t β§ erase t a β π := by
- simp_rw [mem_upShadow_iff_exists_sdiff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_erase]
+ simp_rw [mem_upShadow_iff_exists_sdiff, β covby_iff_card_sdiff_eq_one, covby_iff_exists_erase]
aesop
#align finset.mem_up_shadow_iff_erase_mem Finset.mem_upShadow_iff_erase_mem
@@ -247,7 +247,7 @@ lemma mem_upShadow_iterate_iff_exists_card :
induction' k with k ih generalizing t
Β· simp
simp only [mem_upShadow_iff_erase_mem, ih, Function.iterate_succ_apply', card_eq_succ,
- subset_erase, erase_sdiff_comm, βsdiff_insert]
+ subset_erase, erase_sdiff_comm, β sdiff_insert]
constructor
Β· rintro β¨a, hat, u, rfl, β¨hut, hauβ©, htuβ©
exact β¨_, β¨_, _, hau, rfl, rflβ©, insert_subset hat hut, htuβ©
@@ -324,14 +324,14 @@ theorem mem_upShadow_iff_exists_mem_card_add :
ext s
simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff, mem_compls]
refine (compl_involutive.toPerm _).exists_congr_left.trans ?_
- simp [βcompl_involutive.eq_iff]
+ simp [β compl_involutive.eq_iff]
#align finset.up_shadow_image_compl Finset.shadow_compls
@[simp] lemma upShadow_compls : ββΊ παΆΛ’ = (β π)αΆΛ’ := by
ext s
simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff, mem_compls]
refine (compl_involutive.toPerm _).exists_congr_left.trans ?_
- simp [βcompl_involutive.eq_iff]
+ simp [β compl_involutive.eq_iff]
#align finset.shadow_image_compl Finset.upShadow_compls
end UpShadow
Move the lemmas characterising Covby
on Finset Ξ±
from Data.Finset.Interval
to Data.Finset.Basic
. Golf the other proofs in Data.Finset.Interval
and make sure the lemma names reflect whether each lemma is about insert
or cons
.
@@ -71,6 +71,9 @@ theorem shadow_empty : β (β
: Finset (Finset Ξ±)) = β
:=
rfl
#align finset.shadow_empty Finset.shadow_empty
+@[simp] lemma shadow_iterate_empty (k : β) : β^[k] (β
: Finset (Finset Ξ±)) = β
:= by
+ induction' k <;> simp [*, shadow_empty]
+
@[simp]
theorem shadow_singleton_empty : β ({β
} : Finset (Finset Ξ±)) = β
:=
rfl
@@ -83,9 +86,9 @@ theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Fins
sup_mono
#align finset.shadow_monotone Finset.shadow_monotone
-/-- `s` is in the shadow of `π` iff there is a `t β π` from which we can remove one element to
-get `s`. -/
-theorem mem_shadow_iff : s β β π β β t β π, β a β t, erase t a = s := by
+/-- `t` is in the shadow of `π` iff there is a `s β π` from which we can remove one element to
+get `t`. -/
+lemma mem_shadow_iff : t β β π β β s β π, β a β s, erase s a = t := by
simp only [shadow, mem_sup, mem_image]
#align finset.mem_shadow_iff Finset.mem_shadow_iff
@@ -93,24 +96,74 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β β
mem_shadow_iff.2 β¨s, hs, a, ha, rflβ©
#align finset.erase_mem_shadow Finset.erase_mem_shadow
+/-- `t β βπ` iff `t` is exactly one element less than something from `π`.
+
+See also `Finset.mem_shadow_iff_exists_mem_card_add_one`. -/
+lemma mem_shadow_iff_exists_sdiff : t β β π β β s β π, t β s β§ (s \ t).card = 1 := by
+ simp_rw [mem_shadow_iff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_erase, eq_comm]
+
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
-theorem mem_shadow_iff_insert_mem : s β β π β β (a : _) (_ : a β s), insert a s β π := by
- refine' mem_shadow_iff.trans β¨_, _β©
- Β· rintro β¨s, hs, a, ha, rflβ©
- refine' β¨a, not_mem_erase a s, _β©
- rwa [insert_erase ha]
- Β· rintro β¨a, ha, hsβ©
- exact β¨insert a s, hs, a, mem_insert_self _ _, erase_insert haβ©
+lemma mem_shadow_iff_insert_mem : t β β π β β a, a β t β§ insert a t β π := by
+ simp_rw [mem_shadow_iff_exists_sdiff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
+ aesop
#align finset.mem_shadow_iff_insert_mem Finset.mem_shadow_iff_insert_mem
+/-- `s β β π` iff `s` is exactly one element less than something from `π`.
+
+See also `Finset.mem_shadow_iff_exists_sdiff`. -/
+lemma mem_shadow_iff_exists_mem_card_add_one :
+ t β β π β β s β π, t β s β§ s.card = t.card + 1 := by
+ refine mem_shadow_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ and_congr_right fun hst β¦ ?_
+ rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
+ exact card_mono hst
+#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_one
+
+lemma mem_shadow_iterate_iff_exists_card :
+ t β β^[k] π β β u : Finset Ξ±, u.card = k β§ Disjoint t u β§ t βͺ u β π := by
+ induction' k with k ih generalizing t
+ Β· simp
+ simp only [mem_shadow_iff_insert_mem, ih, Function.iterate_succ_apply', card_eq_succ]
+ aesop
+
+/-- `t β β^k π` iff `t` is exactly `k` elements less than something from `π`.
+
+See also `Finset.mem_shadow_iff_exists_mem_card_add`. -/
+lemma mem_shadow_iterate_iff_exists_sdiff : t β β^[k] π β β s β π, t β s β§ (s \ t).card = k := by
+ rw [mem_shadow_iterate_iff_exists_card]
+ constructor
+ Β· rintro β¨u, rfl, htu, hsuAβ©
+ exact β¨_, hsuA, subset_union_left _ _, by rw [union_sdiff_cancel_left htu]β©
+ Β· rintro β¨s, hs, hts, rflβ©
+ refine β¨s \ t, rfl, disjoint_sdiff, ?_β©
+ rwa [union_sdiff_self_eq_union, union_eq_right.2 hts]
+
+/-- `t β β^k π` iff `t` is exactly `k` elements less than something in `π`.
+
+See also `Finset.mem_shadow_iterate_iff_exists_sdiff`. -/
+lemma mem_shadow_iterate_iff_exists_mem_card_add :
+ t β β^[k] π β β s β π, t β s β§ s.card = t.card + k := by
+ refine mem_shadow_iterate_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ and_congr_right fun hst β¦ ?_
+ rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
+ exact card_mono hst
+#align finset.mem_shadow_iff_exists_mem_card_add Finset.mem_shadow_iterate_iff_exists_mem_card_add
+
/-- The shadow of a family of `r`-sets is a family of `r - 1`-sets. -/
-protected theorem Set.Sized.shadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
+protected theorem _root_.Set.Sized.shadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
(β π : Set (Finset Ξ±)).Sized (r - 1) := by
intro A h
obtain β¨A, hA, i, hi, rflβ© := mem_shadow_iff.1 h
rw [card_erase_of_mem hi, hπ hA]
-#align finset.set.sized.shadow Finset.Set.Sized.shadow
+#align finset.set.sized.shadow Set.Sized.shadow
+
+/-- The `k`-th shadow of a family of `r`-sets is a family of `r - k`-sets. -/
+lemma _root_.Set.Sized.shadow_iterate (hπ : (π : Set (Finset Ξ±)).Sized r) :
+ (β^[k] π : Set (Finset Ξ±)).Sized (r - k) := by
+ simp_rw [Set.Sized, mem_coe, mem_shadow_iterate_iff_exists_sdiff]
+ rintro t β¨s, hs, hts, rflβ©
+ rw [card_sdiff hts, βhπ hs, Nat.sub_sub_self (card_le_of_subset hts)]
theorem sized_shadow_iff (h : β
β π) :
(β π : Set (Finset Ξ±)).Sized r β (π : Set (Finset Ξ±)).Sized (r + 1) := by
@@ -119,55 +172,12 @@ theorem sized_shadow_iff (h : β
β π) :
rw [β hπ (erase_mem_shadow hs ha), card_erase_add_one ha]
#align finset.sized_shadow_iff Finset.sized_shadow_iff
-/-- `s β β π` iff `s` is exactly one element less than something from `π` -/
-theorem mem_shadow_iff_exists_mem_card_add_one :
- s β β π β β t β π, s β t β§ t.card = s.card + 1 := by
- refine' mem_shadow_iff_insert_mem.trans β¨_, _β©
- Β· rintro β¨a, ha, hsβ©
- exact β¨insert a s, hs, subset_insert _ _, card_insert_of_not_mem haβ©
- Β· rintro β¨t, ht, hst, hβ©
- obtain β¨a, haβ© : β a, t \ s = {a} :=
- card_eq_one.1 (by rw [card_sdiff hst, h, add_tsub_cancel_left])
- exact
- β¨a, fun hat => not_mem_sdiff_of_mem_right hat (ha.superset <| mem_singleton_self a),
- by rwa [insert_eq a s, β ha, sdiff_union_of_subset hst]β©
-#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_one
-
/-- Being in the shadow of `π` means we have a superset in `π`. -/
-theorem exists_subset_of_mem_shadow (hs : s β β π) : β t β π, s β t :=
+lemma exists_subset_of_mem_shadow (hs : t β β π) : β s β π, t β s :=
let β¨t, ht, hstβ© := mem_shadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, hst.1β©
#align finset.exists_subset_of_mem_shadow Finset.exists_subset_of_mem_shadow
-/-- `t β β^k π` iff `t` is exactly `k` elements less than something in `π`. -/
-theorem mem_shadow_iff_exists_mem_card_add :
- s β β ^[k] π β β t β π, s β t β§ t.card = s.card + k := by
- induction' k with k ih generalizing π s
- Β· refine' β¨fun hs => β¨s, hs, Subset.refl _, rflβ©, _β©
- rintro β¨t, ht, hst, hcardβ©
- rwa [eq_of_subset_of_card_le hst hcard.le]
- simp only [exists_prop, Function.comp_apply, Function.iterate_succ]
- refine' ih.trans _
- clear ih
- constructor
- Β· rintro β¨t, ht, hst, hcardstβ©
- obtain β¨u, hu, htu, hcardtuβ© := mem_shadow_iff_exists_mem_card_add_one.1 ht
- refine' β¨u, hu, hst.trans htu, _β©
- rw [hcardtu, hcardst]
- rfl
- Β· rintro β¨t, ht, hst, hcardβ©
- obtain β¨u, hsu, hut, huβ© :=
- Finset.exists_intermediate_set k
- (by
- rw [add_comm, hcard]
- exact le_succ _)
- hst
- rw [add_comm] at hu
- refine' β¨u, mem_shadow_iff_exists_mem_card_add_one.2 β¨t, ht, hut, _β©, hsu, huβ©
- rw [hcard, hu]
- rfl
-#align finset.mem_shadow_iff_exists_mem_card_add Finset.mem_shadow_iff_exists_mem_card_add
-
end Shadow
open FinsetFamily
@@ -198,48 +208,83 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
fun _ _ => sup_mono
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/-- `s` is in the upper shadow of `π` iff there is a `t β π` from which we can remove one element
-to get `s`. -/
-theorem mem_upShadow_iff : s β ββΊ π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
- simp_rw [upShadow, mem_sup, mem_image, exists_prop, mem_compl]
+/-- `t` is in the upper shadow of `π` iff there is a `s β π` from which we can remove one element
+to get `t`. -/
+lemma mem_upShadow_iff : t β ββΊ π β β s β π, β a, a β s β§ insert a s = t := by
+ simp_rw [upShadow, mem_sup, mem_image, mem_compl]
#align finset.mem_up_shadow_iff Finset.mem_upShadow_iff
theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β ββΊ π :=
mem_upShadow_iff.2 β¨s, hs, a, ha, rflβ©
#align finset.insert_mem_up_shadow Finset.insert_mem_upShadow
-/-- The upper shadow of a family of `r`-sets is a family of `r + 1`-sets. -/
-protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
- (ββΊ π : Set (Finset Ξ±)).Sized (r + 1) := by
- intro A h
- obtain β¨A, hA, i, hi, rflβ© := mem_upShadow_iff.1 h
- rw [card_insert_of_not_mem hi, hπ hA]
-#align finset.set.sized.up_shadow Finset.Set.Sized.upShadow
+/-- `t` is in the upper shadow of `π` iff `t` is exactly one element more than something from `π`.
+
+See also `Finset.mem_upShadow_iff_exists_mem_card_add_one`. -/
+lemma mem_upShadow_iff_exists_sdiff : t β ββΊ π β β s β π, s β t β§ (t \ s).card = 1 := by
+ simp_rw [mem_upShadow_iff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_insert]
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
finset is in `π`. -/
-theorem mem_upShadow_iff_erase_mem : s β ββΊ π β β a β s, s.erase a β π := by
- refine' mem_upShadow_iff.trans β¨_, _β©
- Β· rintro β¨s, hs, a, ha, rflβ©
- refine' β¨a, mem_insert_self a s, _β©
- rwa [erase_insert ha]
- Β· rintro β¨a, ha, hsβ©
- exact β¨s.erase a, hs, a, not_mem_erase _ _, insert_erase haβ©
+lemma mem_upShadow_iff_erase_mem : t β ββΊ π β β a, a β t β§ erase t a β π := by
+ simp_rw [mem_upShadow_iff_exists_sdiff, βcovby_iff_card_sdiff_eq_one, covby_iff_exists_erase]
+ aesop
#align finset.mem_up_shadow_iff_erase_mem Finset.mem_upShadow_iff_erase_mem
-/-- `s β ββΊ π` iff `s` is exactly one element less than something from `π`. -/
-theorem mem_upShadow_iff_exists_mem_card_add_one :
- s β ββΊ π β β t β π, t β s β§ t.card + 1 = s.card := by
- refine' mem_upShadow_iff_erase_mem.trans β¨_, _β©
- Β· rintro β¨a, ha, hsβ©
- exact β¨s.erase a, hs, erase_subset _ _, card_erase_add_one haβ©
- Β· rintro β¨t, ht, hts, hβ©
- obtain β¨a, haβ© : β a, s \ t = {a} :=
- card_eq_one.1 (by rw [card_sdiff hts, β h, add_tsub_cancel_left])
- refine' β¨a, sdiff_subset _ _ ((ha.ge : _ β _) <| mem_singleton_self a), _β©
- rwa [β sdiff_singleton_eq_erase, β ha, sdiff_sdiff_eq_self hts]
+/-- `t` is in the upper shadow of `π` iff `t` is exactly one element less than something from `π`.
+
+See also `Finset.mem_upShadow_iff_exists_sdiff`. -/
+lemma mem_upShadow_iff_exists_mem_card_add_one :
+ t β ββΊ π β β s β π, s β t β§ t.card = s.card + 1 := by
+ refine mem_upShadow_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ and_congr_right fun hst β¦ ?_
+ rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
+ exact card_mono hst
#align finset.mem_up_shadow_iff_exists_mem_card_add_one Finset.mem_upShadow_iff_exists_mem_card_add_one
+lemma mem_upShadow_iterate_iff_exists_card :
+ t β ββΊ^[k] π β β u : Finset Ξ±, u.card = k β§ u β t β§ t \ u β π := by
+ induction' k with k ih generalizing t
+ Β· simp
+ simp only [mem_upShadow_iff_erase_mem, ih, Function.iterate_succ_apply', card_eq_succ,
+ subset_erase, erase_sdiff_comm, βsdiff_insert]
+ constructor
+ Β· rintro β¨a, hat, u, rfl, β¨hut, hauβ©, htuβ©
+ exact β¨_, β¨_, _, hau, rfl, rflβ©, insert_subset hat hut, htuβ©
+ Β· rintro β¨_, β¨a, u, hau, rfl, rflβ©, hut, htuβ©
+ rw [insert_subset_iff] at hut
+ exact β¨a, hut.1, _, rfl, β¨hut.2, hauβ©, htuβ©
+
+/-- `t` is in the upper shadow of `π` iff `t` is exactly `k` elements less than something from `π`.
+
+See also `Finset.mem_upShadow_iff_exists_mem_card_add`. -/
+lemma mem_upShadow_iterate_iff_exists_sdiff :
+ t β ββΊ^[k] π β β s β π, s β t β§ (t \ s).card = k := by
+ rw [mem_upShadow_iterate_iff_exists_card]
+ constructor
+ Β· rintro β¨u, rfl, hut, htuβ©
+ exact β¨_, htu, sdiff_subset _ _, by rw [sdiff_sdiff_eq_self hut]β©
+ Β· rintro β¨s, hs, hst, rflβ©
+ exact β¨_, rfl, sdiff_subset _ _, by rwa [sdiff_sdiff_eq_self hst]β©
+
+/-- `t β ββΊ^k π` iff `t` is exactly `k` elements less than something in `π`.
+
+See also `Finset.mem_upShadow_iterate_iff_exists_sdiff`. -/
+lemma mem_upShadow_iterate_iff_exists_mem_card_add :
+ t β ββΊ^[k] π β β s β π, s β t β§ t.card = s.card + k := by
+ refine mem_upShadow_iterate_iff_exists_sdiff.trans $ exists_congr fun t β¦ and_congr_right fun _ β¦
+ and_congr_right fun hst β¦ ?_
+ rw [card_sdiff hst, tsub_eq_iff_eq_add_of_le, add_comm]
+ exact card_mono hst
+
+/-- The upper shadow of a family of `r`-sets is a family of `r + 1`-sets. -/
+protected lemma _root_.Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
+ (ββΊ π : Set (Finset Ξ±)).Sized (r + 1) := by
+ intro A h
+ obtain β¨A, hA, i, hi, rflβ© := mem_upShadow_iff.1 h
+ rw [card_insert_of_not_mem hi, hπ hA]
+#align finset.set.sized.up_shadow Set.Sized.upShadow
+
/-- Being in the upper shadow of `π` means we have a superset in `π`. -/
theorem exists_subset_of_mem_upShadow (hs : s β ββΊ π) : β t β π, t β s :=
let β¨t, ht, hts, _β© := mem_upShadow_iff_exists_mem_card_add_one.1 hs
@@ -260,7 +305,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
Β· rintro β¨t, ht, hts, hcardstβ©
obtain β¨u, hu, hut, hcardtuβ© := mem_upShadow_iff_exists_mem_card_add_one.1 ht
refine' β¨u, hu, hut.trans hts, _β©
- rw [β hcardst, β hcardtu, add_right_comm]
+ rw [β hcardst, hcardtu, add_right_comm]
rfl
Β· rintro β¨t, ht, hts, hcardβ©
obtain β¨u, htu, hus, huβ© :=
@@ -270,7 +315,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
exact add_le_add_left (succ_le_of_lt (zero_lt_succ _)) _)
hts
rw [add_comm] at hu
- refine' β¨u, mem_upShadow_iff_exists_mem_card_add_one.2 β¨t, ht, htu, hu.symmβ©, hus, _β©
+ refine' β¨u, mem_upShadow_iff_exists_mem_card_add_one.2 β¨t, ht, htu, huβ©, hus, _β©
rw [hu, β hcard, add_right_comm]
rfl
#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_add
Define Finset.diffs
and Finset.compls
, the pointwise set difference of two finsets and pointwise complement of a finset.
diffs
appears in the statement of the Marica-SchΓΆnheim inequality and compls
in the proof.
Also fix the corresponding statements for sups
and infs
to use the new Β·
notation.
@@ -3,7 +3,7 @@ Copyright (c) 2021 Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Bhavik Mehta, Alena Gusakov, YaΓ«l Dillies
-/
-import Mathlib.Data.Finset.Slice
+import Mathlib.Data.Finset.Sups
import Mathlib.Logic.Function.Iterate
#align_import combinatorics.set_family.shadow from "leanprover-community/mathlib"@"f7fc89d5d5ff1db2d1242c7bb0e9062ce47ef47c"
@@ -20,7 +20,7 @@ to projecting each finset down once in all available directions.
* `Finset.shadow`: The shadow of a set family. Everything we can get by removing a new element from
some set.
-* `Finset.up_shadow`: The upper shadow of a set family. Everything we can get by adding an element
+* `Finset.upShadow`: The upper shadow of a set family. Everything we can get by adding an element
to some set.
## Notation
@@ -275,27 +275,19 @@ theorem mem_upShadow_iff_exists_mem_card_add :
rfl
#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_add
-@[simp]
-theorem shadow_image_compl : (β π).image compl = ββΊ (π.image compl) := by
+@[simp] lemma shadow_compls : β παΆΛ’ = (ββΊ π)αΆΛ’ := by
ext s
- simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff]
- constructor
- Β· rintro β¨_, β¨s, hs, a, ha, rflβ©, rflβ©
- exact β¨sαΆ, β¨s, hs, rflβ©, a, not_mem_compl.2 ha, compl_erase.symmβ©
- Β· rintro β¨_, β¨s, hs, rflβ©, a, ha, rflβ©
- exact β¨s.erase a, β¨s, hs, a, not_mem_compl.1 ha, rflβ©, compl_eraseβ©
-#align finset.shadow_image_compl Finset.shadow_image_compl
+ simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff, mem_compls]
+ refine (compl_involutive.toPerm _).exists_congr_left.trans ?_
+ simp [βcompl_involutive.eq_iff]
+#align finset.up_shadow_image_compl Finset.shadow_compls
-@[simp]
-theorem upShadow_image_compl : (ββΊ π).image compl = β (π.image compl) := by
+@[simp] lemma upShadow_compls : ββΊ παΆΛ’ = (β π)αΆΛ’ := by
ext s
- simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff]
- constructor
- Β· rintro β¨_, β¨s, hs, a, ha, rflβ©, rflβ©
- exact β¨sαΆ, β¨s, hs, rflβ©, a, mem_compl.2 ha, compl_insert.symmβ©
- Β· rintro β¨_, β¨s, hs, rflβ©, a, ha, rflβ©
- exact β¨insert a s, β¨s, hs, a, mem_compl.1 ha, rflβ©, compl_insertβ©
-#align finset.up_shadow_image_compl Finset.upShadow_image_compl
+ simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff, mem_compls]
+ refine (compl_involutive.toPerm _).exists_congr_left.trans ?_
+ simp [βcompl_involutive.eq_iff]
+#align finset.shadow_image_compl Finset.upShadow_compls
end UpShadow
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -45,7 +45,7 @@ shadow, set family
open Finset Nat
-variable {Ξ± : Type _}
+variable {Ξ± : Type*}
namespace Finset
@@ -60,7 +60,6 @@ def shadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
π.sup fun s => s.image (erase s)
#align finset.shadow Finset.shadow
--- mathport name: finset.shadow
-- Porting note: added `inherit_doc` to calm linter
@[inherit_doc] scoped[FinsetFamily] notation:max "β " => Finset.shadow
-- Porting note: had to open FinsetFamily
@@ -130,8 +129,8 @@ theorem mem_shadow_iff_exists_mem_card_add_one :
obtain β¨a, haβ© : β a, t \ s = {a} :=
card_eq_one.1 (by rw [card_sdiff hst, h, add_tsub_cancel_left])
exact
- β¨a, fun hat => not_mem_sdiff_of_mem_right hat ((ha.ge : _ β _) <| mem_singleton_self a), by
- rwa [insert_eq a s, β ha, sdiff_union_of_subset hst]β©
+ β¨a, fun hat => not_mem_sdiff_of_mem_right hat (ha.superset <| mem_singleton_self a),
+ by rwa [insert_eq a s, β ha, sdiff_union_of_subset hst]β©
#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_one
/-- Being in the shadow of `π` means we have a superset in `π`. -/
@@ -178,13 +177,12 @@ section UpShadow
variable [DecidableEq Ξ±] [Fintype Ξ±] {π : Finset (Finset Ξ±)} {s t : Finset Ξ±} {a : Ξ±} {k r : β}
/-- The upper shadow of a set family `π` is all sets we can get by adding one element to any set in
-`π`, and the (`k` times) iterated upper shadow (`up_shadow^[k]`) is all sets we can get by adding
+`π`, and the (`k` times) iterated upper shadow (`upShadow^[k]`) is all sets we can get by adding
`k` elements from any set in `π`. -/
def upShadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
π.sup fun s => sαΆ.image fun a => insert a s
#align finset.up_shadow Finset.upShadow
--- mathport name: finset.up_shadow
-- Porting note: added `inherit_doc` to calm linter
@[inherit_doc] scoped[FinsetFamily] notation:max "ββΊ " => Finset.upShadow
@@ -2,15 +2,12 @@
Copyright (c) 2021 Bhavik Mehta. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Bhavik Mehta, Alena Gusakov, YaΓ«l Dillies
-
-! This file was ported from Lean 3 source module combinatorics.set_family.shadow
-! leanprover-community/mathlib commit f7fc89d5d5ff1db2d1242c7bb0e9062ce47ef47c
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Data.Finset.Slice
import Mathlib.Logic.Function.Iterate
+#align_import combinatorics.set_family.shadow from "leanprover-community/mathlib"@"f7fc89d5d5ff1db2d1242c7bb0e9062ce47ef47c"
+
/-!
# Shadows
@@ -87,7 +87,7 @@ theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Fins
sup_mono
#align finset.shadow_monotone Finset.shadow_monotone
-/-- `s` is in the shadow of `π` iff there is an `t β π` from which we can remove one element to
+/-- `s` is in the shadow of `π` iff there is a `t β π` from which we can remove one element to
get `s`. -/
theorem mem_shadow_iff : s β β π β β t β π, β a β t, erase t a = s := by
simp only [shadow, mem_sup, mem_image]
@@ -203,7 +203,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
fun _ _ => sup_mono
#align finset.up_shadow_monotone Finset.upShadow_monotone
-/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
+/-- `s` is in the upper shadow of `π` iff there is a `t β π` from which we can remove one element
to get `s`. -/
theorem mem_upShadow_iff : s β ββΊ π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
simp_rw [upShadow, mem_sup, mem_image, exists_prop, mem_compl]
@@ -65,18 +65,18 @@ def shadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
-- mathport name: finset.shadow
-- Porting note: added `inherit_doc` to calm linter
-@[inherit_doc] scoped[FinsetFamily] notation:90 "β " => Finset.shadow
+@[inherit_doc] scoped[FinsetFamily] notation:max "β " => Finset.shadow
-- Porting note: had to open FinsetFamily
open FinsetFamily
/-- The shadow of the empty set is empty. -/
@[simp]
-theorem shadow_empty : (β ) (β
: Finset (Finset Ξ±)) = β
:=
+theorem shadow_empty : β (β
: Finset (Finset Ξ±)) = β
:=
rfl
#align finset.shadow_empty Finset.shadow_empty
@[simp]
-theorem shadow_singleton_empty : (β ) ({β
} : Finset (Finset Ξ±)) = β
:=
+theorem shadow_singleton_empty : β ({β
} : Finset (Finset Ξ±)) = β
:=
rfl
#align finset.shadow_singleton_empty Finset.shadow_singleton_empty
@@ -89,17 +89,17 @@ theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Fins
/-- `s` is in the shadow of `π` iff there is an `t β π` from which we can remove one element to
get `s`. -/
-theorem mem_shadow_iff : s β (β ) π β β t β π, β a β t, erase t a = s := by
+theorem mem_shadow_iff : s β β π β β t β π, β a β t, erase t a = s := by
simp only [shadow, mem_sup, mem_image]
#align finset.mem_shadow_iff Finset.mem_shadow_iff
-theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β ) π :=
+theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β β π :=
mem_shadow_iff.2 β¨s, hs, a, ha, rflβ©
#align finset.erase_mem_shadow Finset.erase_mem_shadow
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
-theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _) (_ : a β s), insert a s β π := by
+theorem mem_shadow_iff_insert_mem : s β β π β β (a : _) (_ : a β s), insert a s β π := by
refine' mem_shadow_iff.trans β¨_, _β©
Β· rintro β¨s, hs, a, ha, rflβ©
refine' β¨a, not_mem_erase a s, _β©
@@ -110,14 +110,14 @@ theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _) (_ : a β
/-- The shadow of a family of `r`-sets is a family of `r - 1`-sets. -/
protected theorem Set.Sized.shadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
- ((β ) π : Set (Finset Ξ±)).Sized (r - 1) := by
+ (β π : Set (Finset Ξ±)).Sized (r - 1) := by
intro A h
obtain β¨A, hA, i, hi, rflβ© := mem_shadow_iff.1 h
rw [card_erase_of_mem hi, hπ hA]
#align finset.set.sized.shadow Finset.Set.Sized.shadow
theorem sized_shadow_iff (h : β
β π) :
- ((β ) π : Set (Finset Ξ±)).Sized r β (π : Set (Finset Ξ±)).Sized (r + 1) := by
+ (β π : Set (Finset Ξ±)).Sized r β (π : Set (Finset Ξ±)).Sized (r + 1) := by
refine' β¨fun hπ s hs => _, Set.Sized.shadowβ©
obtain β¨a, haβ© := nonempty_iff_ne_empty.2 (ne_of_mem_of_not_mem hs h)
rw [β hπ (erase_mem_shadow hs ha), card_erase_add_one ha]
@@ -125,7 +125,7 @@ theorem sized_shadow_iff (h : β
β π) :
/-- `s β β π` iff `s` is exactly one element less than something from `π` -/
theorem mem_shadow_iff_exists_mem_card_add_one :
- s β (β ) π β β t β π, s β t β§ t.card = s.card + 1 := by
+ s β β π β β t β π, s β t β§ t.card = s.card + 1 := by
refine' mem_shadow_iff_insert_mem.trans β¨_, _β©
Β· rintro β¨a, ha, hsβ©
exact β¨insert a s, hs, subset_insert _ _, card_insert_of_not_mem haβ©
@@ -138,7 +138,7 @@ theorem mem_shadow_iff_exists_mem_card_add_one :
#align finset.mem_shadow_iff_exists_mem_card_add_one Finset.mem_shadow_iff_exists_mem_card_add_one
/-- Being in the shadow of `π` means we have a superset in `π`. -/
-theorem exists_subset_of_mem_shadow (hs : s β (β ) π) : β t β π, s β t :=
+theorem exists_subset_of_mem_shadow (hs : s β β π) : β t β π, s β t :=
let β¨t, ht, hstβ© := mem_shadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, hst.1β©
#align finset.exists_subset_of_mem_shadow Finset.exists_subset_of_mem_shadow
@@ -189,11 +189,11 @@ def upShadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
-- mathport name: finset.up_shadow
-- Porting note: added `inherit_doc` to calm linter
-@[inherit_doc] scoped[FinsetFamily] notation:90 "ββΊ " => Finset.upShadow
+@[inherit_doc] scoped[FinsetFamily] notation:max "ββΊ " => Finset.upShadow
/-- The upper shadow of the empty set is empty. -/
@[simp]
-theorem upShadow_empty : (ββΊ ) (β
: Finset (Finset Ξ±)) = β
:=
+theorem upShadow_empty : ββΊ (β
: Finset (Finset Ξ±)) = β
:=
rfl
#align finset.up_shadow_empty Finset.upShadow_empty
@@ -205,17 +205,17 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
-theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
+theorem mem_upShadow_iff : s β ββΊ π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
simp_rw [upShadow, mem_sup, mem_image, exists_prop, mem_compl]
#align finset.mem_up_shadow_iff Finset.mem_upShadow_iff
-theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β (ββΊ ) π :=
+theorem insert_mem_upShadow (hs : s β π) (ha : a β s) : insert a s β ββΊ π :=
mem_upShadow_iff.2 β¨s, hs, a, ha, rflβ©
#align finset.insert_mem_up_shadow Finset.insert_mem_upShadow
/-- The upper shadow of a family of `r`-sets is a family of `r + 1`-sets. -/
protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r) :
- ((ββΊ ) π : Set (Finset Ξ±)).Sized (r + 1) := by
+ (ββΊ π : Set (Finset Ξ±)).Sized (r + 1) := by
intro A h
obtain β¨A, hA, i, hi, rflβ© := mem_upShadow_iff.1 h
rw [card_insert_of_not_mem hi, hπ hA]
@@ -223,7 +223,7 @@ protected theorem Set.Sized.upShadow (hπ : (π : Set (Finset Ξ±)).Sized r)
/-- `t` is in the upper shadow of `π` iff we can remove an element from it so that the resulting
finset is in `π`. -/
-theorem mem_upShadow_iff_erase_mem : s β (ββΊ ) π β β a β s, s.erase a β π := by
+theorem mem_upShadow_iff_erase_mem : s β ββΊ π β β a β s, s.erase a β π := by
refine' mem_upShadow_iff.trans β¨_, _β©
Β· rintro β¨s, hs, a, ha, rflβ©
refine' β¨a, mem_insert_self a s, _β©
@@ -234,7 +234,7 @@ theorem mem_upShadow_iff_erase_mem : s β (ββΊ ) π β β a β s, s.era
/-- `s β ββΊ π` iff `s` is exactly one element less than something from `π`. -/
theorem mem_upShadow_iff_exists_mem_card_add_one :
- s β (ββΊ ) π β β t β π, t β s β§ t.card + 1 = s.card := by
+ s β ββΊ π β β t β π, t β s β§ t.card + 1 = s.card := by
refine' mem_upShadow_iff_erase_mem.trans β¨_, _β©
Β· rintro β¨a, ha, hsβ©
exact β¨s.erase a, hs, erase_subset _ _, card_erase_add_one haβ©
@@ -246,7 +246,7 @@ theorem mem_upShadow_iff_exists_mem_card_add_one :
#align finset.mem_up_shadow_iff_exists_mem_card_add_one Finset.mem_upShadow_iff_exists_mem_card_add_one
/-- Being in the upper shadow of `π` means we have a superset in `π`. -/
-theorem exists_subset_of_mem_upShadow (hs : s β (ββΊ ) π) : β t β π, t β s :=
+theorem exists_subset_of_mem_upShadow (hs : s β ββΊ π) : β t β π, t β s :=
let β¨t, ht, hts, _β© := mem_upShadow_iff_exists_mem_card_add_one.1 hs
β¨t, ht, htsβ©
#align finset.exists_subset_of_mem_up_shadow Finset.exists_subset_of_mem_upShadow
@@ -281,7 +281,7 @@ theorem mem_upShadow_iff_exists_mem_card_add :
#align finset.mem_up_shadow_iff_exists_mem_card_add Finset.mem_upShadow_iff_exists_mem_card_add
@[simp]
-theorem shadow_image_compl : ((β ) π).image compl = (ββΊ ) (π.image compl) := by
+theorem shadow_image_compl : (β π).image compl = ββΊ (π.image compl) := by
ext s
simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff]
constructor
@@ -292,7 +292,7 @@ theorem shadow_image_compl : ((β ) π).image compl = (ββΊ ) (π.image c
#align finset.shadow_image_compl Finset.shadow_image_compl
@[simp]
-theorem upShadow_image_compl : ((ββΊ ) π).image compl = (β ) (π.image compl) := by
+theorem upShadow_image_compl : (ββΊ π).image compl = β (π.image compl) := by
ext s
simp only [mem_image, exists_prop, mem_shadow_iff, mem_upShadow_iff]
constructor
@@ -145,7 +145,7 @@ theorem exists_subset_of_mem_shadow (hs : s β (β ) π) : β t β π, s
/-- `t β β^k π` iff `t` is exactly `k` elements less than something in `π`. -/
theorem mem_shadow_iff_exists_mem_card_add :
- s β (β ^[k]) π β β t β π, s β t β§ t.card = s.card + k := by
+ s β β ^[k] π β β t β π, s β t β§ t.card = s.card + k := by
induction' k with k ih generalizing π s
Β· refine' β¨fun hs => β¨s, hs, Subset.refl _, rflβ©, _β©
rintro β¨t, ht, hst, hcardβ©
@@ -253,7 +253,7 @@ theorem exists_subset_of_mem_upShadow (hs : s β (ββΊ ) π) : β t β
/-- `t β β^k π` iff `t` is exactly `k` elements more than something in `π`. -/
theorem mem_upShadow_iff_exists_mem_card_add :
- s β (ββΊ ^[k]) π β β t β π, t β s β§ t.card + k = s.card := by
+ s β ββΊ ^[k] π β β t β π, t β s β§ t.card + k = s.card := by
induction' k with k ih generalizing π s
Β· refine' β¨fun hs => β¨s, hs, Subset.refl _, rflβ©, _β©
rintro β¨t, ht, hst, hcardβ©
@@ -99,7 +99,7 @@ theorem erase_mem_shadow (hs : s β π) (ha : a β s) : erase s a β (β )
/-- `t` is in the shadow of `π` iff we can add an element to it so that the resulting finset is in
`π`. -/
-theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _)(_ : a β s), insert a s β π := by
+theorem mem_shadow_iff_insert_mem : s β (β ) π β β (a : _) (_ : a β s), insert a s β π := by
refine' mem_shadow_iff.trans β¨_, _β©
Β· rintro β¨s, hs, a, ha, rflβ©
refine' β¨a, not_mem_erase a s, _β©
@@ -205,7 +205,7 @@ theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (
/-- `s` is in the upper shadow of `π` iff there is an `t β π` from which we can remove one element
to get `s`. -/
-theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _)(_ : a β t), insert a t = s := by
+theorem mem_upShadow_iff : s β (ββΊ ) π β β t β π, β (a : _) (_ : a β t), insert a t = s := by
simp_rw [upShadow, mem_sup, mem_image, exists_prop, mem_compl]
#align finset.mem_up_shadow_iff Finset.mem_upShadow_iff
@@ -188,7 +188,7 @@ def upShadow (π : Finset (Finset Ξ±)) : Finset (Finset Ξ±) :=
#align finset.up_shadow Finset.upShadow
-- mathport name: finset.up_shadow
--- Porting note: added `inheric_doc` to calm linter
+-- Porting note: added `inherit_doc` to calm linter
@[inherit_doc] scoped[FinsetFamily] notation:90 "ββΊ " => Finset.upShadow
/-- The upper shadow of the empty set is empty. -/
fix-comments.py
on all files.@@ -15,7 +15,7 @@ import Mathlib.Logic.Function.Iterate
# Shadows
This file defines shadows of a set family. The shadow of a set family is the set family of sets we
-get by removing any element from any set of the original family. If one pictures `finset Ξ±` as a big
+get by removing any element from any set of the original family. If one pictures `Finset Ξ±` as a big
hypercube (each dimension being membership of a given element), then taking the shadow corresponds
to projecting each finset down once in all available directions.
@@ -32,8 +32,8 @@ We define notation in locale `FinsetFamily`:
* `β π`: Shadow of `π`.
* `ββΊ π`: Upper shadow of `π`.
-We also maintain the convention that `a, b : Ξ±` are elements of the ground type, `s, t : finset Ξ±`
-are finsets, and `π, β¬ : finset (finset Ξ±)` are finset families.
+We also maintain the convention that `a, b : Ξ±` are elements of the ground type, `s, t : Finset Ξ±`
+are finsets, and `π, β¬ : Finset (Finset Ξ±)` are finset families.
## References
@@ -80,7 +80,7 @@ theorem shadow_singleton_empty : (β ) ({β
} : Finset (Finset Ξ±)) = β
:=
rfl
#align finset.shadow_singleton_empty Finset.shadow_singleton_empty
---TODO: Prove `β {{a}} = {β
}` quickly using `covers` and `grade_order`
+--TODO: Prove `β {{a}} = {β
}` quickly using `covers` and `GradeOrder`
/-- The shadow is monotone. -/
@[mono]
theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Finset Ξ±)) := fun _ _ =>
@@ -82,8 +82,7 @@ theorem shadow_singleton_empty : (β ) ({β
} : Finset (Finset Ξ±)) = β
:=
--TODO: Prove `β {{a}} = {β
}` quickly using `covers` and `grade_order`
/-- The shadow is monotone. -/
--- Porting note: unknown attribute `[mono]`
--- @[mono]
+@[mono]
theorem shadow_monotone : Monotone (shadow : Finset (Finset Ξ±) β Finset (Finset Ξ±)) := fun _ _ =>
sup_mono
#align finset.shadow_monotone Finset.shadow_monotone
@@ -199,8 +198,7 @@ theorem upShadow_empty : (ββΊ ) (β
: Finset (Finset Ξ±)) = β
:=
#align finset.up_shadow_empty Finset.upShadow_empty
/-- The upper shadow is monotone. -/
--- Porting note: unknown attribute `[mono]`
--- @[mono]
+@[mono]
theorem upShadow_monotone : Monotone (upShadow : Finset (Finset Ξ±) β Finset (Finset Ξ±)) :=
fun _ _ => sup_mono
#align finset.up_shadow_monotone Finset.upShadow_monotone
The unported dependencies are