finset_family_card_sq_le_of_inter_symm_diff
A family K of subsets of a finite set U that contains the empty set, is closed under intersection and symmetric difference, and contains no singleton has |K|^2 <= 2^|U|.
Statement
theorem finset_family_card_sq_le_of_inter_symm_diff {ι : Type*} [DecidableEq ι] (U : Finset ι) (K : Finset (Finset ι)) (hsub : ∀ A ∈ K, A ⊆ U) (h0 : ∅ ∈ K) (hinter : ∀ A ∈ K, ∀ B ∈ K, A ∩ B ∈ K) (hsd : ∀ A ∈ K, ∀ B ∈ K, symmDiff A B ∈ K) (hsing : ∀ x, ({x} : Finset ι) ∉ K) : K.card ^ 2 ≤ 2 ^ U.card
- Source
- Step toward zero_sum_w_two_le. arXiv:2610.19965 (Proofs and disproofs of some conjectures on zero-sum problems of new types), Theorem 1.2(i) w_r(2) = 2r + 1; the paper's upper bound classifies the w-bad sequences mod 4 (Theorem 3.1); this route replaces the classification by a counting argument.
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- zero_sum_w_two_leUpper bound w_r(2) <= 2r + 1: every sequence of 2r + 1 vectors of Z^r, each nonzero mod 2, has a nonempty subsequence whose sum is 0 mod 2…
The proof, explained
The theorem is proved by strong induction on the size of the ground set U. If U is empty, K consists only of the empty set and the bound holds. When U is nonempty, we select an element x ∈ U; if no set in K contains x, K is supported on U \ {x} and the claim follows directly from the induction hypothesis. Otherwise, let A ∈ K be a set of minimal cardinality containing x. Using closure under intersection and symmetric difference, every set in K is either disjoint from A or contains A, which induces a bijection M ↦ M Δ A between the subfamily K₁ of sets disjoint from A and its complement. Since K contains no singletons, |A| ≥ 2, so applying the induction hypothesis to K₁ on U \ A gives |K|^2 = 4 |K₁|^2 ≤ 4 · 2^|U \ A| ≤ 2^|U|.
The auxiliary lemma is set up by strong induction on the size n = |U| of the ground set.
We assume the induction hypothesis that the inequality holds for all ground sets of size strictly less than n, and introduce the universe U with |U| = n, the family K of subsets of U, and the hypotheses that ∅ ∈ K, K is closed under intersection and symmetric difference, and K contains no singletons.
uses
Nat.strong_induction_onclassical induction n using Nat.strong_induction_on with | h n ih => intro U K hU hsub h0 hinter hsd hsing
If U = ∅, then |K|^2 ≤ 2^|U|. automation
When U = ∅, every A ∈ K satisfies A ⊆ ∅, forcing A = ∅. Since ∅ ∈ K, we have K = {∅}. Thus |K| = 1 and |U| = 0, so |K|^2 = 1 ≤ 1 = 2^0, which simp verifies.
uses
Finset.eq_empty_or_nonempty,Finset.mem_singleton,Finset.subset_empty.mp,Finset.Subset.antisymm,Finset.singleton_subset_iff.mprrcases Finset.eq_empty_or_nonempty U with hUe | hUne · subst hUe have hKsub : K ⊆ {∅} := by intro A hA rw [Finset.mem_singleton] exact Finset.subset_empty.mp (hsub A hA) have hKeq : K = {∅} := Finset.Subset.antisymm hKsub (Finset.singleton_subset_iff.mpr h0) rw [hKeq] simp
When U is nonempty, we pick an element x ∈ U and consider whether any set in K contains x.
Since U is nonempty, there is an element x ∈ U. We divide into two cases based on whether there exists some M ∈ K such that x ∈ M.
· obtain ⟨x, hxU⟩ := hUne by_cases hex : ∃ M ∈ K, x ∈ M
If some set in K contains x, there is a set A ∈ K containing x of minimal cardinality.
The subfamily of sets in K containing x is nonempty. Choosing a set A of minimal size in this subfamily gives A ∈ K, x ∈ A, and |A| ≤ |B| for every B ∈ K containing x.
uses
Finset.exists_min_image,Finset.mem_filter.mp,Finset.mem_filter.mpr· obtain ⟨M0, hM0K, hxM0⟩ := hex have hSne : (K.filter (fun M => x ∈ M)).Nonempty := ⟨M0, Finset.mem_filter.mpr ⟨hM0K, hxM0⟩⟩ obtain ⟨A, hAS, hAmin⟩ := Finset.exists_min_image (K.filter (fun M => x ∈ M)) Finset.card hSne have hAK : A ∈ K := (Finset.mem_filter.mp hAS).1 have hxA : x ∈ A := (Finset.mem_filter.mp hAS).2 have hAmin' : ∀ B ∈ K, x ∈ B → A.card ≤ B.card := by intro B hBK hxB exact hAmin B (Finset.mem_filter.mpr ⟨hBK, hxB⟩)
For every M ∈ K, either A and M are disjoint or A ⊆ M.
If x ∈ M, then A ∩ M ∈ K contains x, so minimality of |A| implies |A| ≤ |A ∩ M|; since A ∩ M ⊆ A, we have A ∩ M = A, hence A ⊆ M. If x ∉ M, then x ∉ A ∩ M, so the symmetric difference A Δ (A ∩ M) = A \ (A ∩ M) belongs to K and contains x. Minimality of |A| forces |A| ≤ |A \ (A ∩ M)|, so A \ (A ∩ M) = A, which implies A ∩ M = ∅, meaning A and M are disjoint.
uses
Finset.inter_subset_left,Finset.eq_of_subset_of_card_le,Finset.inter_eq_left.mp,symmDiff_of_ge,Finset.sdiff_subset,Finset.disjoint_left,Finset.disjoint_iff_inter_eq_empty.mp,Finset.inter_assoc,Finset.inter_selfhave hkey : ∀ M ∈ K, Disjoint A M ∨ A ⊆ M := by intro M hMK by_cases hxM : x ∈ M · right have hAMK : A ∩ M ∈ K := hinter A hAK M hMK have hxAM : x ∈ A ∩ M := Finset.mem_inter.mpr ⟨hxA, hxM⟩ have h1 : A.card ≤ (A ∩ M).card := hAmin' (A ∩ M) hAMK hxAM have h2 : A ∩ M ⊆ A := Finset.inter_subset_left have heq : A ∩ M = A := Finset.eq_of_subset_of_card_le h2 h1 exact Finset.inter_eq_left.mp heq · left have hAMK : A ∩ M ∈ K := hinter A hAK M hMK have hxAM : x ∉ A ∩ M := by intro h; exact hxM (Finset.mem_inter.mp h).2 have hsd' : symmDiff A (A ∩ M) ∈ K := hsd A hAK (A ∩ M) hAMK have hx' : x ∈ symmDiff A (A ∩ M) := by rw [Finset.mem_symmDiff]; exact Or.inl ⟨hxA, hxAM⟩ have h1 : A.card ≤ (symmDiff A (A ∩ M)).card := hAmin' _ hsd' hx' have h2 : symmDiff A (A ∩ M) ⊆ A := by rw [symmDiff_of_ge (Finset.inter_subset_left : A ∩ M ⊆ A)] exact Finset.sdiff_subset have heq : symmDiff A (A ∩ M) = A := Finset.eq_of_subset_of_card_le h2 h1 have heq' : A \ (A ∩ M) = A := by rw [← symmDiff_of_ge (Finset.inter_subset_left : A ∩ M ⊆ A)] exact heq have hdisj : Disjoint A (A ∩ M) := by rw [Finset.disjoint_left] intro y hyA hyAM have hy : y ∈ A \ (A ∩ M) := by rw [heq']; exact hyA exact (Finset.mem_sdiff.mp hy).2 hyAM have hAM : A ∩ M = ∅ := by have h := Finset.disjoint_iff_inter_eq_empty.mp hdisj rw [← Finset.inter_assoc, Finset.inter_self] at h exact h have hdisjAM : Disjoint A M := by rw [Finset.disjoint_left] intro y hyA hyM have hy : y ∈ A ∩ M := Finset.mem_inter.mpr ⟨hyA, hyM⟩ rw [hAM] at hy simp at hy exact hdisjAM
K partitions into the subfamily K₁ of sets disjoint from A and its complement K₁ᶜ in K.
We define K₁ = {M ∈ K | Disjoint A M} and K₁ᶜ = {M ∈ K | ¬ Disjoint A M}. By partitioning K according to disjointness with A, we have |K| = |K₁| + |K₁ᶜ|.
uses
Finset.mem_filter,Finset.card_filter_add_card_filter_notset K1 : Finset (Finset ι) := K.filter (fun M => Disjoint A M) with hK1def set K1c : Finset (Finset ι) := K.filter (fun M => ¬ Disjoint A M) with hK1cdef have hmem1 : ∀ M, M ∈ K1 ↔ M ∈ K ∧ Disjoint A M := by intro M; rw [hK1def]; exact Finset.mem_filter have hmem1c : ∀ M, M ∈ K1c ↔ M ∈ K ∧ ¬ Disjoint A M := by intro M; rw [hK1cdef]; exact Finset.mem_filter have hcard : K.card = K1.card + K1c.card := by have h := Finset.card_filter_add_card_filter_not (s := K) (p := fun M => Disjoint A M) rw [← hK1def, ← hK1cdef] at h exact h.symm
The map M ↦ M Δ A is a bijection between K₁ and K₁ᶜ, so |K| = 2 |K₁|.
If M ∈ K₁, then x ∉ M because A and M are disjoint and x ∈ A; thus x ∈ M Δ A, so M Δ A is not disjoint from A and belongs to K₁ᶜ. Conversely, if M ∈ K₁ᶜ, the dichotomy gives A ⊆ M, so M Δ A = M \ A is disjoint from A and belongs to K₁. Since symmetric difference with A is an involution, this map is injective and surjects onto K₁ᶜ, showing |K₁ᶜ| = |K₁| and therefore |K| = 2 |K₁|.
uses
symmDiff_of_ge,symmDiff_symmDiff_cancel_right,Finset.Subset.antisymm,Finset.card_image_of_injectivehave hf1 : ∀ M ∈ K1, symmDiff M A ∈ K1c := by intro M hM obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM have hK : symmDiff M A ∈ K := hsd M hMK A hAK have hnd : ¬ Disjoint A (symmDiff M A) := by intro hd have hxM : x ∉ M := (Finset.disjoint_left.mp hDM) hxA have hxmem : x ∈ symmDiff M A := by rw [Finset.mem_symmDiff] exact Or.inr ⟨hxA, hxM⟩ exact ((Finset.disjoint_left.mp hd) hxA) hxmem exact (hmem1c _).mpr ⟨hK, hnd⟩ have hf2 : ∀ M ∈ K1c, symmDiff M A ∈ K1 := by intro M hM obtain ⟨hMK, hndM⟩ := (hmem1c M).mp hM have hAM : A ⊆ M := (hkey M hMK).resolve_left hndM have hK : symmDiff M A ∈ K := hsd M hMK A hAK have hdisj : Disjoint A (symmDiff M A) := by have h1 : symmDiff M A = M \ A := symmDiff_of_ge hAM rw [h1, Finset.disjoint_left] intro y hyA hy exact (Finset.mem_sdiff.mp hy).2 hyA exact (hmem1 _).mpr ⟨hK, hdisj⟩ have hff : ∀ M : Finset ι, symmDiff (symmDiff M A) A = M := fun M => symmDiff_symmDiff_cancel_right A M have hinj : Function.Injective (fun M : Finset ι => symmDiff M A) := by intro M N h have h1 : symmDiff (symmDiff M A) A = symmDiff (symmDiff N A) A := congrArg (fun L => symmDiff L A) h simpa only [hff] using h1 have himage : K1.image (fun M => symmDiff M A) = K1c := by apply Finset.Subset.antisymm · intro M hM obtain ⟨N, hN, rfl⟩ := Finset.mem_image.mp hM exact hf1 N hN · intro M hM exact Finset.mem_image.mpr ⟨symmDiff M A, hf2 M hM, hff M⟩ have hK1c_card : K1c.card = K1.card := by rw [← himage, Finset.card_image_of_injective _ hinj] have hKcard : K.card = 2 * K1.card := by rw [hcard, hK1c_card] ring have hAU : A ⊆ U := hsub A hAK
The minimal set A has cardinality at least 2.
Since x ∈ A, A is nonempty, so |A| ≥ 1. If |A| = 1, then A would be a singleton {x} in K, which contradicts the hypothesis that K contains no singletons. Thus |A| ≥ 2.
uses
Finset.card_pos.mpr,Finset.card_eq_one.mphave hAcard : 2 ≤ A.card := by by_contra h have hpos : 0 < A.card := Finset.card_pos.mpr ⟨x, hxA⟩ have h1 : A.card = 1 := by omega obtain ⟨y, hy⟩ := Finset.card_eq_one.mp h1 have hxy : x = y := by have hx : x ∈ ({y} : Finset ι) := by rw [← hy]; exact hxA simpa using hx rw [hy, ← hxy] at hAK exact hsing x hAK
The induction hypothesis applies to K₁ on universe U \ A, yielding |K₁|^2 ≤ 2^|U \ A|.
Because |A| ≥ 2, the ground set U \ A has size strictly less than n. Every set in K₁ is disjoint from A and contained in U, hence is a subset of U \ A. Furthermore, ∅ ∈ K₁, K₁ is closed under intersection and symmetric difference, and K₁ contains no singletons. By the strong induction hypothesis on U \ A, |K₁|^2 ≤ 2^|U \ A|.
uses
Finset.card_sdiff_of_subset,Finset.card_le_card,Finset.subset_sdiff,Disjoint.monohave hlt : (U \ A).card < n := by rw [← hU] have h1 : (U \ A).card = U.card - A.card := Finset.card_sdiff_of_subset hAU have h2 : A.card ≤ U.card := Finset.card_le_card hAU omega have hsub1 : ∀ M ∈ K1, M ⊆ U \ A := by intro M hM obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM rw [Finset.subset_sdiff] exact ⟨hsub M hMK, hDM.symm⟩ have h01 : ∅ ∈ K1 := (hmem1 ∅).mpr ⟨h0, by simp⟩ have hinter1 : ∀ M ∈ K1, ∀ N ∈ K1, M ∩ N ∈ K1 := by intro M hM N hN obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM obtain ⟨hNK, hDN⟩ := (hmem1 N).mp hN exact (hmem1 _).mpr ⟨hinter M hMK N hNK, Disjoint.mono le_rfl Finset.inter_subset_left hDM⟩ have hsd1 : ∀ M ∈ K1, ∀ N ∈ K1, symmDiff M N ∈ K1 := by intro M hM N hN obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM obtain ⟨hNK, hDN⟩ := (hmem1 N).mp hN refine (hmem1 _).mpr ⟨hsd M hMK N hNK, ?_⟩ rw [Finset.disjoint_left] intro y hyA hyMN rw [Finset.mem_symmDiff] at hyMN rcases hyMN with ⟨hyM, -⟩ | ⟨hyN, -⟩ · exact ((Finset.disjoint_left.mp hDM) hyA) hyM · exact ((Finset.disjoint_left.mp hDN) hyA) hyN have hsing1 : ∀ y, ({y} : Finset ι) ∉ K1 := by intro y hy exact hsing y ((hmem1 _).mp hy).1 have hIH := ih (U \ A).card hlt (U \ A) K1 rfl hsub1 h01 hinter1 hsd1 hsing1
In Case 1, |K|^2 ≤ 2^|U|.
Since |A| ≥ 2, |U \ A| + 2 ≤ |U|. Then |K|^2 = (2 |K₁|)^2 = 4 |K₁|^2 ≤ 4 · 2^|U \ A| = 2^(|U \ A| + 2) ≤ 2^|U|.
uses
Finset.card_sdiff_of_subset,Finset.card_le_card,pow_add,Nat.add_comm,Nat.mul_le_mul_left,Nat.pow_le_pow_righthave hdlle : (U \ A).card + 2 ≤ U.card := by have h1 : (U \ A).card = U.card - A.card := Finset.card_sdiff_of_subset hAU have h2 : A.card ≤ U.card := Finset.card_le_card hAU omega have hpow : (4:ℕ) * 2 ^ (U \ A).card = 2 ^ ((U \ A).card + 2) := by rw [show (4:ℕ) = 2^2 by norm_num, ← pow_add, Nat.add_comm] calc K.card ^ 2 = (2 * K1.card) ^ 2 := by rw [hKcard] _ = 4 * K1.card ^ 2 := by ring _ ≤ 4 * 2 ^ (U \ A).card := Nat.mul_le_mul_left 4 hIH _ = 2 ^ ((U \ A).card + 2) := hpow _ ≤ 2 ^ U.card := Nat.pow_le_pow_right (by norm_num) hdlle
In Case 2, where no set in K contains x, |K|^2 ≤ 2^|U|.
If no member of K contains x, then every set in K is contained in U \ {x}. Since x ∈ U, |U \ {x}| < |U| = n. Applying the induction hypothesis to K on the ground set U \ {x} yields |K|^2 ≤ 2^|U \ {x}| ≤ 2^|U|.
uses
Finset.subset_erase,Finset.card_erase_lt_of_mem,Finset.card_erase_le,Nat.pow_le_pow_right· push Not at hex have hsub' : ∀ A ∈ K, A ⊆ U.erase x := by intro A hA rw [Finset.subset_erase] exact ⟨hsub A hA, hex A hA⟩ have hlt : (U.erase x).card < n := by rw [← hU] exact Finset.card_erase_lt_of_mem hxU have hIH := ih (U.erase x).card hlt (U.erase x) K rfl hsub' h0 hinter hsd hsing calc K.card ^ 2 ≤ 2 ^ (U.erase x).card := hIH _ ≤ 2 ^ U.card := Nat.pow_le_pow_right (by norm_num) Finset.card_erase_le
The main theorem follows immediately from the auxiliary lemma.
Specializing the auxiliary lemma to n = |U| establishes the theorem for any universe U.
uses
finset_family_card_sq_le_of_inter_symm_diff_auxK.card ^ 2 ≤ 2 ^ U.card := finset_family_card_sq_le_of_inter_symm_diff_aux U.card U K rfl hsub h0 hinter hsd hsing
Nat.strong_induction_on- Well-founded strong induction on natural numbers: if a property holds for n whenever it holds for all m < n, then it holds for all n.
Finset.eq_empty_or_nonempty- Every finite set is either empty or nonempty.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
Finset.subset_empty.mp- If a finite set is a subset of the empty set, it is empty.
Finset.Subset.antisymm- Two finite sets are equal if each is a subset of the other.
Finset.singleton_subset_iff.mpr- The singleton {a} is a subset of s if a ∈ s.
Finset.exists_min_image- Any nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
Finset.mem_filter.mp- If x is in the filtered set {y ∈ s | p y}, then x ∈ s and p x holds.
Finset.mem_filter.mpr- If x ∈ s and p x holds, then x is in the filtered set {y ∈ s | p y}.
Finset.inter_subset_left- The intersection s ∩ t is a subset of s.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s|, then s = t.
Finset.inter_eq_left.mp- If s ∩ t = s, then s ⊆ t.
symmDiff_of_ge- If b ⊆ a, then the symmetric difference a Δ b equals the set difference a \ b.
Finset.sdiff_subset- The set difference s \ t is a subset of s.
Finset.disjoint_left- Two sets s and t are disjoint if and only if no element of s belongs to t.
Finset.disjoint_iff_inter_eq_empty.mp- If two sets are disjoint, their intersection is empty.
Finset.inter_assoc- Set intersection is associative: (s₁ ∩ s₂) ∩ s₃ = s₁ ∩ (s₂ ∩ s₃).
Finset.inter_self- The intersection of any set with itself is itself: s ∩ s = s.
Finset.mem_filter- An element belongs to {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.card_filter_add_card_filter_not- For any predicate p on a finite set s, |{x ∈ s | p x}| + |{x ∈ s | ¬p x}| = |s|.
symmDiff_symmDiff_cancel_right- Symmetric difference with a fixed set is an involution: (b Δ a) Δ a = b.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the set.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if it contains an element.
Finset.card_eq_one.mp- If a finite set has cardinality 1, it is a singleton {y}.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.subset_sdiff- A set s is a subset of t \ u if and only if s ⊆ t and s is disjoint from u.
Disjoint.mono- If b and d are disjoint and a ≤ b, c ≤ d, then a and c are disjoint.
pow_add- Powers add under multiplication: a^(m + n) = a^m * a^n.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
Nat.mul_le_mul_left- Multiplication by a non-negative integer preserves inequality: if n ≤ m, then k * n ≤ k * m.
Nat.pow_le_pow_right- If n > 0 and i ≤ j, then n^i ≤ n^j.
Finset.subset_erase- A set s is a subset of t \ {a} if and only if s ⊆ t and a ∉ s.
Finset.card_erase_lt_of_mem- Removing an element a ∈ s from a finite set strictly decreases its cardinality: |s \ {a}| < |s|.
Finset.card_erase_le- Removing an element from a finite set cannot increase its cardinality: |s \ {a}| ≤ |s|.
finset_family_card_sq_le_of_inter_symm_diff_aux- The auxiliary lemma stating the bound |K|^2 ≤ 2^|U| parameterized by n = |U|.
- The base case inequality 1^2 ≤ 2^0 and some intermediate arithmetic steps (such as deducing |A| = 1 from 0 < |A| and ¬(2 ≤ |A|)) are closed by automation (simp, omega, ring, norm_num).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma finset_family_card_sq_le_of_inter_symm_diff_aux {ι : Type*} [DecidableEq ι] (n : ℕ) : ∀ (U : Finset ι) (K : Finset (Finset ι)), U.card = n → (∀ A ∈ K, A ⊆ U) → ∅ ∈ K → (∀ A ∈ K, ∀ B ∈ K, A ∩ B ∈ K) → (∀ A ∈ K, ∀ B ∈ K, symmDiff A B ∈ K) → (∀ x, ({x} : Finset ι) ∉ K) → K.card ^ 2 ≤ 2 ^ U.card := by classical induction n using Nat.strong_induction_on with | h n ih => intro U K hU hsub h0 hinter hsd hsing rcases Finset.eq_empty_or_nonempty U with hUe | hUne · subst hUe have hKsub : K ⊆ {∅} := by intro A hA rw [Finset.mem_singleton] exact Finset.subset_empty.mp (hsub A hA) have hKeq : K = {∅} := Finset.Subset.antisymm hKsub (Finset.singleton_subset_iff.mpr h0) rw [hKeq] simp · obtain ⟨x, hxU⟩ := hUne by_cases hex : ∃ M ∈ K, x ∈ M · obtain ⟨M0, hM0K, hxM0⟩ := hex have hSne : (K.filter (fun M => x ∈ M)).Nonempty := ⟨M0, Finset.mem_filter.mpr ⟨hM0K, hxM0⟩⟩ obtain ⟨A, hAS, hAmin⟩ := Finset.exists_min_image (K.filter (fun M => x ∈ M)) Finset.card hSne have hAK : A ∈ K := (Finset.mem_filter.mp hAS).1 have hxA : x ∈ A := (Finset.mem_filter.mp hAS).2 have hAmin' : ∀ B ∈ K, x ∈ B → A.card ≤ B.card := by intro B hBK hxB exact hAmin B (Finset.mem_filter.mpr ⟨hBK, hxB⟩) have hkey : ∀ M ∈ K, Disjoint A M ∨ A ⊆ M := by intro M hMK by_cases hxM : x ∈ M · right have hAMK : A ∩ M ∈ K := hinter A hAK M hMK have hxAM : x ∈ A ∩ M := Finset.mem_inter.mpr ⟨hxA, hxM⟩ have h1 : A.card ≤ (A ∩ M).card := hAmin' (A ∩ M) hAMK hxAM have h2 : A ∩ M ⊆ A := Finset.inter_subset_left have heq : A ∩ M = A := Finset.eq_of_subset_of_card_le h2 h1 exact Finset.inter_eq_left.mp heq · left have hAMK : A ∩ M ∈ K := hinter A hAK M hMK have hxAM : x ∉ A ∩ M := by intro h; exact hxM (Finset.mem_inter.mp h).2 have hsd' : symmDiff A (A ∩ M) ∈ K := hsd A hAK (A ∩ M) hAMK have hx' : x ∈ symmDiff A (A ∩ M) := by rw [Finset.mem_symmDiff]; exact Or.inl ⟨hxA, hxAM⟩ have h1 : A.card ≤ (symmDiff A (A ∩ M)).card := hAmin' _ hsd' hx' have h2 : symmDiff A (A ∩ M) ⊆ A := by rw [symmDiff_of_ge (Finset.inter_subset_left : A ∩ M ⊆ A)] exact Finset.sdiff_subset have heq : symmDiff A (A ∩ M) = A := Finset.eq_of_subset_of_card_le h2 h1 have heq' : A \ (A ∩ M) = A := by rw [← symmDiff_of_ge (Finset.inter_subset_left : A ∩ M ⊆ A)] exact heq have hdisj : Disjoint A (A ∩ M) := by rw [Finset.disjoint_left] intro y hyA hyAM have hy : y ∈ A \ (A ∩ M) := by rw [heq']; exact hyA exact (Finset.mem_sdiff.mp hy).2 hyAM have hAM : A ∩ M = ∅ := by have h := Finset.disjoint_iff_inter_eq_empty.mp hdisj rw [← Finset.inter_assoc, Finset.inter_self] at h exact h have hdisjAM : Disjoint A M := by rw [Finset.disjoint_left] intro y hyA hyM have hy : y ∈ A ∩ M := Finset.mem_inter.mpr ⟨hyA, hyM⟩ rw [hAM] at hy simp at hy exact hdisjAM set K1 : Finset (Finset ι) := K.filter (fun M => Disjoint A M) with hK1def set K1c : Finset (Finset ι) := K.filter (fun M => ¬ Disjoint A M) with hK1cdef have hmem1 : ∀ M, M ∈ K1 ↔ M ∈ K ∧ Disjoint A M := by intro M; rw [hK1def]; exact Finset.mem_filter have hmem1c : ∀ M, M ∈ K1c ↔ M ∈ K ∧ ¬ Disjoint A M := by intro M; rw [hK1cdef]; exact Finset.mem_filter have hcard : K.card = K1.card + K1c.card := by have h := Finset.card_filter_add_card_filter_not (s := K) (p := fun M => Disjoint A M) rw [← hK1def, ← hK1cdef] at h exact h.symm have hf1 : ∀ M ∈ K1, symmDiff M A ∈ K1c := by intro M hM obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM have hK : symmDiff M A ∈ K := hsd M hMK A hAK have hnd : ¬ Disjoint A (symmDiff M A) := by intro hd have hxM : x ∉ M := (Finset.disjoint_left.mp hDM) hxA have hxmem : x ∈ symmDiff M A := by rw [Finset.mem_symmDiff] exact Or.inr ⟨hxA, hxM⟩ exact ((Finset.disjoint_left.mp hd) hxA) hxmem exact (hmem1c _).mpr ⟨hK, hnd⟩ have hf2 : ∀ M ∈ K1c, symmDiff M A ∈ K1 := by intro M hM obtain ⟨hMK, hndM⟩ := (hmem1c M).mp hM have hAM : A ⊆ M := (hkey M hMK).resolve_left hndM have hK : symmDiff M A ∈ K := hsd M hMK A hAK have hdisj : Disjoint A (symmDiff M A) := by have h1 : symmDiff M A = M \ A := symmDiff_of_ge hAM rw [h1, Finset.disjoint_left] intro y hyA hy exact (Finset.mem_sdiff.mp hy).2 hyA exact (hmem1 _).mpr ⟨hK, hdisj⟩ have hff : ∀ M : Finset ι, symmDiff (symmDiff M A) A = M := fun M => symmDiff_symmDiff_cancel_right A M have hinj : Function.Injective (fun M : Finset ι => symmDiff M A) := by intro M N h have h1 : symmDiff (symmDiff M A) A = symmDiff (symmDiff N A) A := congrArg (fun L => symmDiff L A) h simpa only [hff] using h1 have himage : K1.image (fun M => symmDiff M A) = K1c := by apply Finset.Subset.antisymm · intro M hM obtain ⟨N, hN, rfl⟩ := Finset.mem_image.mp hM exact hf1 N hN · intro M hM exact Finset.mem_image.mpr ⟨symmDiff M A, hf2 M hM, hff M⟩ have hK1c_card : K1c.card = K1.card := by rw [← himage, Finset.card_image_of_injective _ hinj] have hKcard : K.card = 2 * K1.card := by rw [hcard, hK1c_card] ring have hAU : A ⊆ U := hsub A hAK have hAcard : 2 ≤ A.card := by by_contra h have hpos : 0 < A.card := Finset.card_pos.mpr ⟨x, hxA⟩ have h1 : A.card = 1 := by omega obtain ⟨y, hy⟩ := Finset.card_eq_one.mp h1 have hxy : x = y := by have hx : x ∈ ({y} : Finset ι) := by rw [← hy]; exact hxA simpa using hx rw [hy, ← hxy] at hAK exact hsing x hAK have hlt : (U \ A).card < n := by rw [← hU] have h1 : (U \ A).card = U.card - A.card := Finset.card_sdiff_of_subset hAU have h2 : A.card ≤ U.card := Finset.card_le_card hAU omega have hsub1 : ∀ M ∈ K1, M ⊆ U \ A := by intro M hM obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM rw [Finset.subset_sdiff] exact ⟨hsub M hMK, hDM.symm⟩ have h01 : ∅ ∈ K1 := (hmem1 ∅).mpr ⟨h0, by simp⟩ have hinter1 : ∀ M ∈ K1, ∀ N ∈ K1, M ∩ N ∈ K1 := by intro M hM N hN obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM obtain ⟨hNK, hDN⟩ := (hmem1 N).mp hN exact (hmem1 _).mpr ⟨hinter M hMK N hNK, Disjoint.mono le_rfl Finset.inter_subset_left hDM⟩ have hsd1 : ∀ M ∈ K1, ∀ N ∈ K1, symmDiff M N ∈ K1 := by intro M hM N hN obtain ⟨hMK, hDM⟩ := (hmem1 M).mp hM obtain ⟨hNK, hDN⟩ := (hmem1 N).mp hN refine (hmem1 _).mpr ⟨hsd M hMK N hNK, ?_⟩ rw [Finset.disjoint_left] intro y hyA hyMN rw [Finset.mem_symmDiff] at hyMN rcases hyMN with ⟨hyM, -⟩ | ⟨hyN, -⟩ · exact ((Finset.disjoint_left.mp hDM) hyA) hyM · exact ((Finset.disjoint_left.mp hDN) hyA) hyN have hsing1 : ∀ y, ({y} : Finset ι) ∉ K1 := by intro y hy exact hsing y ((hmem1 _).mp hy).1 have hIH := ih (U \ A).card hlt (U \ A) K1 rfl hsub1 h01 hinter1 hsd1 hsing1 have hdlle : (U \ A).card + 2 ≤ U.card := by have h1 : (U \ A).card = U.card - A.card := Finset.card_sdiff_of_subset hAU have h2 : A.card ≤ U.card := Finset.card_le_card hAU omega have hpow : (4:ℕ) * 2 ^ (U \ A).card = 2 ^ ((U \ A).card + 2) := by rw [show (4:ℕ) = 2^2 by norm_num, ← pow_add, Nat.add_comm] calc K.card ^ 2 = (2 * K1.card) ^ 2 := by rw [hKcard] _ = 4 * K1.card ^ 2 := by ring _ ≤ 4 * 2 ^ (U \ A).card := Nat.mul_le_mul_left 4 hIH _ = 2 ^ ((U \ A).card + 2) := hpow _ ≤ 2 ^ U.card := Nat.pow_le_pow_right (by norm_num) hdlle · push Not at hex have hsub' : ∀ A ∈ K, A ⊆ U.erase x := by intro A hA rw [Finset.subset_erase] exact ⟨hsub A hA, hex A hA⟩ have hlt : (U.erase x).card < n := by rw [← hU] exact Finset.card_erase_lt_of_mem hxU have hIH := ih (U.erase x).card hlt (U.erase x) K rfl hsub' h0 hinter hsd hsing calc K.card ^ 2 ≤ 2 ^ (U.erase x).card := hIH _ ≤ 2 ^ U.card := Nat.pow_le_pow_right (by norm_num) Finset.card_erase_letheorem finset_family_card_sq_le_of_inter_symm_diff {ι : Type*} [DecidableEq ι] (U : Finset ι) (K : Finset (Finset ι)) (hsub : ∀ A ∈ K, A ⊆ U) (h0 : ∅ ∈ K) (hinter : ∀ A ∈ K, ∀ B ∈ K, A ∩ B ∈ K) (hsd : ∀ A ∈ K, ∀ B ∈ K, symmDiff A B ∈ K) (hsing : ∀ x, ({x} : Finset ι) ∉ K) : K.card ^ 2 ≤ 2 ^ U.card := finset_family_card_sq_le_of_inter_symm_diff_aux U.card U K rfl hsub h0 hinter hsd hsing