AFTD Auto-Formalizing Theoretical Domains

condorcet_voter_bad_outsiders_eq_min_rank

theoremverified

For a permutation perm of Fin m and a nonempty subset S, the number of candidates outside S ranked strictly above every element of S by perm equals the minimum rank of S under perm.

Statement

theorem condorcet_voter_bad_outsiders_eq_min_rank {m : ℕ} (perm : Equiv.Perm (Fin m))
    (S : Finset (Fin m)) (hS : S.Nonempty) :
    ((Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s)).card =
      (S.image (fun s => (perm s).val)).min' (hS.image _)
Source
step towards condorcet_dimension_le_three_balanced
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

To count candidates outside S ranked strictly above every element of S, we first note that no candidate in S can rank strictly above itself, so the restriction to outside candidates is redundant. Being ranked strictly above every member of S is equivalent to having a rank strictly less than the minimum rank r of S. Since voter preferences are a bijection on Fin m, the number of such candidates equals the number of elements in Fin m strictly less than r, which evaluates to min(m, r) = r because r < m.

  1. Letting `r` be the minimum rank in `S`, the condition that a candidate lies outside `S` is redundant.

    We define `r` to be the minimum rank of any element of `S` under `perm`. Any candidate `a` ranked strictly above every element of `S` cannot belong to `S` itself, since taking `s = a` would imply `perm a < perm a`, contradicting irreflexivity of `<` (`lt_irrefl`). Hence, filtering over `univ \ S` is identical to filtering over all of `univ`.

    lines 6–12

    uses Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and, lt_irrefl

      set r := (S.image (fun s => (perm s).val)).min' (hS.image _) with hr
      have h_filter_sdiff : (Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s) =
          Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) := by
        ext a
        simp only [Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and]
        refine ⟨fun ⟨_, h⟩ => h, fun h => ⟨fun ha => lt_irrefl _ (h a ha), h⟩⟩
      rw [h_filter_sdiff]
  2. Ranking strictly above all elements of `S` is equivalent to having a rank strictly less than `r`.

    By `Finset.lt_min'_iff`, a rank is strictly less than the minimum of a nonempty set if and only if it is strictly less than every rank in that set. Replacing this condition in the filter characterizes the set as all `a : Fin m` with `(perm a).val < r`.

    lines 13–20

    uses Finset.lt_min'_iff, Finset.mem_filter, Finset.mem_univ, true_and

      have h_pred (a : Fin m) : (∀ s ∈ S, perm a < perm s) ↔ (perm a).val < r := by
        rw [hr, Finset.lt_min'_iff]
        simp
      have h_filter_eq : Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) =
          Finset.univ.filter (fun a => (perm a).val < r) := by
        ext a
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, h_pred]
      rw [h_filter_eq]
  3. The number of candidates with rank strictly less than `r` equals the number of indices in `Fin m` strictly less than `r`.

    Because `perm` is a permutation of `Fin m`, its inverse `perm.symm` defines a bijection (embedding) from `{b : Fin m | b.val < r}` to `{a : Fin m | (perm a).val < r}`. By `Finset.card_map`, the two sets have the same cardinality.

    lines 21–28

    uses Finset.card_map

      have h_card_perm : (Finset.univ.filter (fun a => (perm a).val < r)).card =
          (Finset.univ.filter (fun b : Fin m => b.val < r)).card := by
        have h_map : Finset.univ.filter (fun a => (perm a).val < r) =
            (Finset.univ.filter (fun b : Fin m => b.val < r)).map perm.symm.toEmbedding := by
          ext a
          simp
        rw [h_map, Finset.card_map]
      rw [h_card_perm]
  4. The cardinality of `{b : Fin m | b.val < r}` is `r`.

    By `Fin.card_filter_val_lt`, the number of elements in `Fin m` strictly below `r` is `min m r`. Since `S` is nonempty, the minimum rank `r` is attained at some `s ∈ S` (`Finset.min'_mem`, `Finset.mem_image`), and every element of `Fin m` has value strictly less than `m` (`Fin.isLt`), so `r < m`. Thus `min m r = r` (`min_eq_right`, `le_of_lt`), completing the proof.

    lines 29–37

    uses Fin.card_filter_val_lt, Finset.min'_mem, Finset.mem_image, Fin.isLt, min_eq_right, le_of_lt

      rw [Fin.card_filter_val_lt]
      have hr_lt : r < m := by
        rw [hr]
        have hr_mem := Finset.min'_mem (S.image (fun s => (perm s).val)) (hS.image _)
        simp only [Finset.mem_image] at hr_mem
        rcases hr_mem with ⟨s, _, hs⟩
        rw [← hs]
        exact (perm s).isLt
      exact min_eq_right (le_of_lt hr_lt)
Fin.isLt
The underlying natural number of an element in `Fin n` is strictly less than `n`.
Fin.card_filter_val_lt
The number of elements in `Fin n` with numerical value strictly less than `m` is `min n m`.
Finset.card_map
Mapping a finite set along an embedding preserves its cardinality.
Finset.mem_filter
An element belongs to the filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_image
An element belongs to the image of a finset under `f` if and only if it is the image of some element in the finset.
Finset.mem_sdiff
An element belongs to the set difference `s \ t` if and only if it belongs to `s` and does not belong to `t`.
Finset.mem_univ
Every element of a finite type belongs to its universal finset `Finset.univ`.
Finset.lt_min'_iff
An element is strictly less than the minimum of a nonempty finite set if and only if it is strictly less than every element of that set.
Finset.min'_mem
The minimum element of a nonempty finite set belongs to the set.
le_of_lt
If `a < b`, then `a ≤ b`.
lt_irrefl
Strict inequality is irreflexive: `¬ a < a`.
min_eq_right
If `b ≤ a`, then `min a b = b`.
true_and
Conjunction with `True` simplifies to the proposition itself: `(True ∧ p) = p`.

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

/-- For a single voter, the number of outside candidates ranked above all members of S equals the minimum rank of S under that voter's preference permutation. -/theorem condorcet_voter_bad_outsiders_eq_min_rank {m : ℕ} (perm : Equiv.Perm (Fin m))    (S : Finset (Fin m)) (hS : S.Nonempty) :    ((Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s)).card =      (S.image (fun s => (perm s).val)).min' (hS.image _) := by  set r := (S.image (fun s => (perm s).val)).min' (hS.image _) with hr  have h_filter_sdiff : (Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s) =      Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) := by    ext a    simp only [Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and]    refine ⟨fun ⟨_, h⟩ => h, fun h => ⟨fun ha => lt_irrefl _ (h a ha), h⟩⟩  rw [h_filter_sdiff]  have h_pred (a : Fin m) : (∀ s ∈ S, perm a < perm s) ↔ (perm a).val < r := by    rw [hr, Finset.lt_min'_iff]    simp  have h_filter_eq : Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) =      Finset.univ.filter (fun a => (perm a).val < r) := by    ext a    simp only [Finset.mem_filter, Finset.mem_univ, true_and, h_pred]  rw [h_filter_eq]  have h_card_perm : (Finset.univ.filter (fun a => (perm a).val < r)).card =      (Finset.univ.filter (fun b : Fin m => b.val < r)).card := by    have h_map : Finset.univ.filter (fun a => (perm a).val < r) =        (Finset.univ.filter (fun b : Fin m => b.val < r)).map perm.symm.toEmbedding := by      ext a      simp    rw [h_map, Finset.card_map]  rw [h_card_perm]  rw [Fin.card_filter_val_lt]  have hr_lt : r < m := by    rw [hr]    have hr_mem := Finset.min'_mem (S.image (fun s => (perm s).val)) (hS.image _)    simp only [Finset.mem_image] at hr_mem    rcases hr_mem with ⟨s, _, hs⟩    rw [← hs]    exact (perm s).isLt  exact min_eq_right (le_of_lt hr_lt)
See it in the graphDiscuss this resultChallenge it