AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_undominated_extension

theoremverified

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

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.

  1. 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.

    lines 15–16

      classical
      by_contra! h
  2. 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.

    lines 17–22

      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)
  3. There exists an element c in the universe.

    Applying `hroot` to the empty set ∅ (whose cardinality is 0 ≤ k) yields a vertex c.

    line 23

      obtain ⟨c,_,_⟩ := hroot ∅ (by simp)
  4. 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.

    lines 24–31

    uses card_insert_le, mem_insert_self, mem_erase.mpr, mem_univ, mem_insert_of_mem

      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)⟩
  5. 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.

    lines 32–33

    uses mem_univ, mem_erase.mp

      have 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)

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_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
See it in the graphDiscuss this resultChallenge it