AFTD Auto-Formalizing Theoretical Domains

op_639_card_eq_sum_fiber_traces

theoremverified

For 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 over non-empty subsets of T.

Statement

theorem op_639_card_eq_sum_fiber_traces
    {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (T : Finset V)
    (hT_trans : ∀ e ∈ F, ¬Disjoint e T) :
    F.card = ∑ S ∈ T.powerset.erase ∅, (F.filter (fun e => e ∩ T = S)).card
Source
step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The identity counts the edges of $F$ by partitioning them into fibers according to their trace on $T$, which is the map $e \mapsto e \cap T$. By `Finset.card_eq_sum_card_fiberwise`, this sum identity reduces to verifying that every edge $e \in F$ maps to a non-empty subset of $T$. This holds because $e \cap T \subseteq T$ is automatic, and $e \cap T \ne \emptyset$ follows from the transversal hypothesis that no edge in $F$ is disjoint from $T$.

  1. It suffices to show that the trace map $e \mapsto e \cap T$ maps every edge $e \in F$ to a non-empty subset of $T$.

    By the fiberwise counting formula (`Finset.card_eq_sum_card_fiberwise`), partitioning $F$ by the image of $e \mapsto e \cap T$ expresses $|F|$ as the sum of the sizes of the fibers over $S \in \mathcal{P}(T) \setminus \{\emptyset\}$, provided every $e \in F$ satisfies $e \cap T \in \mathcal{P}(T) \setminus \{\emptyset\}$.

    lines 6–7

    uses Finset.card_eq_sum_card_fiberwise

      refine Finset.card_eq_sum_card_fiberwise (f := fun e : Finset V => e ∩ T) (s := F)
        (t := T.powerset.erase ∅) ?_
  2. For an arbitrary edge $e \in F$, membership in $\mathcal{P}(T) \setminus \{\emptyset\}$ unfolds to $e \cap T \ne \emptyset$ and $e \cap T \subseteq T$.

    Fixing an edge $e \in F$, membership in the erased power set is unwound by `Finset.mem_erase` and `Finset.mem_powerset` into two conditions: $e \cap T \ne \emptyset$ and $e \cap T \subseteq T$.

    lines 8–10

    uses Finset.mem_erase, Finset.mem_powerset

      intro e he
      change e ∩ T ∈ T.powerset.erase ∅
      rw [Finset.mem_erase, Finset.mem_powerset]
  3. The trace $e \cap T$ is non-empty and contained in $T$.

    The inclusion $e \cap T \subseteq T$ holds immediately by `Finset.inter_subset_right`. If the intersection were empty, $e$ and $T$ would be disjoint by `Finset.disjoint_iff_inter_eq_empty`, which directly contradicts the transversal hypothesis $hT\_trans$ that $e$ and $T$ are not disjoint.

    lines 11–12

    uses Finset.disjoint_iff_inter_eq_empty, Finset.inter_subset_right

      exact ⟨fun h => hT_trans e he ((Finset.disjoint_iff_inter_eq_empty).mpr h),
        Finset.inter_subset_right⟩
Finset.card_eq_sum_card_fiberwise
For a map $f$ mapping a finite set $s$ into a finite set $t$, the cardinality of $s$ equals the sum of the cardinalities of the fibers $\{a \in s \mid f(a) = b\}$ over all $b \in t$.
Finset.mem_erase
An element $a$ is in $s \setminus \{b\}$ if and only if $a \ne b$ and $a \in s$.
Finset.mem_powerset
A set $s$ belongs to the power set of $t$ if and only if $s \subseteq t$.
Finset.disjoint_iff_inter_eq_empty
Two finite sets are disjoint if and only if their intersection is empty.
Finset.inter_subset_right
The intersection $s_1 \cap s_2$ is a subset of $s_2$.

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

/-- The size of F equals the sum of sizes of trace fibers e ∩ T over non-empty subsets S of T. -/theorem op_639_card_eq_sum_fiber_traces    {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (T : Finset V)    (hT_trans : ∀ e ∈ F, ¬Disjoint e T) :    F.card = ∑ S ∈ T.powerset.erase ∅, (F.filter (fun e => e ∩ T = S)).card := by  refine Finset.card_eq_sum_card_fiberwise (f := fun e : Finset V => e ∩ T) (s := F)    (t := T.powerset.erase ∅) ?_  intro e he  change e ∩ T ∈ T.powerset.erase ∅  rw [Finset.mem_erase, Finset.mem_powerset]  exact ⟨fun h => hT_trans e he ((Finset.disjoint_iff_inter_eq_empty).mpr h),    Finset.inter_subset_right⟩
See it in the graphDiscuss this resultChallenge it