AFTD Auto-Formalizing Theoretical Domains

condorcet_triple_predecessor_arc_minimal

theoremverified

Every finite relation in which each set of at most three vertices has an outside common predecessor has an irreflexive subrelation retaining that property such that every retained arrow a to b belongs to a private triple at a: there is a set J of exactly three vertices, containing b and excluding a, for which a is the unique outside common predecessor. No bound on the vertex count is asserted.

Statement

theorem condorcet_triple_predecessor_arc_minimal (m : ℕ) (R : Fin m → Fin m → Prop)
    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →
      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) :
    ∃ Q : Fin m → Fin m → Prop,
      (∀ a b, Q a b → R a b) ∧ (∀ a, ¬ Q a a) ∧
      (∀ J : Finset (Fin m), J.card ≤ 3 →
        ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧
      (∀ a b, Q a b → ∃ J : Finset (Fin m), J.card = 3 ∧ b ∈ J ∧ a ∉ J ∧
        (∀ c ∈ J, Q a c) ∧
        ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a)
Source
IN-362 structural helper for OP-19 and condorcet_dimension_le_three_iff_acyclic_weight_separation. Elementary finite arc minimization, no new election bound or research advance.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

We consider the finite family of all irreflexive subrelations of R that retain the property that every set of at most three vertices has an outside common predecessor, and choose a subrelation Q with a minimal number of directed edges. For each retained edge (a, b), minimality ensures that removing (a, b) destroys this property, giving a subset J of at most three vertices with no outside predecessor in Q \ {(a, b)}. Because Q itself satisfies the property, J must have an outside predecessor in Q, which can only be a, forcing b ∈ J and making a the unique outside predecessor of J. Finally, |J| = 3, because if |J| < 3, the set J ∪ {a} would also have an outside predecessor in Q, which would have to equal a, yielding a contradiction.

  1. The set E of all irreflexive edges in R satisfies property P (every set of at most three vertices has an outside common predecessor), so the family of subgraphs satisfying P is non-empty.

    We work classically (line 15) and define E as the set of pairs (u, v) such that R(u, v) holds and u ≠ v (line 16). Property P(F) states that every subset J of at most three vertices has an outside common predecessor in F (lines 17–18), and family collects all subgraphs of E satisfying P (line 19). For any J of size at most 3, the hypothesis hroot yields an outside vertex a ∉ J with R(a, b) for all b ∈ J. Since a ∉ J and b ∈ J, we have a ≠ b, so each (a, b) lies in E (lines 20–26). Thus P(E) holds, and E belongs to family (line 27).

    lines 15–27

    uses mem_univ, subset_refl

      classical
      let E : Finset (Fin m × Fin m) := univ.filter (fun e => R e.1 e.2 ∧ e.1 ≠ e.2)
      let P : Finset (Fin m × Fin m) → Prop := fun F =>
        ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, (a,b) ∈ F
      let family := E.powerset.filter P
      have hE : P E := by
        intro J hJ
        obtain ⟨a, ha, hR⟩ := hroot J hJ
        refine ⟨a, ha, fun b hb => mem_filter.mpr ⟨mem_univ _, hR b hb, ?_⟩⟩
        intro hab
        have hab' : a = b := hab
        exact ha (hab'.symm ▸ hb)
      have hEF : E ∈ family := mem_filter.mpr ⟨mem_powerset.mpr (subset_refl E), hE⟩
  2. There exists a cardinality-minimal edge set F in family, defining candidate relation Q.

    Because family is a non-empty finite set, it has an element F that minimizes the number of edges |F| (line 28). By definition, F ⊆ E (line 29) and F satisfies P (line 30). We define Q(a, b) by (a, b) ∈ F (line 31), which immediately satisfies the predecessor condition using P(F) (line 32).

    lines 28–32

      obtain ⟨F,hF,hmin⟩ := family.exists_min_image Finset.card ⟨E,hEF⟩
      have hsub : F ⊆ E := mem_powerset.mp (mem_filter.mp hF).1
      have hP : P F := (mem_filter.mp hF).2
      let Q := fun a b => (a,b) ∈ F
      refine ⟨Q, ?_, ?_, hP, ?_⟩
  3. The relation Q is a subrelation of R and is irreflexive.

    If Q(a, b) holds, then (a, b) ∈ F ⊆ E, so R(a, b) holds by definition of E (lines 33–34). Moreover, elements of E satisfy a ≠ b, which precludes Q(a, a) and ensures that Q is irreflexive (lines 35–36).

    lines 33–36

      · intro a b hab
        exact (mem_filter.mp (hsub hab)).2.1
      · intro a haa
        exact (mem_filter.mp (hsub haa)).2.2 rfl
  4. Removing any edge (a, b) from F yields an edge set that fails property P.

    Fix an edge (a, b) ∈ F (line 37). If F \ {(a, b)} satisfied P, it would belong to family (lines 39–41). By minimality of F, we would have |F| ≤ |F \ {(a, b)}| (line 42). But removing an existing edge strictly reduces the cardinality (line 43), giving |F \ {(a, b)}| < |F|, a linear arithmetic contradiction resolved by omega (line 44).

    lines 37–44

    uses erase_subset, card_erase_lt_of_mem

      · intro a b hab
        have hbad : ¬ P (F.erase (a,b)) := by
          intro h
          have hmem : F.erase (a,b) ∈ family :=
            mem_filter.mpr ⟨mem_powerset.mpr ((erase_subset _ _).trans hsub), h⟩
          have hle := hmin _ hmem
          have hlt := card_erase_lt_of_mem hab
          omega
  5. There exists a vertex subset J of size at most 3 with no outside predecessor in F \ {(a, b)}.

    Because F \ {(a, b)} fails property P, by contraposition there must be some subset J with |J| ≤ 3 such that no vertex d ∉ J can serve as a common predecessor of J in F \ {(a, b)} (lines 45–52).

    lines 45–52

        have hex : ∃ J : Finset (Fin m), J.card ≤ 3 ∧
            ¬ ∃ d, d ∉ J ∧ ∀ c ∈ J, (d,c) ∈ F.erase (a,b) := by
          by_contra h
          apply hbad
          intro J hJ
          by_contra hno
          exact h ⟨J,hJ,hno⟩
        obtain ⟨J,hJ,hno⟩ := hex
  6. The subset J has an outside predecessor under Q, and a is the unique such predecessor.

    Since F satisfies P, there is an outside predecessor d ∉ J in F (line 53). If any outside predecessor d under Q were distinct from a, then for every c ∈ J the pair (d, c) would differ from (a, b) in its first component (lines 59–60), and hence remain in F \ {(a, b)}. That would make d an outside predecessor for J in F \ {(a, b)}, contradicting the choice of J (lines 54–60). Hence any outside predecessor must equal a; in particular d = a, so a ∉ J and Q(a, c) for all c ∈ J (lines 61–62).

    lines 53–62

    uses congrArg, Prod.fst

        obtain ⟨d,hd,hdQ⟩ := hP J hJ
        have hprivate : ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a := by
          intro d hd hdQ
          by_contra hda
          apply hno
          refine ⟨d, hd, fun c hc => mem_erase.mpr ⟨?_, hdQ c hc⟩⟩
          intro heq
          exact hda (congrArg Prod.fst heq)
        have hda : d = a := hprivate d hd hdQ
        subst d
  7. The vertex b belongs to J.

    Suppose, for contradiction, that b ∉ J (line 64). Then for every c ∈ J, c ≠ b, so (a, c) differs from (a, b) in the second component (lines 67–69). Thus every edge (a, c) remains in F \ {(a, b)}. Since a ∉ J, a would be an outside predecessor for J in F \ {(a, b)}, contradicting the choice of J (lines 65–66). Hence b ∈ J.

    lines 63–69

    uses congrArg, Prod.snd

        have hbJ : b ∈ J := by
          by_contra hb
          apply hno
          refine ⟨a,hd,fun c hc => mem_erase.mpr ⟨?_,hdQ c hc⟩⟩
          intro heq
          have hcb : c = b := congrArg Prod.snd heq
          exact hb (hcb ▸ hc)
  8. The subset J has cardinality exactly 3.

    Suppose |J| ≠ 3 (lines 70–71). Since |J| ≤ 3, this implies |J| ≤ 2. Because a ∉ J, the set J ∪ {a} has size |J| + 1 ≤ 3 (lines 72–74). By property P for F, there exists an outside predecessor r ∉ J ∪ {a} for J ∪ {a} (line 75). In particular, r ∉ J and r is a predecessor for J. By uniqueness of the outside predecessor of J, we must have r = a (lines 76–78). But then r ∈ J ∪ {a}, contradicting r ∉ J ∪ {a} (lines 79–80). Thus |J| = 3.

    lines 70–80

    uses card_insert_of_notMem, mem_insert_of_mem, mem_insert_self

        have hthree : J.card = 3 := by
          by_contra hn
          have hcard : (insert a J).card ≤ 3 := by
            rw [card_insert_of_notMem hd]
            omega
          obtain ⟨r,hr,hrQ⟩ := hP (insert a J) hcard
          have hra : r = a := hprivate r
            (fun h => hr (mem_insert_of_mem h))
            (fun c hc => hrQ c (mem_insert_of_mem hc))
          subst r
          exact hr (mem_insert_self _ _)
  9. The subset J witnesses all required properties of a private triple for (a, b).

    We combine J with the established facts that |J| = 3, b ∈ J, a ∉ J, Q(a, c) for all c ∈ J, and that a is the unique outside common predecessor of J under Q (line 81).

    line 81

        exact ⟨J,hthree,hbJ,hd,hdQ,hprivate⟩
mem_univ
In any finite type, every element belongs to the universal finite set univ.
subset_refl
Every set is a subset of itself.
erase_subset
Removing an element from a finite set yields a subset of the original set.
card_erase_lt_of_mem
Removing an element that belongs to a finite set strictly decreases its cardinality.
congrArg
Applying a function to equal arguments produces equal results.
Prod.fst
The first projection function of an ordered pair, mapping (x, y) to x.
Prod.snd
The second projection function of an ordered pair, mapping (x, y) to y.
card_insert_of_notMem
Inserting an element into a finite set that does not contain it increases its cardinality by 1.
mem_insert_of_mem
An element belonging to a finite set also belongs to the set obtained by inserting another element.
mem_insert_self
An element always belongs to the set obtained by inserting that element into any finite set.

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_arc_minimal (m : ℕ) (R : Fin m → Fin m → Prop)    (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 →      ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) :    ∃ Q : Fin m → Fin m → Prop,      (∀ a b, Q a b → R a b) ∧ (∀ a, ¬ Q a a) ∧      (∀ J : Finset (Fin m), J.card ≤ 3 →        ∃ a, a ∉ J ∧ ∀ b ∈ J, Q a b) ∧      (∀ a b, Q a b → ∃ J : Finset (Fin m), J.card = 3 ∧ b ∈ J ∧ a ∉ J ∧        (∀ c ∈ J, Q a c) ∧        ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a) := by  classical  let E : Finset (Fin m × Fin m) := univ.filter (fun e => R e.1 e.2 ∧ e.1 ≠ e.2)  let P : Finset (Fin m × Fin m) → Prop := fun F =>    ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, (a,b) ∈ F  let family := E.powerset.filter P  have hE : P E := by    intro J hJ    obtain ⟨a, ha, hR⟩ := hroot J hJ    refine ⟨a, ha, fun b hb => mem_filter.mpr ⟨mem_univ _, hR b hb, ?_⟩⟩    intro hab    have hab' : a = b := hab    exact ha (hab'.symm ▸ hb)  have hEF : E ∈ family := mem_filter.mpr ⟨mem_powerset.mpr (subset_refl E), hE⟩  obtain ⟨F,hF,hmin⟩ := family.exists_min_image Finset.card ⟨E,hEF⟩  have hsub : F ⊆ E := mem_powerset.mp (mem_filter.mp hF).1  have hP : P F := (mem_filter.mp hF).2  let Q := fun a b => (a,b) ∈ F  refine ⟨Q, ?_, ?_, hP, ?_⟩  · intro a b hab    exact (mem_filter.mp (hsub hab)).2.1  · intro a haa    exact (mem_filter.mp (hsub haa)).2.2 rfl  · intro a b hab    have hbad : ¬ P (F.erase (a,b)) := by      intro h      have hmem : F.erase (a,b) ∈ family :=        mem_filter.mpr ⟨mem_powerset.mpr ((erase_subset _ _).trans hsub), h⟩      have hle := hmin _ hmem      have hlt := card_erase_lt_of_mem hab      omega    have hex : ∃ J : Finset (Fin m), J.card ≤ 3 ∧        ¬ ∃ d, d ∉ J ∧ ∀ c ∈ J, (d,c) ∈ F.erase (a,b) := by      by_contra h      apply hbad      intro J hJ      by_contra hno      exact h ⟨J,hJ,hno⟩    obtain ⟨J,hJ,hno⟩ := hex    obtain ⟨d,hd,hdQ⟩ := hP J hJ    have hprivate : ∀ d, d ∉ J → (∀ c ∈ J, Q d c) → d = a := by      intro d hd hdQ      by_contra hda      apply hno      refine ⟨d, hd, fun c hc => mem_erase.mpr ⟨?_, hdQ c hc⟩⟩      intro heq      exact hda (congrArg Prod.fst heq)    have hda : d = a := hprivate d hd hdQ    subst d    have hbJ : b ∈ J := by      by_contra hb      apply hno      refine ⟨a,hd,fun c hc => mem_erase.mpr ⟨?_,hdQ c hc⟩⟩      intro heq      have hcb : c = b := congrArg Prod.snd heq      exact hb (hcb ▸ hc)    have hthree : J.card = 3 := by      by_contra hn      have hcard : (insert a J).card ≤ 3 := by        rw [card_insert_of_notMem hd]        omega      obtain ⟨r,hr,hrQ⟩ := hP (insert a J) hcard      have hra : r = a := hprivate r        (fun h => hr (mem_insert_of_mem h))        (fun c hc => hrQ c (mem_insert_of_mem hc))      subst r      exact hr (mem_insert_self _ _)    exact ⟨J,hthree,hbJ,hd,hdQ,hprivate⟩
See it in the graphDiscuss this resultChallenge it