condorcet_acyclic_cut_switch
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
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- Used by 1
- condorcet_integer_acyclic_separator_neighbor_massIf a finite directed relation has a nonnegative integer strict-half separator of its induced acyclic sets, it has such a separator w for…
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`.
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).
uses
condorcet_acyclic_cover_ranking_of_wellFounded,condorcet_acyclic_cover_wellFounded_sourcesclassical 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)
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).
uses
measurelet 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 ?_
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.
uses
mem_union,mem_sdiffintro 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
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).
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
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`.
uses
if_pos,if_negby_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
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.
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.
- Acyclicity on a finite type is formalized as well-foundedness of the binary relation (`WellFounded`), and acyclicity of the switched set is proved by exhibiting a rank function into ℕ that strictly increases along every edge, using `measure`.
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_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