op_639_card_eq_sum_four_trace_levels
Let T be a 4-element transversal of F. Then the size of F is partitioned into the sum of the sizes of the trace fibers on T of cardinalities 4 (the full fiber), 3, 2, and 1.
Statement
theorem op_639_card_eq_sum_four_trace_levels {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (T : Finset V) (hT : T.card = 4) (hT_trans : ∀ e ∈ F, ¬Disjoint e T) : F.card = (F.filter (fun e => e ∩ T = T)).card + (∑ S ∈ T.powersetCard 3, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 2, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 1, (F.filter (fun e => e ∩ T = S)).card)
- Source
- step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op_639_card_eq_sum_fiber_tracesFor any transversal T of F, every edge e in F has non-empty trace e ∩ T on T, so F is partitioned into the fibers of the map e ↦ e ∩ T…
The proof, explained
The theorem partitions the cardinality of a family of sets F equipped with a 4-element transversal T into the sum of the sizes of its trace fibers of sizes 4, 3, 2, and 1. The proof begins with the known partition of F into trace fibers over all nonempty subsets of T, then adds the empty subset since its corresponding fiber is empty for a transversal. Grouping the subsets of T by cardinality and unrolling the five levels (sizes 0 through 4), the size-0 term vanishes and the size-4 term reduces to the full trace fiber on T, leaving the desired four-level sum.
|F| is the sum of the fiber sizes over all nonempty subsets of T: |F| = ∑_{S ∈ 𝒫(T) \ {∅}} |{e ∈ F | e ∩ T = S}|.
Because T is a transversal of F, every edge in F intersects T. Applying the lemma op_639_card_eq_sum_fiber_traces decomposes |F| into the sum of the sizes of trace fibers {e ∈ F | e ∩ T = S} across all nonempty subsets S ⊆ T.
uses
op_639_card_eq_sum_fiber_tracesopen Finset in have h_fibers := op_639_card_eq_sum_fiber_traces F T hT_trans
|F| is the sum of the fiber sizes over all subsets of T, including the empty set: |F| = ∑_{S ∈ 𝒫(T)} |{e ∈ F | e ∩ T = S}|.
The fiber for S = ∅ consists of edges e ∈ F disjoint from T. Since T is a transversal, no such edge exists, so this fiber is empty and its cardinality is 0. Using Finset.sum_erase, including ∅ in the summation does not change its value.
uses
Finset.sum_erase,Finset.card_eq_zero,Finset.filter_eq_empty_iff,Finset.disjoint_iff_inter_eq_empty.mprhave h_erase : ∑ S ∈ T.powerset.erase ∅, (F.filter (fun e => e ∩ T = S)).card = ∑ S ∈ T.powerset, (F.filter (fun e => e ∩ T = S)).card := by apply Finset.sum_erase simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro e he h exact hT_trans e he (Finset.disjoint_iff_inter_eq_empty.mpr h) rw [h_erase] at h_fibers
|F| is partitioned by subset size: |F| = ∑_{j=0}^4 ∑_{S ∈ (T choose j)} |{e ∈ F | e ∩ T = S}|.
By Finset.sum_powerset, the sum over all subsets of T is grouped by subset cardinality into a sum over j ∈ {0, ..., |T|}. Substituting |T| = 4 yields a sum over j ∈ range 5.
uses
Finset.sum_powersethave h_split := Finset.sum_powerset (β := ℕ) T (fun S => (F.filter (fun e => e ∩ T = S)).card) rw [h_split, hT] at h_fibers
The summation over j ∈ range 5 unrolls into the explicit sum of the 5 level sums for j = 0, 1, 2, 3, 4.
Repeatedly applying Finset.sum_range_succ peels off the terms for j = 4, 3, 2, 1, and 0 from range 5, and the base case Finset.sum_range_zero with zero_add simplifies the remaining empty sum. Rewriting with this equality expands the partition of |F| into five explicit summands.
uses
Finset.sum_range_succ,Finset.sum_range_zero,zero_addhave h_range : ∑ j ∈ range 5, (∑ S ∈ T.powersetCard j, (F.filter (fun e => e ∩ T = S)).card) = (∑ S ∈ T.powersetCard 0, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 1, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 2, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 3, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 4, (F.filter (fun e => e ∩ T = S)).card) := by repeat rw [Finset.sum_range_succ] rw [Finset.sum_range_zero, zero_add] rw [h_range] at h_fibers
The level-0 sum ∑_{S ∈ (T choose 0)} |{e ∈ F | e ∩ T = S}| equals 0.
The only subset of T of size 0 is ∅ (Finset.powersetCard_zero). Because T meets every edge of F, the fiber {e ∈ F | e ∩ T = ∅} is empty, hence its cardinality is 0.
uses
Finset.powersetCard_zero,Finset.sum_singleton,Finset.card_eq_zero,Finset.filter_eq_empty_iff,Finset.disjoint_iff_inter_eq_empty.mprhave h0 : (∑ S ∈ T.powersetCard 0, (F.filter (fun e => e ∩ T = S)).card) = 0 := by rw [Finset.powersetCard_zero, Finset.sum_singleton] simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro e he h exact hT_trans e he (Finset.disjoint_iff_inter_eq_empty.mpr h)
The level-4 sum ∑_{S ∈ (T choose 4)} |{e ∈ F | e ∩ T = S}| equals the full fiber cardinality |{e ∈ F | e ∩ T = T}|.
Because |T| = 4, the only 4-element subset of T is T itself (Finset.powersetCard_self). Thus the sum over (T choose 4) reduces via Finset.sum_singleton to the single term where S = T.
uses
Finset.powersetCard_self,Finset.sum_singletonhave h4 : (∑ S ∈ T.powersetCard 4, (F.filter (fun e => e ∩ T = S)).card) = (F.filter (fun e => e ∩ T = T)).card := by have : T.powersetCard 4 = {T} := by rw [← hT, Finset.powersetCard_self] rw [this, Finset.sum_singleton]
|F| = |{e ∈ F | e ∩ T = T}| + ∑_{S ∈ (T choose 3)} |{e ∈ F | e ∩ T = S}| + ∑_{S ∈ (T choose 2)} |{e ∈ F | e ∩ T = S}| + ∑_{S ∈ (T choose 1)} |{e ∈ F | e ∩ T = S}|.
Substituting the value 0 for the level-0 sum and the full fiber for the level-4 sum into the 5-term partition leaves only levels 1, 2, 3, and 4. Linear arithmetic (omega) reorders the summands into descending order of trace sizes: full fiber (level 4), triples (level 3), pairs (level 2), and singletons (level 1).
rw [h0, h4] at h_fibers omega
op_639_card_eq_sum_fiber_traces- For a transversal T of a family F, the cardinality of F is the sum over all nonempty subsets S of T of the sizes of the trace fibers {e ∈ F | e ∩ T = S}.
Finset.sum_erase- If f evaluates to 0 at a, then the sum of f over s with a erased equals the sum of f over s.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate is empty if and only if no element satisfies the predicate.
Finset.disjoint_iff_inter_eq_empty.mpr- Two sets are disjoint if their intersection is empty.
Finset.sum_powerset- A sum over the power set of s decomposes into a sum over j from 0 to |s| of the sums over subsets of s of size j.
Finset.sum_range_succ- The sum over range (n + 1) equals the sum over range n plus the term at n.
Finset.sum_range_zero- The sum of any function over range 0 is 0.
zero_add- 0 + a = a in an additive structure with zero.
Finset.powersetCard_zero- The only subset of size 0 of any set is the empty set.
Finset.sum_singleton- A sum over a singleton set {a} equals the value of the function at a.
Finset.powersetCard_self- The only subset of a finite set s whose cardinality is |s| is s itself.
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.
/-- For any transversal T of size 4 in F, the cardinality of F is the sum of the full fiber, triple fibers, doubleton fibers, and singleton fibers. -/theorem op_639_card_eq_sum_four_trace_levels {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (T : Finset V) (hT : T.card = 4) (hT_trans : ∀ e ∈ F, ¬Disjoint e T) : F.card = (F.filter (fun e => e ∩ T = T)).card + (∑ S ∈ T.powersetCard 3, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 2, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 1, (F.filter (fun e => e ∩ T = S)).card) := by open Finset in have h_fibers := op_639_card_eq_sum_fiber_traces F T hT_trans have h_erase : ∑ S ∈ T.powerset.erase ∅, (F.filter (fun e => e ∩ T = S)).card = ∑ S ∈ T.powerset, (F.filter (fun e => e ∩ T = S)).card := by apply Finset.sum_erase simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro e he h exact hT_trans e he (Finset.disjoint_iff_inter_eq_empty.mpr h) rw [h_erase] at h_fibers have h_split := Finset.sum_powerset (β := ℕ) T (fun S => (F.filter (fun e => e ∩ T = S)).card) rw [h_split, hT] at h_fibers have h_range : ∑ j ∈ range 5, (∑ S ∈ T.powersetCard j, (F.filter (fun e => e ∩ T = S)).card) = (∑ S ∈ T.powersetCard 0, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 1, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 2, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 3, (F.filter (fun e => e ∩ T = S)).card) + (∑ S ∈ T.powersetCard 4, (F.filter (fun e => e ∩ T = S)).card) := by repeat rw [Finset.sum_range_succ] rw [Finset.sum_range_zero, zero_add] rw [h_range] at h_fibers have h0 : (∑ S ∈ T.powersetCard 0, (F.filter (fun e => e ∩ T = S)).card) = 0 := by rw [Finset.powersetCard_zero, Finset.sum_singleton] simp only [Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro e he h exact hT_trans e he (Finset.disjoint_iff_inter_eq_empty.mpr h) have h4 : (∑ S ∈ T.powersetCard 4, (F.filter (fun e => e ∩ T = S)).card) = (F.filter (fun e => e ∩ T = T)).card := by have : T.powersetCard 4 = {T} := by rw [← hT, Finset.powersetCard_self] rw [this, Finset.sum_singleton] rw [h0, h4] at h_fibers omega