AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_three_iff_oriented_acyclic_weight_separation

theoremverified

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
Used by 1

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.

  1. 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.

    lines 13–21

      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⟩)⟩
  2. 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.

    lines 26–41

    uses exists_subsuperset_card_eq, condorcet_private_stationary_s3, condorcet_private_stationary_tournament.1

      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))
  3. 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.

    lines 56–63

    uses finProdFinEquiv, condorcet_tensor_half_cover_pullback

      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,?_⟩
  4. 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.

    lines 64–70

    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
  5. 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.

    lines 71–82

    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
  6. 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.

    lines 83–85

      · intro a
        rw [hcount a]
        exact hhalf (e.symm a).1
  7. 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.

    lines 97–99

    uses condorcet_dimension_le_three_iff_acyclic_weight_separation.mp

      constructor
      · intro hmain m R _ hR
        exact condorcet_dimension_le_three_iff_acyclic_weight_separation.mp hmain m R hR
  8. 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.

    lines 100–109

    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.

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 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))
See it in the graphDiscuss this resultChallenge it