condorcet_minimal_predecessor_undominated_extension
For every natural k, a finite relation globally minimal under induced restriction among S_k relations has an undominated set of exactly k+1 vertices. Thus its canonical family of missing (k+1)-sets is nonempty. No irreflexivity or positive-k hypothesis is needed.
Statement
theorem condorcet_minimal_predecessor_undominated_extension (m 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) : ∃ T : Finset (Fin m), T.card = k+1 ∧ ¬∃ a, a∉T ∧ ∀ b∈T,R a b
- Source
- IN-383, OP-19 campaign session 9, 2026-10-30. Constructive completion of the minimal-core incidence argument developed in this session; all four proofs were scratch-checked together in CanonicalAndTransport3.log. General supporting route lemmas, not a new election bound or a research novelty claim.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_minimal_predecessor_reciprocal_completion_integer_weightsIf a globally minimal finite S_k core with k positive maps into a finite relation, preserving arrows, and every missing (k+1)-set has a…
The proof, explained
The proof proceeds by contradiction. Assuming every set of size k+1 has an external dominating vertex, this dominance property extends from sets of size at most k to all sets of size at most k+1. Using an arbitrary element c, the extended property guarantees that the proper subset univ \ {c} satisfies the global minimality condition, forcing univ \ {c} = univ. This implies c ∈ univ \ {c}, which directly contradicts c ≠ c.
Assume for contradiction that every subset of size k+1 has an external dominating vertex.
We work classically and negate the goal: we suppose that for every subset T of size k+1, there exists an element a ∉ T such that R a b holds for all b ∈ T.
classical by_contra! h
Every subset of size at most k+1 has an external dominating vertex.
Given a subset J with |J| ≤ k+1, we split into two cases: if |J| ≤ k, the hypothesis `hroot` directly provides an external dominating vertex. Otherwise, |J| = k+1 by integer arithmetic, so the contradiction hypothesis `h` provides one.
have hstrong : ∀ J : Finset (Fin m), J.card ≤ k+1 → ∃ a, a∉J ∧ ∀ b∈J,R a b := by intro J hJ by_cases hJk : J.card ≤ k · exact hroot J hJk · exact h J (by omega)
There exists an element c in the universe.
Applying `hroot` to the empty set ∅ (whose cardinality is 0 ≤ k) yields a vertex c.
obtain ⟨c,_,_⟩ := hroot ∅ (by simp)
The subset univ \ {c} is equal to the full universe univ.
By the minimality hypothesis `hminimal`, it suffices to show that any J ⊆ univ \ {c} with |J| ≤ k has an external dominating vertex in univ \ {c}. Given such J, the set {c} ∪ J has cardinality at most |J| + 1 ≤ k+1 by `card_insert_le`. By `hstrong`, there exists an element a ∉ {c} ∪ J dominating every element of {c} ∪ J. Because a ∉ {c} ∪ J, a ≠ c (via `mem_insert_self`), so a ∈ univ \ {c} by `mem_erase.mpr` and `mem_univ`. Furthermore, a ∉ J and a dominates each vertex in J by `mem_insert_of_mem`. Thus univ \ {c} satisfies the condition, so `hminimal` gives univ \ {c} = univ.
uses
card_insert_le,mem_insert_self,mem_erase.mpr,mem_univ,mem_insert_of_memhave heq : univ.erase c = (univ : Finset (Fin m)) := by apply hminimal intro J hJC hJ obtain ⟨a,ha,har⟩ := hstrong (insert c J) ((card_insert_le _ _).trans (by omega)) have hac : a≠c := fun h => ha (h ▸ mem_insert_self c J) exact ⟨a,mem_erase.mpr ⟨hac,mem_univ _⟩, fun h => ha (mem_insert_of_mem h),fun b hb => har b (mem_insert_of_mem hb)⟩
A contradiction is obtained from c ∈ univ \ {c}.
Since univ \ {c} = univ, the element c (which belongs to univ by `mem_univ`) must belong to univ \ {c}. But by definition of erase (`mem_erase.mp`), every element in univ \ {c} must be distinct from c, which entails c ≠ c, a contradiction.
uses
mem_univ,mem_erase.mphave hmem : c∈(univ : Finset (Fin m)).erase c := heq.symm ▸ mem_univ c exact (mem_erase.mp hmem).1 rfl
card_insert_le- inserting an element into a finite set increases its cardinality by at most 1
mem_insert_self- an element belongs to the set formed by inserting itself into any finite set
mem_erase.mpr- an element x belongs to s.erase y if and only if x ≠ y and x ∈ s (here, the right-to-left direction)
mem_univ- every element of a finite type belongs to the universal set univ
mem_insert_of_mem- if an element belongs to s, then it belongs to s with another element inserted
mem_erase.mp- if an element x belongs to s.erase y, then x ≠ y and x ∈ s (here, the left-to-right direction)
- Linear integer arithmetic reasoning in lines 22 and 28 is handled by `omega`, and the cardinality of the empty set in line 23 is simplified by `simp`.
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_minimal_predecessor_undominated_extension (m 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) : ∃ T : Finset (Fin m), T.card = k+1 ∧ ¬∃ a, a∉T ∧ ∀ b∈T,R a b := by classical by_contra! h have hstrong : ∀ J : Finset (Fin m), J.card ≤ k+1 → ∃ a, a∉J ∧ ∀ b∈J,R a b := by intro J hJ by_cases hJk : J.card ≤ k · exact hroot J hJk · exact h J (by omega) obtain ⟨c,_,_⟩ := hroot ∅ (by simp) have heq : univ.erase c = (univ : Finset (Fin m)) := by apply hminimal intro J hJC hJ obtain ⟨a,ha,har⟩ := hstrong (insert c J) ((card_insert_le _ _).trans (by omega)) have hac : a≠c := fun h => ha (h ▸ mem_insert_self c J) exact ⟨a,mem_erase.mpr ⟨hac,mem_univ _⟩, fun h => ha (mem_insert_of_mem h),fun b hb => har b (mem_insert_of_mem hb)⟩ have hmem : c∈(univ : Finset (Fin m)).erase c := heq.symm ▸ mem_univ c exact (mem_erase.mp hmem).1 rfl