condorcet_selector_closed_candidates_global_core
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.
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.
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
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.
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))
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).
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
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).
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⟩))
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.
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
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.
exact ⟨hsize,hmem,fun i hi => mem_image.mpr ⟨i,hmem i hi,rfl⟩⟩
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.
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
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.
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⟩,?_,?_⟩
The index i does not belong to J.
If i ∈ J, then f(i) ∈ f(J) ⊆ S(i), contradicting f(i) ∉ S(i).
· intro hiJ apply hout i rw [hi] exact hJT (mem_image.mpr ⟨i,hiJ,rfl⟩)
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).
· intro j hj rw [hi] exact hJT (mem_image.mpr ⟨j,hj,rfl⟩)
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).
classical obtain ⟨hsize,hmem,hclose⟩ := condorcet_selector_core_root_image S f hcard hout hinj B hBf(B) is the entire candidate universe.
Since |f(B)| ≥ 4 and f(B) is closed, the hypothesis hclosed implies f(B) = univ.
have hall := hclosed (B.image f) hsize hcloseB 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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _