op_639_card_eq_sum_fiber_traces
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
- op_639_card_eq_sum_four_trace_levelsLet 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…
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$.
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\}$.
uses
Finset.card_eq_sum_card_fiberwiserefine Finset.card_eq_sum_card_fiberwise (f := fun e : Finset V => e ∩ T) (s := F) (t := T.powerset.erase ∅) ?_
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$.
uses
Finset.mem_erase,Finset.mem_powersetintro e he change e ∩ T ∈ T.powerset.erase ∅ rw [Finset.mem_erase, Finset.mem_powerset]
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.
uses
Finset.disjoint_iff_inter_eq_empty,Finset.inter_subset_rightexact ⟨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
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.
/-- 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⟩