AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_cut_switch

theoremverified

For a finite directed relation, let S and N be vertex sets such that every arrow from S ends in N. For every induced acyclic set A, the set (S minus N) union (A minus the symmetric difference of S and N) is also induced acyclic. No S3 or looplessness hypothesis is needed.

Statement

theorem condorcet_acyclic_cut_switch
    (m : ℕ) (R : Fin m → Fin m → Prop)
    (S N A : Finset (Fin m))
    (hN : ∀ a b, a ∈ S → R a b → b ∈ N)
    (hA : WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) :
    WellFounded (fun a b : {a : Fin m //
      a ∈ (S \ N) ∪ (A \ ((S \ N) ∪ (N \ S)))} => R a.val b.val)
Source
IN-380, OP-19 campaign session 8, 2026-10-30. Self-contained helper for the strict-half acyclic-separation route. The general unrestricted one-child equality was refuted in IN-372; this work repairs only the strict-half existence reduction. Standard finite matching, rational density, and circulation weak duality are used. No new election bound or research novelty is claimed. See lean/AFTD/Scratch/In380Oct30/HalfThresholdDerivation.txt.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof demonstrates that the switched set is acyclic by constructing a ranking function into ℕ that strictly increases along every directed edge in the set. First, the acyclicity of A is extended to a global topological sorting σ for all edges originating in A. Vertices in the switched set are then assigned to three tiers: vertices outside S (rank σ(a) < m), vertices in S \ N (rank m), and vertices in S ∩ N (rank 2m + σ(a)). Because all edges leaving S must enter N by hypothesis, any edge from S must land in S ∩ N (tier 3), while edges originating outside S either cross to a higher tier or stay in tier 1 where σ strictly increases. In every case the rank strictly increases, establishing well-foundedness via `measure`.

  1. There exists a permutation σ of Fin m that strictly increases along every edge whose source lies in A.

    Since the induced relation on A is well-founded (hA), the relation on Fin m consisting only of edges originating in A is also well-founded by `condorcet_acyclic_cover_wellFounded_sources`. Applying `condorcet_acyclic_cover_ranking_of_wellFounded`, this acyclic relation embeds into a linear order given by a permutation σ, meaning that whenever a ∈ A and R a b, σ(a) < σ(b).

    lines 13–16

    uses condorcet_acyclic_cover_ranking_of_wellFounded, condorcet_acyclic_cover_wellFounded_sources

      classical
      obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m
        (fun a b => a ∈ A ∧ R a b)
        (condorcet_acyclic_cover_wellFounded_sources R {a | a ∈ A} hA)
  2. To prove well-foundedness on the switched set, it suffices to define a rank function into ℕ and show that it strictly increases along every directed edge.

    We partition the vertices into three tiers via `rank`: vertices outside S receive rank σ(a) < m; vertices in S \ N receive rank m; and vertices in S ∩ N receive rank 2m + σ(a). By `measure`, pulling back the well-founded order on ℕ gives a well-founded relation on the switched set, so by monotonicity (`wf.mono`) it suffices to show that R a b implies rank(a) < rank(b).

    lines 17–20

    uses measure

      let rank : Fin m → ℕ := fun a =>
        if a ∈ S then (if a ∈ N then 2*m + (σ a).val else m) else (σ a).val
      refine (measure (fun a : {a : Fin m //
        a ∈ (S \ N) ∪ (A \ ((S \ N) ∪ (N \ S)))} => rank a.val)).wf.mono ?_
  3. Any vertex in the switched set satisfies: if it is outside S, it is outside N and belongs to A; and if it is in both S and N, it belongs to A.

    We introduce an arbitrary edge a → b between vertices in the switched set (S \ N) ∪ (A \ (S Δ N)). Unfolding the definition of set difference and union (`mem_sdiff`, `mem_union`), propositional reasoning (`tauto`) confirms that elements of this set outside S cannot belong to N \ S and thus must belong to A without N, while elements in S ∩ N cannot belong to S \ N and thus must also come from A. We record these membership properties ha and hb for a and b.

    lines 21–27

    uses mem_union, mem_sdiff

      intro a b hab
      have hmem (x : Fin m) (hx : x ∈ (S \ N) ∪ (A \ ((S \ N) ∪ (N \ S)))) :
          (x ∉ S → x ∉ N ∧ x ∈ A) ∧ (x ∈ S → x ∈ N → x ∈ A) := by
        simp only [mem_union,mem_sdiff] at hx
        tauto
      have ha := hmem a.val a.property
      have hb := hmem b.val b.property
  4. Whenever a vertex lies in A, σ strictly increases along the edge, and the remaining goal is to prove rank(a) < rank(b).

    From the defining property of σ, if a ∈ A then σ(a) < σ(b). In addition, since σ(a) ∈ Fin m, its value is bounded by m. We then rephrase the goal as showing rank(a) < rank(b).

    lines 28–31

      have hσa : a.val ∈ A → (σ a.val).val < (σ b.val).val :=
        fun haA => hσ a.val b.val ⟨haA,hab⟩
      have hσlt := (σ a.val).isLt
      change rank a.val < rank b.val
  5. If a ∈ S, then b ∈ S ∩ N and rank(a) < rank(b).

    We split on whether a ∈ S. Since a ∈ S and R a b, the cut hypothesis hN forces b ∈ N. By contradiction, b must also belong to S, because if b ∉ S, the membership property for b would imply b ∉ N. Thus b ∈ S ∩ N, placing b in tier 3 with rank(b) = 2m + σ(b). We then subcase on whether a ∈ N: if a ∈ N, then a ∈ S ∩ N, so a ∈ A by ha, which gives σ(a) < σ(b) and thus 2m + σ(a) < 2m + σ(b); if a ∉ N, then a ∈ S \ N (tier 2), so rank(a) = m < 2m ≤ rank(b). In each subcase, rewriting `rank` with `if_pos` and `if_neg` reduces the inequality to linear arithmetic closed by `omega`.

    lines 32–42

    uses if_pos, if_neg

      by_cases haS : a.val ∈ S
      · have hbN := hN a.val b.val haS hab
        have hbS : b.val ∈ S := by
          by_contra hbS
          exact (hb.1 hbS).1 hbN
        by_cases haN : a.val ∈ N
        · have hlt := hσa (ha.2 haS haN)
          simp only [rank,if_pos haS,if_pos hbS,if_pos haN,if_pos hbN]
          omega
        · simp only [rank,if_pos haS,if_pos hbS,if_neg haN,if_pos hbN]
          omega
  6. If a ∉ S, then a ∈ A and rank(a) < rank(b).

    When a ∉ S, the membership property ha implies a ∈ A, which guarantees σ(a) < σ(b). Here a is in tier 1, so rank(a) = σ(a) < m. We then split on whether b ∈ S: if b ∈ S, then b is in tier 2 or 3, so rank(b) ≥ m > rank(a), which `simp` and `omega` settle; if b ∉ S, then b is also in tier 1, so rank(a) < rank(b) simplifies via `if_neg` to σ(a) < σ(b), which was already established.

    lines 43–46

    uses if_neg

      · have hlt := hσa (ha.1 haS).2
        by_cases hbS : b.val ∈ S
        · by_cases hbN : b.val ∈ N <;> simp [rank,haS,hbS,hbN] <;> omega
        · simpa only [rank,if_neg haS,if_neg hbS] using hlt
condorcet_acyclic_cover_ranking_of_wellFounded
Any well-founded relation on a finite set Fin m embeds into a linear ranking (a permutation σ) such that R a b implies σ a < σ b.
condorcet_acyclic_cover_wellFounded_sources
If a relation is well-founded when restricted to a subset, then the relation keeping only edges whose source lies in that subset is well-founded on the whole domain.
measure
Constructs a well-founded relation on a type by pulling back the standard strict order on ℕ along a given function.
mem_union
An element belongs to the union of two finite sets if and only if it belongs to the first or to the second.
mem_sdiff
An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
if_pos
Simplifies an if-then-else expression to its 'then' branch when the condition is true.
if_neg
Simplifies an if-then-else expression to its 'else' branch when the condition is false.

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_acyclic_cut_switch    (m : ℕ) (R : Fin m → Fin m → Prop)    (S N A : Finset (Fin m))    (hN : ∀ a b, a ∈ S → R a b → b ∈ N)    (hA : WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) :    WellFounded (fun a b : {a : Fin m //      a ∈ (S \ N) ∪ (A \ ((S \ N) ∪ (N \ S)))} => R a.val b.val) := by  classical  obtain ⟨σ,hσ⟩ := condorcet_acyclic_cover_ranking_of_wellFounded m    (fun a b => a ∈ A ∧ R a b)    (condorcet_acyclic_cover_wellFounded_sources R {a | a ∈ A} hA)  let rank : Fin m → ℕ := fun a =>    if a ∈ S then (if a ∈ N then 2*m + (σ a).val else m) else (σ a).val  refine (measure (fun a : {a : Fin m //    a ∈ (S \ N) ∪ (A \ ((S \ N) ∪ (N \ S)))} => rank a.val)).wf.mono ?_  intro a b hab  have hmem (x : Fin m) (hx : x ∈ (S \ N) ∪ (A \ ((S \ N) ∪ (N \ S)))) :      (x ∉ S → x ∉ N ∧ x ∈ A) ∧ (x ∈ S → x ∈ N → x ∈ A) := by    simp only [mem_union,mem_sdiff] at hx    tauto  have ha := hmem a.val a.property  have hb := hmem b.val b.property  have hσa : a.val ∈ A → (σ a.val).val < (σ b.val).val :=    fun haA => hσ a.val b.val ⟨haA,hab⟩  have hσlt := (σ a.val).isLt  change rank a.val < rank b.val  by_cases haS : a.val ∈ S  · have hbN := hN a.val b.val haS hab    have hbS : b.val ∈ S := by      by_contra hbS      exact (hb.1 hbS).1 hbN    by_cases haN : a.val ∈ N    · have hlt := hσa (ha.2 haS haN)      simp only [rank,if_pos haS,if_pos hbS,if_pos haN,if_pos hbN]      omega    · simp only [rank,if_pos haS,if_pos hbS,if_neg haN,if_pos hbN]      omega  · have hlt := hσa (ha.1 haS).2    by_cases hbS : b.val ∈ S    · by_cases hbN : b.val ∈ N <;> simp [rank,haS,hbS,hbN] <;> omega    · simpa only [rank,if_neg haS,if_neg hbS] using hlt
See it in the graphDiscuss this resultChallenge it