AFTD Auto-Formalizing Theoretical Domains

condorcet_selector_closed_candidates_global_core

theoremverified

Consider uniquely indexed three-candidate committees S(i), each with an outside root f(i), and the claim relation R(i,j) iff f(j) belongs to S(i). Suppose the only candidate set C of cardinal at least four that is closed under the selector (S(i) subset C implies f(i) in C) is the whole candidate set. Then the only induced claim subset retaining an outside common predecessor for every at-most-three claims is the whole claim graph. The proof extracts the candidate image f(B), proves it has at least four elements, and proves it is closed. Auxiliary lemmas also show that, when every triple is present, every closed candidate set with at least four members induces an S3 claim graph. Thus global core checks can be performed on candidate labels, without enumerating every claim subset.

Statement

theorem condorcet_selector_closed_candidates_global_core
    {A I : Type*} [Fintype A] [Fintype I] [DecidableEq A] [DecidableEq I]
    (S : I → Finset A) (f : I → A)
    (hcard : ∀ i, (S i).card = 3) (hout : ∀ i, f i ∉ S i)
    (hinj : Function.Injective S)
    (hclosed : ∀ C : Finset A, 4 ≤ C.card →
      (∀ i, S i ⊆ C → f i ∈ C) → C = univ)
    (B : Finset I)
    (hB : ∀ J : Finset I, J ⊆ B → J.card ≤ 3 →
      ∃ i ∈ B, i ∉ J ∧ ∀ j ∈ J, f j ∈ S i) : B = univ
Source
IN-362 structural helper for the OP-19 acyclic-cover and optimized private-policy routes. Elementary finite image and closure argument. No new election bound or research advance.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

The proof, explained

To prove that the claim subset B is all of I, the proof first examines the candidate image f(B). An auxiliary lifting lemma shows that any candidate subset T ⊆ f(B) with at most 3 elements is contained in some committee S(i) with i ∈ B; this implies |f(B)| ≥ 4 (otherwise f(i) ∈ S(i)) and that f(B) is closed under the selector. By the uniqueness hypothesis, any closed candidate set of size at least 4 is the entire universe, so f(B) = univ. Finally, because every committee S(i) is contained in univ = f(B), every claim i must belong to B, establishing B = univ.

  1. Any subset of f(B) with at most 3 elements has preimages in B.

    For each element of T ⊆ f(B), by definition of image there is a preimage in B. We use choice to obtain a selection function g.

    lines 12–16

      classical
      have hpre : ∀ a : T, ∃ i, i ∈ B ∧ f i = a.val := by
        intro a
        exact mem_image.mp (hT a.property)
      choose g hg using hpre
  2. The chosen preimages form a subset J ⊆ B of size at most 3.

    The image J of T under g is contained in B and has size |J| ≤ |T| ≤ 3.

    lines 17–23

      let J : Finset I := T.attach.image g
      have hJB : J ⊆ B := by
        intro j hj
        obtain ⟨a,_,rfl⟩ := mem_image.mp hj
        exact (hg a).1
      have hJcard : J.card ≤ 3 := by
        exact (card_image_le.trans (by simpa using hcard))
  3. There is an element i ∈ B whose committee S(i) covers T.

    By the hypothesis hB applied to J, there is some i ∈ B such that f(j) ∈ S(i) for all j ∈ J. Since each element a ∈ T is f(g(a)), it follows that T ⊆ S(i).

    lines 24–28

      obtain ⟨i,hi,_,hdom⟩ := hB J hJB hJcard
      refine ⟨i,hi,?_⟩
      intro a ha
      have hd := hdom (g ⟨a,ha⟩) (mem_image.mpr ⟨⟨a,ha⟩,mem_attach _ _,rfl⟩)
      simpa only [(hg ⟨a,ha⟩).2] using hd
  4. The candidate image f(B) has at least 4 elements.

    If |f(B)| ≤ 3, then lifting f(B) to B yields an index i ∈ B with f(B) ⊆ S(i), which implies f(i) ∈ S(i), contradicting f(i) ∉ S(i).

    lines 40–46

      classical
      have hsize : 4 ≤ (B.image f).card := by
        by_contra h
        have hsmall : (B.image f).card ≤ 3 := by omega
        obtain ⟨i,hi,hsub⟩ := condorcet_selector_core_lift_small_set S f B hB
          (B.image f) (Subset.refl _) hsmall
        exact hout i (hsub (mem_image.mpr ⟨i,hi,rfl⟩))
  5. Any committee contained in f(B) has its index in B.

    If S(i) ⊆ f(B), lifting S(i) yields j ∈ B with S(i) ⊆ S(j). Since both have size 3, S(i) = S(j), so i = j ∈ B by injectivity.

    lines 47–53

      have hmem : ∀ i, S i ⊆ B.image f → i ∈ B := by
        intro i hi
        obtain ⟨j,hj,hsub⟩ := condorcet_selector_core_lift_small_set S f B hB
          (S i) hi (by rw [hcard])
        have heq : S i = S j := eq_of_subset_of_card_le hsub (by rw [hcard,hcard])
        have hij : i = j := hinj heq
        simpa only [hij] using hj
  6. f(B) has size at least 4, detects membership in B, and is closed under the selector.

    Combining the previous two claims with the fact that i ∈ B implies f(i) ∈ f(B) gives all three properties.

    line 54

      exact ⟨hsize,hmem,fun i hi => mem_image.mpr ⟨i,hmem i hi,rfl⟩⟩
  7. For J in the induced claim set, f(J) is contained in C.

    Since every j ∈ J has S(j) ⊆ C, closure of C implies f(j) ∈ C.

    lines 64–69

      classical
      intro J hJ hcard
      have himage : J.image f ⊆ C := by
        intro a ha
        obtain ⟨j,hj,rfl⟩ := mem_image.mp ha
        exact hclosed j (mem_filter.mp (hJ hj)).2
  8. We can extend f(J) to a 3-element committee S(i) contained in C.

    Since |f(J)| ≤ |J| ≤ 3 ≤ |C|, f(J) embeds into a 3-element subset T ⊆ C, which equals S(i) for some i by full coverage.

    lines 70–74

      obtain ⟨T,hJT,hTC,hTcard⟩ := exists_subsuperset_card_eq himage
        (card_image_le.trans hcard) (show 3 ≤ C.card by omega)
      obtain ⟨i,hi⟩ := hfull T hTcard
      have hiC : S i ⊆ C := by simpa only [hi] using hTC
      refine ⟨i,mem_filter.mpr ⟨mem_univ _,hiC⟩,?_,?_⟩
  9. The index i does not belong to J.

    If i ∈ J, then f(i) ∈ f(J) ⊆ S(i), contradicting f(i) ∉ S(i).

    lines 75–78

      · intro hiJ
        apply hout i
        rw [hi]
        exact hJT (mem_image.mpr ⟨i,hiJ,rfl⟩)
  10. The committee S(i) covers f(j) for all j ∈ J.

    By construction f(J) ⊆ S(i), so each f(j) is in S(i).

    lines 79–81

      · intro j hj
        rw [hi]
        exact hJT (mem_image.mpr ⟨j,hj,rfl⟩)
  11. f(B) has size at least 4 and is closed under the selector.

    Applying condorcet_selector_core_root_image to B gives the required size and closure of f(B).

    lines 93–94

      classical
      obtain ⟨hsize,hmem,hclose⟩ := condorcet_selector_core_root_image S f hcard hout hinj B hB
  12. f(B) is the entire candidate universe.

    Since |f(B)| ≥ 4 and f(B) is closed, the hypothesis hclosed implies f(B) = univ.

    line 95

      have hall := hclosed (B.image f) hsize hclose
  13. B is the entire claim universe.

    For any i ∈ I, S(i) ⊆ univ = f(B). Since S(i) ⊆ f(B) implies i ∈ B, every index i belongs to B, so B = univ.

    lines 96–100

      apply eq_univ_of_forall
      intro i
      apply hmem i
      rw [hall]
      exact subset_univ _

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

open Finsetset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_selector_core_lift_small_set    {A I : Type*} [Fintype A] [Fintype I] [DecidableEq A] [DecidableEq I]    (S : I → Finset A) (f : I → A) (B : Finset I)    (hB : ∀ J : Finset I, J ⊆ B → J.card ≤ 3 →      ∃ i ∈ B, i ∉ J ∧ ∀ j ∈ J, f j ∈ S i)    (T : Finset A) (hT : T ⊆ B.image f) (hcard : T.card ≤ 3) :    ∃ i ∈ B, T ⊆ S i := by  classical  have hpre : ∀ a : T, ∃ i, i ∈ B ∧ f i = a.val := by    intro a    exact mem_image.mp (hT a.property)  choose g hg using hpre  let J : Finset I := T.attach.image g  have hJB : J ⊆ B := by    intro j hj    obtain ⟨a,_,rfl⟩ := mem_image.mp hj    exact (hg a).1  have hJcard : J.card ≤ 3 := by    exact (card_image_le.trans (by simpa using hcard))  obtain ⟨i,hi,_,hdom⟩ := hB J hJB hJcard  refine ⟨i,hi,?_⟩  intro a ha  have hd := hdom (g ⟨a,ha⟩) (mem_image.mpr ⟨⟨a,ha⟩,mem_attach _ _,rfl⟩)  simpa only [(hg ⟨a,ha⟩).2] using hdtheorem condorcet_selector_core_root_image    {A I : Type*} [Fintype A] [Fintype I] [DecidableEq A] [DecidableEq I]    (S : I → Finset A) (f : I → A)    (hcard : ∀ i, (S i).card = 3) (hout : ∀ i, f i ∉ S i)    (hinj : Function.Injective S) (B : Finset I)    (hB : ∀ J : Finset I, J ⊆ B → J.card ≤ 3 →      ∃ i ∈ B, i ∉ J ∧ ∀ j ∈ J, f j ∈ S i) :    4 ≤ (B.image f).card ∧    (∀ i, S i ⊆ B.image f → i ∈ B) ∧    (∀ i, S i ⊆ B.image f → f i ∈ B.image f) := by  classical  have hsize : 4 ≤ (B.image f).card := by    by_contra h    have hsmall : (B.image f).card ≤ 3 := by omega    obtain ⟨i,hi,hsub⟩ := condorcet_selector_core_lift_small_set S f B hB      (B.image f) (Subset.refl _) hsmall    exact hout i (hsub (mem_image.mpr ⟨i,hi,rfl⟩))  have hmem : ∀ i, S i ⊆ B.image f → i ∈ B := by    intro i hi    obtain ⟨j,hj,hsub⟩ := condorcet_selector_core_lift_small_set S f B hB      (S i) hi (by rw [hcard])    have heq : S i = S j := eq_of_subset_of_card_le hsub (by rw [hcard,hcard])    have hij : i = j := hinj heq    simpa only [hij] using hj  exact ⟨hsize,hmem,fun i hi => mem_image.mpr ⟨i,hmem i hi,rfl⟩⟩theorem condorcet_selector_closed_candidates_predecessors    {A I : Type*} [Fintype A] [Fintype I] [DecidableEq A] [DecidableEq I]    (S : I → Finset A) (f : I → A) (hout : ∀ i, f i ∉ S i)    (hfull : ∀ T : Finset A, T.card = 3 → ∃ i, S i = T)    (C : Finset A) (hC : 4 ≤ C.card)    (hclosed : ∀ i, S i ⊆ C → f i ∈ C) :    ∀ J : Finset I, J ⊆ univ.filter (fun i => S i ⊆ C) → J.card ≤ 3 →      ∃ i ∈ univ.filter (fun i => S i ⊆ C), i ∉ J ∧ ∀ j ∈ J, f j ∈ S i := by  classical  intro J hJ hcard  have himage : J.image f ⊆ C := by    intro a ha    obtain ⟨j,hj,rfl⟩ := mem_image.mp ha    exact hclosed j (mem_filter.mp (hJ hj)).2  obtain ⟨T,hJT,hTC,hTcard⟩ := exists_subsuperset_card_eq himage    (card_image_le.trans hcard) (show 3 ≤ C.card by omega)  obtain ⟨i,hi⟩ := hfull T hTcard  have hiC : S i ⊆ C := by simpa only [hi] using hTC  refine ⟨i,mem_filter.mpr ⟨mem_univ _,hiC⟩,?_,?_⟩  · intro hiJ    apply hout i    rw [hi]    exact hJT (mem_image.mpr ⟨i,hiJ,rfl⟩)  · intro j hj    rw [hi]    exact hJT (mem_image.mpr ⟨j,hj,rfl⟩)theorem condorcet_selector_closed_candidates_global_core    {A I : Type*} [Fintype A] [Fintype I] [DecidableEq A] [DecidableEq I]    (S : I → Finset A) (f : I → A)    (hcard : ∀ i, (S i).card = 3) (hout : ∀ i, f i ∉ S i)    (hinj : Function.Injective S)    (hclosed : ∀ C : Finset A, 4 ≤ C.card →      (∀ i, S i ⊆ C → f i ∈ C) → C = univ)    (B : Finset I)    (hB : ∀ J : Finset I, J ⊆ B → J.card ≤ 3 →      ∃ i ∈ B, i ∉ J ∧ ∀ j ∈ J, f j ∈ S i) : B = univ := by  classical  obtain ⟨hsize,hmem,hclose⟩ := condorcet_selector_core_root_image S f hcard hout hinj B hB  have hall := hclosed (B.image f) hsize hclose  apply eq_univ_of_forall  intro i  apply hmem i  rw [hall]  exact subset_univ _
See it in the graphDiscuss this resultChallenge it