AFTD Auto-Formalizing Theoretical Domains

op_639_card_eq_sum_four_trace_levels

theoremverified

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.

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

    lines 9–10

    uses op_639_card_eq_sum_fiber_traces

      open Finset in
      have h_fibers := op_639_card_eq_sum_fiber_traces F T hT_trans
  2. |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.

    lines 11–17

    uses Finset.sum_erase, Finset.card_eq_zero, Finset.filter_eq_empty_iff, Finset.disjoint_iff_inter_eq_empty.mpr

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

    lines 18–19

    uses Finset.sum_powerset

      have h_split := Finset.sum_powerset (β := ℕ) T (fun S => (F.filter (fun e => e ∩ T = S)).card)
      rw [h_split, hT] at h_fibers
  4. 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.

    lines 20–28

    uses Finset.sum_range_succ, Finset.sum_range_zero, zero_add

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

    lines 29–33

    uses Finset.powersetCard_zero, Finset.sum_singleton, Finset.card_eq_zero, Finset.filter_eq_empty_iff, Finset.disjoint_iff_inter_eq_empty.mpr

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

    lines 34–37

    uses Finset.powersetCard_self, Finset.sum_singleton

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

    lines 38–39

      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

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