AFTD Auto-Formalizing Theoretical Domains

condorcet_critical_rank_core_source_exchange

theoremverified

For positive k and n=k+q, a nonempty induced S_k subset of a rank relation whose vertices all have q active indices and satisfy the contained-signature Pareto antichain condition admits a source for each restricted activity set. For each vertex a and inactive index j there is a predecessor r of a, active at j, with signature contained in that of a plus j, also preceding every source of an index outside that union. Sources of nonempty restricted activity sets belong to those sets; all sources belong to B.

Statement

theorem condorcet_critical_rank_core_source_exchange
    {m n k q : ℕ} (hk : 0 < k) (hn : n = k + q)
    (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ)
    (B : Finset (Fin m)) (hBne : B.Nonempty)
    (hcard : ∀ a ∈ B, (univ.filter fun v => a ∈ U v).card = q)
    (hroot : ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k →
      ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c)
    (hanti : ∀ a ∈ B, ∀ b ∈ B, a ≠ b →
      (∀ v, a ∈ U v → b ∈ U v) →
      ∃ v, a ∈ U v ∧ p v b < p v a) :
    ∃ s : Fin n → Fin m,
      (∀ v, s v ∈ B) ∧
      (∀ v, (B ∩ U v).Nonempty → s v ∈ U v) ∧
      (∀ v, ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r (s v)) ∧
      ∀ a ∈ B, ∀ j : Fin n, a ∉ U j →
        ∃ r, r ∈ B ∧ condorcet_cover_rank_relation U p r a ∧ r ∈ U j ∧
          (∀ v, r ∈ U v → a ∈ U v ∨ v = j) ∧
          (∀ v, v ≠ j → a ∉ U v → condorcet_cover_rank_relation U p r (s v))
Source
IN-391, OP-19 campaign session10, 2026-10-30. Supporting lemmas and precisely scoped method diagnostics for the rank-saturated acyclic-cover route. The main election theorem remains open; no new election bound or novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof first constructs a source s(v) ∈ B for each index v by minimizing the rank p(v, ·) on B ∩ U(v) (or choosing an arbitrary element if empty), which guarantees that no element in B ∩ U(v) can cover s(v). To find the desired predecessor r for a given a ∈ B and inactive index j, we consider the set W of all k - 1 indices outside the signature of a and {j}, and form the test set J = {a} ∪ s(W), which has cardinality at most k. By the S_k property, some r ∈ B covers all elements of J; this r cannot be active on W (which would contradict the source property of s(v)), and cannot be inactive at j (which would contradict the Pareto antichain condition since r covers a). Hence r is active at j, has its signature contained in that of a plus j, and covers all sources s(v) for v ∈ W.

  1. For each index v, there exists a source s(v) ∈ B which belongs to U(v) whenever B ∩ U(v) is nonempty and cannot be covered by any element of B ∩ U(v).

    If B ∩ U(v) is nonempty, choose s(v) ∈ B ∩ U(v) minimizing the rank p(v, ·) via exists_min_image. If some r ∈ B ∩ U(v) were to cover s(v), then by definition of the covering relation, p(v, r) < p(v, s(v)), contradicting the minimality of p(v, s(v)). If B ∩ U(v) is empty, choose an arbitrary element b ∈ B (given by hBne), for which both conditions hold vacuously. Using choice, we obtain a function s : Fin n → B satisfying these source conditions, reducing the goal to finding the required predecessor r for any a ∈ B and inactive index j.

    lines 23–37

    uses exists_min_image, not_lt_of_ge

      classical
      obtain ⟨b,hb⟩ := hBne
      have hex : ∀ v : Fin n, ∃ s, s ∈ B ∧
          ((B ∩ U v).Nonempty → s ∈ U v) ∧
          ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r s := by
        intro v
        by_cases hnon : (B ∩ U v).Nonempty
        · obtain ⟨s,hs,hmin⟩ := (B ∩ U v).exists_min_image (p v) hnon
          refine ⟨s,(mem_inter.mp hs).1,fun _ => (mem_inter.mp hs).2,?_⟩
          intro r hrB hrU hrs
          exact (not_lt_of_ge (hmin r (mem_inter.mpr ⟨hrB,hrU⟩)))
            (hrs.2 v hrU (mem_inter.mp hs).2)
        · exact ⟨b,hb,fun h => (hnon h).elim,fun r hrB hrU _ => hnon ⟨r,mem_inter.mpr ⟨hrB,hrU⟩⟩⟩
      choose s hsB hsU hs using hex
      refine ⟨s,hsB,hsU,hs,?_⟩
  2. For a fixed vertex a ∈ B and inactive index j ∉ U(a), the set W of indices outside {j} ∪ {v | a ∈ U(v)} has size k - 1.

    Let I be the signature of a, which has cardinality q by hypothesis hcard. Since a ∉ U(j), the index j does not belong to I, so the set {j} ∪ I has size q + 1. The complement W = Fin n \ ({j} ∪ I) in the universe of n = k + q indices therefore has cardinality (k + q) - (q + 1) = k - 1.

    lines 38–46

    uses card_sdiff, inter_univ, card_univ, Fintype.card_fin, card_insert_of_notMem

      intro a ha j haj
      let I := univ.filter fun v => a ∈ U v
      let W := univ \ insert j I
      have hI : I.card = q := hcard a ha
      have hjI : j ∉ I := by simpa only [I,mem_filter,mem_univ,true_and] using haj
      have hW : W.card = k - 1 := by
        dsimp only [W]
        rw [card_sdiff,inter_univ,card_univ,Fintype.card_fin,card_insert_of_notMem hjI,hI,hn]
        omega
  3. The set J = {a} ∪ s(W) is a subset of B of cardinality at most k.

    Because a ∈ B and each s(v) ∈ B, the set J = {a} ∪ s(W) is contained in B. Since |s(W)| ≤ |W| = k - 1 by card_image_le, inserting a yields |J| ≤ (k - 1) + 1 = k by card_insert_le.

    lines 47–55

    uses insert_subset, card_image_le, card_insert_le

      have hJsub : insert a (W.image s) ⊆ B := by
        apply insert_subset ha
        intro x hx
        obtain ⟨v,_,rfl⟩ := mem_image.mp hx
        exact hsB v
      have hJcard : (insert a (W.image s)).card ≤ k := by
        have hle := card_image_le (f := s) (s := W)
        have hle' := card_insert_le a (W.image s)
        omega
  4. There exists a vertex r ∈ B that covers every element of J, and in particular covers a.

    Applying the S_k property hroot to the set J ⊆ B of size at most k yields an element r ∈ B that covers every element of J. Since a ∈ J, r covers a.

    lines 56–57

    uses mem_insert_self

      obtain ⟨r,hrB,_,hr⟩ := hroot (insert a (W.image s)) hJsub hJcard
      have hra := hr a (mem_insert_self _ _)
  5. For every index v, if r ∈ U(v) then a ∈ U(v) or v = j.

    Assume for contradiction that r ∈ U(v) for some index v with a ∉ U(v) and v ≠ j. Then v belongs to the complement W, so s(v) ∈ s(W) ⊆ J. Hence r covers s(v). But r ∈ B ∩ U(v), so this directly contradicts the source property of s(v), which states that no element of B ∩ U(v) can cover s(v).

    lines 58–70

    uses mem_insert_of_mem

      have htype : ∀ v, r ∈ U v → a ∈ U v ∨ v = j := by
        intro v hrv
        by_contra h
        push_neg at h
        have hvW : v ∈ W := by
          apply mem_sdiff.mpr
          refine ⟨mem_univ _,?_⟩
          intro hv
          rcases mem_insert.mp hv with hv | hv
          · exact h.2 hv
          · exact h.1 (mem_filter.mp hv).2
        exact hs v r hrB hrv
          (hr (s v) (mem_insert_of_mem (mem_image.mpr ⟨v,hvW,rfl⟩)))
  6. The vertex r is active at index j, that is, r ∈ U(j).

    Assume for contradiction that r ∉ U(j). Combining this with the signature containment from the previous step, every index where r is active must also be active for a (∀ v, r ∈ U(v) → a ∈ U(v)). Since r covers a, r ≠ a. By the Pareto antichain condition hanti, there must be some index v where r ∈ U(v) and p(v, a) < p(v, r) (meaning a is ranked better than r at v). But since r covers a and both are active at v, we also have p(v, r) < p(v, a), which is impossible.

    lines 71–79

    uses not_lt_of_ge, le_of_lt

      have hrj : r ∈ U j := by
        by_contra hnot
        have hsub : ∀ v, r ∈ U v → a ∈ U v := by
          intro v hv
          rcases htype v hv with h | rfl
          · exact h
          · exact (hnot hv).elim
        obtain ⟨v,hrv,hlt⟩ := hanti r hrB a ha hra.1 hsub
        exact (not_lt_of_ge (le_of_lt hlt)) (hra.2 v hrv (hsub v hrv))
  7. The vertex r satisfies all conditions: it belongs to B, covers a, is active at j, has signature contained in that of a plus j, and covers s(v) for all v ≠ j with a ∉ U(v).

    Assembling the properties established for r: r ∈ B, r covers a, r ∈ U(j), and its signature is contained in {j} ∪ {v | a ∈ U(v)}. Finally, for any index v ≠ j where a ∉ U(v), v lies in W, which implies s(v) ∈ s(W) ⊆ J. Since r covers every element of J, r covers s(v).

    lines 80–91

    uses mem_insert_of_mem

      refine ⟨r,hrB,hra,hrj,htype,?_⟩
      intro v hvj hva
      apply hr (s v)
      apply mem_insert_of_mem
      apply mem_image.mpr
      refine ⟨v,?_,rfl⟩
      apply mem_sdiff.mpr
      refine ⟨mem_univ _,?_⟩
      intro hv
      rcases mem_insert.mp hv with hv | hv
      · exact hvj hv
      · exact hva (mem_filter.mp hv).2
exists_min_image
Every nonempty finite set contains an element that minimizes a given function into a linearly ordered type.
not_lt_of_ge
If a ≤ b, then b is not strictly less than a.
card_sdiff
The cardinality of the set difference t \ s is the cardinality of t minus the cardinality of s ∩ t.
inter_univ
The intersection of a finite set with the universal set is the finite set itself.
card_univ
The cardinality of the universal finset is the cardinality of the underlying finite type.
Fintype.card_fin
The finite type Fin n has cardinality n.
card_insert_of_notMem
Inserting an element into a finite set that does not already contain it increases the cardinality by 1.
insert_subset
If a ∈ t and s ⊆ t, then {a} ∪ s ⊆ t.
card_image_le
The cardinality of the image of a finite set under a function is at most the cardinality of the domain set.
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 obtained by inserting it into any set.
mem_insert_of_mem
If an element belongs to a set s, it also belongs to the set obtained by inserting another element into s.
le_of_lt
A strict inequality a < b implies the non-strict inequality a ≤ b.

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 Finsetset_option maxHeartbeats 100000000set_option maxRecDepth 30000theorem condorcet_critical_rank_core_source_exchange    {m n k q : ℕ} (hk : 0 < k) (hn : n = k + q)    (U : Fin n → Finset (Fin m)) (p : Fin n → Fin m → ℕ)    (B : Finset (Fin m)) (hBne : B.Nonempty)    (hcard : ∀ a ∈ B, (univ.filter fun v => a ∈ U v).card = q)    (hroot : ∀ J : Finset (Fin m), J ⊆ B → J.card ≤ k →      ∃ r, r ∈ B ∧ r ∉ J ∧ ∀ c ∈ J, condorcet_cover_rank_relation U p r c)    (hanti : ∀ a ∈ B, ∀ b ∈ B, a ≠ b →      (∀ v, a ∈ U v → b ∈ U v) →      ∃ v, a ∈ U v ∧ p v b < p v a) :    ∃ s : Fin n → Fin m,      (∀ v, s v ∈ B) ∧      (∀ v, (B ∩ U v).Nonempty → s v ∈ U v) ∧      (∀ v, ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r (s v)) ∧      ∀ a ∈ B, ∀ j : Fin n, a ∉ U j →        ∃ r, r ∈ B ∧ condorcet_cover_rank_relation U p r a ∧ r ∈ U j ∧          (∀ v, r ∈ U v → a ∈ U v ∨ v = j) ∧          (∀ v, v ≠ j → a ∉ U v → condorcet_cover_rank_relation U p r (s v)) := by  classical  obtain ⟨b,hb⟩ := hBne  have hex : ∀ v : Fin n, ∃ s, s ∈ B ∧      ((B ∩ U v).Nonempty → s ∈ U v) ∧      ∀ r ∈ B, r ∈ U v → ¬condorcet_cover_rank_relation U p r s := by    intro v    by_cases hnon : (B ∩ U v).Nonempty    · obtain ⟨s,hs,hmin⟩ := (B ∩ U v).exists_min_image (p v) hnon      refine ⟨s,(mem_inter.mp hs).1,fun _ => (mem_inter.mp hs).2,?_⟩      intro r hrB hrU hrs      exact (not_lt_of_ge (hmin r (mem_inter.mpr ⟨hrB,hrU⟩)))        (hrs.2 v hrU (mem_inter.mp hs).2)    · exact ⟨b,hb,fun h => (hnon h).elim,fun r hrB hrU _ => hnon ⟨r,mem_inter.mpr ⟨hrB,hrU⟩⟩⟩  choose s hsB hsU hs using hex  refine ⟨s,hsB,hsU,hs,?_⟩  intro a ha j haj  let I := univ.filter fun v => a ∈ U v  let W := univ \ insert j I  have hI : I.card = q := hcard a ha  have hjI : j ∉ I := by simpa only [I,mem_filter,mem_univ,true_and] using haj  have hW : W.card = k - 1 := by    dsimp only [W]    rw [card_sdiff,inter_univ,card_univ,Fintype.card_fin,card_insert_of_notMem hjI,hI,hn]    omega  have hJsub : insert a (W.image s) ⊆ B := by    apply insert_subset ha    intro x hx    obtain ⟨v,_,rfl⟩ := mem_image.mp hx    exact hsB v  have hJcard : (insert a (W.image s)).card ≤ k := by    have hle := card_image_le (f := s) (s := W)    have hle' := card_insert_le a (W.image s)    omega  obtain ⟨r,hrB,_,hr⟩ := hroot (insert a (W.image s)) hJsub hJcard  have hra := hr a (mem_insert_self _ _)  have htype : ∀ v, r ∈ U v → a ∈ U v ∨ v = j := by    intro v hrv    by_contra h    push_neg at h    have hvW : v ∈ W := by      apply mem_sdiff.mpr      refine ⟨mem_univ _,?_⟩      intro hv      rcases mem_insert.mp hv with hv | hv      · exact h.2 hv      · exact h.1 (mem_filter.mp hv).2    exact hs v r hrB hrv      (hr (s v) (mem_insert_of_mem (mem_image.mpr ⟨v,hvW,rfl⟩)))  have hrj : r ∈ U j := by    by_contra hnot    have hsub : ∀ v, r ∈ U v → a ∈ U v := by      intro v hv      rcases htype v hv with h | rfl      · exact h      · exact (hnot hv).elim    obtain ⟨v,hrv,hlt⟩ := hanti r hrB a ha hra.1 hsub    exact (not_lt_of_ge (le_of_lt hlt)) (hra.2 v hrv (hsub v hrv))  refine ⟨r,hrB,hra,hrj,htype,?_⟩  intro v hvj hva  apply hr (s v)  apply mem_insert_of_mem  apply mem_image.mpr  refine ⟨v,?_,rfl⟩  apply mem_sdiff.mpr  refine ⟨mem_univ _,?_⟩  intro hv  rcases mem_insert.mp hv with hv | hv  · exact hvj hv  · exact hva (mem_filter.mp hv).2
See it in the graphDiscuss this resultChallenge it