AFTD Auto-Formalizing Theoretical Domains

outside_voters_subset_top_choices_compl

theoremverified

For any candidate set S and candidate x, any voter who ranks x strictly above every member of S has their top-choice candidate outside S.

Statement

theorem outside_voters_subset_top_choices_compl {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
    (S : Finset (Fin m)) (x : Fin m) (hm : 0 < m) :
    (Finset.univ.filter fun v => ∀ c ∈ S, P v x < P v c) ⊆
      Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S
Source
step towards condorcet_dimension_le_three
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof proceeds by contradiction. Consider any voter v who ranks candidate x strictly above every candidate in S. If v's top-choice candidate (the candidate assigned rank 0) were in S, then x would have to be ranked strictly ahead of this top choice. That would require x to have a numerical rank strictly less than 0, which is impossible for natural numbers.

  1. Consider any voter v who ranks x strictly above every candidate in S; it suffices to derive a contradiction assuming that v's top choice belongs to S.

    We take an arbitrary voter v in the subset. Unfolding the definition of set filtering with `Finset.mem_filter`, voter v satisfies `P v x < P v c` for all `c ∈ S`. To show that v belongs to the target set, it suffices to prove that v's top choice candidate `(P v).symm ⟨0, hm⟩` is not in S; we assume for contradiction that it is in S (`h_top_in_S`).

    lines 6–8

    uses Finset.mem_filter

      intro v hv
      rw [Finset.mem_filter] at hv ⊢
      refine ⟨hv.1, fun h_top_in_S => ?_⟩
  2. Voter v must rank candidate x with a numerical rank strictly less than 0: `P v x < 0`.

    Since voter v's top choice `(P v).symm ⟨0, hm⟩` is assumed to belong to S, we can specialize the assumption that v ranks x strictly above every candidate in S to this top choice. This yields `P v x < P v ((P v).symm ⟨0, hm⟩)`. By `Equiv.apply_symm_apply`, `P v ((P v).symm ⟨0, hm⟩)` simplifies to `⟨0, hm⟩`, so `P v x < 0`.

    lines 9–10

    uses Equiv.apply_symm_apply

      have h_lt := hv.2 ((P v).symm ⟨0, hm⟩) h_top_in_S
      rw [Equiv.apply_symm_apply] at h_lt
  3. A contradiction is reached, completing the proof.

    No natural number is strictly less than 0 (`Nat.not_lt_zero`), which directly contradicts the inequality `P v x < 0`.

    line 11

    uses Nat.not_lt_zero

      exact Nat.not_lt_zero _ h_lt
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Equiv.apply_symm_apply
Applying an equivalence to the image of an element under its inverse returns the original element: `e (e.symm x) = x`.
Nat.not_lt_zero
No natural number is strictly less than zero.

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

/-- Any voter ranking x above every candidate in S must have their top choice outside S. -/theorem outside_voters_subset_top_choices_compl {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))    (S : Finset (Fin m)) (x : Fin m) (hm : 0 < m) :    (Finset.univ.filter fun v => ∀ c ∈ S, P v x < P v c) ⊆      Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S := by  intro v hv  rw [Finset.mem_filter] at hv ⊢  refine ⟨hv.1, fun h_top_in_S => ?_⟩  have h_lt := hv.2 ((P v).symm ⟨0, hm⟩) h_top_in_S  rw [Equiv.apply_symm_apply] at h_lt  exact Nat.not_lt_zero _ h_lt
See it in the graphDiscuss this resultChallenge it