finset_down_closed_family_avg_card_le
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
- simple_graph_local_avg_dominating_order_geFor every finite graph G of order n and every vertex v, the dominating sets containing v have average size at least (n+1)/2, with equality…
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.
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.
uses
Finset.card_filter_add_card_filter_notclassical -- `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 _
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).
uses
Finset.card_filter,Finset.filter_mem_eq_inter,Finset.sum_congr,Finset.sum_commhave 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]
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).
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_cardhave 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
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.
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_selfhave 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⟩
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|.
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_sumhave 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) _
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.
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
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).
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_selfrw [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
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.
uses
Finset.mem_powerset,Finset.insert_subset,le_antisymm,Finset.sum_add_distrib,two_mul,Finset.sum_congr,div_eq_iffhave 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.
- The double counting of incidences is formalized by writing the size of each subset as a sum of indicator variables over X and exchanging the order of summation.
- To prove that the deletion map is surjective when a(x) = b(x), the proof uses Finset.eq_of_subset_of_card_le, which deduces equality of two finite sets from inclusion and equal cardinality, avoiding the need to construct an explicit inverse.
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.
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