AFTD Auto-Formalizing Theoretical Domains

condorcet_triple_predecessor_minimal_core

theoremverified

For every finite directed relation with an outside common predecessor for every vertex set of size at most three, there is an induced subset A of at least four vertices retaining this property and having minimum cardinality among ALL induced subsets retaining it. This is a global minimum, stronger than vertex-deletion criticality alone. For every vertex a in A there is a set J contained in A, of size exactly three and excluding a, such that a points to all of J and is the unique outside common predecessor of J within A. The statement does not bound the size of A.

Statement

theorem condorcet_triple_predecessor_minimal_core
    (m : ℕ) (R : Fin m → Fin m → Prop)
    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →
      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) :
    ∃ A : Finset (Fin m), 4 ≤ A.card ∧
      (∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 →
        ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b) ∧
      (∀ B : Finset (Fin m),
        (∀ J : Finset (Fin m), J ⊆ B → J.card ≤ 3 →
          ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, R a b) → A.card ≤ B.card) ∧
      (∀ a ∈ A, ∃ J : Finset (Fin m), J ⊆ A ∧ J.card = 3 ∧ a ∉ J ∧
        (∀ b ∈ J, R a b) ∧
        ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a)
Source
IN-357 supporting structural reduction for OP-19 and the proved condorcet_dimension_le_three_iff_acyclic_weight_separation. Ordinary finite minimal-counterexample argument, with no novelty claim. The2015 high-girth S3 construction (Theorem11, https://drops.dagstuhl.de/storage/00lipics/lipics-vol040-approx-random2015/LIPIcs.APPROX-RANDOM.2015.78/LIPIcs.APPROX-RANDOM.2015.78.pdf) prevents assuming bounded-size cores; no such bound is asserted.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

We consider the family of all vertex subsets satisfying property P that every subset of size at most three has an outside common predecessor. Since the full vertex set satisfies P by hypothesis, we can choose a subset A of minimum cardinality, which must satisfy |A| ≥ 4 because otherwise applying P to A itself would yield a vertex in A \ A. For each vertex a ∈ A, deleting a produces a strictly smaller subset A \ {a}, which cannot satisfy P by minimality, yielding a subset J ⊆ A \ {a} of size at most three with no outside predecessor in A \ {a}. Consequently, a is the unique predecessor of J in A \ J; furthermore, J must have size exactly three, because if |J| ≤ 2, applying P to {a} ∪ J would produce an outside predecessor that must equal a by uniqueness, a contradiction.

  1. There exists a subset of vertices A of minimal cardinality satisfying the property P that every subset of size at most 3 has an outside common predecessor in A.

    We define the property P(A) asserting that every subset J ⊆ A with |J| ≤ 3 has an outside predecessor a ∈ A \ J pointing to every vertex in J. The full vertex universe univ satisfies P by the global assumption hroot. Since the family F of subsets satisfying P is non-empty, we can choose a subset A ∈ F of minimum cardinality.

    lines 18–30

    uses mem_univ

      classical
      let P : Finset (Fin m) → Prop := fun A =>
        ∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 →
          ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b
      let F : Finset (Finset (Fin m)) := univ.filter P
      have hF : (univ : Finset (Fin m)) ∈ F := by
        apply mem_filter.mpr
        refine ⟨mem_univ _, ?_⟩
        intro J hJ hcard
        obtain ⟨a, ha, hR⟩ := hroot J hcard
        exact ⟨a, mem_univ _, ha, hR⟩
      obtain ⟨A, hAF, hmin⟩ := F.exists_min_image Finset.card ⟨univ, hF⟩
      have hA : P A := (mem_filter.mp hAF).2
  2. The minimal subset A contains at least 4 vertices (|A| ≥ 4).

    Suppose for contradiction that |A| ≤ 3. Since A ⊆ A, property P(A) applies to J = A itself, yielding an outside predecessor a ∈ A with a ∉ A, which is impossible.

    lines 31–35

    uses subset_refl

      have hfour : 4 ≤ A.card := by
        by_contra h
        have hcard : A.card ≤ 3 := by omega
        obtain ⟨a, ha, hna, _⟩ := hA A (subset_refl A) hcard
        exact hna ha
  3. The set A satisfies |A| ≥ 4, property P(A), and global minimality among all subsets satisfying P.

    We instantiate the existential goal with A, supplying the proofs of |A| ≥ 4, property P(A), and the minimality of |A| compared to any other subset B satisfying P. This leaves only the existence of a private triple for each vertex in A.

    lines 36–37

    uses mem_univ

      refine ⟨A, hfour, hA,
        fun B hB => hmin B (mem_filter.mpr ⟨mem_univ _, hB⟩), ?_⟩
  4. For any vertex a ∈ A, the deleted subset A \ {a} fails property P.

    Fix a ∈ A. Removing a yields a strictly smaller subset A \ {a}. If A \ {a} satisfied property P, the minimality of |A| would force |A| ≤ |A \ {a}|, contradicting the fact that deleting an element strictly decreases cardinality.

    lines 38–43

    uses mem_univ, card_erase_lt_of_mem

      intro a ha
      have hdelete : ¬ P (A.erase a) := by
        intro hP
        have hle := hmin (A.erase a) (mem_filter.mpr ⟨mem_univ _, hP⟩)
        have hdrop := card_erase_lt_of_mem ha
        omega
  5. There exists a subset J ⊆ A \ {a} of size at most 3 with no outside predecessor in A \ {a}.

    Because A \ {a} fails property P, expanding the negated definition gives a witness subset J ⊆ A \ {a} with |J| ≤ 3 that has no outside predecessor in A \ {a}. Since A \ {a} ⊆ A, J is also a subset of A.

    lines 44–52

    uses erase_subset

      have hbad : ∃ J : Finset (Fin m), J ⊆ A.erase a ∧ J.card ≤ 3 ∧
          ¬ ∃ c, c ∈ A.erase a ∧ c ∉ J ∧ ∀ b ∈ J, R c b := by
        by_contra hnone
        apply hdelete
        intro J hsub hcard
        by_contra hNo
        exact hnone ⟨J, hsub, hcard, hNo⟩
      obtain ⟨J, hJsub, hJcard, hJnone⟩ := hbad
      have hJA : J ⊆ A := hJsub.trans (erase_subset a A)
  6. The vertex a points to all of J and is the unique common predecessor of J in A \ J.

    Any vertex c ∈ A \ J pointing to all of J cannot lie in A \ {a} (since J has no predecessor in A \ {a}), which forces c = a. On the other hand, because A satisfies property P and J ⊆ A has size at most 3, there must exist some predecessor c ∈ A \ J pointing to all of J. By uniqueness, c must be a.

    lines 53–59

      have hprivate : ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a := by
        intro c hc hcJ hcR
        by_contra hne
        exact hJnone ⟨c, mem_erase.mpr ⟨hne, hc⟩, hcJ, hcR⟩
      obtain ⟨c, hc, hcJ, hcR⟩ := hA J hJA hJcard
      have heq := hprivate c hc hcJ hcR
      subst c
  7. The subset J has size exactly 3, completing the proof that a has a private triple.

    Suppose |J| ≠ 3. Since |J| ≤ 3, this means |J| ≤ 2. Then the set {a} ∪ J has size |J| + 1 ≤ 3 (since a ∉ J) and is a subset of A. Applying property P(A) to {a} ∪ J yields an outside predecessor r ∈ A \ ({a} ∪ J) pointing to all of {a} ∪ J, and hence to all of J. Because r ∈ A \ J points to all of J, uniqueness forces r = a, contradicting r ∉ {a} ∪ J. Hence |J| = 3, and J satisfies all required conditions for a.

    lines 60–73

    uses insert_subset, card_insert_of_notMem, mem_insert_of_mem, mem_insert_self

      have hJthree : J.card = 3 := by
        by_contra hne
        have hJtwo : J.card ≤ 2 := by omega
        have hsub : insert a J ⊆ A := insert_subset ha hJA
        have hcard : (insert a J).card ≤ 3 := by
          rw [card_insert_of_notMem hcJ]
          omega
        obtain ⟨r, hrA, hrnot, hrR⟩ := hA (insert a J) hsub hcard
        have hrJ : r ∉ J := fun hr => hrnot (mem_insert_of_mem hr)
        have hra : r = a := hprivate r hrA hrJ
          (fun b hb => hrR b (mem_insert_of_mem hb))
        subst r
        exact hrnot (mem_insert_self a J)
      exact ⟨J, hJA, hJthree, hcJ, hcR, hprivate⟩
mem_univ
Every element of a finite type belongs to the universal finite set univ.
subset_refl
The subset relation is reflexive: every set is a subset of itself.
card_erase_lt_of_mem
Removing an element from a finite set strictly decreases its cardinality.
erase_subset
Deleting an element from a set yields a subset of the original set.
insert_subset
If an element a and a subset s are both contained in t, then {a} ∪ s ⊆ t.
card_insert_of_notMem
Inserting an element not already present into a finite set increases its cardinality by 1.
mem_insert_of_mem
An element belonging to a set s also belongs to the set obtained by inserting another element into s.
mem_insert_self
An element a always belongs to the set {a} ∪ s.

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 4000000set_option maxRecDepth 10000theorem condorcet_triple_predecessor_minimal_core    (m : ℕ) (R : Fin m → Fin m → Prop)    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) :    ∃ A : Finset (Fin m), 4 ≤ A.card ∧      (∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 →        ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b) ∧      (∀ B : Finset (Fin m),        (∀ J : Finset (Fin m), J ⊆ B → J.card ≤ 3 →          ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, R a b) → A.card ≤ B.card) ∧      (∀ a ∈ A, ∃ J : Finset (Fin m), J ⊆ A ∧ J.card = 3 ∧ a ∉ J ∧        (∀ b ∈ J, R a b) ∧        ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a) := by  classical  let P : Finset (Fin m) → Prop := fun A =>    ∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 →      ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b  let F : Finset (Finset (Fin m)) := univ.filter P  have hF : (univ : Finset (Fin m)) ∈ F := by    apply mem_filter.mpr    refine ⟨mem_univ _, ?_⟩    intro J hJ hcard    obtain ⟨a, ha, hR⟩ := hroot J hcard    exact ⟨a, mem_univ _, ha, hR⟩  obtain ⟨A, hAF, hmin⟩ := F.exists_min_image Finset.card ⟨univ, hF⟩  have hA : P A := (mem_filter.mp hAF).2  have hfour : 4 ≤ A.card := by    by_contra h    have hcard : A.card ≤ 3 := by omega    obtain ⟨a, ha, hna, _⟩ := hA A (subset_refl A) hcard    exact hna ha  refine ⟨A, hfour, hA,    fun B hB => hmin B (mem_filter.mpr ⟨mem_univ _, hB⟩), ?_⟩  intro a ha  have hdelete : ¬ P (A.erase a) := by    intro hP    have hle := hmin (A.erase a) (mem_filter.mpr ⟨mem_univ _, hP⟩)    have hdrop := card_erase_lt_of_mem ha    omega  have hbad : ∃ J : Finset (Fin m), J ⊆ A.erase a ∧ J.card ≤ 3 ∧      ¬ ∃ c, c ∈ A.erase a ∧ c ∉ J ∧ ∀ b ∈ J, R c b := by    by_contra hnone    apply hdelete    intro J hsub hcard    by_contra hNo    exact hnone ⟨J, hsub, hcard, hNo⟩  obtain ⟨J, hJsub, hJcard, hJnone⟩ := hbad  have hJA : J ⊆ A := hJsub.trans (erase_subset a A)  have hprivate : ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a := by    intro c hc hcJ hcR    by_contra hne    exact hJnone ⟨c, mem_erase.mpr ⟨hne, hc⟩, hcJ, hcR⟩  obtain ⟨c, hc, hcJ, hcR⟩ := hA J hJA hJcard  have heq := hprivate c hc hcJ hcR  subst c  have hJthree : J.card = 3 := by    by_contra hne    have hJtwo : J.card ≤ 2 := by omega    have hsub : insert a J ⊆ A := insert_subset ha hJA    have hcard : (insert a J).card ≤ 3 := by      rw [card_insert_of_notMem hcJ]      omega    obtain ⟨r, hrA, hrnot, hrR⟩ := hA (insert a J) hsub hcard    have hrJ : r ∉ J := fun hr => hrnot (mem_insert_of_mem hr)    have hra : r = a := hprivate r hrA hrJ      (fun b hb => hrR b (mem_insert_of_mem hb))    subst r    exact hrnot (mem_insert_self a J)  exact ⟨J, hJA, hJthree, hcJ, hcR, hprivate⟩
See it in the graphDiscuss this resultChallenge it