AFTD Auto-Formalizing Theoretical Domains

condorcet_reversal_tensor_acyclic_half_cover_iff

theoremverified

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
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 2

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.

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

    lines 15–17

      classical
      let V : Fin n → Finset A := fun v => univ.filter fun a => f a ∈ U v
      refine ⟨V, ?_, ?_⟩
  2. 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.

    lines 18–21

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

    lines 22–25

      · intro a
        congr 1
        ext v
        simp [V]
  4. 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`.

    lines 37–38

      classical
      constructor
  5. Given 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}|.

    lines 39–43

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

    lines 44–46

        intro a
        rw [hcount a]
        exact hhalf (a, τ a)
  7. 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}|.

    lines 47–51

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

    lines 52–54

        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

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