AFTD Auto-Formalizing Theoretical Domains

finset_family_card_sq_le_of_inter_symm_diff

theoremverified

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|.

  1. 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.

    lines 6–9

    uses Nat.strong_induction_on

      classical
      induction n using Nat.strong_induction_on with
      | h n ih =>
        intro U K hU hsub h0 hinter hsd hsing
  2. 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.

    lines 10–18

    uses Finset.eq_empty_or_nonempty, Finset.mem_singleton, Finset.subset_empty.mp, Finset.Subset.antisymm, Finset.singleton_subset_iff.mpr

        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
  3. 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.

    lines 19–20

        · obtain ⟨x, hxU⟩ := hUne
          by_cases hex : ∃ M ∈ K, x ∈ M
  4. 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.

    lines 21–29

    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⟩)
  5. 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.

    lines 30–70

    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_self

            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
  6. 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₁ᶜ|.

    lines 71–80

    uses Finset.mem_filter, Finset.card_filter_add_card_filter_not

            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
  7. 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₁|.

    lines 81–123

    uses symmDiff_of_ge, symmDiff_symmDiff_cancel_right, Finset.Subset.antisymm, Finset.card_image_of_injective

            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
  8. 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.

    lines 124–133

    uses Finset.card_pos.mpr, Finset.card_eq_one.mp

            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
  9. 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|.

    lines 134–164

    uses Finset.card_sdiff_of_subset, Finset.card_le_card, Finset.subset_sdiff, Disjoint.mono

            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
  10. 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|.

    lines 165–175

    uses Finset.card_sdiff_of_subset, Finset.card_le_card, pow_add, Nat.add_comm, Nat.mul_le_mul_left, Nat.pow_le_pow_right

            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
  11. 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|.

    lines 176–186

    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
  12. The main theorem follows immediately from the auxiliary lemma.

    Specializing the auxiliary lemma to n = |U| establishes the theorem for any universe U.

    line 192

    uses finset_family_card_sq_le_of_inter_symm_diff_aux

        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
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|.

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

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
See it in the graphDiscuss this resultChallenge it