condorcet_reversal_tensor_acyclic_half_cover_iff
Let 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 on pairs with an arrow from (a,b) to (c,d) exactly when R a c and R d b has an integer acyclic half-cover with n sets if and only if R has such a cover with the same n sets. A half-cover means each vertex belongs to at least half the sets, and every set induces a well-founded relation. No bijectivity of tau, positivity of n, or triple-predecessor property is assumed.
Statement
theorem condorcet_reversal_tensor_acyclic_half_cover_iff (m n : ℕ) (R : Fin m → Fin m → Prop) (τ : Fin m → Fin m) (hτ : ∀ a b, R a b → R (τ b) (τ a)) : (∃ U : Fin n → Finset (Fin m × Fin m), (∀ v, WellFounded (fun a b : {a : Fin m × Fin m // a ∈ U v} => R a.val.1 b.val.1 ∧ R b.val.2 a.val.2)) ∧ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card)) ↔ (∃ V : Fin n → Finset (Fin m), (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val)) ∧ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card))
- Source
- IN-357 structural diagnostic for the OP-19 acyclic-cover route, continuing IN-348 tensor experiment 8741. Categorical products and fractional acyclic colourings are standard, see https://www.ub.edu/comb/koljaknauer/Gil_manuscript.pdf , Sections 1.3 and 7.1. This is the ordinary homomorphism pullback argument; no novelty or research advance is asserted. It rules out a cover-cost improvement from tensoring a relation with its converse when a reversal map exists. Computation 8885 separately audits particular residue tournaments; their numeric maxima are not assumptions of this theorem.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Used by 2
- condorcet_dimension_le_three_iff_oriented_acyclic_weight_separationThe unchanged universal strict three-candidate election conjecture is equivalent to the strict acyclic-weight-separation assertion…
- 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 result is established by first proving a general pullback lemma (condorcet_tensor_half_cover_pullback): pulling back an acyclic cover along any arrow-preserving map yields an acyclic cover with identical vertex coverage counts. For the forward direction, the diagonal embedding a ↦ (a, τ a) preserves arrows because τ reverses R-arrows, pulling the product relation's half-cover back to an acyclic half-cover of Fin m. For the backward direction, the projection (a, b) ↦ a preserves arrows by projecting to the first conjunct, pulling an acyclic half-cover of Fin m back to one for the product relation.
The candidate pullback cover V on A is defined by preimages V v = {a ∈ A | f a ∈ U v}, reducing the pullback lemma to checking well-foundedness and coverage counts.
In classical logic, we define each V v as the filter of elements a ∈ A whose image f a belongs to U v, and provide this family V as the existential witness.
classical let V : Fin n → Finset A := fun v => univ.filter fun a => f a ∈ U v refine ⟨V, ?_, ?_⟩
For each index v, the relation induced by R on the subset V v is well-founded.
Given an index v, the restriction g : V v → U v of f sends elements of V v to U v and preserves arrows (R a b → T (f a) (f b)). Since T is well-founded on U v, the pullback relation under g is well-founded by `InvImage.wf`, and because R on V v is a subrelation of this inverse image relation, it is also well-founded.
uses
InvImage.wf· intro v let g : {a : A // a ∈ V v} → {a : B // a ∈ U v} := fun a => ⟨f a.val, (mem_filter.mp a.property).2⟩ exact (InvImage.wf g (hacyclic v)).mono (fun a b hab => hf a.val b.val hab)
For every vertex a ∈ A, the number of sets V v containing a equals the number of sets U v containing f a.
For each a ∈ A, the index sets {v | a ∈ V v} and {v | f a ∈ U v} are identical by extensionality, since by definition a ∈ V v if and only if f a ∈ U v. Thus their cardinalities are equal.
· intro a congr 1 ext v simp [V]
The equivalence splits into two implications: constructing a cover for R from a cover for the product relation, and conversely.
We work under classical logic and split the bi-implication into forward and backward directions using `constructor`.
classical constructorGiven an acyclic half-cover U for the product relation, pulling it back along a ↦ (a, τ a) yields an acyclic cover V on Fin m with matching coverage counts.
Assume an acyclic half-cover U of size n on Fin m × Fin m. The map a ↦ (a, τ a) preserves arrows because R a b implies R a b and, by the arrow-reversing property of τ, R (τ b) (τ a). Applying `condorcet_tensor_half_cover_pullback` with this map produces a family V of subsets of Fin m such that each V v induces a well-founded relation and |{v | a ∈ V v}| = |{v | (a, τ a) ∈ U v}|.
uses
condorcet_tensor_half_cover_pullback· rintro ⟨U, hU, hhalf⟩ obtain ⟨V, hV, hcount⟩ := condorcet_tensor_half_cover_pullback R (fun a b : Fin m × Fin m => R a.1 b.1 ∧ R b.2 a.2) (fun a => (a, τ a)) (fun a b hab => ⟨hab, hτ a b hab⟩) n U hU refine ⟨V, hV, ?_⟩The pulled-back family V covers every vertex of Fin m at least n/2 times, completing the forward direction.
For each vertex a, rewriting the count #{v | a ∈ V v} to #{v | (a, τ a) ∈ U v} shows that n ≤ 2 * #{v | a ∈ V v} follows immediately from the half-cover property of U evaluated at (a, τ a).
intro a rw [hcount a] exact hhalf (a, τ a)
Given an acyclic half-cover V for R, pulling it back along the first projection Prod.fst yields an acyclic cover U on Fin m × Fin m with matching coverage counts.
Conversely, assume an acyclic half-cover V of size n on Fin m. The first coordinate projection Prod.fst preserves arrows: if (a, b) → (c, d) in the product relation, then R a c ∧ R d b, which implies R a c. Applying `condorcet_tensor_half_cover_pullback` with Prod.fst produces a family U of subsets of Fin m × Fin m such that each U v induces a well-founded relation and |{v | a ∈ U v}| = |{v | a.1 ∈ V v}|.
uses
condorcet_tensor_half_cover_pullback,Prod.fst· rintro ⟨V, hV, hhalf⟩ obtain ⟨U, hU, hcount⟩ := condorcet_tensor_half_cover_pullback (fun a b : Fin m × Fin m => R a.1 b.1 ∧ R b.2 a.2) R Prod.fst (fun a b hab => hab.1) n V hV refine ⟨U, hU, ?_⟩The pulled-back family U covers every vertex of Fin m × Fin m at least n/2 times, completing the backward direction.
For each pair a, rewriting the count #{v | a ∈ U v} to #{v | a.1 ∈ V v} shows that n ≤ 2 * #{v | a ∈ U v} follows immediately from the half-cover property of V evaluated at the first coordinate a.1.
intro a rw [hcount a] exact hhalf a.1
InvImage.wf- If a relation r on β is well-founded, then its inverse image (pullback) under any map f : α → β is also well-founded.
condorcet_tensor_half_cover_pullback- Given an arrow-preserving map f : A → B between finite types with relations R and T, any family of sets in B inducing well-founded relations pulls back along f to a family of sets in A inducing well-founded relations, with identical vertex coverage counts: #{v | a ∈ V v} = #{v | f a ∈ U v}.
Prod.fst- The first projection map from a Cartesian product, sending (a, b) to a.
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_tensor_half_cover_pullback {A B : Type*} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B] (R : A → A → Prop) (T : B → B → Prop) (f : A → B) (hf : ∀ a b, R a b → T (f a) (f b)) (n : ℕ) (U : Fin n → Finset B) (hacyclic : ∀ v, WellFounded (fun a b : {a : B // a ∈ U v} => T a.val b.val)) : ∃ V : Fin n → Finset A, (∀ v, WellFounded (fun a b : {a : A // a ∈ V v} => R a.val b.val)) ∧ (∀ a, (univ.filter fun v => a ∈ V v).card = (univ.filter fun v => f a ∈ U v).card) := by classical let V : Fin n → Finset A := fun v => univ.filter fun a => f a ∈ U v refine ⟨V, ?_, ?_⟩ · intro v let g : {a : A // a ∈ V v} → {a : B // a ∈ U v} := fun a => ⟨f a.val, (mem_filter.mp a.property).2⟩ exact (InvImage.wf g (hacyclic v)).mono (fun a b hab => hf a.val b.val hab) · intro a congr 1 ext v simp [V]theorem condorcet_reversal_tensor_acyclic_half_cover_iff (m n : ℕ) (R : Fin m → Fin m → Prop) (τ : Fin m → Fin m) (hτ : ∀ a b, R a b → R (τ b) (τ a)) : (∃ U : Fin n → Finset (Fin m × Fin m), (∀ v, WellFounded (fun a b : {a : Fin m × Fin m // a ∈ U v} => R a.val.1 b.val.1 ∧ R b.val.2 a.val.2)) ∧ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ U v).card)) ↔ (∃ V : Fin n → Finset (Fin m), (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val)) ∧ (∀ a, n ≤ 2 * (univ.filter fun v => a ∈ V v).card)) := by classical constructor · rintro ⟨U, hU, hhalf⟩ obtain ⟨V, hV, hcount⟩ := condorcet_tensor_half_cover_pullback R (fun a b : Fin m × Fin m => R a.1 b.1 ∧ R b.2 a.2) (fun a => (a, τ a)) (fun a b hab => ⟨hab, hτ a b hab⟩) n U hU refine ⟨V, hV, ?_⟩ intro a rw [hcount a] exact hhalf (a, τ a) · rintro ⟨V, hV, hhalf⟩ obtain ⟨U, hU, hcount⟩ := condorcet_tensor_half_cover_pullback (fun a b : Fin m × Fin m => R a.1 b.1 ∧ R b.2 a.2) R Prod.fst (fun a b hab => hab.1) n V hV refine ⟨U, hU, ?_⟩ intro a rw [hcount a] exact hhalf a.1