AFTD Auto-Formalizing Theoretical Domains

finite_parent_collision_incidence_budget

theoremverified

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
Used by 1

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.

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

    lines 9–11

    uses Finset.card_le_card

      have hc' : ∀ e ∈ S, (C e).card ≤ (P e).card := by
        intro e he
        exact Finset.card_le_card (hc e he)
  2. ∑_{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.

    lines 12–13

    uses oriented_overlap_multiplicity_budget

      have hb := oriented_overlap_multiplicity_budget ι S (fun e => (P e).card)
        (fun e => (C e).card) hm hc' h2
  3. |⋃_{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.

    line 14

    uses Finset.card_biUnion_le

      have hd : (S.biUnion P).card ≤ ∑ e ∈ S, (P e).card := Finset.card_biUnion_le
  4. |⋃_{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).

    line 15

      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

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