combinatorics.set_family.harris_kleitman
⟷
Mathlib.Combinatorics.SetFamily.HarrisKleitman
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)
(last sync)
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -85,7 +85,7 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
card_le_of_subset hℬ.member_subfamily_subset_non_member_subfamily)
_).trans
_
- rw [← two_mul, pow_succ, mul_assoc]
+ rw [← two_mul, pow_succ', mul_assoc]
have h₀ :
∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.nonMemberSubfamily a, t ⊆ s :=
by
mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83
@@ -69,7 +69,7 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
𝒜.card * ℬ.card ≤ 2 ^ s.card * (𝒜 ∩ ℬ).card :=
by
induction' s using Finset.induction with a s hs ih generalizing 𝒜 ℬ
- · simp_rw [subset_empty, ← subset_singleton_iff', subset_singleton_iff] at h𝒜s hℬs
+ · simp_rw [subset_empty, ← subset_singleton_iff', subset_singleton_iff] at h𝒜s hℬs
obtain rfl | rfl := h𝒜s
· simp only [card_empty, empty_inter, MulZeroClass.mul_zero, MulZeroClass.zero_mul]
obtain rfl | rfl := hℬs
@@ -90,12 +90,12 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.nonMemberSubfamily a, t ⊆ s :=
by
rintro 𝒞 h𝒞 t ht
- rw [mem_non_member_subfamily] at ht
+ rw [mem_non_member_subfamily] at ht
exact (subset_insert_iff_of_not_mem ht.2).1 (h𝒞 _ ht.1)
have h₁ : ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.memberSubfamily a, t ⊆ s :=
by
rintro 𝒞 h𝒞 t ht
- rw [mem_member_subfamily] at ht
+ rw [mem_member_subfamily] at ht
exact (subset_insert_iff_of_not_mem ht.2).1 ((subset_insert _ _).trans <| h𝒞 _ ht.1)
refine' mul_le_mul_left' _ _
refine'
@@ -122,11 +122,11 @@ theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset
theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
by
- rw [← isLowerSet_compl, ← coe_compl] at h𝒜
+ rw [← isLowerSet_compl, ← coe_compl] at h𝒜
have := h𝒜.le_card_inter_finset hℬ
rwa [card_compl, Fintype.card_finset, tsub_mul, tsub_le_iff_tsub_le, ← mul_tsub, ←
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl, _root_.inf_comm] at
- this
+ this
#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finset
-/
@@ -143,11 +143,11 @@ theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset
theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
by
- rw [← isLowerSet_compl, ← coe_compl] at h𝒜
+ rw [← isLowerSet_compl, ← coe_compl] at h𝒜
have := h𝒜.card_inter_le_finset hℬ
rwa [card_compl, Fintype.card_finset, tsub_mul, le_tsub_iff_le_tsub, ← mul_tsub, ←
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl, _root_.inf_comm] at
- this
+ this
· exact mul_le_mul_left' (card_le_of_subset <| inter_subset_right _ _) _
· rw [← Fintype.card_finset]
exact mul_le_mul_right' (card_le_univ _) _
mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451
@@ -3,9 +3,9 @@ Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-/
-import Mathbin.Combinatorics.SetFamily.Compression.Down
-import Mathbin.Order.UpperLower.Basic
-import Mathbin.Data.Fintype.BigOperators
+import Combinatorics.SetFamily.Compression.Down
+import Order.UpperLower.Basic
+import Data.Fintype.BigOperators
#align_import combinatorics.set_family.harris_kleitman from "leanprover-community/mathlib"@"0a0ec35061ed9960bf0e7ffb0335f44447b58977"
mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345
@@ -2,16 +2,13 @@
Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module combinatorics.set_family.harris_kleitman
-! leanprover-community/mathlib commit 0a0ec35061ed9960bf0e7ffb0335f44447b58977
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathbin.Combinatorics.SetFamily.Compression.Down
import Mathbin.Order.UpperLower.Basic
import Mathbin.Data.Fintype.BigOperators
+#align_import combinatorics.set_family.harris_kleitman from "leanprover-community/mathlib"@"0a0ec35061ed9960bf0e7ffb0335f44447b58977"
+
/-!
# Harris-Kleitman inequality
mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb
@@ -72,7 +72,7 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
𝒜.card * ℬ.card ≤ 2 ^ s.card * (𝒜 ∩ ℬ).card :=
by
induction' s using Finset.induction with a s hs ih generalizing 𝒜 ℬ
- · simp_rw [subset_empty, ← subset_singleton_iff', subset_singleton_iff] at h𝒜s hℬs
+ · simp_rw [subset_empty, ← subset_singleton_iff', subset_singleton_iff] at h𝒜s hℬs
obtain rfl | rfl := h𝒜s
· simp only [card_empty, empty_inter, MulZeroClass.mul_zero, MulZeroClass.zero_mul]
obtain rfl | rfl := hℬs
@@ -93,12 +93,12 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.nonMemberSubfamily a, t ⊆ s :=
by
rintro 𝒞 h𝒞 t ht
- rw [mem_non_member_subfamily] at ht
+ rw [mem_non_member_subfamily] at ht
exact (subset_insert_iff_of_not_mem ht.2).1 (h𝒞 _ ht.1)
have h₁ : ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.memberSubfamily a, t ⊆ s :=
by
rintro 𝒞 h𝒞 t ht
- rw [mem_member_subfamily] at ht
+ rw [mem_member_subfamily] at ht
exact (subset_insert_iff_of_not_mem ht.2).1 ((subset_insert _ _).trans <| h𝒞 _ ht.1)
refine' mul_le_mul_left' _ _
refine'
@@ -125,11 +125,11 @@ theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset
theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
by
- rw [← isLowerSet_compl, ← coe_compl] at h𝒜
+ rw [← isLowerSet_compl, ← coe_compl] at h𝒜
have := h𝒜.le_card_inter_finset hℬ
rwa [card_compl, Fintype.card_finset, tsub_mul, tsub_le_iff_tsub_le, ← mul_tsub, ←
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl, _root_.inf_comm] at
- this
+ this
#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finset
-/
@@ -146,11 +146,11 @@ theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset
theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
by
- rw [← isLowerSet_compl, ← coe_compl] at h𝒜
+ rw [← isLowerSet_compl, ← coe_compl] at h𝒜
have := h𝒜.card_inter_le_finset hℬ
rwa [card_compl, Fintype.card_finset, tsub_mul, le_tsub_iff_le_tsub, ← mul_tsub, ←
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl, _root_.inf_comm] at
- this
+ this
· exact mul_le_mul_left' (card_le_of_subset <| inter_subset_right _ _) _
· rw [← Fintype.card_finset]
exact mul_le_mul_right' (card_le_univ _) _
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -35,15 +35,18 @@ correlate in the uniform measure.
open Finset
-open BigOperators
+open scoped BigOperators
variable {α : Type _} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
+#print IsLowerSet.nonMemberSubfamily /-
theorem IsLowerSet.nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.nonMemberSubfamily a : Set (Finset α)) := fun s t hts => by
simp_rw [mem_coe, mem_non_member_subfamily]; exact And.imp (h hts) (mt <| @hts _)
#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamily
+-/
+#print IsLowerSet.memberSubfamily /-
theorem IsLowerSet.memberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.memberSubfamily a : Set (Finset α)) :=
by
@@ -51,14 +54,18 @@ theorem IsLowerSet.memberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
simp_rw [mem_coe, mem_member_subfamily]
exact And.imp (h <| insert_subset_insert _ hts) (mt <| @hts _)
#align is_lower_set.member_subfamily IsLowerSet.memberSubfamily
+-/
+#print IsLowerSet.memberSubfamily_subset_nonMemberSubfamily /-
theorem IsLowerSet.memberSubfamily_subset_nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
𝒜.memberSubfamily a ⊆ 𝒜.nonMemberSubfamily a := fun s =>
by
rw [mem_member_subfamily, mem_non_member_subfamily]
exact And.imp_left (h <| subset_insert _ _)
#align is_lower_set.member_subfamily_subset_non_member_subfamily IsLowerSet.memberSubfamily_subset_nonMemberSubfamily
+-/
+#print IsLowerSet.le_card_inter_finset' /-
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) (h𝒜s : ∀ t ∈ 𝒜, t ⊆ s) (hℬs : ∀ t ∈ ℬ, t ⊆ s) :
@@ -101,15 +108,19 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
rw [← mul_add, ← member_subfamily_inter, ← non_member_subfamily_inter,
card_member_subfamily_add_card_non_member_subfamily]
#align is_lower_set.le_card_inter_finset' IsLowerSet.le_card_inter_finset'
+-/
variable [Fintype α]
+#print IsLowerSet.le_card_inter_finset /-
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
h𝒜.le_card_inter_finset' hℬ (fun _ _ => subset_univ _) fun _ _ => subset_univ _
#align is_lower_set.le_card_inter_finset IsLowerSet.le_card_inter_finset
+-/
+#print IsUpperSet.card_inter_le_finset /-
/-- **Harris-Kleitman inequality**: Upper sets and lower sets of finsets anticorrelate. -/
theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
@@ -120,13 +131,17 @@ theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl, _root_.inf_comm] at
this
#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finset
+-/
+#print IsLowerSet.card_inter_le_finset /-
/-- **Harris-Kleitman inequality**: Lower sets and upper sets of finsets anticorrelate. -/
theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
by rw [inter_comm, mul_comm 𝒜.card]; exact hℬ.card_inter_le_finset h𝒜
#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finset
+-/
+#print IsUpperSet.le_card_inter_finset /-
/-- **Harris-Kleitman inequality**: Any two upper sets of finsets correlate. -/
theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
@@ -140,4 +155,5 @@ theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
· rw [← Fintype.card_finset]
exact mul_le_mul_right' (card_le_univ _) _
#align is_upper_set.le_card_inter_finset IsUpperSet.le_card_inter_finset
+-/
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -39,23 +39,11 @@ open BigOperators
variable {α : Type _} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
-/- warning: is_lower_set.non_member_subfamily -> IsLowerSet.nonMemberSubfamily is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
-Case conversion may be inaccurate. Consider using '#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamilyₓ'. -/
theorem IsLowerSet.nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.nonMemberSubfamily a : Set (Finset α)) := fun s t hts => by
simp_rw [mem_coe, mem_non_member_subfamily]; exact And.imp (h hts) (mt <| @hts _)
#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamily
-/- warning: is_lower_set.member_subfamily -> IsLowerSet.memberSubfamily is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
-Case conversion may be inaccurate. Consider using '#align is_lower_set.member_subfamily IsLowerSet.memberSubfamilyₓ'. -/
theorem IsLowerSet.memberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.memberSubfamily a : Set (Finset α)) :=
by
@@ -64,12 +52,6 @@ theorem IsLowerSet.memberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
exact And.imp (h <| insert_subset_insert _ hts) (mt <| @hts _)
#align is_lower_set.member_subfamily IsLowerSet.memberSubfamily
-/- warning: is_lower_set.member_subfamily_subset_non_member_subfamily -> IsLowerSet.memberSubfamily_subset_nonMemberSubfamily is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (HasSubset.Subset.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasSubset.{u1} (Finset.{u1} α)) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (HasSubset.Subset.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instHasSubsetFinset.{u1} (Finset.{u1} α)) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜))
-Case conversion may be inaccurate. Consider using '#align is_lower_set.member_subfamily_subset_non_member_subfamily IsLowerSet.memberSubfamily_subset_nonMemberSubfamilyₓ'. -/
theorem IsLowerSet.memberSubfamily_subset_nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
𝒜.memberSubfamily a ⊆ 𝒜.nonMemberSubfamily a := fun s =>
by
@@ -77,12 +59,6 @@ theorem IsLowerSet.memberSubfamily_subset_nonMemberSubfamily (h : IsLowerSet (
exact And.imp_left (h <| subset_insert _ _)
#align is_lower_set.member_subfamily_subset_non_member_subfamily IsLowerSet.memberSubfamily_subset_nonMemberSubfamily
-/- warning: is_lower_set.le_card_inter_finset' -> IsLowerSet.le_card_inter_finset' is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} {s : Finset.{u1} α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (forall (t : Finset.{u1} α), (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)) -> (forall (t : Finset.{u1} α), (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)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Finset.card.{u1} α s)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} {s : Finset.{u1} α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (forall (t : Finset.{u1} α), (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)) -> (forall (t : Finset.{u1} α), (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)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Finset.card.{u1} α s)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
-Case conversion may be inaccurate. Consider using '#align is_lower_set.le_card_inter_finset' IsLowerSet.le_card_inter_finset'ₓ'. -/
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) (h𝒜s : ∀ t ∈ 𝒜, t ⊆ s) (hℬs : ∀ t ∈ ℬ, t ⊆ s) :
@@ -128,24 +104,12 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
variable [Fintype α]
-/- warning: is_lower_set.le_card_inter_finset -> IsLowerSet.le_card_inter_finset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
-Case conversion may be inaccurate. Consider using '#align is_lower_set.le_card_inter_finset IsLowerSet.le_card_inter_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
h𝒜.le_card_inter_finset' hℬ (fun _ _ => subset_univ _) fun _ _ => subset_univ _
#align is_lower_set.le_card_inter_finset IsLowerSet.le_card_inter_finset
-/- warning: is_upper_set.card_inter_le_finset -> IsUpperSet.card_inter_le_finset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
-Case conversion may be inaccurate. Consider using '#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Upper sets and lower sets of finsets anticorrelate. -/
theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
@@ -157,24 +121,12 @@ theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
this
#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finset
-/- warning: is_lower_set.card_inter_le_finset -> IsLowerSet.card_inter_le_finset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
-Case conversion may be inaccurate. Consider using '#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Lower sets and upper sets of finsets anticorrelate. -/
theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
by rw [inter_comm, mul_comm 𝒜.card]; exact hℬ.card_inter_le_finset h𝒜
#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finset
-/- warning: is_upper_set.le_card_inter_finset -> IsUpperSet.le_card_inter_finset is a dubious translation:
-lean 3 declaration is
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
-but is expected to have type
- forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
-Case conversion may be inaccurate. Consider using '#align is_upper_set.le_card_inter_finset IsUpperSet.le_card_inter_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Any two upper sets of finsets correlate. -/
theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb
@@ -46,10 +46,8 @@ but is expected to have type
forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
Case conversion may be inaccurate. Consider using '#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamilyₓ'. -/
theorem IsLowerSet.nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
- IsLowerSet (𝒜.nonMemberSubfamily a : Set (Finset α)) := fun s t hts =>
- by
- simp_rw [mem_coe, mem_non_member_subfamily]
- exact And.imp (h hts) (mt <| @hts _)
+ IsLowerSet (𝒜.nonMemberSubfamily a : Set (Finset α)) := fun s t hts => by
+ simp_rw [mem_coe, mem_non_member_subfamily]; exact And.imp (h hts) (mt <| @hts _)
#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamily
/- warning: is_lower_set.member_subfamily -> IsLowerSet.memberSubfamily is a dubious translation:
@@ -168,9 +166,7 @@ Case conversion may be inaccurate. Consider using '#align is_lower_set.card_inte
/-- **Harris-Kleitman inequality**: Lower sets and upper sets of finsets anticorrelate. -/
theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
- by
- rw [inter_comm, mul_comm 𝒜.card]
- exact hℬ.card_inter_le_finset h𝒜
+ by rw [inter_comm, mul_comm 𝒜.card]; exact hℬ.card_inter_le_finset h𝒜
#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finset
/- warning: is_upper_set.le_card_inter_finset -> IsUpperSet.le_card_inter_finset is a dubious translation:
mathlib commit https://github.com/leanprover-community/mathlib/commit/0b9eaaa7686280fad8cce467f5c3c57ee6ce77f8
@@ -39,16 +39,25 @@ open BigOperators
variable {α : Type _} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
-#print IsLowerSet.nonMemberSubfamily /-
+/- warning: is_lower_set.non_member_subfamily -> IsLowerSet.nonMemberSubfamily is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
+Case conversion may be inaccurate. Consider using '#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamilyₓ'. -/
theorem IsLowerSet.nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.nonMemberSubfamily a : Set (Finset α)) := fun s t hts =>
by
simp_rw [mem_coe, mem_non_member_subfamily]
exact And.imp (h hts) (mt <| @hts _)
#align is_lower_set.non_member_subfamily IsLowerSet.nonMemberSubfamily
--/
-#print IsLowerSet.memberSubfamily /-
+/- warning: is_lower_set.member_subfamily -> IsLowerSet.memberSubfamily is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜)))
+Case conversion may be inaccurate. Consider using '#align is_lower_set.member_subfamily IsLowerSet.memberSubfamilyₓ'. -/
theorem IsLowerSet.memberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.memberSubfamily a : Set (Finset α)) :=
by
@@ -56,18 +65,26 @@ theorem IsLowerSet.memberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
simp_rw [mem_coe, mem_member_subfamily]
exact And.imp (h <| insert_subset_insert _ hts) (mt <| @hts _)
#align is_lower_set.member_subfamily IsLowerSet.memberSubfamily
--/
-#print IsLowerSet.memberSubfamily_subset_nonMemberSubfamily /-
+/- warning: is_lower_set.member_subfamily_subset_non_member_subfamily -> IsLowerSet.memberSubfamily_subset_nonMemberSubfamily is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (HasSubset.Subset.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasSubset.{u1} (Finset.{u1} α)) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {a : α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (HasSubset.Subset.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instHasSubsetFinset.{u1} (Finset.{u1} α)) (Finset.memberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜) (Finset.nonMemberSubfamily.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a 𝒜))
+Case conversion may be inaccurate. Consider using '#align is_lower_set.member_subfamily_subset_non_member_subfamily IsLowerSet.memberSubfamily_subset_nonMemberSubfamilyₓ'. -/
theorem IsLowerSet.memberSubfamily_subset_nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
𝒜.memberSubfamily a ⊆ 𝒜.nonMemberSubfamily a := fun s =>
by
rw [mem_member_subfamily, mem_non_member_subfamily]
exact And.imp_left (h <| subset_insert _ _)
#align is_lower_set.member_subfamily_subset_non_member_subfamily IsLowerSet.memberSubfamily_subset_nonMemberSubfamily
--/
-#print IsLowerSet.le_card_inter_finset' /-
+/- warning: is_lower_set.le_card_inter_finset' -> IsLowerSet.le_card_inter_finset' is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} {s : Finset.{u1} α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (forall (t : Finset.{u1} α), (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)) -> (forall (t : Finset.{u1} α), (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)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Finset.card.{u1} α s)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} {s : Finset.{u1} α}, (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (forall (t : Finset.{u1} α), (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)) -> (forall (t : Finset.{u1} α), (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)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Finset.card.{u1} α s)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
+Case conversion may be inaccurate. Consider using '#align is_lower_set.le_card_inter_finset' IsLowerSet.le_card_inter_finset'ₓ'. -/
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) (h𝒜s : ∀ t ∈ 𝒜, t ⊆ s) (hℬs : ∀ t ∈ ℬ, t ⊆ s) :
@@ -110,19 +127,27 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
rw [← mul_add, ← member_subfamily_inter, ← non_member_subfamily_inter,
card_member_subfamily_add_card_non_member_subfamily]
#align is_lower_set.le_card_inter_finset' IsLowerSet.le_card_inter_finset'
--/
variable [Fintype α]
-#print IsLowerSet.le_card_inter_finset /-
+/- warning: is_lower_set.le_card_inter_finset -> IsLowerSet.le_card_inter_finset is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
+Case conversion may be inaccurate. Consider using '#align is_lower_set.le_card_inter_finset IsLowerSet.le_card_inter_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
h𝒜.le_card_inter_finset' hℬ (fun _ _ => subset_univ _) fun _ _ => subset_univ _
#align is_lower_set.le_card_inter_finset IsLowerSet.le_card_inter_finset
--/
-#print IsUpperSet.card_inter_le_finset /-
+/- warning: is_upper_set.card_inter_le_finset -> IsUpperSet.card_inter_le_finset is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
+Case conversion may be inaccurate. Consider using '#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Upper sets and lower sets of finsets anticorrelate. -/
theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsLowerSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
@@ -133,9 +158,13 @@ theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl, _root_.inf_comm] at
this
#align is_upper_set.card_inter_le_finset IsUpperSet.card_inter_le_finset
--/
-#print IsLowerSet.card_inter_le_finset /-
+/- warning: is_lower_set.card_inter_le_finset -> IsLowerSet.card_inter_le_finset is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsLowerSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)))
+Case conversion may be inaccurate. Consider using '#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Lower sets and upper sets of finsets anticorrelate. -/
theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card :=
@@ -143,9 +172,13 @@ theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset
rw [inter_comm, mul_comm 𝒜.card]
exact hℬ.card_inter_le_finset h𝒜
#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finset
--/
-#print IsUpperSet.le_card_inter_finset /-
+/- warning: is_upper_set.le_card_inter_finset -> IsUpperSet.le_card_inter_finset is a dubious translation:
+lean 3 declaration is
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toHasLe.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) ((fun (a : Type.{u1}) (b : Type.{u1}) [self : HasLiftT.{succ u1, succ u1} a b] => self.0) (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (HasLiftT.mk.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (CoeTCₓ.coe.{succ u1, succ u1} (Finset.{u1} (Finset.{u1} α)) (Set.{u1} (Finset.{u1} α)) (Finset.Set.hasCoeT.{u1} (Finset.{u1} α)))) ℬ)) -> (LE.le.{0} Nat Nat.hasLe (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat Nat.hasMul) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat (Monoid.Pow.{0} Nat Nat.monoid)) (OfNat.ofNat.{0} Nat 2 (OfNat.mk.{0} Nat 2 (bit0.{0} Nat Nat.hasAdd (One.one.{0} Nat Nat.hasOne)))) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.hasInter.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
+but is expected to have type
+ forall {α : Type.{u1}} [_inst_1 : DecidableEq.{succ u1} α] {𝒜 : Finset.{u1} (Finset.{u1} α)} {ℬ : Finset.{u1} (Finset.{u1} α)} [_inst_2 : Fintype.{u1} α], (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) 𝒜)) -> (IsUpperSet.{u1} (Finset.{u1} α) (Preorder.toLE.{u1} (Finset.{u1} α) (PartialOrder.toPreorder.{u1} (Finset.{u1} α) (Finset.partialOrder.{u1} α))) (Finset.toSet.{u1} (Finset.{u1} α) ℬ)) -> (LE.le.{0} Nat instLENat (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (Finset.card.{u1} (Finset.{u1} α) 𝒜) (Finset.card.{u1} (Finset.{u1} α) ℬ)) (HMul.hMul.{0, 0, 0} Nat Nat Nat (instHMul.{0} Nat instMulNat) (HPow.hPow.{0, 0, 0} Nat Nat Nat (instHPow.{0, 0} Nat Nat instPowNat) (OfNat.ofNat.{0} Nat 2 (instOfNatNat 2)) (Fintype.card.{u1} α _inst_2)) (Finset.card.{u1} (Finset.{u1} α) (Inter.inter.{u1} (Finset.{u1} (Finset.{u1} α)) (Finset.instInterFinset.{u1} (Finset.{u1} α) (fun (a : Finset.{u1} α) (b : Finset.{u1} α) => Finset.decidableEq.{u1} α (fun (a : α) (b : α) => _inst_1 a b) a b)) 𝒜 ℬ))))
+Case conversion may be inaccurate. Consider using '#align is_upper_set.le_card_inter_finset IsUpperSet.le_card_inter_finsetₓ'. -/
/-- **Harris-Kleitman inequality**: Any two upper sets of finsets correlate. -/
theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
(hℬ : IsUpperSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
@@ -159,5 +192,4 @@ theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
· rw [← Fintype.card_finset]
exact mul_le_mul_right' (card_le_univ _) _
#align is_upper_set.le_card_inter_finset IsUpperSet.le_card_inter_finset
--/
mathlib commit https://github.com/leanprover-community/mathlib/commit/3180fab693e2cee3bff62675571264cb8778b212
@@ -76,9 +76,9 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
induction' s using Finset.induction with a s hs ih generalizing 𝒜 ℬ
· simp_rw [subset_empty, ← subset_singleton_iff', subset_singleton_iff] at h𝒜s hℬs
obtain rfl | rfl := h𝒜s
- · simp only [card_empty, empty_inter, mul_zero, zero_mul]
+ · simp only [card_empty, empty_inter, MulZeroClass.mul_zero, MulZeroClass.zero_mul]
obtain rfl | rfl := hℬs
- · simp only [card_empty, inter_empty, mul_zero, zero_mul]
+ · simp only [card_empty, inter_empty, MulZeroClass.mul_zero, MulZeroClass.zero_mul]
· simp only [card_empty, pow_zero, inter_singleton_of_mem, mem_singleton, card_singleton]
rw [card_insert_of_not_mem hs, ← card_member_subfamily_add_card_non_member_subfamily a 𝒜, ←
card_member_subfamily_add_card_non_member_subfamily a ℬ, add_mul, mul_add, mul_add,
mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc
We change the following field in the definition of an additive commutative monoid:
nsmul_succ : ∀ (n : ℕ) (x : G),
- AddMonoid.nsmul (n + 1) x = x + AddMonoid.nsmul n x
+ AddMonoid.nsmul (n + 1) x = AddMonoid.nsmul n x + x
where the latter is more natural
We adjust the definitions of ^
in monoids, groups, etc.
Originally there was a warning comment about why this natural order was preferred
use
x * npowRec n x
and notnpowRec n x * x
in the definition to make sure that definitional unfolding ofnpowRec
is blocked, to avoid deep recursion issues.
but it seems to no longer apply.
Remarks on the PR :
pow_succ
and pow_succ'
have switched their meanings.Ideal.IsPrime.mul_mem_pow
which is defined in [Mathlib/RingTheory/DedekindDomain/Ideal.lean]. Changing the order of operation forced me to add the symmetric lemma Ideal.IsPrime.mem_pow_mul
.@@ -72,7 +72,7 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
card_le_card hℬ.memberSubfamily_subset_nonMemberSubfamily)
_).trans
_
- rw [← two_mul, pow_succ, mul_assoc]
+ rw [← two_mul, pow_succ', mul_assoc]
have h₀ : ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) →
∀ t ∈ 𝒞.nonMemberSubfamily a, t ⊆ s := by
rintro 𝒞 h𝒞 t ht
@@ -5,7 +5,7 @@ Authors: Yaël Dillies
-/
import Mathlib.Combinatorics.SetFamily.Compression.Down
import Mathlib.Order.UpperLower.Basic
-import Mathlib.Data.Fintype.BigOperators
+import Mathlib.Data.Fintype.Powerset
#align_import combinatorics.set_family.harris_kleitman from "leanprover-community/mathlib"@"b363547b3113d350d053abdf2884e9850a56b205"
@@ -29,8 +29,6 @@ correlate in the uniform measure.
open Finset
-open BigOperators
-
variable {α : Type*} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
theorem IsLowerSet.nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
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
@@ -70,8 +70,8 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
refine'
(add_le_add_right
(mul_add_mul_le_mul_add_mul
- (card_le_of_subset h𝒜.memberSubfamily_subset_nonMemberSubfamily) <|
- card_le_of_subset hℬ.memberSubfamily_subset_nonMemberSubfamily)
+ (card_le_card h𝒜.memberSubfamily_subset_nonMemberSubfamily) <|
+ card_le_card hℬ.memberSubfamily_subset_nonMemberSubfamily)
_).trans
_
rw [← two_mul, pow_succ, mul_assoc]
@@ -128,7 +128,7 @@ theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
rwa [card_compl, Fintype.card_finset, tsub_mul, le_tsub_iff_le_tsub, ← mul_tsub, ←
card_sdiff (inter_subset_right _ _), sdiff_inter_self_right, sdiff_compl,
_root_.inf_comm] at this
- · exact mul_le_mul_left' (card_le_of_subset <| inter_subset_right _ _) _
+ · exact mul_le_mul_left' (card_le_card <| inter_subset_right _ _) _
· rw [← Fintype.card_finset]
exact mul_le_mul_right' (card_le_univ _) _
#align is_upper_set.le_card_inter_finset IsUpperSet.le_card_inter_finset
This is the supremum of
along with some minor fixes from failures on nightly-testing as Mathlib master
is merged into it.
Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.
I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0
branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.
In particular this includes adjustments for the Lean PRs
We can get rid of all the
local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)
macros across Mathlib (and in any projects that want to write natural number powers of reals).
Changes the default behaviour of simp
to (config := {decide := false})
. This makes simp
(and consequentially norm_num
) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp
or norm_num
to decide
or rfl
, or adding (config := {decide := true})
.
This changed the behaviour of simp
so that simp [f]
will only unfold "fully applied" occurrences of f
. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true })
. We may in future add a syntax for this, e.g. simp [!f]
; please provide feedback! In the meantime, we have made the following changes:
(config := { unfoldPartialApp := true })
in some places, to recover the old behaviour@[eqns]
to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp
and Function.flip
.This change in Lean may require further changes down the line (e.g. adding the !f
syntax, and/or upstreaming the special treatment for Function.comp
and Function.flip
, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!
Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>
@@ -59,10 +59,11 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
induction' s using Finset.induction with a s hs ih generalizing 𝒜 ℬ
· simp_rw [subset_empty, ← subset_singleton_iff', subset_singleton_iff] at h𝒜s hℬs
obtain rfl | rfl := h𝒜s
- · simp only [card_empty, empty_inter, mul_zero, zero_mul]
+ · simp only [card_empty, zero_mul, empty_inter, mul_zero, le_refl]
obtain rfl | rfl := hℬs
- · simp only [card_empty, inter_empty, mul_zero, zero_mul]
- · simp only [card_empty, pow_zero, inter_singleton_of_mem, mem_singleton, card_singleton]
+ · simp only [card_empty, inter_empty, mul_zero, zero_mul, le_refl]
+ · simp only [card_empty, pow_zero, inter_singleton_of_mem, mem_singleton, card_singleton,
+ le_refl]
rw [card_insert_of_not_mem hs, ← card_memberSubfamily_add_card_nonMemberSubfamily a 𝒜, ←
card_memberSubfamily_add_card_nonMemberSubfamily a ℬ, add_mul, mul_add, mul_add,
add_comm (_ * _), add_add_add_comm]
A linter that throws on seeing a colon at the start of a line, according to the style guideline that says these operators should go before linebreaks.
@@ -95,8 +95,8 @@ variable [Fintype α]
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
- (hℬ : IsLowerSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card
- := h𝒜.le_card_inter_finset' hℬ (fun _ _ => subset_univ _) fun _ _ => subset_univ _
+ (hℬ : IsLowerSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card :=
+h𝒜.le_card_inter_finset' hℬ (fun _ _ => subset_univ _) fun _ _ => subset_univ _
#align is_lower_set.le_card_inter_finset IsLowerSet.le_card_inter_finset
/-- **Harris-Kleitman inequality**: Upper sets and lower sets of finsets anticorrelate. -/
Type _
and Sort _
(#6499)
We remove all possible occurences of Type _
and Sort _
in favor of Type*
and Sort*
.
This has nice performance benefits.
@@ -31,7 +31,7 @@ open Finset
open BigOperators
-variable {α : Type _} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
+variable {α : Type*} [DecidableEq α] {𝒜 ℬ : Finset (Finset α)} {s : Finset α} {a : α}
theorem IsLowerSet.nonMemberSubfamily (h : IsLowerSet (𝒜 : Set (Finset α))) :
IsLowerSet (𝒜.nonMemberSubfamily a : Set (Finset α)) := fun s t hts => by
@@ -2,16 +2,13 @@
Copyright (c) 2022 Yaël Dillies. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Yaël Dillies
-
-! This file was ported from Lean 3 source module combinatorics.set_family.harris_kleitman
-! leanprover-community/mathlib commit b363547b3113d350d053abdf2884e9850a56b205
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-/
import Mathlib.Combinatorics.SetFamily.Compression.Down
import Mathlib.Order.UpperLower.Basic
import Mathlib.Data.Fintype.BigOperators
+#align_import combinatorics.set_family.harris_kleitman from "leanprover-community/mathlib"@"b363547b3113d350d053abdf2884e9850a56b205"
+
/-!
# Harris-Kleitman inequality
by
s! (#3825)
This PR puts, with one exception, every single remaining by
that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh
. The exception is when the by
begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.
Essentially this is s/\n *by$/ by/g
, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated by
s".
@@ -77,23 +77,19 @@ theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset
_).trans
_
rw [← two_mul, pow_succ, mul_assoc]
- have h₀ :
- ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.nonMemberSubfamily a, t ⊆ s :=
- by
+ have h₀ : ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) →
+ ∀ t ∈ 𝒞.nonMemberSubfamily a, t ⊆ s := by
rintro 𝒞 h𝒞 t ht
rw [mem_nonMemberSubfamily] at ht
exact (subset_insert_iff_of_not_mem ht.2).1 (h𝒞 _ ht.1)
- have h₁ : ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) → ∀ t ∈ 𝒞.memberSubfamily a, t ⊆ s
- :=
- by
+ have h₁ : ∀ 𝒞 : Finset (Finset α), (∀ t ∈ 𝒞, t ⊆ insert a s) →
+ ∀ t ∈ 𝒞.memberSubfamily a, t ⊆ s := by
rintro 𝒞 h𝒞 t ht
rw [mem_memberSubfamily] at ht
exact (subset_insert_iff_of_not_mem ht.2).1 ((subset_insert _ _).trans <| h𝒞 _ ht.1)
refine' mul_le_mul_left' _ _
- refine'
- (add_le_add (ih h𝒜.memberSubfamily hℬ.memberSubfamily (h₁ _ h𝒜s) <| h₁ _ hℬs) <|
- ih h𝒜.nonMemberSubfamily hℬ.nonMemberSubfamily (h₀ _ h𝒜s) <| h₀ _ hℬs).trans_eq
- _
+ refine' (add_le_add (ih h𝒜.memberSubfamily hℬ.memberSubfamily (h₁ _ h𝒜s) <| h₁ _ hℬs) <|
+ ih h𝒜.nonMemberSubfamily hℬ.nonMemberSubfamily (h₀ _ h𝒜s) <| h₀ _ hℬs).trans_eq _
rw [← mul_add, ← memberSubfamily_inter, ← nonMemberSubfamily_inter,
card_memberSubfamily_add_card_nonMemberSubfamily]
#align is_lower_set.le_card_inter_finset' IsLowerSet.le_card_inter_finset'
@@ -108,9 +104,8 @@ theorem IsLowerSet.le_card_inter_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset
/-- **Harris-Kleitman inequality**: Upper sets and lower sets of finsets anticorrelate. -/
theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
- (hℬ : IsLowerSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card
- :=
- by
+ (hℬ : IsLowerSet (ℬ : Set (Finset α))) :
+ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card := by
rw [← isLowerSet_compl, ← coe_compl] at h𝒜
have := h𝒜.le_card_inter_finset hℬ
rwa [card_compl, Fintype.card_finset, tsub_mul, tsub_le_iff_tsub_le, ← mul_tsub, ←
@@ -120,18 +115,16 @@ theorem IsUpperSet.card_inter_le_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset
/-- **Harris-Kleitman inequality**: Lower sets and upper sets of finsets anticorrelate. -/
theorem IsLowerSet.card_inter_le_finset (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
- (hℬ : IsUpperSet (ℬ : Set (Finset α))) : 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card
- :=
- by
+ (hℬ : IsUpperSet (ℬ : Set (Finset α))) :
+ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card ≤ 𝒜.card * ℬ.card := by
rw [inter_comm, mul_comm 𝒜.card]
exact hℬ.card_inter_le_finset h𝒜
#align is_lower_set.card_inter_le_finset IsLowerSet.card_inter_le_finset
/-- **Harris-Kleitman inequality**: Any two upper sets of finsets correlate. -/
theorem IsUpperSet.le_card_inter_finset (h𝒜 : IsUpperSet (𝒜 : Set (Finset α)))
- (hℬ : IsUpperSet (ℬ : Set (Finset α))) : 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card
- :=
- by
+ (hℬ : IsUpperSet (ℬ : Set (Finset α))) :
+ 𝒜.card * ℬ.card ≤ 2 ^ Fintype.card α * (𝒜 ∩ ℬ).card := by
rw [← isLowerSet_compl, ← coe_compl] at h𝒜
have := h𝒜.card_inter_le_finset hℬ
rwa [card_compl, Fintype.card_finset, tsub_mul, le_tsub_iff_le_tsub, ← mul_tsub, ←
This PR fixes two things:
align
statements for definitions and theorems and instances that are separated by two newlines from the relevant declaration (s/\n\n#align/\n#align
). This is often seen in the mathport output after ending calc
blocks.#align
statements. (This was needed for a script I wrote for #3630.)@@ -53,8 +53,7 @@ theorem IsLowerSet.memberSubfamily_subset_nonMemberSubfamily (h : IsLowerSet (
𝒜.memberSubfamily a ⊆ 𝒜.nonMemberSubfamily a := fun s => by
rw [mem_memberSubfamily, mem_nonMemberSubfamily]
exact And.imp_left (h <| subset_insert _ _)
-#align is_lower_set.member_subfamily_subset_non_member_subfamily
- IsLowerSet.memberSubfamily_subset_nonMemberSubfamily
+#align is_lower_set.member_subfamily_subset_non_member_subfamily IsLowerSet.memberSubfamily_subset_nonMemberSubfamily
/-- **Harris-Kleitman inequality**: Any two lower sets of finsets correlate. -/
theorem IsLowerSet.le_card_inter_finset' (h𝒜 : IsLowerSet (𝒜 : Set (Finset α)))
The unported dependencies are