AFTD Auto-Formalizing Theoretical Domains

condorcet_minimal_predecessor_acyclic_cut

theoremverified

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

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.

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

    lines 18–22

    uses Set.mem_univ

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

    lines 23–27

    uses mem_univ, mem_sdiff

      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
  3. 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`.

    lines 28–33

    uses mem_sdiff

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

    lines 34–35

    uses card_insert_le, Nat.add_le_add_right

      let T := insert c.val J
      have hTle : T.card ≤ k+1 := (card_insert_le _ _).trans (Nat.add_le_add_right hJcard 1)
  5. 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`).

    lines 36–43

    uses mem_insert_self, mem_sdiff, mem_insert_of_mem

      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))
  6. 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.

    lines 44–46

      have hTcard : T.card = k+1 := by
        have hnotle : ¬ T.card ≤ k := fun h => hTbad (hroot T h)
        omega
  7. 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.

    lines 47–50

    uses card_insert_of_notMem, card_pos

      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
  8. 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`).

    lines 51–52

    uses mem_insert_self, mem_insert_of_mem, mem_sdiff

      exact ⟨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.

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