finite_parent_collision_incidence_budget
For finite repeated-pair parent sets and charge sets contained in them, if a two-parent pair receives at most one charge, the number of parents in their union plus the total number of charges is at most three times their total excess multiplicity.
Statement
theorem finite_parent_collision_incidence_budget (ι α : Type) [DecidableEq ι] [DecidableEq α] (S : Finset ι) (P C : ι → Finset α) (hm : ∀ e ∈ S, 2 ≤ (P e).card) (hc : ∀ e ∈ S, C e ⊆ P e) (h2 : ∀ e ∈ S, (P e).card = 2 → (C e).card ≤ 1) : (S.biUnion P).card + (∑ e ∈ S, (C e).card) ≤ 3 * ∑ e ∈ S, ((P e).card - 1)
- Source
- Finite collision-charge assembly for the OP-110 small-overlap route.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- oriented_overlap_multiplicity_budgetSummed multiplicities and charges cost at most three times overlap when multiplicity-two edges have at most one charge.
- Used by 1
- finite_parent_collision_budget_with_coverUnder the same repeated-pair parent and charge assumptions, any dirty set covered by the parent sets and any missing set no larger than…
The proof, explained
The theorem bounds the cardinality of the union of parent sets plus the total charge by reducing to the numerical budget lemma `oriented_overlap_multiplicity_budget`. First, the set inclusion C(e) ⊆ P(e) implies |C(e)| ≤ |P(e)|, fulfilling the prerequisites of the budget lemma with multiplicities |P(e)| and charges |C(e)|. Next, subadditivity of cardinality bounds |⋃_{e ∈ S} P(e)| by ∑_{e ∈ S} |P(e)|. Linear arithmetic then combines the budget inequality and the union bound to yield the desired result.
For every e ∈ S, |C(e)| ≤ |P(e)|.
Since each charge set C(e) is a subset of the corresponding parent set P(e) by hypothesis hc, the cardinality of C(e) cannot exceed the cardinality of P(e) by monotonicity of finite set cardinality (Finset.card_le_card).
uses
Finset.card_le_cardhave hc' : ∀ e ∈ S, (C e).card ≤ (P e).card := by intro e he exact Finset.card_le_card (hc e he)
∑_{e ∈ S} |P(e)| + ∑_{e ∈ S} |C(e)| ≤ 3 * ∑_{e ∈ S} (|P(e)| - 1).
We apply the numerical multiplicity budget lemma oriented_overlap_multiplicity_budget with multiplicity function e ↦ |P(e)| and charge function e ↦ |C(e)|. Its requirements that |P(e)| ≥ 2, |C(e)| ≤ |P(e)|, and |P(e)| = 2 → |C(e)| ≤ 1 for all e ∈ S are provided by hm, the cardinality bound hc' just established, and h2, respectively.
uses
oriented_overlap_multiplicity_budgethave hb := oriented_overlap_multiplicity_budget ι S (fun e => (P e).card) (fun e => (C e).card) hm hc' h2
|⋃_{e ∈ S} P(e)| ≤ ∑_{e ∈ S} |P(e)|.
By the union bound for finite sets (Finset.card_biUnion_le), the cardinality of the union of the parent sets is at most the sum of their individual sizes.
uses
Finset.card_biUnion_lehave hd : (S.biUnion P).card ≤ ∑ e ∈ S, (P e).card := Finset.card_biUnion_le|⋃_{e ∈ S} P(e)| + ∑_{e ∈ S} |C(e)| ≤ 3 * ∑_{e ∈ S} (|P(e)| - 1).
Linear arithmetic (omega) closes the goal by combining the union bound |⋃_{e ∈ S} P(e)| ≤ ∑_{e ∈ S} |P(e)| with the multiplicity budget inequality ∑_{e ∈ S} |P(e)| + ∑_{e ∈ S} |C(e)| ≤ 3 * ∑_{e ∈ S} (|P(e)| - 1).
omega
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.card_biUnion_le- The cardinality of a union of finite sets indexed by a finite set S is at most the sum of the cardinalities of the individual sets: |⋃_{e ∈ S} P(e)| ≤ ∑_{e ∈ S} |P(e)|.
oriented_overlap_multiplicity_budget- For functions m, c : ι → ℕ on a finite set S satisfying 2 ≤ m(e), c(e) ≤ m(e), and m(e) = 2 → c(e) ≤ 1 for all e ∈ S, the sum of multiplicities plus charges satisfies ∑_{e ∈ S} m(e) + ∑_{e ∈ S} c(e) ≤ 3 * ∑_{e ∈ S} (m(e) - 1).
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 finite_parent_collision_incidence_budget (ι α : Type) [DecidableEq ι] [DecidableEq α] (S : Finset ι) (P C : ι → Finset α) (hm : ∀ e ∈ S, 2 ≤ (P e).card) (hc : ∀ e ∈ S, C e ⊆ P e) (h2 : ∀ e ∈ S, (P e).card = 2 → (C e).card ≤ 1) : (S.biUnion P).card + (∑ e ∈ S, (C e).card) ≤ 3 * ∑ e ∈ S, ((P e).card - 1) := by have hc' : ∀ e ∈ S, (C e).card ≤ (P e).card := by intro e he exact Finset.card_le_card (hc e he) have hb := oriented_overlap_multiplicity_budget ι S (fun e => (P e).card) (fun e => (C e).card) hm hc' h2 have hd : (S.biUnion P).card ≤ ∑ e ∈ S, (P e).card := Finset.card_biUnion_le omega