AFTD Auto-Formalizing Theoretical Domains

relation_reaches_terminal_of_nat_rank_ascent

theoremverified

Let P and Term be predicates and R a relation on a type α, with r : α → ℕ. If every non-terminal P-state X has a P-successor Y (that is, R X Y) with r Y < r X, then every P-state X starts a finite R-chain X → ⋯ → Q whose last element Q is terminal.

Statement

theorem relation_reaches_terminal_of_nat_rank_ascent {α : Type*} (P Term : α → Prop)
    (R : α → α → Prop) (r : α → ℕ)
    (h : ∀ X, P X → ¬ Term X → ∃ Y, P Y ∧ r Y < r X ∧ R X Y) :
    ∀ X, P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q
Source
step towards op223_poset_connectivity
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof proceeds by mathematical induction on an upper bound k ∈ ℕ on the rank r(X). In the base case k = 0, either X is already terminal (so an empty path reaches it), or X must have a successor with strictly smaller rank, which is impossible for non-negative integers. In the inductive step, if X is not terminal, the hypothesis provides a successor Y with r(Y) < r(X) ≤ k + 1, giving r(Y) ≤ k; the induction hypothesis then yields a path from Y to a terminal state Q, and prepending the initial step X → Y completes the reachability chain from X to Q.

  1. It suffices to prove that for all k ∈ ℕ, any state X with r(X) ≤ k and P(X) reaches some terminal state Q via R.

    We strengthen the target by introducing an explicit upper bound k on the rank r(X). If this bounded statement holds for all k, then for any given state X with P(X), choosing k = r(X) (using r(X) ≤ r(X) via le_rfl) immediately establishes the theorem.

    lines 6–8

    uses le_rfl

      suffices H : ∀ k, ∀ X, r X ≤ k → P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q by
        intro X hX
        exact H (r X) X le_rfl hX
  2. The base case k = 0 holds: any state X satisfying P(X) with r(X) ≤ 0 reaches a terminal state.

    We proceed by induction on k. For k = 0, we have r(X) ≤ 0, so r(X) = 0. We case-split on whether X is already terminal. If it is, X reaches itself in zero steps by reflexivity (Relation.ReflTransGen.refl). If X is not terminal, hypothesis h provides a successor Y with r(Y) < r(X) ≤ 0, which is impossible for natural numbers; omega detects this arithmetic contradiction and closes the branch.

    lines 9–16

    uses Relation.ReflTransGen.refl

      intro k
      induction k with
      | zero =>
        intro X hk hX
        by_cases hT : Term X
        · exact ⟨X, hT, Relation.ReflTransGen.refl⟩
        · obtain ⟨Y, -, hlt, -⟩ := h X hX hT
          omega
  3. The inductive step holds: if every state with rank at most k reaches a terminal state, the same holds for states with rank at most k + 1.

    Assume the induction hypothesis for k, and consider a state X with P(X) and r(X) ≤ k + 1. If X is terminal, reflexivity (Relation.ReflTransGen.refl) finishes the proof with Q = X. If X is not terminal, hypothesis h yields an R-successor Y satisfying P(Y) with r(Y) < r(X). Since r(Y) < r(X) ≤ k + 1, integer arithmetic (omega) gives r(Y) ≤ k. Applying the induction hypothesis to Y produces a terminal state Q reachable from Y in zero or more R-steps. Prepending the step R(X, Y) via Relation.ReflTransGen.head yields a complete path from X to Q.

    lines 17–23

    uses Relation.ReflTransGen.refl, Relation.ReflTransGen.head

      | succ k ih =>
        intro X hk hX
        by_cases hT : Term X
        · exact ⟨X, hT, Relation.ReflTransGen.refl⟩
        · obtain ⟨Y, hPY, hlt, hR⟩ := h X hX hT
          obtain ⟨Q, hTQ, hstep⟩ := ih Y (by omega) hPY
          exact ⟨Q, hTQ, Relation.ReflTransGen.head hR hstep⟩
le_rfl
Every element in a preorder is less than or equal to itself (a ≤ a).
Relation.ReflTransGen.refl
The reflexive-transitive closure of a relation is reflexive: every element reaches itself in zero steps.
Relation.ReflTransGen.head
If a relates to b and b reaches c in zero or more steps, then a reaches c in zero or more steps.

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

/-- Ascent from a state to a terminal state through a ℕ-valued rank: a non-terminal P-state always has an R-successor of strictly smaller rank. -/theorem relation_reaches_terminal_of_nat_rank_ascent {α : Type*} (P Term : α → Prop)    (R : α → α → Prop) (r : α → ℕ)    (h : ∀ X, P X → ¬ Term X → ∃ Y, P Y ∧ r Y < r X ∧ R X Y) :    ∀ X, P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q := by  suffices H : ∀ k, ∀ X, r X ≤ k → P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q by    intro X hX    exact H (r X) X le_rfl hX  intro k  induction k with  | zero =>    intro X hk hX    by_cases hT : Term X    · exact ⟨X, hT, Relation.ReflTransGen.refl⟩    · obtain ⟨Y, -, hlt, -⟩ := h X hX hT      omega  | succ k ih =>    intro X hk hX    by_cases hT : Term X    · exact ⟨X, hT, Relation.ReflTransGen.refl⟩    · obtain ⟨Y, hPY, hlt, hR⟩ := h X hX hT      obtain ⟨Q, hTQ, hstep⟩ := ih Y (by omega) hPY      exact ⟨Q, hTQ, Relation.ReflTransGen.head hR hstep⟩
See it in the graphDiscuss this resultChallenge it