AFTD Auto-Formalizing Theoretical Domains

droop_valid_assignment_real_voters_card

theoremverified

For any Droop-valid Monroe assignment π of n voters to committee size k, the number of voters assigned to a real candidate (not none) is exactly n - n / (k + 1).

Statement

theorem droop_valid_assignment_real_voters_card {n m k : ℕ} {W : Finset (Fin m)}
    {π : Fin n → Option (Fin m)} (hv : is_droop_valid_assignment k W π) :
    (Finset.univ.filter fun i => π i ≠ none).card = n - n / (k + 1)
Source
arXiv:2508.00811, Def. 16
Verified
09 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_droop_valid_assignmentA Droop-valid Monroe assignment (arXiv:2508.00811, Def. 16): |W| = k, each voter goes to a member of W or to the dummy (none), each c ∈ W…

Read back from the Lean

For any natural numbers n, m, and k, any subset W : Finset (Fin m), and any function π : Fin n → Option (Fin m): if π is a Droop-valid assignment with parameter k and winning set W (i.e., is_droop_valid_assignment k W π), then the number of elements i : Fin n such that π i ≠ none equals n - n / (k + 1).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof partitions the n voters into those assigned to a real candidate and those assigned to none (dummy voters). By the definition of a Droop-valid assignment, exactly ⌊n / (k + 1)⌋ voters are assigned to none. Subtracting this count from the total population of n voters yields n - ⌊n / (k + 1)⌋ voters assigned to real candidates.

  1. The number of dummy voters (those assigned to none) is n / (k + 1).

    By definition of a Droop-valid Monroe assignment (specifically its fourth condition, accessed via hv.2.2.2), exactly n / (k + 1) voters are assigned to none.

    line 5

      have hdummy : (Finset.univ.filter fun i => π i = none).card = n / (k + 1) := hv.2.2.2
  2. The set of voters assigned to a real candidate is the complement of the dummy voters in the universe of all voters.

    By set extensionality (ext i), a voter i is assigned to a real candidate (π i ≠ none) if and only if i belongs to the universe of voters without being assigned to none. Line 8 simplifies this equivalence to close the subproof.

    lines 6–8

      have h_compl : (Finset.univ.filter fun i => π i ≠ none) = Finset.univ \ (Finset.univ.filter fun i => π i = none) := by
        ext i
        simp
  3. The number of voters assigned to a real candidate equals the total number of voters minus the number of dummy voters, which is n - n / (k + 1).

    Rewriting with h_compl expresses the set of real voters as univ \ {i | π i = none}. Since the dummy voters form a subset of all voters (by Finset.filter_subset), Finset.card_sdiff_of_subset rewrites the cardinality of this difference as the total number of voters minus the number of dummy voters. Finally, simp simplifies the total number of voters in Fin n to n and substitutes the dummy voter count hdummy to obtain n - n / (k + 1).

    lines 9–10

    uses Finset.card_sdiff_of_subset, Finset.filter_subset

      rw [h_compl, Finset.card_sdiff_of_subset (Finset.filter_subset _ _)]
      simp [hdummy]
Finset.card_sdiff_of_subset
For any finite set s that is a subset of a finite set t, the cardinality of the difference t \ s is |t| - |s|.
Finset.filter_subset
The elements of a finite set s satisfying a predicate p form a subset of s.

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

/-- In any Droop-valid Monroe assignment, the number of voters assigned to real candidates is n - ⌊n/(k+1)⌋. -/theorem droop_valid_assignment_real_voters_card {n m k : ℕ} {W : Finset (Fin m)}    {π : Fin n → Option (Fin m)} (hv : is_droop_valid_assignment k W π) :    (Finset.univ.filter fun i => π i ≠ none).card = n - n / (k + 1) := by  have hdummy : (Finset.univ.filter fun i => π i = none).card = n / (k + 1) := hv.2.2.2  have h_compl : (Finset.univ.filter fun i => π i ≠ none) = Finset.univ \ (Finset.univ.filter fun i => π i = none) := by    ext i    simp  rw [h_compl, Finset.card_sdiff_of_subset (Finset.filter_subset _ _)]  simp [hdummy]
See it in the graphDiscuss this resultChallenge it