AFTD Auto-Formalizing Theoretical Domains

digraph_linear_arc_dominated_unique_common_successor

theoremverified

Every arc of a finite loopless linear arc-dominated digraph has exactly one common successor; regularity and orientation are not required.

Statement

theorem digraph_linear_arc_dominated_unique_common_successor
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (hloop : ∀ v, ¬ D.Adj v v)
    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)
    (hlinear : ∀ u v, u ≠ v → ∀ a b,
      D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b)
    (u v : α) (huv : D.Adj u v) :
    ∃! w, D.Adj u w ∧ D.Adj v w
Source
General zero-overlap duality route for OP-110; exhaustive small checks in experiment 12675.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

By arc-domination, every arc e = (x, y) has a chosen common predecessor pred(e), giving rise to a shift map f(e) = (pred(e), x) on the finite set of arcs. Linearity and looplessness guarantee that f is injective: if two arcs had the same image but different targets, their source and chosen predecessor would be distinct common predecessors of those targets, which linearity would force to coincide and create an impossible self-loop. By the pigeonhole principle on finite sets, f is surjective, so the given arc (u, v) is in the image of f and its preimage provides a common successor. Finally, uniqueness of the common successor follows by linearity and looplessness through an analogous argument.

  1. Define the set of arcs and a self-map f on arcs shifting each arc (x, y) to (pred(x, y), x), where pred(x, y) is a common predecessor of x and y.

    By arc-domination, for every arc e = (x, y) there exists a vertex dominating both x and y. Using classical choice (`Classical.choose`), we select such a predecessor pred(e), which satisfies pred(e) → x and pred(e) → y (`Classical.choose_spec`). We then define f(e) = (pred(e), x), which is an arc because pred(e) → x.

    lines 9–15

    uses Classical.choose, Classical.choose_spec

      classical
      let Arc := {e : α × α // D.Adj e.1 e.2}
      let pred : Arc → α := fun e => Classical.choose (hdom e.val.1 e.val.2 e.property)
      have hpred : ∀ e : Arc, D.Adj (pred e) e.val.1 ∧ D.Adj (pred e) e.val.2 := by
        intro e
        exact Classical.choose_spec (hdom e.val.1 e.val.2 e.property)
      let f : Arc → Arc := fun e => ⟨(pred e, e.val.1), (hpred e).1⟩
  2. The shift map f on arcs is injective.

    Assume f(e) = f(k) for two arcs e and k. Comparing components (`congrArg`), we have pred(e) = pred(k) and e₁ = k₁. To show e = k (`Subtype.ext`, `Prod.ext`), it remains to show e₂ = k₂. Suppose for contradiction that e₂ ≠ k₂. Then both e₁ and pred(e) are common predecessors of e₂ and k₂ (since e₁ → e₂, e₁ = k₁ → k₂, pred(e) → e₂, and pred(e) = pred(k) → k₂). By linearity, e₁ = pred(e). But pred(e) → e₁ by construction, so e₁ → e₁, contradicting the assumption that D has no self-loops (`hloop`). Thus e₂ = k₂, so e = k.

    lines 16–29

    uses congrArg, Subtype.ext, Prod.ext

      have hinj : Function.Injective f := by
        intro e k h
        have hp : pred e = pred k := congrArg (fun z : Arc => z.val.1) h
        have ht : e.val.1 = k.val.1 := congrArg (fun z : Arc => z.val.2) h
        apply Subtype.ext
        apply Prod.ext
        · exact ht
        · by_contra hne
          have hk : D.Adj e.val.1 k.val.2 := by simpa [ht] using k.property
          have hpk : D.Adj (pred e) k.val.2 := by simpa [hp] using (hpred k).2
          have heq : e.val.1 = pred e :=
            hlinear e.val.2 k.val.2 hne e.val.1 (pred e)
              e.property hk (hpred e).2 hpk
          exact hloop e.val.1 (by simpa [← heq] using (hpred e).1)
  3. The shift map f on arcs is surjective.

    Since the vertex set α is finite, the subtype of arcs is also finite. Any injective endofunction on a finite type is surjective (`Finite.surjective_of_injective`).

    line 30

    uses Finite.surjective_of_injective

      have hsurj : Function.Surjective f := Finite.surjective_of_injective hinj
  4. The given arc (u, v) has a common successor.

    By surjectivity of f, there exists an arc e such that f(e) = (u, v). Matching components (`congrArg`), pred(e) = u and e₁ = v. Since pred(e) → e₂ and e₁ → e₂, we obtain u → e₂ and v → e₂. Hence e₂ is a common successor of u and v.

    lines 31–36

    uses congrArg

      obtain ⟨e, he⟩ := hsurj ⟨(u, v), huv⟩
      have hp : pred e = u := congrArg (fun z : Arc => z.val.1) he
      have ht : e.val.1 = v := congrArg (fun z : Arc => z.val.2) he
      have h1 : D.Adj u e.val.2 := by simpa [hp] using (hpred e).2
      have h2 : D.Adj v e.val.2 := by simpa [ht] using e.property
      refine ⟨e.val.2, ⟨h1, h2⟩, ?_⟩
  5. The common successor of u and v is unique.

    Let w be any common successor of u and v, so u → w and v → w. Suppose for contradiction that w ≠ e₂. Then both u and v are common predecessors of the two distinct vertices w and e₂. By linearity, this requires u = v. However, u → v is an arc in D, so u = v implies the self-loop u → u, contradicting looplessness (`hloop`). Therefore w = e₂.

    lines 37–40

      intro w hw
      by_contra hne
      have heq : u = v := hlinear w e.val.2 hne u v hw.1 h1 hw.2 h2
      exact hloop u (by simpa [← heq] using huv)
Classical.choose
Given a proof that an element with property P exists, returns such an element.
Classical.choose_spec
The witness selected by Classical.choose satisfies the property P.
congrArg
Functions preserve equality: if a = b, then f(a) = f(b).
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
Finite.surjective_of_injective
An injective function from a finite type to itself is surjective.

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

theorem digraph_linear_arc_dominated_unique_common_successor    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (hloop : ∀ v, ¬ D.Adj v v)    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)    (hlinear : ∀ u v, u ≠ v → ∀ a b,      D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b)    (u v : α) (huv : D.Adj u v) :    ∃! w, D.Adj u w ∧ D.Adj v w := by  classical  let Arc := {e : α × α // D.Adj e.1 e.2}  let pred : Arc → α := fun e => Classical.choose (hdom e.val.1 e.val.2 e.property)  have hpred : ∀ e : Arc, D.Adj (pred e) e.val.1 ∧ D.Adj (pred e) e.val.2 := by    intro e    exact Classical.choose_spec (hdom e.val.1 e.val.2 e.property)  let f : Arc → Arc := fun e => ⟨(pred e, e.val.1), (hpred e).1⟩  have hinj : Function.Injective f := by    intro e k h    have hp : pred e = pred k := congrArg (fun z : Arc => z.val.1) h    have ht : e.val.1 = k.val.1 := congrArg (fun z : Arc => z.val.2) h    apply Subtype.ext    apply Prod.ext    · exact ht    · by_contra hne      have hk : D.Adj e.val.1 k.val.2 := by simpa [ht] using k.property      have hpk : D.Adj (pred e) k.val.2 := by simpa [hp] using (hpred k).2      have heq : e.val.1 = pred e :=        hlinear e.val.2 k.val.2 hne e.val.1 (pred e)          e.property hk (hpred e).2 hpk      exact hloop e.val.1 (by simpa [← heq] using (hpred e).1)  have hsurj : Function.Surjective f := Finite.surjective_of_injective hinj  obtain ⟨e, he⟩ := hsurj ⟨(u, v), huv⟩  have hp : pred e = u := congrArg (fun z : Arc => z.val.1) he  have ht : e.val.1 = v := congrArg (fun z : Arc => z.val.2) he  have h1 : D.Adj u e.val.2 := by simpa [hp] using (hpred e).2  have h2 : D.Adj v e.val.2 := by simpa [ht] using e.property  refine ⟨e.val.2, ⟨h1, h2⟩, ?_⟩  intro w hw  by_contra hne  have heq : u = v := hlinear w e.val.2 hne u v hw.1 h1 hw.2 h2  exact hloop u (by simpa [← heq] using huv)
See it in the graphDiscuss this resultChallenge it