condorcet_dimension_le_three_iff_oriented_acyclic_weight_separation
The unchanged universal strict three-candidate election conjecture is equivalent to the strict acyclic-weight-separation assertion restricted to ORIENTED finite relations: R(a,b) excludes R(b,a), but completeness is not assumed. The relation must still give an outside common predecessor for every set of at most three vertices. The auxiliary construction lifts any S3 integer acyclic half-cover on m vertices to an oriented S3 half-cover on19*m vertices, preserving the number of voters. Thus reciprocal edges can be eliminated from a hypothetical counterexample; one may focus on arbitrary incomplete oriented S3 relations. No graph-size bound or universal weight construction is supplied.
Statement
theorem condorcet_dimension_le_three_iff_oriented_acyclic_weight_separation : (∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) ↔ (∀ (m : ℕ) (R : Fin m → Fin m → Prop), (∀ a b, R a b → ¬ R b a) → (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) → ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a)
- Source
- IN-362 exact structural reformulation for OP-19. Standard categorical product and homomorphism pullback, using the already Lean-verified19-vertex oriented S3 relation. Background products/fractional colouring: https://www.ub.edu/comb/koljaknauer/Gil_manuscript.pdf . No new election bound, novel research theorem, or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- condorcet_private_triple_stationarity_obstructionThere exist a strict tournament R on19 vertices with a common predecessor for every ordered triple, a chosen three-element set J(a) for…
- condorcet_reversal_tensor_acyclic_half_cover_iffLet R be any directed relation on Fin m, let n be any natural number, and suppose a map tau on Fin m reverses every R-arrow. The relation…
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
- Used by 1
- condorcet_acyclic_half_cover_minimal_oriented_coreAny integer acyclic half-cover of an S3 relation on m vertices yields a half-cover with the same number of voters on k vertices,…
The proof, explained
The theorem shows that the Condorcet dimension conjecture for dimension 3 is equivalent to strict acyclic weight separation restricted to oriented relations (relations with no reciprocal edges). The forward direction is immediate from the known equivalence for arbitrary relations, because oriented relations are a special case. For the reverse direction, Farkas-type duality characterizes the failure of weight separation on a relation R as the existence of an integer acyclic half-cover. Taking the tensor product of R with a fixed 19-vertex tournament that possesses the triple-predecessor property lifts any acyclic half-cover to an oriented relation on 19m vertices while preserving the triple-predecessor property and voter count, showing that counterexamples with reciprocal edges can always be converted into oriented ones.
The coordinatewise product of two relations satisfying the outside triple-predecessor property also satisfies the outside triple-predecessor property.
Let J be a subset of A × B with |J| ≤ 3. The projections of J onto the first and second factors have size at most |J| ≤ 3. By the triple-predecessor hypotheses on R and T, there exist an element a not in the first projection dominating all of its elements under R, and an element b not in the second projection dominating all of its elements under T. Then (a, b) cannot belong to J because a is not in the first projection, and by coordinatewise construction (a, b) dominates every element of J under R × T.
classical intro J hJ obtain ⟨a,ha,haR⟩ := hR (J.image Prod.fst) (card_image_le.trans hJ) obtain ⟨b,hb,hbT⟩ := hT (J.image Prod.snd) (card_image_le.trans hJ) refine ⟨(a,b),?_,?_⟩ · intro hab exact ha (mem_image.mpr ⟨(a,b),hab,rfl⟩) · intro c hc exact ⟨haR c.1 (mem_image.mpr ⟨c,hc,rfl⟩), hbT c.2 (mem_image.mpr ⟨c,hc,rfl⟩)⟩
The auxiliary 19-vertex tournament relation satisfies the outside triple-predecessor property.
Any subset J ⊆ Fin 19 with |J| ≤ 3 extends to a set K of size exactly 3 using exists_subsuperset_card_eq since 3 ≤ 19. For this 3-element set, condorcet_private_stationary_s3 gives a vertex r that dominates every element of K, and thus every element of J. If r were in J, then r would be in K and would dominate itself, contradicting the irreflexivity of this tournament (condorcet_private_stationary_tournament.1). Hence r is an outside common predecessor for J.
uses
exists_subsuperset_card_eq,condorcet_private_stationary_s3,condorcet_private_stationary_tournament.1intro J hJ obtain ⟨K,hJK,_,hK⟩ := exists_subsuperset_card_eq (subset_univ J) hJ (show 3 ≤ (univ : Finset (Fin 19)).card by decide) obtain ⟨a,b,c,_,_,_,hKabc⟩ := card_eq_three.mp hK obtain ⟨r,hra,hrb,hrc⟩ := condorcet_private_stationary_s3 a b c have hr : ∀ x ∈ K, condorcet_private_stationary_relation r x := by intro x hx rw [hKabc] at hx simp only [mem_insert,mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hra · exact hrb · exact hrc refine ⟨r,?_,fun x hx => hr x (hJK hx)⟩ intro hrJ exact condorcet_private_stationary_tournament.1 r (hr r (hJK hrJ))
Construct the tensor product relation Q on Fin (m * 19) and pull back the acyclic half-cover U to a family V on Fin (m * 19).
Identify Fin (m * 19) with Fin m × Fin 19 via the equivalence e = finProdFinEquiv. Define Q to relate two pairs if R relates their first coordinates and the auxiliary 19-vertex tournament relates their second coordinates. Using condorcet_tensor_half_cover_pullback along the first projection, the family U pulls back to a family V on Fin (m * 19). Because Q(a, b) implies R on the first coordinates, well-foundedness of R on each U_v is inherited by Q on V_v, and the number of sets covering each element is preserved.
uses
finProdFinEquiv,condorcet_tensor_half_cover_pullbackclassical let e : Fin m × Fin 19 ≃ Fin (m * 19) := finProdFinEquiv let Q : Fin (m * 19) → Fin (m * 19) → Prop := fun a b => R (e.symm a).1 (e.symm b).1 ∧ condorcet_private_stationary_relation (e.symm a).2 (e.symm b).2 obtain ⟨V,hV,hcount⟩ := condorcet_tensor_half_cover_pullback Q R (fun a => (e.symm a).1) (fun a b hab => hab.1) n U hU refine ⟨Q,V,?_,?_,hV,?_⟩
The relation Q is oriented (asymmetric).
Suppose Q(a, b) and Q(b, a) both hold. Then the second coordinates of a and b are mutually related by condorcet_private_stationary_relation. If the second coordinates are equal, this contradicts irreflexivity (condorcet_private_stationary_tournament.1). If they are distinct, this contradicts tournament asymmetry (condorcet_private_stationary_tournament.2). Thus no reciprocal edges exist.
uses
condorcet_private_stationary_tournament.1,condorcet_private_stationary_tournament.2· intro a b hab hba have habT := hab.2 have hbaT := hba.2 by_cases heq : (e.symm a).2 = (e.symm b).2 · rw [heq] at habT exact condorcet_private_stationary_tournament.1 _ habT · exact (condorcet_private_stationary_tournament.2 _ _ heq).mp habT hbaT
The relation Q satisfies the outside triple-predecessor property.
Given a subset J ⊆ Fin (m * 19) of size at most 3, its preimage e⁻¹(J) in Fin m × Fin 19 has size at most 3. Applying condorcet_triple_predecessor_tensor to R and the auxiliary tournament (which satisfies the triple-predecessor property by condorcet_oriented_tensor_auxiliary_s3) produces an outside common predecessor for e⁻¹(J). Mapping this predecessor forward by e gives an outside common predecessor for J under Q.
uses
condorcet_triple_predecessor_tensor,condorcet_oriented_tensor_auxiliary_s3· intro J hJ obtain ⟨a,ha,haR⟩ := condorcet_triple_predecessor_tensor R condorcet_private_stationary_relation hR condorcet_oriented_tensor_auxiliary_s3 (J.image e.symm) (card_image_le.trans hJ) refine ⟨e a,?_,?_⟩ · intro hea exact ha (mem_image.mpr ⟨e a,hea,e.symm_apply_apply a⟩) · intro b hb have h := haR (e.symm b) (mem_image.mpr ⟨b,hb,rfl⟩) change R (e.symm (e a)).1 (e.symm b).1 ∧ condorcet_private_stationary_relation (e.symm (e a)).2 (e.symm b).2 simpa only [e.symm_apply_apply] using h
The family V is an acyclic half-cover of Fin (m * 19).
By construction, each element a of Fin (m * 19) belongs to exactly as many sets V_v as its first coordinate e⁻¹(a)₁ belongs to sets U_v. Since U covers every vertex of Fin m at least n / 2 times, V covers every vertex of Fin (m * 19) at least n / 2 times.
· intro a rw [hcount a] exact hhalf (e.symm a).1
Condorcet dimension at most 3 implies strict acyclic weight separation for oriented relations.
By condorcet_dimension_le_three_iff_acyclic_weight_separation.mp, the Condorcet dimension conjecture implies acyclic weight separation for all relations satisfying the triple-predecessor property. Since oriented relations are a subclass of all relations, the implication holds immediately.
uses
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpconstructor · intro hmain m R _ hR exact condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hR
Strict acyclic weight separation for oriented relations implies the full Condorcet dimension at most 3 conjecture.
By condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr, it suffices to prove weight separation for an arbitrary relation R on Fin m satisfying the triple-predecessor property. By Farkas-type duality (condorcet_half_cover_acyclic_half_cover_duality), this is equivalent to showing R has no integer acyclic half-cover. If a counterexample half-cover (n, U) existed, condorcet_oriented_tensor_half_cover_lift would lift R and U to an oriented S3 relation Q and an acyclic half-cover V on Fin (m * 19). The hypothesis would then supply separating weights w for Q, which condorcet_half_cover_finite_weighted_half_cover_exclusion proves cannot coexist with an acyclic half-cover V, reaching a contradiction.
uses
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr,condorcet_half_cover_acyclic_half_cover_duality,condorcet_oriented_tensor_half_cover_lift,condorcet_half_cover_finite_weighted_half_cover_exclusion· intro horiented apply condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr intro m R hR apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩ obtain ⟨Q,V,hQasym,hQroot,hV,hVhalf⟩ := condorcet_oriented_tensor_half_cover_lift m n R U hR hU hhalf obtain ⟨w,hw,hsep⟩ := horiented (m * 19) Q hQasym hQroot exact condorcet_half_cover_finite_weighted_half_cover_exclusion (m * 19) n hn V hVhalf w hw (fun v => hsep _ (hV v))
condorcet_triple_predecessor_tensor- If relations R on A and T on B each have the outside common predecessor property for subsets of size at most 3, then their coordinatewise product relation on A × B also does.
exists_subsuperset_card_eq- For any subsets s ⊆ t with |s| ≤ n ≤ |t|, there exists an intermediate subset u with s ⊆ u ⊆ t and |u| = n.
condorcet_private_stationary_s3- For any three vertices in Fin 19, there exists a vertex that dominates all three under the relation condorcet_private_stationary_relation.
condorcet_private_stationary_tournament.1- The relation condorcet_private_stationary_relation is irreflexive: no vertex dominates itself.
condorcet_private_stationary_tournament.2- The relation condorcet_private_stationary_relation is a tournament: for distinct vertices a ≠ b, a dominates b if and only if b does not dominate a.
finProdFinEquiv- The canonical equivalence between the Cartesian product Fin m × Fin n and Fin (m * n).
condorcet_tensor_half_cover_pullback- Given an edge-preserving map from (A, R) to (B, T), any acyclic family on B pulls back to an acyclic family on A preserving vertex coverage counts.
condorcet_oriented_tensor_auxiliary_s3- The relation condorcet_private_stationary_relation on Fin 19 has an outside common predecessor for every subset of size at most 3.
condorcet_dimension_le_three_iff_acyclic_weight_separation.mp- The Condorcet dimension at most 3 conjecture implies acyclic weight separation for all relations satisfying the S3 property.
condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr- Acyclic weight separation for all relations satisfying the S3 property implies the Condorcet dimension at most 3 conjecture.
condorcet_half_cover_acyclic_half_cover_duality- Farkas-type duality: a relation admits a strictly separating weight vector for all acyclic subsets if and only if it admits no integer acyclic half-cover.
condorcet_oriented_tensor_half_cover_lift- Lifts an S3 relation on m vertices equipped with an acyclic half-cover to an oriented S3 relation on 19m vertices with an acyclic half-cover with the same number of voters.
condorcet_half_cover_finite_weighted_half_cover_exclusion- A relation cannot simultaneously admit an acyclic half-cover and a strictly separating nonnegative weight vector for all acyclic subsets.
- The construction relies on a specific 19-vertex tournament (`condorcet_private_stationary_relation`) known to satisfy the S3 property (every 3 vertices have a common predecessor). Taking the tensor product with this tournament eliminates reciprocal edges because an edge in the product requires an edge in both coordinates, and the 19-vertex relation is an asymmetric tournament.
- The theorem is purely qualitative: it shows that any hypothetical counterexample can be converted to an oriented counterexample, but does not provide an explicit size bound on counterexamples or an explicit weight construction.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_triple_predecessor_tensor {A B : Type*} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B] (R : A → A → Prop) (T : B → B → Prop) (hR : ∀ J : Finset A, J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hT : ∀ J : Finset B, J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, T a b) : ∀ J : Finset (A × B), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a.1 b.1 ∧ T a.2 b.2 := by classical intro J hJ obtain ⟨a,ha,haR⟩ := hR (J.image Prod.fst) (card_image_le.trans hJ) obtain ⟨b,hb,hbT⟩ := hT (J.image Prod.snd) (card_image_le.trans hJ) refine ⟨(a,b),?_,?_⟩ · intro hab exact ha (mem_image.mpr ⟨(a,b),hab,rfl⟩) · intro c hc exact ⟨haR c.1 (mem_image.mpr ⟨c,hc,rfl⟩), hbT c.2 (mem_image.mpr ⟨c,hc,rfl⟩)⟩theorem condorcet_oriented_tensor_auxiliary_s3 : ∀ J : Finset (Fin 19), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_private_stationary_relation a b := by intro J hJ obtain ⟨K,hJK,_,hK⟩ := exists_subsuperset_card_eq (subset_univ J) hJ (show 3 ≤ (univ : Finset (Fin 19)).card by decide) obtain ⟨a,b,c,_,_,_,hKabc⟩ := card_eq_three.mp hK obtain ⟨r,hra,hrb,hrc⟩ := condorcet_private_stationary_s3 a b c have hr : ∀ x ∈ K, condorcet_private_stationary_relation r x := by intro x hx rw [hKabc] at hx simp only [mem_insert,mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hra · exact hrb · exact hrc refine ⟨r,?_,fun x hx => hr x (hJK hx)⟩ intro hrJ exact condorcet_private_stationary_tournament.1 r (hr r (hJK hrJ))theorem condorcet_oriented_tensor_half_cover_lift (m n : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (hR : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hU : ∀ v, WellFounded (fun a b : {a : Fin m // a ∈ U v} => R a.val b.val)) (hhalf : ∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card) : ∃ (Q : Fin (m * 19) → Fin (m * 19) → Prop) (V : Fin n → Finset (Fin (m * 19))), (∀ a b, Q a b → ¬ Q b a) ∧ (∀ J : Finset (Fin (m * 19)), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧ (∀ v, WellFounded (fun a b : {a : Fin (m * 19) // a ∈ V v} => Q a.val b.val)) ∧ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card) := by classical let e : Fin m × Fin 19 ≃ Fin (m * 19) := finProdFinEquiv let Q : Fin (m * 19) → Fin (m * 19) → Prop := fun a b => R (e.symm a).1 (e.symm b).1 ∧ condorcet_private_stationary_relation (e.symm a).2 (e.symm b).2 obtain ⟨V,hV,hcount⟩ := condorcet_tensor_half_cover_pullback Q R (fun a => (e.symm a).1) (fun a b hab => hab.1) n U hU refine ⟨Q,V,?_,?_,hV,?_⟩ · intro a b hab hba have habT := hab.2 have hbaT := hba.2 by_cases heq : (e.symm a).2 = (e.symm b).2 · rw [heq] at habT exact condorcet_private_stationary_tournament.1 _ habT · exact (condorcet_private_stationary_tournament.2 _ _ heq).mp habT hbaT · intro J hJ obtain ⟨a,ha,haR⟩ := condorcet_triple_predecessor_tensor R condorcet_private_stationary_relation hR condorcet_oriented_tensor_auxiliary_s3 (J.image e.symm) (card_image_le.trans hJ) refine ⟨e a,?_,?_⟩ · intro hea exact ha (mem_image.mpr ⟨e a,hea,e.symm_apply_apply a⟩) · intro b hb have h := haR (e.symm b) (mem_image.mpr ⟨b,hb,rfl⟩) change R (e.symm (e a)).1 (e.symm b).1 ∧ condorcet_private_stationary_relation (e.symm (e a)).2 (e.symm b).2 simpa only [e.symm_apply_apply] using h · intro a rw [hcount a] exact hhalf (e.symm a).1theorem condorcet_dimension_le_three_iff_oriented_acyclic_weight_separation : (∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) ↔ (∀ (m : ℕ) (R : Fin m → Fin m → Prop), (∀ a b, R a b → ¬ R b a) → (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) → ∃ w : Fin m → ℝ, (∀ a, 0 ≤ w a) ∧ ∀ A : Finset (Fin m), WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val) → 2 * (∑ a ∈ A, w a) < ∑ a, w a) := by constructor · intro hmain m R _ hR exact condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hR · intro horiented apply condorcet_dimension_le_three_iff_acyclic_weight_separation.mpr intro m R hR apply (condorcet_half_cover_acyclic_half_cover_duality m R).mp rintro ⟨n,U,hn,hU,hhalf⟩ obtain ⟨Q,V,hQasym,hQroot,hV,hVhalf⟩ := condorcet_oriented_tensor_half_cover_lift m n R U hR hU hhalf obtain ⟨w,hw,hsep⟩ := horiented (m * 19) Q hQasym hQroot exact condorcet_half_cover_finite_weighted_half_cover_exclusion (m * 19) n hn V hVhalf w hw (fun v => hsep _ (hV v))