condorcet_minimal_predecessor_acyclic_cut
For k positive, a finite relation globally minimal under induced restriction among relations with the outside common predecessor property for sets of at most k vertices has an undominated set of exactly k+1 vertices crossing every nonempty induced acyclic subset.
Statement
theorem condorcet_minimal_predecessor_acyclic_cut (m k : ℕ) (hk : 0 < k) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ k → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hminimal : ∀ S : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ S → J.card ≤ k → ∃ a ∈ S, a ∉ J ∧ ∀ b ∈ J, R a b) → S = univ) (A : Finset (Fin m)) (hAne : A.Nonempty) (hA : WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) : ∃ T : Finset (Fin m), T.card = k+1 ∧ (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) ∧ (∃ a ∈ T, a ∈ A) ∧ (∃ b ∈ T, b ∉ A)
- Source
- IN-383, OP-19 campaign session 9, 2026-10-30. Structural analysis of the S2-to-S3 completion route from IN-362; finite diagnostics audited in experiments9630 and9640. Supports the general campaign only; no new election bound or research novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- condorcet_minimal_predecessor_completion_integer_certificateFor a globally minimal S_k core and a nonempty uniform family F containing every undominated (k+1)-set, the incidence weights Z*d(a) on…
- condorcet_minimal_predecessor_coalition_completion_exclusionSuch a globally minimal predecessor core cannot have an acyclic half-cover if every undominated (k+1)-set has an additional event of at…
The proof, explained
The theorem is proved by constructing an explicit witness set T = {c} ∪ J of size k + 1. First, well-foundedness of R on A yields an R-minimal source vertex c ∈ A with no predecessor in A. Next, because the complement C = univ \ A is a proper subset of the universe, the global minimality hypothesis implies that C fails the outside predecessor property, providing a subset J ⊆ C of size at most k with no common predecessor in C \ J. Defining T = {c} ∪ J, no vertex in the universe can precede all of T: a candidate predecessor in A would contradict the minimality of c, while one in C would contradict the choice of J. Finally, T must have size k + 1 (otherwise it would have an outside predecessor by the global root property), and T crosses the cut between A and its complement via c ∈ A and the nonemptiness of J ⊆ univ \ A.
There exists an element c ∈ A with no predecessor in A under R.
Since A is nonempty, we select an element a ∈ A. Well-foundedness of R on the subtype A ensures that the set of all elements in A has an R-minimal element c (using `Set.mem_univ`). By minimality, no element b ∈ A satisfies R b c.val (`hsource`).
uses
Set.mem_univclassical obtain ⟨a,ha⟩ := hAne obtain ⟨c,_,hc⟩ := hA.has_min Set.univ ⟨⟨a,ha⟩,Set.mem_univ _⟩ have hsource : ∀ b ∈ A, ¬ R b c.val := fun b hb hbc => hc ⟨b,hb⟩ (Set.mem_univ _) hbc
The complement C = univ \ A is a proper subset of the universe.
If C were the whole universe, then c.val would belong to C by `mem_univ`. But by definition of C via `mem_sdiff`, elements of C do not belong to A, contradicting c ∈ A.
uses
mem_univ,mem_sdifflet C := univ \ A have hproper : C ≠ univ := by intro heq have hm : c.val ∈ C := by rw [heq]; exact mem_univ _ exact (mem_sdiff.mp hm).2 c.property
There exists a subset J ⊆ C of size at most k that has no common outside predecessor in C, and c.val ∉ J.
By the global minimality hypothesis `hminimal`, any subset satisfying the outside common predecessor property for subsets of size at most k must be the whole universe. Since C ≠ univ, C fails this property. Negating the condition yields a subset J ⊆ C with |J| ≤ k such that every candidate predecessor a ∈ C \ J fails to dominate some vertex in J. Since J ⊆ C and c.val ∈ A, c.val ∉ J by `mem_sdiff`.
uses
mem_sdiffhave hnot : ¬(∀ J : Finset (Fin m), J ⊆ C → J.card ≤ k → ∃ a ∈ C, a ∉ J ∧ ∀ b ∈ J, R a b) := fun h => hproper (hminimal C h) push_neg at hnot obtain ⟨J,hJC,hJcard,hJbad⟩ := hnot have hcJ : c.val ∉ J := fun h => (mem_sdiff.mp (hJC h)).2 c.property
Defining T = {c.val} ∪ J, the cardinality of T is at most k + 1.
Inserting c.val into J increases cardinality by at most 1 by `card_insert_le`. Since |J| ≤ k, `Nat.add_le_add_right` gives |T| ≤ k + 1.
uses
card_insert_le,Nat.add_le_add_rightlet T := insert c.val J have hTle : T.card ≤ k+1 := (card_insert_le _ _).trans (Nat.add_le_add_right hJcard 1)
T has no common outside predecessor in the entire universe.
Suppose for contradiction that some d ∉ T precedes every vertex in T. We case split on whether d ∈ A: if d ∈ A, then since c.val ∈ T (by `mem_insert_self`), we have R d c.val, contradicting that c has no predecessor in A (`hsource`). If d ∉ A, then d ∈ C by `mem_sdiff` and d ∉ J by `mem_insert_of_mem`. But J has no common predecessor in C \ J, so there exists b ∈ J such that ¬ R d b, which contradicts that d precedes all vertices in T (using `mem_insert_of_mem`).
uses
mem_insert_self,mem_sdiff,mem_insert_of_memhave hTbad : ¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b := by rintro ⟨d,hd,hdR⟩ by_cases hdA : d ∈ A · exact hsource d hdA (hdR c.val (mem_insert_self _ _)) · have hdC : d ∈ C := mem_sdiff.mpr ⟨mem_univ _,hdA⟩ have hdJ : d ∉ J := fun h => hd (mem_insert_of_mem h) obtain ⟨b,hb,hnb⟩ := hJbad d hdC hdJ exact hnb (hdR b (mem_insert_of_mem hb))
The cardinality of T is exactly k + 1.
If |T| ≤ k, the hypothesis `hroot` would supply an outside common predecessor for T, contradicting that T has none. Since |T| ≤ k + 1 and ¬(|T| ≤ k), Presburger arithmetic (`omega`) implies |T| = k + 1.
have hTcard : T.card = k+1 := by have hnotle : ¬ T.card ≤ k := fun h => hTbad (hroot T h) omega
The subset J is nonempty, so it contains at least one vertex b.
Since c.val ∉ J, `card_insert_of_notMem` gives |T| = |J| + 1. Given |T| = k + 1 and k > 0, linear arithmetic (`omega`) shows 0 < |J|. By `card_pos`, J is nonempty, so we choose an element b ∈ J.
uses
card_insert_of_notMem,card_poshave hJpos : 0 < J.card := by have hcount : T.card = J.card+1 := card_insert_of_notMem hcJ omega obtain ⟨b,hb⟩ := card_pos.mp hJpos
T satisfies all required properties: |T| = k + 1, T has no outside predecessor, T intersects A, and T intersects univ \ A.
We supply T as the witness: its size is k + 1, it has no outside predecessor, c.val ∈ T ∩ A (using `mem_insert_self`), and b ∈ T \ A because b ∈ J ⊆ C (using `mem_insert_of_mem` and `mem_sdiff`).
uses
mem_insert_self,mem_insert_of_mem,mem_sdiffexact ⟨T,hTcard,hTbad,⟨c.val,mem_insert_self _ _,c.property⟩, ⟨b,mem_insert_of_mem hb,(mem_sdiff.mp (hJC hb)).2⟩⟩
Set.mem_univ- Every element of a type belongs to the universal set `Set.univ`.
mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
mem_sdiff- An element belongs to the difference of two sets `s \ t` if and only if it belongs to `s` and does not belong to `t`.
card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Nat.add_le_add_right- Adding a natural number to both sides of an inequality preserves the inequality.
mem_insert_self- An element always belongs to the set obtained by inserting itself into a set.
mem_insert_of_mem- If an element belongs to a set, it also belongs to the set with an element inserted.
card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by exactly 1.
card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
- The well-foundedness hypothesis `hA` is formalized on the subtype `{a : Fin m // a ∈ A}` rather than via an indicator on `Fin m`, so the minimal element `c` is a subtype term whose underlying vertex is `c.val`.
- Steps 6 and 7 invoke `omega` to handle elementary Presburger arithmetic on cardinalities.
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 30000000set_option maxRecDepth 20000theorem condorcet_minimal_predecessor_acyclic_cut (m k : ℕ) (hk : 0 < k) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ k → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) (hminimal : ∀ S : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ S → J.card ≤ k → ∃ a ∈ S, a ∉ J ∧ ∀ b ∈ J, R a b) → S = univ) (A : Finset (Fin m)) (hAne : A.Nonempty) (hA : WellFounded (fun a b : {a : Fin m // a ∈ A} => R a.val b.val)) : ∃ T : Finset (Fin m), T.card = k+1 ∧ (¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b) ∧ (∃ a ∈ T, a ∈ A) ∧ (∃ b ∈ T, b ∉ A) := by classical obtain ⟨a,ha⟩ := hAne obtain ⟨c,_,hc⟩ := hA.has_min Set.univ ⟨⟨a,ha⟩,Set.mem_univ _⟩ have hsource : ∀ b ∈ A, ¬ R b c.val := fun b hb hbc => hc ⟨b,hb⟩ (Set.mem_univ _) hbc let C := univ \ A have hproper : C ≠ univ := by intro heq have hm : c.val ∈ C := by rw [heq]; exact mem_univ _ exact (mem_sdiff.mp hm).2 c.property have hnot : ¬(∀ J : Finset (Fin m), J ⊆ C → J.card ≤ k → ∃ a ∈ C, a ∉ J ∧ ∀ b ∈ J, R a b) := fun h => hproper (hminimal C h) push_neg at hnot obtain ⟨J,hJC,hJcard,hJbad⟩ := hnot have hcJ : c.val ∉ J := fun h => (mem_sdiff.mp (hJC h)).2 c.property let T := insert c.val J have hTle : T.card ≤ k+1 := (card_insert_le _ _).trans (Nat.add_le_add_right hJcard 1) have hTbad : ¬∃ a, a ∉ T ∧ ∀ b ∈ T, R a b := by rintro ⟨d,hd,hdR⟩ by_cases hdA : d ∈ A · exact hsource d hdA (hdR c.val (mem_insert_self _ _)) · have hdC : d ∈ C := mem_sdiff.mpr ⟨mem_univ _,hdA⟩ have hdJ : d ∉ J := fun h => hd (mem_insert_of_mem h) obtain ⟨b,hb,hnb⟩ := hJbad d hdC hdJ exact hnb (hdR b (mem_insert_of_mem hb)) have hTcard : T.card = k+1 := by have hnotle : ¬ T.card ≤ k := fun h => hTbad (hroot T h) omega have hJpos : 0 < J.card := by have hcount : T.card = J.card+1 := card_insert_of_notMem hcJ omega obtain ⟨b,hb⟩ := card_pos.mp hJpos exact ⟨T,hTcard,hTbad,⟨c.val,mem_insert_self _ _,c.property⟩, ⟨b,mem_insert_of_mem hb,(mem_sdiff.mp (hJC hb)).2⟩⟩