condorcet_triple_predecessor_arc_minimal
Every finite relation in which each set of at most three vertices has an outside common predecessor has an irreflexive subrelation retaining that property such that every retained arrow a to b belongs to a private triple at a: there is a set J of exactly three vertices, containing b and excluding a, for which a is the unique outside common predecessor. No bound on the vertex count is asserted.
Statement
theorem condorcet_triple_predecessor_arc_minimal (m : ℕ) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) : ∃ Q : Fin m → Fin m → Prop, (∀ a b, Q a b → R a b) ∧ (∀ a, ¬ Q a a) ∧ (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧ (∀ a b, Q a b → ∃ J : Finset (Fin m), J.card = 3 ∧ b ∈ J ∧ a ∉ J ∧ (∀ c ∈ J, Q a c) ∧ ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a)
- Source
- IN-362 structural helper for OP-19 and condorcet_dimension_le_three_iff_acyclic_weight_separation. Elementary finite arc minimization, no new election bound or research advance.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- 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
We consider the finite family of all irreflexive subrelations of R that retain the property that every set of at most three vertices has an outside common predecessor, and choose a subrelation Q with a minimal number of directed edges. For each retained edge (a, b), minimality ensures that removing (a, b) destroys this property, giving a subset J of at most three vertices with no outside predecessor in Q \ {(a, b)}. Because Q itself satisfies the property, J must have an outside predecessor in Q, which can only be a, forcing b ∈ J and making a the unique outside predecessor of J. Finally, |J| = 3, because if |J| < 3, the set J ∪ {a} would also have an outside predecessor in Q, which would have to equal a, yielding a contradiction.
The set E of all irreflexive edges in R satisfies property P (every set of at most three vertices has an outside common predecessor), so the family of subgraphs satisfying P is non-empty.
We work classically (line 15) and define E as the set of pairs (u, v) such that R(u, v) holds and u ≠ v (line 16). Property P(F) states that every subset J of at most three vertices has an outside common predecessor in F (lines 17–18), and family collects all subgraphs of E satisfying P (line 19). For any J of size at most 3, the hypothesis hroot yields an outside vertex a ∉ J with R(a, b) for all b ∈ J. Since a ∉ J and b ∈ J, we have a ≠ b, so each (a, b) lies in E (lines 20–26). Thus P(E) holds, and E belongs to family (line 27).
uses
mem_univ,subset_reflclassical let E : Finset (Fin m × Fin m) := univ.filter (fun e => R e.1 e.2 ∧ e.1 ≠ e.2) let P : Finset (Fin m × Fin m) → Prop := fun F => ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, (a,b) ∈ F let family := E.powerset.filter P have hE : P E := by intro J hJ obtain ⟨a, ha, hR⟩ := hroot J hJ refine ⟨a, ha, fun b hb => mem_filter.mpr ⟨mem_univ _, hR b hb, ?_⟩⟩ intro hab have hab' : a = b := hab exact ha (hab'.symm ▸ hb) have hEF : E ∈ family := mem_filter.mpr ⟨mem_powerset.mpr (subset_refl E), hE⟩
There exists a cardinality-minimal edge set F in family, defining candidate relation Q.
Because family is a non-empty finite set, it has an element F that minimizes the number of edges |F| (line 28). By definition, F ⊆ E (line 29) and F satisfies P (line 30). We define Q(a, b) by (a, b) ∈ F (line 31), which immediately satisfies the predecessor condition using P(F) (line 32).
obtain ⟨F,hF,hmin⟩ := family.exists_min_image Finset.card ⟨E,hEF⟩ have hsub : F ⊆ E := mem_powerset.mp (mem_filter.mp hF).1 have hP : P F := (mem_filter.mp hF).2 let Q := fun a b => (a,b) ∈ F refine ⟨Q, ?_, ?_, hP, ?_⟩
The relation Q is a subrelation of R and is irreflexive.
If Q(a, b) holds, then (a, b) ∈ F ⊆ E, so R(a, b) holds by definition of E (lines 33–34). Moreover, elements of E satisfy a ≠ b, which precludes Q(a, a) and ensures that Q is irreflexive (lines 35–36).
· intro a b hab exact (mem_filter.mp (hsub hab)).2.1 · intro a haa exact (mem_filter.mp (hsub haa)).2.2 rfl
Removing any edge (a, b) from F yields an edge set that fails property P.
Fix an edge (a, b) ∈ F (line 37). If F \ {(a, b)} satisfied P, it would belong to family (lines 39–41). By minimality of F, we would have |F| ≤ |F \ {(a, b)}| (line 42). But removing an existing edge strictly reduces the cardinality (line 43), giving |F \ {(a, b)}| < |F|, a linear arithmetic contradiction resolved by omega (line 44).
uses
erase_subset,card_erase_lt_of_mem· intro a b hab have hbad : ¬ P (F.erase (a,b)) := by intro h have hmem : F.erase (a,b) ∈ family := mem_filter.mpr ⟨mem_powerset.mpr ((erase_subset _ _).trans hsub), h⟩ have hle := hmin _ hmem have hlt := card_erase_lt_of_mem hab omega
There exists a vertex subset J of size at most 3 with no outside predecessor in F \ {(a, b)}.
Because F \ {(a, b)} fails property P, by contraposition there must be some subset J with |J| ≤ 3 such that no vertex d ∉ J can serve as a common predecessor of J in F \ {(a, b)} (lines 45–52).
have hex : ∃ J : Finset (Fin m), J.card ≤ 3 ∧ ¬ ∃ d, d ∉ J ∧ ∀ c ∈ J, (d,c) ∈ F.erase (a,b) := by by_contra h apply hbad intro J hJ by_contra hno exact h ⟨J,hJ,hno⟩ obtain ⟨J,hJ,hno⟩ := hex
The subset J has an outside predecessor under Q, and a is the unique such predecessor.
Since F satisfies P, there is an outside predecessor d ∉ J in F (line 53). If any outside predecessor d under Q were distinct from a, then for every c ∈ J the pair (d, c) would differ from (a, b) in its first component (lines 59–60), and hence remain in F \ {(a, b)}. That would make d an outside predecessor for J in F \ {(a, b)}, contradicting the choice of J (lines 54–60). Hence any outside predecessor must equal a; in particular d = a, so a ∉ J and Q(a, c) for all c ∈ J (lines 61–62).
uses
congrArg,Prod.fstobtain ⟨d,hd,hdQ⟩ := hP J hJ have hprivate : ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a := by intro d hd hdQ by_contra hda apply hno refine ⟨d, hd, fun c hc => mem_erase.mpr ⟨?_, hdQ c hc⟩⟩ intro heq exact hda (congrArg Prod.fst heq) have hda : d = a := hprivate d hd hdQ subst d
The vertex b belongs to J.
Suppose, for contradiction, that b ∉ J (line 64). Then for every c ∈ J, c ≠ b, so (a, c) differs from (a, b) in the second component (lines 67–69). Thus every edge (a, c) remains in F \ {(a, b)}. Since a ∉ J, a would be an outside predecessor for J in F \ {(a, b)}, contradicting the choice of J (lines 65–66). Hence b ∈ J.
uses
congrArg,Prod.sndhave hbJ : b ∈ J := by by_contra hb apply hno refine ⟨a,hd,fun c hc => mem_erase.mpr ⟨?_,hdQ c hc⟩⟩ intro heq have hcb : c = b := congrArg Prod.snd heq exact hb (hcb ▸ hc)
The subset J has cardinality exactly 3.
Suppose |J| ≠ 3 (lines 70–71). Since |J| ≤ 3, this implies |J| ≤ 2. Because a ∉ J, the set J ∪ {a} has size |J| + 1 ≤ 3 (lines 72–74). By property P for F, there exists an outside predecessor r ∉ J ∪ {a} for J ∪ {a} (line 75). In particular, r ∉ J and r is a predecessor for J. By uniqueness of the outside predecessor of J, we must have r = a (lines 76–78). But then r ∈ J ∪ {a}, contradicting r ∉ J ∪ {a} (lines 79–80). Thus |J| = 3.
uses
card_insert_of_notMem,mem_insert_of_mem,mem_insert_selfhave hthree : J.card = 3 := by by_contra hn have hcard : (insert a J).card ≤ 3 := by rw [card_insert_of_notMem hd] omega obtain ⟨r,hr,hrQ⟩ := hP (insert a J) hcard have hra : r = a := hprivate r (fun h => hr (mem_insert_of_mem h)) (fun c hc => hrQ c (mem_insert_of_mem hc)) subst r exact hr (mem_insert_self _ _)
The subset J witnesses all required properties of a private triple for (a, b).
We combine J with the established facts that |J| = 3, b ∈ J, a ∉ J, Q(a, c) for all c ∈ J, and that a is the unique outside common predecessor of J under Q (line 81).
exact ⟨J,hthree,hbJ,hd,hdQ,hprivate⟩
mem_univ- In any finite type, every element belongs to the universal finite set univ.
subset_refl- Every set is a subset of itself.
erase_subset- Removing an element from a finite set yields a subset of the original set.
card_erase_lt_of_mem- Removing an element that belongs to a finite set strictly decreases its cardinality.
congrArg- Applying a function to equal arguments produces equal results.
Prod.fst- The first projection function of an ordered pair, mapping (x, y) to x.
Prod.snd- The second projection function of an ordered pair, mapping (x, y) to y.
card_insert_of_notMem- Inserting an element into a finite set that does not contain it increases its cardinality by 1.
mem_insert_of_mem- An element belonging to a finite set also belongs to the set obtained by inserting another element.
mem_insert_self- An element always belongs to the set obtained by inserting that element into any finite set.
- The relation is represented as a finite set of directed pairs F ⊆ univ rather than directly as a predicate, allowing the proof to apply cardinality-based finite minimization to select a minimal subrelation.
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_triple_predecessor_arc_minimal (m : ℕ) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) : ∃ Q : Fin m → Fin m → Prop, (∀ a b, Q a b → R a b) ∧ (∀ a, ¬ Q a a) ∧ (∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧ (∀ a b, Q a b → ∃ J : Finset (Fin m), J.card = 3 ∧ b ∈ J ∧ a ∉ J ∧ (∀ c ∈ J, Q a c) ∧ ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a) := by classical let E : Finset (Fin m × Fin m) := univ.filter (fun e => R e.1 e.2 ∧ e.1 ≠ e.2) let P : Finset (Fin m × Fin m) → Prop := fun F => ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, (a,b) ∈ F let family := E.powerset.filter P have hE : P E := by intro J hJ obtain ⟨a, ha, hR⟩ := hroot J hJ refine ⟨a, ha, fun b hb => mem_filter.mpr ⟨mem_univ _, hR b hb, ?_⟩⟩ intro hab have hab' : a = b := hab exact ha (hab'.symm ▸ hb) have hEF : E ∈ family := mem_filter.mpr ⟨mem_powerset.mpr (subset_refl E), hE⟩ obtain ⟨F,hF,hmin⟩ := family.exists_min_image Finset.card ⟨E,hEF⟩ have hsub : F ⊆ E := mem_powerset.mp (mem_filter.mp hF).1 have hP : P F := (mem_filter.mp hF).2 let Q := fun a b => (a,b) ∈ F refine ⟨Q, ?_, ?_, hP, ?_⟩ · intro a b hab exact (mem_filter.mp (hsub hab)).2.1 · intro a haa exact (mem_filter.mp (hsub haa)).2.2 rfl · intro a b hab have hbad : ¬ P (F.erase (a,b)) := by intro h have hmem : F.erase (a,b) ∈ family := mem_filter.mpr ⟨mem_powerset.mpr ((erase_subset _ _).trans hsub), h⟩ have hle := hmin _ hmem have hlt := card_erase_lt_of_mem hab omega have hex : ∃ J : Finset (Fin m), J.card ≤ 3 ∧ ¬ ∃ d, d ∉ J ∧ ∀ c ∈ J, (d,c) ∈ F.erase (a,b) := by by_contra h apply hbad intro J hJ by_contra hno exact h ⟨J,hJ,hno⟩ obtain ⟨J,hJ,hno⟩ := hex obtain ⟨d,hd,hdQ⟩ := hP J hJ have hprivate : ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a := by intro d hd hdQ by_contra hda apply hno refine ⟨d, hd, fun c hc => mem_erase.mpr ⟨?_, hdQ c hc⟩⟩ intro heq exact hda (congrArg Prod.fst heq) have hda : d = a := hprivate d hd hdQ subst d have hbJ : b ∈ J := by by_contra hb apply hno refine ⟨a,hd,fun c hc => mem_erase.mpr ⟨?_,hdQ c hc⟩⟩ intro heq have hcb : c = b := congrArg Prod.snd heq exact hb (hcb ▸ hc) have hthree : J.card = 3 := by by_contra hn have hcard : (insert a J).card ≤ 3 := by rw [card_insert_of_notMem hd] omega obtain ⟨r,hr,hrQ⟩ := hP (insert a J) hcard have hra : r = a := hprivate r (fun h => hr (mem_insert_of_mem h)) (fun c hc => hrQ c (mem_insert_of_mem hc)) subst r exact hr (mem_insert_self _ _) exact ⟨J,hthree,hbJ,hd,hdQ,hprivate⟩