AFTD Auto-Formalizing Theoretical Domains

finset_down_closed_family_avg_card_le

theoremverified

A nonempty downward-closed family I of subsets of a finite set X has average set size at most |X|/2, with equality exactly when I is the whole power set of X.

Statement

theorem finset_down_closed_family_avg_card_le {α : Type*} [DecidableEq α] (X : Finset α)
    (I : Finset (Finset α)) (hI : I.Nonempty) (hsub : ∀ S ∈ I, S ⊆ X)
    (hdown : ∀ S ∈ I, ∀ T ⊆ S, T ∈ I) :
    (∑ S ∈ I, (S.card : ℚ)) / I.card ≤ (X.card : ℚ) / 2 ∧
      ((∑ S ∈ I, (S.card : ℚ)) / I.card = (X.card : ℚ) / 2 ↔ I = X.powerset)
Source
arXiv:2610.11446 (On the local average order of dominating sets), Lemma 2.1 (quoted there from earlier work on the average order of dominating sets, Proposition 2.3), serving Theorem 2.2.
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

By double counting element-set incidences, the total sum of set sizes in I equals the sum over x ∈ X of the number a(x) of members containing x. Because I is downward-closed, deleting x injectively maps members containing x to members avoiding x, which gives a(x) ≤ b(x) and thus 2 a(x) ≤ a(x) + b(x) = |I| for each x. Summing this over X proves that the average cardinality is at most |X|/2. Equality holds precisely when a(x) = b(x) for all x ∈ X, making deletion a bijection; this forces I to be closed under element insertion, which inductively implies that I is the full power set of X.

  1. For every element x, the number a(x) of sets in I containing x plus the number b(x) avoiding x equals |I|.

    We define a(x) as the cardinality of {S ∈ I | x ∈ S} and b(x) as the cardinality of {S ∈ I | x ∉ S}. Partitioning I into members containing x and members avoiding x gives a(x) + b(x) = |I| for all x.

    lines 6–11

    uses Finset.card_filter_add_card_filter_not

      classical
      -- `a x` members containing `x`, `b x` members avoiding `x`
      set a : α → ℕ := fun x => (I.filter (fun S => x ∈ S)).card with ha
      set b : α → ℕ := fun x => (I.filter (fun S => x ∉ S)).card with hb
      have hab : ∀ x, a x + b x = I.card := fun x =>
        Finset.card_filter_add_card_filter_not _
  2. The sum of the sizes of all sets in I equals the sum of a(x) over all x ∈ X.

    Because every set S in I is a subset of X, its cardinality |S| is the sum of the indicator function [x ∈ S] over x ∈ X. Exchanging the order of summation gives ∑_{S ∈ I} |S| = ∑_{x ∈ X} a(x).

    lines 12–19

    uses Finset.card_filter, Finset.filter_mem_eq_inter, Finset.sum_congr, Finset.sum_comm

      have hsum : ∑ S ∈ I, S.card = ∑ x ∈ X, a x := by
        have h : ∀ S ∈ I, S.card = ∑ x ∈ X, if x ∈ S then 1 else 0 := by
          intro S hS
          rw [← Finset.card_filter, Finset.filter_mem_eq_inter,
            Finset.inter_eq_right.2 (hsub S hS)]
        rw [Finset.sum_congr rfl h, Finset.sum_comm]
        refine Finset.sum_congr rfl fun x _ => ?_
        simp only [ha]; rw [Finset.card_filter]
  3. For every element x, the count a(x) is at most b(x).

    The operation S ↦ S \ {x} is injective on {S ∈ I | x ∈ S} because reinserting x recovers S. Since I is downward-closed, S \ {x} belongs to I, and by construction it avoids x. Hence deletion injectively maps the sets containing x into the sets avoiding x, which implies a(x) ≤ b(x).

    lines 21–37

    uses Finset.coe_filter, Set.mem_ofPred_eq, Finset.insert_erase, congrArg, Finset.mem_filter, Finset.erase_subset, Finset.card_image_of_injOn, Finset.card_le_card

      have erase_inj : ∀ x, Set.InjOn (fun S : Finset α => S.erase x)
          ↑(I.filter (fun S => x ∈ S)) := by
        intro x S hS T hT h
        simp only [Finset.coe_filter, Set.mem_ofPred_eq] at hS hT
        rw [← Finset.insert_erase hS.2, ← Finset.insert_erase hT.2]
        exact congrArg (insert x) h
      have erase_maps : ∀ x, ∀ S ∈ I.filter (fun S => x ∈ S), S.erase x ∈ I.filter (fun S => x ∉ S) := by
        intro x S hS
        rw [Finset.mem_filter] at hS ⊢
        exact ⟨hdown S hS.1 _ (Finset.erase_subset x S), by simp⟩
      have hle : ∀ x, a x ≤ b x := by
        intro x
        simp only [ha, hb]; rw [← Finset.card_image_of_injOn (erase_inj x)]
        apply Finset.card_le_card
        intro T hT
        obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT
        exact erase_maps x S hS
  4. If I is closed under inserting elements of X, then b(x) ≤ a(x) for all x ∈ X.

    Under this hypothesis, the map S ↦ S ∪ {x} injectively sends {S ∈ I | x ∉ S} into {S ∈ I | x ∈ S}, since erasing x recovers S. Therefore, the size b(x) of the domain is at most the size a(x) of the codomain.

    lines 39–51

    uses Finset.coe_filter, Set.mem_ofPred_eq, Finset.erase_insert, congrArg, Finset.card_image_of_injOn, Finset.card_le_card, Finset.mem_filter, Finset.mem_insert_self

      have hge : (∀ S ∈ I, ∀ x ∈ X, x ∉ S → insert x S ∈ I) → ∀ x ∈ X, b x ≤ a x := by
        intro hup x hx
        have inj : Set.InjOn (fun S : Finset α => insert x S) ↑(I.filter (fun S => x ∉ S)) := by
          intro S hS T hT h
          simp only [Finset.coe_filter, Set.mem_ofPred_eq] at hS hT
          rw [← Finset.erase_insert hS.2, ← Finset.erase_insert hT.2]
          exact congrArg (fun U => Finset.erase U x) h
        simp only [ha, hb]; rw [← Finset.card_image_of_injOn inj]
        apply Finset.card_le_card
        intro T hT
        obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT
        rw [Finset.mem_filter] at hS ⊢
        exact ⟨hup S hS.1 x hx hS.2, Finset.mem_insert_self x S⟩
  5. The sum ∑_{x ∈ X} (a(x) + b(x)) equals |X| · |I|, and 2 ∑_{x ∈ X} a(x) ≤ |X| · |I|.

    Summing the constant a(x) + b(x) = |I| over all x ∈ X gives |X| · |I|. Adding the inequality a(x) ≤ b(x) to a(x) ≤ a(x) and summing over X yields 2 ∑_{x ∈ X} a(x) ≤ ∑_{x ∈ X} (a(x) + b(x)) = |X| · |I|.

    lines 52–59

    uses Finset.sum_congr, Finset.sum_const, smul_eq_mul, Nat.cast_sum, Finset.sum_add_distrib, two_mul, Nat.add_le_add_left, Finset.sum_le_sum

      have htot : ∑ x ∈ X, (a x + b x) = X.card * I.card := by
        rw [Finset.sum_congr rfl fun x _ => hab x, Finset.sum_const, smul_eq_mul]
      have hIpos : (0 : ℚ) < I.card := by exact_mod_cast hI.card_pos
      have havg : (∑ S ∈ I, (S.card : ℚ)) / I.card = ((∑ x ∈ X, a x : ℕ) : ℚ) / I.card := by
        rw [← hsum, Nat.cast_sum]
      have hnat : 2 * ∑ x ∈ X, a x ≤ X.card * I.card := by
        rw [← htot, Finset.sum_add_distrib, two_mul]
        exact Nat.add_le_add_left (Finset.sum_le_sum fun x _ => hle x) _
  6. The average set size in I is at most |X| / 2.

    We split the goal into the average inequality and the equivalence for equality. Using the relation ∑_{S ∈ I} |S| = ∑_{x ∈ X} a(x) and the fact that |I| > 0, dividing the integer inequality 2 ∑_{x ∈ X} a(x) ≤ |X| · |I| by 2 |I| gives (∑_{S ∈ I} |S|) / |I| ≤ |X| / 2.

    lines 60–63

    uses div_le_iff₀

      refine ⟨?_, ⟨fun heq => ?_, fun hI' => ?_⟩⟩
      · rw [havg, div_le_iff₀ hIpos]
        have : (2 : ℚ) * ((∑ x ∈ X, a x : ℕ) : ℚ) ≤ (X.card : ℚ) * I.card := by exact_mod_cast hnat
        linarith
  7. If the average set size in I equals |X| / 2, then I is the power set of X.

    Equality implies 2 ∑_{x ∈ X} a(x) = |X| · |I| = ∑_{x ∈ X} (a(x) + b(x)), so ∑_{x ∈ X} a(x) = ∑_{x ∈ X} b(x). Since a(x) ≤ b(x) pointwise, we must have a(x) = b(x) for all x ∈ X. The injection S ↦ S \ {x} between equinumerous finite sets is therefore surjective, meaning every set in I avoiding x comes from deleting x from a member of I; thus I is closed under inserting x. Since I is nonempty and downward-closed, ∅ ∈ I. By finite set induction, starting from ∅ and inserting elements of X shows every subset of X belongs to I, so I = powerset(X).

    lines 65–99

    uses div_eq_iff, Finset.sum_add_distrib, Finset.sum_eq_sum_iff_of_le, Finset.eq_of_subset_of_card_le, Finset.card_image_of_injOn, Finset.mem_filter, Finset.insert_erase, Finset.empty_subset, Finset.mem_powerset, Finset.induction_on, Finset.subset_insert, Finset.mem_insert_self

        rw [havg, div_eq_iff hIpos.ne'] at heq
        have h2 : 2 * ∑ x ∈ X, a x = X.card * I.card := by
          have : (2 : ℚ) * ((∑ x ∈ X, a x : ℕ) : ℚ) = (X.card : ℚ) * I.card := by linarith
          exact_mod_cast this
        have hsab : ∑ x ∈ X, a x = ∑ x ∈ X, b x := by
          rw [← htot, Finset.sum_add_distrib] at h2
          omega
        have hpt := (Finset.sum_eq_sum_iff_of_le fun x _ => hle x).1 hsab
        have hup : ∀ S ∈ I, ∀ x ∈ X, x ∉ S → insert x S ∈ I := by
          intro S hS x hx hxS
          have himg : (I.filter (fun S => x ∈ S)).image (fun S => S.erase x) =
              I.filter (fun S => x ∉ S) := by
            apply Finset.eq_of_subset_of_card_le
            · intro T hT
              obtain ⟨U, hU, rfl⟩ := Finset.mem_image.1 hT
              exact erase_maps x U hU
            · rw [Finset.card_image_of_injOn (erase_inj x)]
              exact (hpt x hx).ge
          have hmem : S ∈ (I.filter (fun S => x ∈ S)).image (fun S => S.erase x) := by
            rw [himg, Finset.mem_filter]; exact ⟨hS, hxS⟩
          obtain ⟨T, hT, hTS⟩ := Finset.mem_image.1 hmem
          rw [Finset.mem_filter] at hT
          rw [← hTS, Finset.insert_erase hT.2]
          exact hT.1
        have hempty : ∅ ∈ I := by
          obtain ⟨S, hS⟩ := hI
          exact hdown S hS ∅ (Finset.empty_subset S)
        ext T
        rw [Finset.mem_powerset]
        refine ⟨hsub T, fun hT => ?_⟩
        induction T using Finset.induction_on with
        | empty => exact hempty
        | insert x T hxT ih =>
          have hTX : T ⊆ X := (Finset.subset_insert x T).trans hT
          exact hup T (ih hTX) x (hT (Finset.mem_insert_self x T)) hxT
  8. If I is the power set of X, then the average set size in I equals |X| / 2.

    When I is the full power set of X, it is closed under inserting elements of X, so b(x) ≤ a(x) for all x ∈ X. Combined with a(x) ≤ b(x), this gives a(x) = b(x) everywhere on X. Then 2 ∑_{x ∈ X} a(x) = ∑_{x ∈ X} (a(x) + b(x)) = |X| · |I|, which implies that the average set size is exactly |X| / 2.

    lines 101–110

    uses Finset.mem_powerset, Finset.insert_subset, le_antisymm, Finset.sum_add_distrib, two_mul, Finset.sum_congr, div_eq_iff

        have hup : ∀ S ∈ I, ∀ x ∈ X, x ∉ S → insert x S ∈ I := by
          intro S hS x hx _
          rw [hI', Finset.mem_powerset] at hS ⊢
          exact Finset.insert_subset hx hS
        have hpt : ∀ x ∈ X, a x = b x := fun x hx => le_antisymm (hle x) (hge hup x hx)
        have h2 : 2 * ∑ x ∈ X, a x = X.card * I.card := by
          rw [← htot, Finset.sum_add_distrib, two_mul, Finset.sum_congr rfl hpt]
        rw [havg, div_eq_iff hIpos.ne']
        have : (2 : ℚ) * ((∑ x ∈ X, a x : ℕ) : ℚ) = (X.card : ℚ) * I.card := by exact_mod_cast h2
        linarith
Finset.card_filter_add_card_filter_not
For any finite set and predicate, the number of elements satisfying the predicate plus the number not satisfying it equals the cardinality of the set.
Finset.card_filter
The number of elements in a finite set satisfying a predicate equals the sum over the set of the indicator function of the predicate.
Finset.filter_mem_eq_inter
Filtering a finite set by membership in another set equals the intersection of the two sets.
Finset.sum_congr
Two sums over finite sets are equal if the index sets are equal and the summands agree on every element.
Finset.sum_comm
Swapping the order of summation in a double sum over two finite sets preserves the sum.
Finset.coe_filter
The coercion to a set of a filtered finite set equals the set comprehension of elements satisfying the predicate.
Set.mem_ofPred_eq
Membership of an element in a set comprehension {y | p y} is equivalent to the predicate p holding for that element.
Finset.insert_erase
Inserting an element into a finite set from which it was erased recovers the original set, provided the element belonged to the set.
congrArg
Applying a function to equal inputs yields equal results.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.erase_subset
Erasing an element from a finite set produces a subset of the original set.
Finset.card_image_of_injOn
If a map is injective on a finite set, the cardinality of its image equals the cardinality of the original set.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to that of the superset.
Finset.erase_insert
Erasing an element from a set after inserting it recovers the original set, provided the element was not originally in the set.
Finset.mem_insert_self
An element always belongs to the set formed by inserting it into any finite set.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set scalar-multiplied by the constant.
smul_eq_mul
Scalar multiplication by a natural number in a semiring agrees with ordinary multiplication.
Nat.cast_sum
The coercion of a sum of natural numbers to another semiring equals the sum of the coerced terms.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of the first function plus the sum of the second.
two_mul
Multiplying an element by 2 is equal to adding the element to itself.
Nat.add_le_add_left
Adding a natural number to both sides of an inequality preserves the inequality.
Finset.sum_le_sum
If a function is pointwise at most another on a finite set, the sum of the first is at most the sum of the second.
div_le_iff₀
For a positive divisor, a quotient is at most a value if and only if the numerator is at most the product of the value and the divisor.
div_eq_iff
For a nonzero denominator, a quotient equals a value if and only if the numerator equals the product of the value and the denominator.
Finset.sum_eq_sum_iff_of_le
When one function is pointwise bounded by another on a finite set, their sums are equal if and only if the functions agree pointwise everywhere on the set.
Finset.eq_of_subset_of_card_le
If a finite set is a subset of another and has cardinality at least that of the other, the two sets are equal.
Finset.empty_subset
The empty set is a subset of every finite set.
Finset.mem_powerset
A finite set belongs to the powerset of another if and only if it is a subset of that set.
Finset.induction_on
To prove a property for all finite sets, it suffices to prove it for the empty set and show it is preserved under inserting an element.
Finset.subset_insert
A finite set is a subset of the set obtained by inserting an element into it.
Finset.insert_subset
Inserting an element belonging to a superset into a subset yields another subset of the superset.
le_antisymm
In a partial order, if two elements are less than or equal to each other, they are equal.

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

theorem finset_down_closed_family_avg_card_le {α : Type*} [DecidableEq α] (X : Finset α)    (I : Finset (Finset α)) (hI : I.Nonempty) (hsub : ∀ S ∈ I, S ⊆ X)    (hdown : ∀ S ∈ I, ∀ T ⊆ S, T ∈ I) :    (∑ S ∈ I, (S.card : ℚ)) / I.card ≤ (X.card : ℚ) / 2 ∧      ((∑ S ∈ I, (S.card : ℚ)) / I.card = (X.card : ℚ) / 2 ↔ I = X.powerset) := by  classical  -- `a x` members containing `x`, `b x` members avoiding `x`  set a : α → ℕ := fun x => (I.filter (fun S => x ∈ S)).card with ha  set b : α → ℕ := fun x => (I.filter (fun S => x ∉ S)).card with hb  have hab : ∀ x, a x + b x = I.card := fun x =>    Finset.card_filter_add_card_filter_not _  have hsum : ∑ S ∈ I, S.card = ∑ x ∈ X, a x := by    have h : ∀ S ∈ I, S.card = ∑ x ∈ X, if x ∈ S then 1 else 0 := by      intro S hS      rw [← Finset.card_filter, Finset.filter_mem_eq_inter,        Finset.inter_eq_right.2 (hsub S hS)]    rw [Finset.sum_congr rfl h, Finset.sum_comm]    refine Finset.sum_congr rfl fun x _ => ?_    simp only [ha]; rw [Finset.card_filter]  -- deleting `x` is injective on the members containing `x`  have erase_inj : ∀ x, Set.InjOn (fun S : Finset α => S.erase x)      ↑(I.filter (fun S => x ∈ S)) := by    intro x S hS T hT h    simp only [Finset.coe_filter, Set.mem_ofPred_eq] at hS hT    rw [← Finset.insert_erase hS.2, ← Finset.insert_erase hT.2]    exact congrArg (insert x) h  have erase_maps : ∀ x, ∀ S ∈ I.filter (fun S => x ∈ S), S.erase x ∈ I.filter (fun S => x ∉ S) := by    intro x S hS    rw [Finset.mem_filter] at hS ⊢    exact ⟨hdown S hS.1 _ (Finset.erase_subset x S), by simp⟩  have hle : ∀ x, a x ≤ b x := by    intro x    simp only [ha, hb]; rw [← Finset.card_image_of_injOn (erase_inj x)]    apply Finset.card_le_card    intro T hT    obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT    exact erase_maps x S hS  -- with insertion also closed, the two counts agree  have hge : (∀ S ∈ I, ∀ x ∈ X, x ∉ S → insert x S ∈ I) → ∀ x ∈ X, b x ≤ a x := by    intro hup x hx    have inj : Set.InjOn (fun S : Finset α => insert x S) ↑(I.filter (fun S => x ∉ S)) := by      intro S hS T hT h      simp only [Finset.coe_filter, Set.mem_ofPred_eq] at hS hT      rw [← Finset.erase_insert hS.2, ← Finset.erase_insert hT.2]      exact congrArg (fun U => Finset.erase U x) h    simp only [ha, hb]; rw [← Finset.card_image_of_injOn inj]    apply Finset.card_le_card    intro T hT    obtain ⟨S, hS, rfl⟩ := Finset.mem_image.1 hT    rw [Finset.mem_filter] at hS ⊢    exact ⟨hup S hS.1 x hx hS.2, Finset.mem_insert_self x S⟩  have htot : ∑ x ∈ X, (a x + b x) = X.card * I.card := by    rw [Finset.sum_congr rfl fun x _ => hab x, Finset.sum_const, smul_eq_mul]  have hIpos : (0 : ℚ) < I.card := by exact_mod_cast hI.card_pos  have havg : (∑ S ∈ I, (S.card : ℚ)) / I.card = ((∑ x ∈ X, a x : ℕ) : ℚ) / I.card := by    rw [← hsum, Nat.cast_sum]  have hnat : 2 * ∑ x ∈ X, a x ≤ X.card * I.card := by    rw [← htot, Finset.sum_add_distrib, two_mul]    exact Nat.add_le_add_left (Finset.sum_le_sum fun x _ => hle x) _  refine ⟨?_, ⟨fun heq => ?_, fun hI' => ?_⟩⟩  · rw [havg, div_le_iff₀ hIpos]    have : (2 : ℚ) * ((∑ x ∈ X, a x : ℕ) : ℚ) ≤ (X.card : ℚ) * I.card := by exact_mod_cast hnat    linarith  · -- equality: every count agrees, so the family is closed under insertion    rw [havg, div_eq_iff hIpos.ne'] at heq    have h2 : 2 * ∑ x ∈ X, a x = X.card * I.card := by      have : (2 : ℚ) * ((∑ x ∈ X, a x : ℕ) : ℚ) = (X.card : ℚ) * I.card := by linarith      exact_mod_cast this    have hsab : ∑ x ∈ X, a x = ∑ x ∈ X, b x := by      rw [← htot, Finset.sum_add_distrib] at h2      omega    have hpt := (Finset.sum_eq_sum_iff_of_le fun x _ => hle x).1 hsab    have hup : ∀ S ∈ I, ∀ x ∈ X, x ∉ S → insert x S ∈ I := by      intro S hS x hx hxS      have himg : (I.filter (fun S => x ∈ S)).image (fun S => S.erase x) =          I.filter (fun S => x ∉ S) := by        apply Finset.eq_of_subset_of_card_le        · intro T hT          obtain ⟨U, hU, rfl⟩ := Finset.mem_image.1 hT          exact erase_maps x U hU        · rw [Finset.card_image_of_injOn (erase_inj x)]          exact (hpt x hx).ge      have hmem : S ∈ (I.filter (fun S => x ∈ S)).image (fun S => S.erase x) := by        rw [himg, Finset.mem_filter]; exact ⟨hS, hxS⟩      obtain ⟨T, hT, hTS⟩ := Finset.mem_image.1 hmem      rw [Finset.mem_filter] at hT      rw [← hTS, Finset.insert_erase hT.2]      exact hT.1    have hempty : ∅ ∈ I := by      obtain ⟨S, hS⟩ := hI      exact hdown S hS ∅ (Finset.empty_subset S)    ext T    rw [Finset.mem_powerset]    refine ⟨hsub T, fun hT => ?_⟩    induction T using Finset.induction_on with    | empty => exact hempty    | insert x T hxT ih =>      have hTX : T ⊆ X := (Finset.subset_insert x T).trans hT      exact hup T (ih hTX) x (hT (Finset.mem_insert_self x T)) hxT  · -- the whole power set: the two counts agree    have hup : ∀ S ∈ I, ∀ x ∈ X, x ∉ S → insert x S ∈ I := by      intro S hS x hx _      rw [hI', Finset.mem_powerset] at hS ⊢      exact Finset.insert_subset hx hS    have hpt : ∀ x ∈ X, a x = b x := fun x hx => le_antisymm (hle x) (hge hup x hx)    have h2 : 2 * ∑ x ∈ X, a x = X.card * I.card := by      rw [← htot, Finset.sum_add_distrib, two_mul, Finset.sum_congr rfl hpt]    rw [havg, div_eq_iff hIpos.ne']    have : (2 : ℚ) * ((∑ x ∈ X, a x : ℕ) : ℚ) = (X.card : ℚ) * I.card := by exact_mod_cast h2    linarith
See it in the graphDiscuss this resultChallenge it